## Abstract

In this chapter, we consider the single machine scheduling problem with given release dates, processing times, and due dates with two objective functions. The first one is to minimize the maximum lateness, that is, maximum difference between each job due date and its actual completion time. The second one is to minimize the maximum completion time, that is, to complete all the jobs as soon as possible. The problem is NP-hard in the strong sense. We provide a polynomial time algorithm for constructing a Pareto-optimal set of schedules on criteria of maximum lateness and maximum completion time, that is, problem 1 ∣ r j ∣ L max , C max , for the subcase of the problem: d 1 ≤ d 2 ≤ … ≤ d n ; d 1 − r 1 − p 1 ≥ d 2 − r 2 − p 2 ≥ … ≥ d n − r n − p n .

### Keywords

- single machine scheduling
- two-criteria scheduling
- Pareto-set
- Pareto-optimality
- minimization of maximum lateness
- minimization of maximum completion time
- polynomial time algorithm

## 1. Introduction

We consider a classical scheduling problem on a single machine. A release time of each job is predefined and represents the minimum possible start time of the job. When constructing schedules, we consider two objective functions. The first one is to minimize the maximum lateness, that is, maximum difference between each job due date and its actual completion time. The second one is to minimize the maximum completion time, that is, to complete all the jobs as soon as possible. The problem is NP-hard in the strong sense [1]. We provide a polynomial time algorithm for constructing a Pareto-optimal set of schedules on criteria of maximum lateness and maximum completion time, that is, problem

## 2. Statement of the problem 1 ∣ r j ∣ L max , C max

We consider single machine scheduling problem, where a set of

The schedule is represented by a set *feasible* if

We denote the completion time of all jobs of the set

The problem is to find the optimal schedule

For any arbitrary set of jobs

In the standard notation of Graham et al. [2], this problem is denoted as

Potts [3] introduced an iterative version of extended Jackson rule (IJ) [4] and proved that

A number of polynomially solvable cases of the problem were found, starting with Jackson’s early result [4] for the case

Schedule is constructed according to the extended Jackson rule (Schrage schedule): on the next place in the schedule we select a released non-ordered job with the minimum due date; if there are no such jobs, then we select the job with the minimum release time among the unscheduled jobs.

If process times of all jobs are equal, the complexity can be reduced to

A case when job processing times are mutually divisible is considered in [9]. Author suggest a polynomial-time algorithm with a complexity of

Special cases

We denote by

This paper deals with a problem with two objective functions

**Definition 1.1** For any instance *early schedule*

Early schedules play an important role in our construction, since it is sufficient to check all early schedules to find the optimal schedule of any problem instance.

By

We denote by

## 3. Problem 1 ∣ d i ≤ d j , d i − r i − p i ≥ d j − r j − p j ∣ L max , C max

This section deals with the problem of constructing a Pareto-optimal set by criteria

There is no schedule

### 3.1 Problem properties

We denote the precedence of the jobs

In cases when its obvious how many jobs we mean, we write

We assume that the job parameters satisfy the following constraints:

For example, these constraints correspond to the case when

We assume that

where

Lemma 1.1 If the jobs of the set

is true, and for all

where

**Proof:** For each job

therefore (12) is valid.

If for job

Since

The inequality (13) can be proved in a similar way.

For each job

Let for the job

Since

Since

Hence,

Theorem 1.1 If conditions (9) are true for jobs in the subset

and one of the jobs

**Proof:** Let

From the lemma 1.1 we have

Obviously, the following inequality is true for job

From (20)–(23) we get

Let

Let us assume

For each job

Job

Since

From the lemma 1.1

Moreover, it is obvious that

From inequalities (24)–(29) it follows that

We call a schedule **effective** if there is no schedule

Thus, when constraints (9) are satisfied for jobs from the set

We define the set of schedules

Example 1.1

The set

Theorem 1.2 If for the jobs of the subset

**Proof:** Let

According to the theorem 1.1 for the jobs of the set

Let us denote

After no more than

We form the following partial schedule

**Algorithm 1.1** for constructing schedule

1: **Initial step.** Let

2: **Main step.** Find the jobs

3: **if****then**

4:

5: **else**

6: algorithm stops;

7: **end if**

8: Let

Lemma 1.2 The complexity of the algorithm 1.1 for finding the schedule

**Proof:** At each iteration of the algorithm 1.1 we find two jobs:

The main step of algorithm 1.1 is finding the jobs *O(n)*, therefore, the complexity of the algorithm 1.1 of

Lemma 1.3 If for jobs of the set

**Proof:** If

Let

Let us use the following notation

Consequence 1.1 **from Lemma 1.3.** If the jobs of the set

Theorem 1.3 If the jobs of the set

**Proof:** In the case

If

Consider the case of

Let us choose any arbitrary schedules

For case

The other case is

Therefore, our assumption is not true and

Therefore, jobs of the set

### 3.2 Performance problem with constraint on maximum lateness

The problem

Lemma 1.4 The complexity of algorithm 1.2 does not exceed

**Proof:** At each iteration of the main step of the algorithm 1.2 we find the schedules

**Algorithm 1.2** for solving the problem

1: **Initial step.** Let

2: **Main step.**

3: **if****then**

4:

5: **end if**

6: Find

7: **if****then**

8: the algorithm stops.

9: **else**

10: **if****then**

11:

12: **end if**

13: **if****then**

14:

15: **end if**

16: **if****then**

17:

18: **end if**

19: **end if**

The problem *Example 1.1*). The optimal schedule for this example is

We denote by

Theorem 1.4 Let the jobs of the set

**Proof:** In case if for schedule

According to Lemma 1.3, all schedules of the set

After

Let

If

Thus, at each main step of the algorithm, we choose the fastest continuation of the partial schedule

Let us assume that after the

Repeating our proof as many times as the main step of algorithm 1.2 (no more than

### 3.3 Algorithm for constructing a set of Pareto schedules by criteria C max and L max

Let us develop an algorithm for constructing a set of Pareto schedules

Schedule

**Algorithm 1.3** for constructing a set of Pareto schedules by criteria

1: **Initial step.**

2: **if****then**

3:

4: **end if**

5: **Main step.**

6: **if****then**

7:

8: **end if**

9: **if****then**

10: **if****then**

11: find

12: **if****then**

13:

14: **else**

15:

16: **if****then**

17:

18: **else**

19:

20: **end if**

21: **end if**

22: **if****then**

23: find

24: **if****then**

25:

26: **else**

27:

28: **end if**

29: **end if**

30: **end if**

31: **end if**

As a result of the algorithm 1.3, a set of schedules *Example 1.1* consists of two schedules, although set

Lemma 1.5 The complexity of the algorithm 1.3 does not exceed

**Proof:** At each iteration of the main step of the algorithm 1.3 we find schedules

Theorem 1.5 If case if (9) is true for each job of the set

**Proof:** According to Theorem 1.2, there exists an optimal (by

Let

If

If

Repeating our proof no more than

The set of schedules

Suppose there is a schedule

We assume that the first

Figure 1 schematically shows the considered schedule.

For the set of schedules

The schedule

## 4. Conclusions

Single machine scheduling problem with given release dates and two objective functions is considered in this chapter, which is

an algorithm for constructing a Pareto-optimal set of schedules by criteria

An experimental study of the algorithm showed that it can be used to construct optimal schedules (by

## Acknowledgments

The research was supported by RFBR (project 20-58-S52006).