## 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:

4:

5:

6: algorithm stops;

7:

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:

3:

4:

5:

6: Find

7:

8: the algorithm stops.

9:

10:

11:

12:

13:

14:

15:

16:

17:

18:

19:

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:

2:

3:

4:

5:

6:

7:

8:

9:

10:

11: find

12:

13:

14:

15:

16:

17:

18:

19:

20:

21:

22:

23: find

24:

25:

26:

27:

28:

29:

30:

31:

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

## References

- 1.
Lenstra JK, Rinnooy Kan AHG, Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics. 1977; 1 :343-362 - 2.
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics. 1979; 5 :287-326 - 3.
Potts CN. Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research. 1980; 28 :1436-1441 - 4.
Jackson JR. Scheduling a Production Line to Minimize Maximum Tardiness. Los Angeles, CA: University of California; 1955. Manag. Sci. Res. Project. Research Report N 43 - 5.
Hall LA, Shmoys DB. Jackson’s rule for one-machine schedulings: Making a good heuristic better. Mathematics of Operations Research. 1992; 17 :22-35 - 6.
Mastrolilli M. Efficient approximation schemes for scheduling problems with release dates and delivery times. Journal of Scheduling. 2003; 6 (6):521-531 - 7.
Garey MR, Johnson DS, Simons BB, Tarjan RE. Scheduling UnitTime tasks with arbitrary release times and deadlines. SIAM Journal on Computing. 1981; 10 :256-269 - 8.
Vakhania N. Single-machine scheduling with release times and tails. Annals of Operations Research. 2004; 129 (1–4):253-271 - 9.
Vakhania N. Dynamic restructuring framework for Scheduling with release times and due-dates. Mathematics. 2019; 7 (11):1104 - 10.
Lawler EL. Optimal sequencing of a single machine subject to precedence constraints. Management Science. 1973; 19 (5):544-546 - 11.
Simons BB. A fast algorithm for single processor scheduling. In: Proceedings of the 19th IEEE Annual Symposium on Foundations of Computer Science. New York: Ann. Arbor. Mich; 1978. pp. 246-252 - 12.
Baker KR, Lawler EL, Lenstra JK, Rinnooy Kan AHG. Preemtive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. Operations Research. 1983; 31 (2):381-386 - 13.
Hoogeveen JA. Minimizing maximum promptness and maximum lateness on a single machine. Mathematics of Operations Research. 1996; 21 :100-114 - 14.
Lazarev AA, Shulgina ON. Polynomially solvable subcases of the problem of minimizing maximum lateness. Izvestiya VUZov. Mathematics. 2000 (in Russian) - 15.
Vakhania N. Scheduling a single machine with primary and secondary objectives. Algorithms. 2018; 11 (6):80 - 16.
Vakhania N. Fast solution of single-machine scheduling problem with embedded jobs. Theoretical Computer Science. 2019; 782 :91-106