Polynomial Algorithm for Constructing Pareto-Optimal Schedules for Problem 1∣r_j∣L_max,C_max

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 .

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 $1\mid r_j\mid L_{\mathit{max}},C_{\mathit{max}}$ , for the subcase of the problem when due dates are: $d_1\le d_2\le \dots \le d_n;d_1-r_1-p_1\ge d_2-r_2-p_2\ge \dots \ge d_n-r_n-p_n$ . Example of a problem case that meets these constraints will be the case when all jobs have the same time for processing before due date.

2. Statement of the problem $1\mid r_j\mid L_{\max },C_{\max }$

We consider single machine scheduling problem, where a set of $n$ jobs $N=\left\{1,2,\dots ,n\right\}$ has to be processed on a single machine. Each job we is numbered, that is, the entry “job $j$ ” is equivalent to the entry “job numbered $j$ .” Simultaneous executing of jobs or preemptions of the processing of a job are prohibited. For jobs $j\in N$ , value $r_j$ is the minimum possible start time, $p_j\ge 0$ is a processing time of job $j$ and $d_j$ is a due date of job $j$ .

The schedule is represented by a set $\pi =\left\{s_j|j\in N\right\}$ of start times of each job. By $\tau$ , we denote the permutation of $\left(j_1,\dots ,j_n\right)$ elements of the set $N$ . A set of all different schedules of jobs from the set $N$ is denoted by $\mathrm{\Pi }\left(N\right)$ . Schedule $\pi$ is called feasible if $s_j\left(\pi \right)\ge r_j$ , $\forall j\in N$ . We denote the completion time of job $j\in N$ in schedule $\pi$ as $C_j\left(\pi \right)$ . Difference $L_j\left(\pi \right)=C_j\left(\pi \right)-d_j$ , $j\in N$ , denotes lateness of job $j$ in the schedule $\pi$ . Maximum lateness of jobs of the set $N$ under the schedule $\pi$ is

$$L_{\max }\left(\pi \right)=\underset{j\in N}{max}\left\{C_j\left(\pi \right)-d_j\right\}.$$ E1

We denote the completion time of all jobs of the set $N$ in schedule $\pi$ as

$$C_{\max }\left(\pi \right)=\underset{j\in N}{max}{C}_j\left(\pi \right).$$

The problem is to find the optimal schedule ${\pi }^{\ast }$ with the smallest value of the maximum lateness:

$$L_{\max }^{\ast }=\underset{\pi \in \mathrm{\Pi }\left(N\right)}{min}{L}_{\max }\left(\pi \right)=L_{\max }\left({\pi }^{\ast }\right).$$ E2

For any arbitrary set of jobs $M\subseteq N$ we also denote:

$$r_M=\underset{j\in M}{min}{r}_j,d_M=\underset{j\in M}{max}{d}_j,p_M=\sum _{j\in M}{p}_j.$$ E3

In the standard notation of Graham et al. [2], this problem is denoted as $1\mid r_j\mid L_{\max }$ . Intensive work on the solution of this problem has continued since the early 50s of the 20th century. Lenstra et al. [1] showed that the general case of the problem $1\mid r_j\mid L_{\max }$ is $\mathit{NP}$ -hard in the strong sense.

Potts [3] introduced an iterative version of extended Jackson rule (IJ) [4] and proved that $\frac{L_{\max }\left({\pi }_{\mathit{IJ}}\right)}{L_{\max }^{\ast }}\le \frac{3}{2}$ . Hall and Shmoys [5] modified the iterative version and created an algorithm (MIJ) that guarantees the evaluation $\frac{L_{\max }\left({\pi }_{\mathit{MIJ}}\right)}{L_{\max }^{\ast }}\le \frac{4}{3}$ . They also presented two approximation schemes that guarantee finding $\epsilon$ -approximate solution in $O\left(nlogn+n{\left(1/\epsilon \right)}^{O\left(1/{\epsilon }^2\right)}\right)$ and $O\left({\left(n/\epsilon \right)}^{O\left(1/\epsilon \right)}\right)$ operations. Mastrolilli [6] introduced an improved approximation scheme with complexity of $O\left(n+{\left(1/\epsilon \right)}^{O\left(1/\epsilon \right)}\right)$ operations.

A number of polynomially solvable cases of the problem were found, starting with Jackson’s early result [4] for the case $r_j=0$ , $j\in N$ , when the solution is a schedule in which jobs are ordered by nondecreasing due dates (by rule $\mathit{EDD}$ ). Such a schedule is also be optimal for the case when the release times and due dates are associated ( $r_i\le r_j\iff d_i\le d_j$ , $\forall i,j\in N$ ).

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 $O\left(nlogn\right)$ [7]. Vakhania generalized this result [8] considering the case when the processing times of some jobs are restricted to either $p$ or $2p$ . An algorithm with complexity of $O\left(n^{2}lognlogp\right)$ was suggested.

A case when job processing times are mutually divisible is considered in [9]. Author suggest a polynomial-time algorithm with a complexity of $O\left(n^{3}logn{log}^2{p}_{\max }\right)$ operations for solving this case.

Special cases $1\mid \mathit{\text{prec}};r_j\mid C_{\max }$ , $1\mid \mathit{\text{prec}};p_j=p;r_j\mid L_{\max }$ and $1\mid \mathit{\text{prec}};r_j;\mathit{\text{pmtn}}\mid L_{\max }$ with precedence constraints for jobs have been addressed in works of Lawler [10], Simons [11], Baker et al. [12]. Hoogeveen [13] proposed a polynomial algorithm for the special case when job parameters satisfy the constraints $d_j-p_j-A\le r_j\le d_j-A$ , $\forall j\in N$ , for some constant $A$ . A pseudo-polynomial algorithm for the NP-hard case when release times and due dates are in the reversed order ( $d_1\le \dots \le d_n$ and $r_1\ge \dots \ge r_n$ ) was developed in [14].

We denote by $L_j^A\left(\pi \right)$ and $C_j^A\left(\pi \right)$ the lateness and completion time of job $j\in N$ in schedule $\pi$ , for instance, $A$ with job parameters $\left\{r_j^A,p_j^A,d_j^A\right\}$ , $j\in N$ . Respectively, $L_{\max }^A\left(\pi \right)=\underset{j\in N}{max}{L}_j^A\left(\pi \right)$ is a maximum lateness of the schedule $\pi$ for instance $A$ .

This paper deals with a problem with two objective functions $L_{\max }$ and $C_{\max }$ , which in general case can be referred as $1\mid r_j\mid L_{\max },C_{\max }$ . This problem was considered in [15], where authors consider some dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time.

Definition 1.1 For any instance $A$ of the problem, each permutation $\tau$ of the jobs of the set $N$ is uniquely defines early schedule ${\pi }_{\tau }^A$ . In the early schedule, each job $j\in N$ starts immediately after the end of the previous job in the corresponding permutation. If the completion time of the previous job is less than the release time of the current job, then the beginning of the current job is equal to its release time. That is, if $\tau =\left(j_1,j_2,\dots ,j_n\right)$ , then ${\pi }_{\tau }^A=\left(s_{j_1},s_{j_2},\dots ,s_{j_n}\right)$ , where

$$s_{j_1}=r_{j_1}^A,s_{j_k}=max\left\{s_{j_{k-1}}+p_{j_{k-1}}^A,r_{j_k}^A\right\},k=2,\dots ,n.$$ E4

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 ${\tau }^A$ we denote the optimal permutation and ${\pi }^A$ we denote the optimal schedule for instance $A$ . Only early optimal schedules are be considered, that is, ${\pi }^A={\pi }_{{\tau }^A}^A$ .

We denote by $\mathrm{\Pi }\left(N\right)$ the set of all permutations of jobs of the set $N$ , and by ${\mathrm{\Pi }}_A$ the set of feasible schedules for instance $A$ .

3. Problem $1\mid d_i\le d_j,d_i-r_i-p_i\ge d_j-r_j-p_j\mid L_{\max },C_{\max }$

This section deals with the problem of constructing a Pareto-optimal set by criteria $C_{\max }$ and $L_{\max }$ , that is, problem $1\mid r_j\mid L_{\max }$ , $C_{\max }$ . We suggest an algorithm for constructing a set of schedules $\mathrm{\Phi }\left(N,t\right)=\left\{{\pi }_1^{\prime },{\pi }_2^{\prime },\dots ,{\pi }_m^{\prime }\right\}$ for which

$$C_{\max }\left({\pi }_1^{\prime }\right)<C_{\max }\left({\pi }_2^{\prime }\right)<\dots <C_{\max }\left({\pi }_m^{\prime }\right),$$ E5

$$L_{\max }\left({\pi }_1^{\prime }\right)>L_{\max }\left({\pi }_2^{\prime }\right)>\dots >L_{\max }\left({\pi }_m^{\prime }\right).$$ E6

There is no schedule $\pi$ such that $C_{\max }\left(\pi \right)\le C_{\max }\left({\pi }_i^{\prime }\right)$ and $L_{\max }\left(\pi \right)\le L_{\max }\left({\pi }_i^{\prime }\right)$ , at least one of the inequalities is strict for some $i$ , $i=1,\dots ,m$ . It is shown that $m\le n$ .

3.1 Problem properties

We denote the precedence of the jobs $i$ and $j$ in schedule $\pi$ as ${\left(i\to j\right)}_{\pi }$ . We also introduce

$$r_j\left(t\right)=max\left\{r_j,t\right\};$$ E7

$$r\left(N,t\right)=\underset{j\in N}{min}\left\{r_j\left(t\right)\right\}.$$ E8

In cases when its obvious how many jobs we mean, we write $r\left(t\right)$ instead of $r\left(N,t\right)$ .

We assume that the job parameters satisfy the following constraints:

$$d_1\le \dots \le d_n,d_1-r_1-p_1\ge \dots \ge d_n-r_n-p_n.$$ E9

For example, these constraints correspond to the case when $d_j=r_j+p_j+z$ , $j=1,\dots ,n$ , where $z$ is a constant, that is, when all jobs have the same time for processing before due date. A problem with similar constraints but for a single objective function ( $L_{\max }$ ) is considered in [16].

We assume that $\mid N\mid >1$ and $t$ is the time when the machine is ready. From the set $N$ , we find two jobs $f=f\left(N,t\right)$ and $s=s\left(N,t\right)$ in the following way:

$$f\left(N,t\right)=arg\underset{j\in N}{min}\left\{d_j|r_j\left(t\right)=r\left(N,t\right)\right\},$$ E10

$$s\left(N,t\right)=arg\underset{j\in N\backslash \left\{f\right\}}{min}\left\{d_j|r_j\left(t\right)=r\left(N\backslash f,t\right)\right\},$$ E11

where $f=f\left(N,t\right)$ . If $N=\left\{i\right\}$ , then we set $f\left(N,t\right)=i$ , $s\left(N,t\right)=0$ , $\forall t$ . We also define $d_0=+\infty$ , $f\left(\varnothing ,t\right)=0$ , $s\left(\varnothing ,t\right)=0$ , $\forall t$ . For jobs $f$ and $s$ the following properties are true.

Lemma 1.1 If the jobs of the set $N$ satisfy (4), then for any schedule $\pi \in \mathrm{\Pi }\left(N\right)$ for all $j\in N\backslash \left\{f\right\},$ for which ${\left(j\to f\right)}_{\pi }$

$$L_j\left(\pi \right)<L_f\left(\pi \right)$$ E12

is true, and for all $j\in N\backslash \left\{f,s\right\},$ satisfying the condition ${\left(j\to s\right)}_{\pi }$ ,

$$L_j\left(\pi \right)<L_s\left(\pi \right),$$ E13

where $f=f\left(N,t\right)$ and $s=s\left(N,t\right)$ , is also true.

Proof: For each job $j$ such that ${\left(j\to f\right)}_{\pi }$ , completion time $C_j\left(\pi \right)<C_f\left(\pi \right)$ . If $d_j\ge d_f$ , then obviously

$$L_j\left(\pi \right)=C_j\left(\pi \right)-d_j<C_f\left(\pi \right)-d_f=L_f\left(\pi \right),$$ E14

therefore (12) is valid.

If for job $j\in N$ , ${\left(j\to f\right)}_{\pi }$ , then $d_j<d_f$ . Then $r_j>r_f$ . If $r_j\le r_f$ , then $r_j\left(t\right)\le r_f\left(t\right)$ and $r_f\left(t\right)=r\left(t\right)$ , as follows from (7) and (10). Then $r_j\left(t\right)=r_f\left(t\right)=r\left(t\right)$ and $d_j<d_f$ , but this contradicts the definition of job $f$ (10). Therefore, $r_j>r_f$ . Its obvious that $C_j\left(\pi \right)-p_j<C_f\left(\pi \right)-p_f$ and, since $r_j>r_f$ ,

$$C_j\left(\pi \right)-p_j-r_j<C_f\left(\pi \right)-p_f-r_f,$$ E15

$$C_j\left(\pi \right)-C_f\left(\pi \right)<p_j+r_j-p_f-r_f.$$ E16

Since $d_j<d_f$ , then (from (9)) $d_j-r_j-p_j\ge d_f-r_f-p_f$ or $d_j-d_f\ge r_j+p_j-r_f-p_f$ , so $C_j\left(\pi \right)-C_f\left(\pi \right)<p_j+r_j-p_f-r_f\le d_j-d_f$ . Then, $L_j\left(\pi ,t\right)<L_f\left(\pi ,t\right)$ for each job $j,{\left(j\to f\right)}_{\pi }$ .

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

For each job $j$ satisfying the condition ${\left(j\to s\right)}_{\pi }$ , we have $C_j\left(\pi \right)<C_s\left(\pi \right)$ . If $d_j\ge d_s$ , then $L_j\left(\pi ,t\right)=C_j\left(\pi \right)-d_j<C_s\left(\pi \right)-d_s=L_s\left(\pi ,t\right)$ , therefore (13) is true.

Let for the job $j\in N\backslash \left\{f\right\}$ , ${\left(j\to s\right)}_{\pi }$ , $d_j<d_s$ , then $r_j>r_s$ . Indeed, if we assume that $r_j\le r_s$ , then $r_j\left(t\right)\le r_s\left(t\right)$ (it follows from (7)). In addition, $r_s\left(t\right)\ge r\left(t\right)$ for any job $s$ according to definitions (8) and (11). If $r_s\left(t\right)=r\left(t\right)$ , then for the jobs $j$ and $s$ we can write $r_j\left(t\right)=r_s\left(t\right)=r\left(t\right)$ and $d_j<d_s$ , which contradicts the definition (11) of job $s\left(N,t\right)$ . If $r_s\left(t\right)>r\left(t\right)$ , that is, $r_s>r\left(t\right)$ , then there is no job $i\in N\backslash \left\{f,s\right\}$ , for which $r_s>r_i>r\left(t\right)$ . Therefore, for the jobs $j$ and $s$ we get $r_j\left(t\right)=r_s\left(t\right)$ and $d_j<d_s$ , which contradicts the definition (11) of job $s\left(N,t\right)$ . Therefore, $r_j>r_s.$

Since $C_j\left(\pi \right)\le C_s\left(\pi \right)-p_s$ and $p_j>0$ , then $C_j\left(\pi \right)-p_j<C_s\left(\pi \right)-p_s$ and since $r_j>r_s$ , therefore $C_j\left(\pi \right)-p_j-r_j<C_s\left(\pi \right)-p_s-r_s$ and

$$C_j\left(\pi \right)-C_s\left(\pi \right)<p_j+r_j-p_s-r_s.$$ E17

Since $d_j<d_s$ , then from (9) we have $d_j-r_j-p_j\ge d_s-r_s-p_s$ or

$$C_j\left(\pi \right)-C_s\left(\pi \right)<p_j+r_j-p_s-r_s\le d_j-d_s.$$ E18

Hence, $L_j\left(\pi \right)<L_s\left(\pi \right)$ for each job $j\in N\backslash \left\{f\right\},{\left(j\to s\right)}_{\pi }$ .

Theorem 1.1 If conditions (9) are true for jobs in the subset $N^{\prime }\subseteq N$ , then at any time $t^{\prime }\ge t$ and any early schedule $\pi \in \mathrm{\Pi }\left(N^{\prime }\right)$ there exists ${\pi }^{\prime }\in \mathrm{\Pi }\left(N^{\prime }\right)$ such that

$$L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le L_{\max }\left(\pi ,t^{\prime }\right),\text{and}{C}_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right)$$ E19

and one of the jobs $f=f\left(N^{\prime },t^{\prime }\right)$ or $s=s\left(N^{\prime },t^{\prime }\right)$ is at the first position in schedule ${\pi }^{\prime }$ . If $d_f\le d_s$ , then job $f$ is at the first position in schedule ${\pi }^{\prime }$ .

Proof: Let $\pi =\left({\pi }_1,f,{\pi }_2,s,{\pi }_3\right)$ , where ${\pi }_1,{\pi }_2$ and ${\pi }_3$ are partial schedules of $\pi$ . Then, we construct a schedule ${\pi }^{\prime }=\left(f,{\pi }_1,{\pi }_2,s,{\pi }_3\right)$ . From the definitions (7), (8), (10) we get $r_f\left(t^{\prime }\right)\le r_j\left(t^{\prime }\right)$ , $j\in N^{\prime }$ , hence $C_{\max }\left(\left(f,{\pi }_1\right),t^{\prime }\right)\le C_{\max }\left(\left({\pi }_1,f\right),t^{\prime }\right)$ and

$$C_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right),\text{and}$$ E20

$$L_j\left({\pi }^{\prime },t^{\prime }\right)\le L_j\left(\pi ,t^{\prime }\right),\forall j\in \left\{\left({\pi }_2,s,{\pi }_3\right)\right\}.$$ E21

From the lemma 1.1 we have

$$L_j\left({\pi }^{\prime },t^{\prime }\right)<L_s\left({\pi }^{\prime },t^{\prime }\right),\forall j\in \left\{{\pi }_1\right\}\cup \left\{{\pi }_2\right\}.$$ E22

Obviously, the following inequality is true for job $f$

$$L_f\left({\pi }^{\prime },t^{\prime }\right)\le L_f\left(\pi ,t^{\prime }\right).$$ E23

From (20)–(23) we get $C_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right)$ and $L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le L_{\max }\left(\pi ,t^{\prime }\right)$ .

Let $\pi =\left({\pi }_1,s,{\pi }_2,f,{\pi }_3\right)$ , that is, job $s$ is before job $f$ . Construct a schedule ${\pi }^{\prime }=\left(s,{\pi }_1,{\pi }_2,f,{\pi }_3\right)$ . Further proof may be repeated as for job $f$ . The first part of the theorem is proved.

Let us assume $d_f\le d_s$ and the schedule $\pi =\left({\pi }_1,s,{\pi }_2,f,{\pi }_3\right)$ . Then, we construct a schedule ${\pi }^{\prime }=\left(f,{\pi }_{11},{\pi }_{12},{\pi }_3\right)$ , where ${\pi }_{11},{\pi }_{12}$ are schedules of jobs of the sets $\left\{j\in N^{\prime }:j\in \left\{\left({\pi }_1,s,{\pi }_2\right)\right\},d_j<d_f\right\}$ and $\left\{j\in N^{\prime }:j\in \left\{\left({\pi }_1,s,{\pi }_2\right)\right\},d_j\ge d_f\right\}$ . Jobs in ${\pi }_{11}$ and ${\pi }_{12}$ are ordered according to nondecreasing release times $r_j$ . From $d_s\ge d_f$ we can conclude that $s\in \left\{{\pi }_{12}\right\}$ .

For each job $j\in \left\{{\pi }_{11}\right\}$ we have $d_j<d_f$ . Of (9) we get $d_j-r_j-p_j\ge d_f-r_f-p_f$ , hence $r_j+p_j<r_f+p_f$ , $\forall j\in \left\{{\pi }_{11}\right\}$ , and $C_{\max }\left(\left(f,{\pi }_{11}\right),t^{\prime }\right)=r_f\left(t^{\prime }\right)+p_f+{\sum }_{j\in \left\{{\pi }_{11}\right\}}{p}_j$ . Since jobs in schedule $\left\{{\pi }_{12}\right\}$ are sorted by nondecreasing release times, then $C_{\max }\left(\left(f,{\pi }_{11},{\pi }_{12}\right),t^{\prime }\right)\le C_{\max }\left(\left({\pi }_1,s,{\pi }_2,f\right),t^{\prime }\right)$ . As a result

$$C_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right),\text{and}$$ E24

$$L_j\left({\pi }^{\prime },t^{\prime }\right)\le L_j\left(\pi ,t^{\prime }\right),\forall j\in \left\{{\pi }_3\right\}.$$ E25

Job $j\in \left\{{\pi }_{12}\right\}$ satisfies $d_j\ge d_f$ and $C_j\left({\pi }^{\prime },t^{\prime }\right)\le C_f\left(\pi ,t^{\prime }\right)$ , which means

$$L_j\left({\pi }^{\prime },t^{\prime }\right)\le L_f\left(\pi ,t^{\prime }\right),\forall j\in \left\{{\pi }_{12}\right\}.$$ E26

Since $s\in \left\{{\pi }_{12}\right\}$ , then

$$L_s\left({\pi }^{\prime },t^{\prime }\right)\le L_f\left(\pi ,t^{\prime }\right).$$ E27

From the lemma 1.1

$$L_j\left({\pi }^{\prime },t^{\prime }\right)\le L_s\left({\pi }^{\prime },t^{\prime }\right),\forall j\in \left\{{\pi }_{11}\right\}.$$ E28

Moreover, it is obvious that

$$L_f\left({\pi }^{\prime },t^{\prime }\right)\le L_f\left(\pi ,t^{\prime }\right).$$ E29

From inequalities (24)–(29) it follows that $C_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right)$ and $L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le L_{\max }\left(\pi ,t^{\prime }\right)$ , the theorem is proved.

We call a schedule ${\pi }^{\prime }\in \mathrm{\Pi }\left(N\right)$ effective if there is no schedule $\pi \in \mathrm{\Pi }\left(N\right)$ such that $L_{\max }\left(\pi \right)\le L_{\max }\left({\pi }^{\prime }\right)$ and $C_{\max }\left(\pi \right)\le C_{\max }\left({\pi }^{\prime }\right)$ , that is, at least one inequality would be strict.

Thus, when constraints (9) are satisfied for jobs from the set $N$ , then there is an effective schedule ${\pi }^{\prime }$ , in which either the job $f=f\left(N,t\right)$ , or $s=s\left(N,t\right)$ is present. Moreover, if $d_f\le d_s$ , then there is an effective schedule ${\pi }^{\prime }$ with a priority of job $f$ .

We define the set of schedules $\mathrm{\Omega }\left(N,t\right)$ as a subset of $\mathrm{\Pi }\left(N\right)$ consisting of $n!$ schedules. Schedule $\pi =\left(i_1,i_2,\dots ,i_n\right)$ belongs to $\mathrm{\Omega }\left(N,t\right)$ if we choose job $i_k,k=1,2,\dots ,n$ as $f_k=f\left(N_{k-1},C_{i_{k-1}}\right)$ or $s_k=s\left(N_{k-1},C_{i_{k-1}}\right)$ , where $N_{k-1}=N\backslash \left\{i_1,i_2,\dots ,i_{k-1}\right\}$ , $C_{i_{k-1}}=C_{i_{k-1}}\left(\pi \right)$ and $N_0=N$ , $C_{i_0}=t$ . For $d_{f_k}\le d_{s_k}$ it is true that $i_k=f_k$ , so if $d_{f_k}>d_{s_k}$ , then $i_k=f_k$ or $i_k=s_k$ . Its obvious that the set of schedules $\mathrm{\Omega }\left(N,t\right)$ contains at most $2^n$ schedules.that is, $p_{2i}>y\ge p_{2i-1}$ .

Example 1.1

$$\left\{\begin{array}{l}n=2m,t\le r_1<r_2<\dots <r_n,\\ r_{2i-1}<r_{2i}+p_{2i}<r_{2i-1}+p_{2i-1},1\le i\le m,\\ r_{2i-1}+p_{2i-1}+p_{2i}<r_{2i+1}<r_{2i}+p_{2i}+p_{2i-1}<r_{2i+2},1\le i\le m-1,\\ r_{2i-1}+p_{2i-1}+p_{2i}-d_{2i-1}>y,1\le i\le m-1,\\ r_{2i}+p_{2i}+p_{2i-1}-d_{2i}\le y.\end{array}\right.$$

The set $\mathrm{\Omega }\left(N,t\right)$ contains $2^m$ schedules. The value of $y$ is used below in the text. The optimal solution of the problem $1\mid r_j,d_j=r_j+p_j,L_{\mathit{max}}\le y\mid C_{\max }$ is ${\pi }^{\ast }=\left(\mathrm{2,1,4,3},\dots ,n,n-1\right).$

Theorem 1.2 If for the jobs of the subset $N^{\prime }\subseteq N,\mid N^{\prime }\mid =n^{\prime },$ is true (9), then at any time $t^{\prime }\ge t$ and any schedule $\pi \in \mathrm{\Pi }\left(N^{\prime }\right)$ exists a schedule ${\pi }^{\prime }\in \mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ such that

$$L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le L_{\max }\left(\pi ,t^{\prime }\right)\text{and}{C}_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right).$$ E30

Proof: Let $\pi =\left(j_1,j_2,\dots ,j_{n^{\prime }}\right)$ be an arbitrary schedule. We denote the first $l$ jobs of the schedule $\pi$ as ${\pi }_l,l=\mathrm{0,1,2},\dots ,n^{\prime }$ , where ${\pi }_0$ is an empty schedule, and ${\overline{\pi }}_l=\left(j_{l+1},\dots ,j_{n^{\prime }}\right)$ , then $\pi =\left({\pi }_l,{\overline{\pi }}_l\right)$ . We introduce $N_l=N^{\prime }\backslash \left\{{\pi }_l\right\}$ and $C_l=C_{\max }\left({\pi }_l,t^{\prime }\right)$ . Suppose for some $l,0\le l<n^{\prime }$ , ${\pi }_l$ is the largest initial partial the schedule of some schedule from $\mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ . If $j_1\ne f\left(N^{\prime },t^{\prime }\right)$ and $j_1\ne s\left(N^{\prime },t^{\prime }\right)$ , then ${\pi }_l={\pi }_0$ , $l=0$ , then the largest partial schedule is empty. Let us say $f=f\left(N_l,C_l\right)$ and $s=s\left(N_l,C_l\right)$ . If $d_f>d_s$ , then $j_{l+1}\ne f$ and $j_{l+1}\ne s$ , moreover when $d_f\le d_s$ , then $j_{l+1}\ne f$ , since ${\pi }_{l+1}$ is not an initial schedule of some schedule from $\mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ .

According to the theorem 1.1 for the jobs of the set $\left\{{\overline{\pi }}_l\right\},{\overline{\pi }}_l\in \mathrm{\Pi }\left(N_l\right)$ , there is a schedule ${\overline{\pi }}_l^{\prime }$ starting at time $C_l$ , for which $L_{\max }\left({\overline{\pi }}_l^{\prime },C_l\right)\le L_{\max }\left({\overline{\pi }}_l,C_l\right)$ , $C_{\max }\left({\overline{\pi }}_l^{\prime },C_l\right)\le C_{\max }\left({\overline{\pi }}_l,C_l\right)$ , and ${\left[{\overline{\pi }}_l^{\prime }\right]}_1=\left(f\text{or}s\right)$ , moreover, with $d_f\le d_s$ , true ${\left[{\overline{\pi }}_l^{\prime }\right]}_1=f$ , where ${\left[\sigma \right]}_k$ is the job in the $k$ -th place in schedule $\sigma$ . Hence, $L_{\max }\left(\left({\pi }_l,{\overline{\pi }}_l^{\prime }\right),t^{\prime }\right)\le L_{\max }\left(\left({\pi }_l,{\overline{\pi }}_l\right),t^{\prime }\right)$ and $C_{\max }\left(\left({\pi }_l,{\overline{\pi }}_l^{\prime }\right),t^{\prime }\right)\le C_{\max }\left(\left({\pi }_l,{\overline{\pi }}_l\right),t^{\prime }\right)$ .

Let us denote ${\pi }^{\prime }=\left({\pi }_l,{\overline{\pi }}_l^{\prime }\right)$ . A feature of schedule ${\pi }^{\prime }$ is that the first $l+1$ jobs are the same as first $l+1$ jobs of some schedule from the set $\mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ , and $L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le L_{\max }\left(\pi ,t^{\prime }\right)$ , $C_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right)$ .

After no more than $n^{\prime }$ sequential conversions (since schedule length $n^{\prime }\le n$ ) of the original randomly selected schedule $\pi$ we come to schedule ${\pi }^{\prime }\in \mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ , for which $L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le L_{\max }\left(\pi ,t^{\prime }\right)$ and $C_{\max }\left({\pi }^{\prime },t^{\prime }\right)\le C_{\max }\left(\pi ,t^{\prime }\right)$ . The theorem is proved.

We form the following partial schedule $\omega \left(N,t\right)=\left(i_1,i_2,\dots ,i_l\right)$ . For each job $i_k,k=1,2,\dots ,l$ , we have $i_k=f_k$ and $d_{f_k}\le d_{s_k}$ , where $f_k=f\left(N_{k-1},C_{k-1}\right)$ and $s_k=s\left(N_{k-1},C_{k-1}\right)$ . For $f=f\left(N_l,C_l\right)$ and $s=s\left(N_l,C_l\right)$ inequality $d_f>d_s$ is true. In case when $d_f>d_s$ for $f=f\left(N,t\right)$ and $s=s\left(N,t\right)$ , then $\omega \left(N,t\right)=\varnothing$ . So $\omega \left(N,t\right)$ is the “maximum” schedule, during the construction of which job (like $f$ ) for the next place of the schedule can be uniquely selected. We can construct a schedule $\omega \left(N,t\right)$ for set of jobs $N$ starting at time $t$ using the algorithm 1.1.

Algorithm 1.1 for constructing schedule $\omega \left(N,t\right)$ .

1: Initial step. Let $\omega =\varnothing$ .

2: Main step. Find the jobs $f≔f\left(N,t\right)$ and $s≔s\left(N,t\right)$ ;

3: if $d_f\le d_s$ then

4: $\omega ≔\left(\omega ,f\right)$

5: else

6: algorithm stops;

7: end if

8: Let $N≔N\backslash \left\{f\right\}$ , $t≔r_f\left(t\right)+p_f$ and go to the next main step.

Lemma 1.2 The complexity of the algorithm 1.1 for finding the schedule $\omega \left(N,t\right)$ is at most $O\left(nlogn\right)$ operations for any $N$ and any $t$ .

Proof: At each iteration of the algorithm 1.1 we find two jobs: $f=f\left(N,t\right)$ and $s=s\left(N,t\right)$ . If jobs are ordered by release times $r_j$ (and, accordingly, time $r\left(t\right)$ is for $O\left(1\right)$ operations), then to find two jobs ( $f$ and $s$ ) you need $O\left(logn\right)$ operations. Total number of iterations is not more than $n$ . Thus, constructing a schedule $\omega \left(N,t\right)$ requires $O\left(nlogn\right)$ operations.

The main step of algorithm 1.1 is finding the jobs $f$ and $s$ and it requires at least $O\left(logn\right)$ operations. Obviously, the number of iterations of the algorithm is O(n), therefore, the complexity of the algorithm 1.1 of $O\left(nlogn\right)$ operations is the minimum possible for constructing the schedule $\omega \left(N,t\right)$ .

Lemma 1.3 If for jobs of the set $N$ conditions (9) are true, then any schedule $\pi \in \mathrm{\Omega }\left(N,t\right)$ starts with the schedule $\omega \left(N,t\right)$ .

Proof: If $\omega \left(N,t\right)=\varnothing$ , that is, $d_f>d_s$ , where $f=f\left(N,t\right)$ , $s=s\left(N,t\right)$ , the statement of the lemma is true, since any schedule starts from empty.

Let $\omega \left(N,t\right)=\left(i_1,i_2,\dots ,i_l\right)$ , $l>0$ , and so for each $i_k$ , $k=1,2,\dots ,l$ , we have $i_k=f_k$ and $d_{f_k}\le d_{s_k}$ , where $f_k=f\left(N_{k-1},C_{k-1}\right)$ and $s_k=s\left(N_{k-1},C_{k-1}\right)$ . For $f=f\left(N_l,C_l\right)$ and $s=s\left(N_l,C_l\right)$ it is true that $d_f>d_s$ . As seen from the definition of the set of schedules $\mathrm{\Omega }\left(N,t\right)$ all schedules in this subset start with a partial schedule $\omega \left(N,t\right)$ .

Let us use the following notation ${\omega }^1\left(N,t\right)=\left(f,\omega \left(N^{\prime },t^{\prime }\right)\right)$ and ${\omega }^2\left(N,t\right)=\left(s,\omega \left(N^{″},{t^{\prime }}^{\prime }\right)\right)$ , where $f=f\left(N,t\right),s=s\left(N,t\right),N^{\prime }=N\backslash \left\{f\right\},{N^{\prime }}^{\prime }=N\backslash \left\{s\right\},t^{\prime }=r_f\left(t\right)+p_f,{t^{\prime }}^{\prime }=r_s\left(t\right)+p_s$ . Obviously, the algorithm for finding ${\omega }^1$ (as well as ${\omega }^2$ ) requires $O\left(nlogn\right)$ operations, as much as the algorithm for constructing $\omega \left(N,t\right)$ .

Consequence 1.1 from Lemma 1.3. If the jobs of the set $N$ satisfy conditions (9), then each schedule $\pi \in \mathrm{\Omega }\left(N,t\right)$ starts either with ${\omega }^1\left(N,t\right)$ , or with ${\omega }^2\left(N,t\right)$ .

Theorem 1.3 If the jobs of the set $N$ satisfy conditions (9), then for any schedule $\pi \in \mathrm{\Omega }\left(N,t\right)$ it is true that ${\left(i\to j\right)}_{\pi }$ for any $i\in \left\{{\omega }^1\left(N,t\right)\right\}$ and $j\in N\backslash \left\{{\omega }^1\left(N,t\right)\right\}$ .

Proof: In the case $\left\{{\omega }^1\left(N,t\right)\right\}=N$ statement of the theorem is obviously true. Let $\left\{{\omega }^1\left(N,t\right)\right\}\ne N$ . Further in in the proof we use the notation ${\omega }^1={\omega }^1\left(N,t\right)$ .

If $f=f\left(N,t\right)$ and $s=s\left(N,t\right)$ are such that $d_f\le d_s$ , then all schedules from the set $\mathrm{\Omega }\left(N,t\right)$ begin with a partial schedule $\omega \left(N,t\right)={\omega }^1$ , therefore the statement of the theorem is also true.

Consider the case of $d_f>d_s$ . All schedules from set $\mathrm{\Omega }\left(N,t\right)$ starting with job $f$ have partial schedule $\omega \left(N,t\right)={\omega }^1$ .

Let us choose any arbitrary schedules $\pi \in \mathrm{\Omega }\left(N,t\right)$ with job $s$ comes first, ${\pi }_1=s$ , and any schedule $\mid {\omega }^1\mid =l,l<n$ , containing $l$ jobs. Let ${\pi }_l=\left(j_1,j_2,\dots ,j_l\right)$ be a partial schedule of schedule $\pi$ containing $l$ jobs, where $j_1=s$ . We need to prove that $\left\{{\pi }_l\right\}=\left\{{\omega }^1\right\}$ . Let us assume the contrary that there is a job $j\in \left\{{\pi }_l\right\}$ , but $j\notin \left\{{\omega }^1\right\}$ .

For case ${\left(j\to f\right)}_{\pi }$ we need to check two subcases. If $d_j<d_f$ , then from (9) we have $d_j-r_j-p_j\ge d_f-r_f-p_f$ , therefore $r_j+p_j<r_f+p_f$ . Then job $j$ is included in schedule ${\omega }^1$ according to the definition of $\omega \left(N,t\right)$ and ${\omega }^1$ , but by our assumption $j\notin \left\{{\omega }^1\right\}$ . If $d_j\ge d_f$ , then from the fact that $\pi \in \mathrm{\Omega }\left(N,t\right)$ follows ${\left(f\to j\right)}_{\pi }$ , but this contradicts ${\left(j\to f\right)}_{\pi }$ . Therefore, $j\in \left\{{\omega }^1\right\}$ .

The other case is ${\left(f\to j\right)}_{\pi }$ . Then for each job $i\in \left\{{\omega }^1\right\}$ , for which $i\notin \left\{{\pi }_l\right\}$ , conditions $r_i<r_i+p_i\le C_{\max }\left({\omega }^1\right)<r_{s_{l+1}}\le r_j$ are true, because $j\notin \left\{{\omega }^1\right\}$ , where $s_{l+1}=s\left(N\backslash \left\{{\omega }^1\right\},C_{\max }\left({\omega }^1\right)\right)$ . Jobs $s_{l+1}$ and $j$ were not ordered in schedule ${\omega }^1$ , therefore, $C_{\max }\left({\omega }^1\right)<r_{s_{l+1}}\le r_j$ . Besides, $d_i\le d_j$ . If $d_i>d_j$ , then $r_i+p_i\ge r_j+p_j$ , but $r_i+p_i<r_j$ is true. Hence ${\left(i\to j\right)}_{{\pi }_l}$ , since $\pi =\left({\pi }_l,{\overline{\pi }}_l\right)\in \mathrm{\Omega }\left(N,t\right)$ , but it contradicts our guess that $i\notin \left\{{\pi }_l\right\}$ and $j\in \left\{{\pi }_l\right\}$ .

Therefore, our assumption is not true and $\left\{{\omega }^1\right\}=\left\{{\pi }_l\right\}$ . The theorem is proved.

Therefore, jobs of the set $\left\{{\omega }^1\left(N,t\right)\right\}$ precede jobs of the set $N\backslash \left\{{\omega }^1\left(N,t\right)\right\}$ for any schedule from the set $\mathrm{\Omega }\left(N,t\right)$ , including the optimal schedule.

3.2 Performance problem with constraint on maximum lateness

The problem $1\mid d_i\le d_j,d_i-r_i-p_i\ge d_j-r_j-p_j;L_{\max }\le y\mid C_{\max }$ consists of the following. We need to find schedule $\theta$ for any $y$ with $C_{\max }\left(\theta \right)=min\left\{C_{\max }\left(\pi \right):L_{\max }\left(\pi \right)\le y\right\}$ . If $L_{\max }\left(\pi \right)>y$ for any $\pi \in \mathrm{\Pi }\left(N\right)$ , then $\theta =\varnothing$ .

Lemma 1.4 The complexity of algorithm 1.2 does not exceed $O\left(n^{2}logn\right)$ operations.

Proof: At each iteration of the main step of the algorithm 1.2 we find the schedules ${\omega }^1$ and, if necessary, ${\omega }^2$ in $O\left(nlogn\right)$ operations. Since ${\omega }^1$ and ${\omega }^2$ consist of at least one job, then at each iteration of the algorithm we either add one or mere jobs to the schedule $\theta$ , or assume $\theta =\varnothing$ and stop. Therefore, the total number of steps of the algorithm is at most $n$ . Thus, algorithm 1.2 requires $O\left(n^{2}logn\right)$ operations.

Algorithm 1.2 for solving the problem $1\mid d_i\le d_j,d_i-r_i-p_i\ge d_j-r_j-p_j;L_{\max }\le y\mid C_{\max }$ .

1: Initial step. Let $\theta ≔\omega \left(N,t\right),t^{\prime }≔t;$

2: Main step.

3: if $L_{\max }\left(\theta ,t^{\prime }\right)>y$ then

4: $\theta ≔\varnothing$ and the algorithm stops.

5: end if

6: Find $N^{\prime }≔N\backslash \left\{\theta \right\}$ , $t^{\prime }≔C_{\max }\left(\theta \right)$ and ${\omega }^1\left(N^{\prime },t^{\prime }\right),{\omega }^2\left(N^{\prime },t^{\prime }\right)$ .

7: if $N^{\prime }=\varnothing$ then

8: the algorithm stops.

9: else

10: if $L_{\max }\left({\omega }^1,t^{\prime }\right)\le y$ then

11: $\theta ≔\left(\theta ,{\omega }^1\right)$ and go to next step;

12: end if

13: if $L_{\max }\left({\omega }^1,t^{\prime }\right)>y$ and $L_{\max }\left({\omega }^2,t^{\prime }\right)\le y$ then

14: $\theta ≔\left(\theta ,{\omega }^2\right)$ and go to next step;

15: end if

16: if $L_{\max }\left({\omega }^1,t^{\prime }\right)>y$ and $L_{\max }\left({\omega }^2,t^{\prime }\right)>y$ then

17: $\theta ≔\varnothing$ and the algorithm stops.

18: end if

19: end if

The problem $1\mid d_i\le d_j,d_i-r_i-p_i\ge d_j-r_j-p_j;L_{\max }\le y\mid C_{\max }$ cannot be solved in less than $O\left(n^{2}logn\right)$ operations because there exists (Example 1.1). The optimal schedule for this example is ${\pi }^{\ast }=\left(\mathrm{2,1,4,3},\dots ,n,n-1\right)$ . To find this schedule, we need $O\left(n^{2}logn\right)$ operations.

We denote by $\theta \left(N,t,y\right)$ the schedule constructed by algorithm 1.2 starting at time $t$ from the jobs of the set $N$ with the maximum lateness not more than $y$ . If $N=\varnothing$ , then $\theta \left(\varnothing ,t,y\right)=\varnothing$ for any $t$ and $y$ .

Theorem 1.4 Let the jobs of the set $N$ satisfy conditions (9). If the algorithm 1.2 constructs the schedule $\theta \left(N,t,y\right)\ne \varnothing$ , then $C_{\max }\left(\theta \right)=min\left\{C_{\max }\left(\pi \right):L_{\max }\left(\pi \right)\le y,\pi \in \mathrm{\Pi }\left(N\right)\right\}$ . If, as a result of the algorithm 1.2 the schedule will not be generated, that is, $\theta \left(N,t,y\right)=\varnothing$ , then $L_{\max }\left(\pi \right)>y$ for each $\pi \in \mathrm{\Pi }\left(N\right)$ .

Proof: In case if for schedule $\pi \in \mathrm{\Pi }\left(N\right)$ condition $L_{\max }\left(\pi \right)\le y$ is true, then according to Theorem 1.2 there is a schedule ${\pi }^{\prime }\in \mathrm{\Omega }\left(N,t\right)$ such that $L_{\max }\left({\pi }^{\prime }\right)\le L_{\max }\left(\pi \right)\le y$ and $C_{\max }\left({\pi }^{\prime }\right)\le C_{\max }\left(\pi \right)$ . Therefore, the required schedule $\theta$ contains in set $\mathrm{\Omega }\left(N,t\right)$ .

According to Lemma 1.3, all schedules of the set $\mathrm{\Omega }\left(N,t\right)$ start with $\omega \left(N,t\right)$ . Let us take ${\theta }_0=\omega \left(N,t\right)$ .

After $k,k\ge 0$ main steps of the algorithm 1.2 we got the schedule ${\theta }_k$ and $N^{\prime }=N\backslash \left\{{\theta }_k\right\}$ , $t^{\prime }=C_{\max }\left({\theta }_k\right)$ . Let us assume that there is an optimal by the criterion of maximum completion time ( $C_{\max }$ ) schedule $\theta$ starting with ${\theta }_k$ . According to Theorem 1.2, there is an optimal extension of the schedule ${\theta }_k$ among the schedules from the set $\mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ .

Let ${\theta }_{k+1}=\left({\theta }_k,{\omega }^1\left(N^{\prime },t^{\prime }\right)\right)$ , that is, $L_{\max }\left({\theta }_{k+1}\right)\le y$ . According to Theorem 1.3, for schedule ${\omega }^1$ , ${\omega }^1={\omega }^1\left(N^{\prime },t^{\prime }\right)$ , there is no artificial idle times of the machine and all schedules from the set $\mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ start with jobs of the set $\left\{{\omega }^1\left(N^{\prime },t^{\prime }\right)\right\}$ . Therefore, ${\omega }^1\left(N^{\prime },t^{\prime }\right)$ is the best by the criterion of $C_{\max }$ among all feasible by maximum lateness ( $L_{\max }$ ) extensions of the partial schedule ${\theta }_k$ .

If ${\theta }_{k+1}=\left({\theta }_k,{\omega }^2\left(N^{\prime },t^{\prime }\right)\right)$ , that is, $L_{\max }\left({\omega }^1,t^{\prime }\right)>y$ , and $L_{\max }\left({\omega }^2,t^{\prime }\right)\le y$ . All schedules of the set $\mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ start with either schedule ${\omega }^1\left(N^{\prime },t^{\prime }\right)$ or ${\omega }^2\left(N^{\prime },t^{\prime }\right)$ . As $L_{\max }\left({\omega }^1,t^{\prime }\right)>y$ , then the only suitable extension is ${\omega }^2\left(N^{\prime },t^{\prime }\right)$ .

Thus, at each main step of the algorithm, we choose the fastest continuation of the partial schedule ${\theta }_k$ among all those allowed by the maximum lateness. After no more than $n$ main steps of the algorithm, the required schedule is constructed.

Let us assume that after the $k+1$ steps of the algorithm $L_{\max }\left({\omega }^1,t^{\prime }\right)>y$ and $L_{\max }\left({\omega }^2,t^{\prime }\right)>y$ . If schedule $\theta$ could exist, that is, $\theta \ne \varnothing$ , then $\theta$ would start with ${\theta }_k$ . Then for any schedule $\pi \in \mathrm{\Pi }\left(N^{\prime },t^{\prime }\right)$ there would exist a schedule ${\pi }^{\prime }\in \mathrm{\Omega }\left(N^{\prime },t^{\prime }\right)$ such that $L_{\max }\left(\pi ,t^{\prime }\right)\ge L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\ge L_{\max }\left({\omega }^1,t^{\prime }\right)>y$ or $L_{\max }\left(\pi ,t^{\prime }\right)\ge L_{\max }\left({\pi }^{\prime },t^{\prime }\right)\ge L_{\max }\left({\omega }^2,t^{\prime }\right)>y$ . Therefore $\theta =\varnothing$ .

Repeating our proof as many times as the main step of algorithm 1.2 (no more than $n$ ), we come to the truth of the statement of the theorem.

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 $\mathrm{\Phi }\left(N,t\right)=\left\{{\pi }_1^{\prime },{\pi }_2^{\prime },\dots ,{\pi }_m^{\prime }\right\}$ , $m\le n$ , by criteria $C_{\max }$ and $L_{\max }$ according to conditions (5)–(6).

Schedule ${\pi }_m^{\prime }$ is a solution to problem $1\mid r_j\mid L_{\max }$ if (9) is true.

Algorithm 1.3 for constructing a set of Pareto schedules by criteria $C_{\max }$ and $L_{\max }$ .

1: Initial step. $Y≔+\infty$ , ${\pi }^{\ast }≔\omega \left(N,t\right)$ , $\mathrm{\Phi }≔\varnothing$ , $m≔0$ , $N^{\prime }≔N\backslash \left\{{\pi }^{\ast }\right\}$ and $t^{\prime }≔C_{\max }\left({\pi }^{\ast }\right)$ .

2: if $N^{\prime }=\varnothing$ then

3: $\mathrm{\Phi }≔\mathrm{\Phi }\cup \left({\pi }^{\ast }\right),m≔1$ and the algorithm stops.

4: end if

5: Main step.

6: if $L_{\max }\left({\omega }^1,t^{\prime }\right)\le L_{\max }\left({\pi }^{\ast }\right)$ then

7: ${\pi }^{\ast }≔\left({\pi }^{\ast },{\omega }^1\right)$ , where ${\omega }^1={\omega }^1\left(N^{\prime },t^{\prime }\right)$ and go to the next step;

8: end if

9: if $L_{\max }\left({\omega }^1,t^{\prime }\right)>L_{\max }\left({\pi }^{\ast }\right)$ then

10: if $L_{\max }\left({\omega }^1,t^{\prime }\right)<y$ then

11: find $\theta =\theta \left(N^{\prime },t^{\prime },y^{\prime }\right)$ using algorithm 1.2, where $y^{\prime }=L_{\max }\left({\omega }^1,t^{\prime }\right)$ ;

12: if $\theta =\varnothing$ then

13: ${\pi }^{\ast }≔\left({\pi }^{\ast },{\omega }^1\right)$ and go to the next step;

14: else

15: ${\pi }^{\prime }≔\left({\pi }^{\ast },\theta \right)$

16: if $C_{\max }\left({\pi }_m^{\prime }\right)<C_{\max }\left({\pi }^{\prime }\right)$ then

17: $m≔m+1$ , ${\pi }_m^{\prime }≔{\pi }^{\prime }$ , $\mathrm{\Phi }≔\mathrm{\Phi }\cup \left({\pi }_m^{\prime }\right)$ , $y=L_{\max }\left({\pi }_m^{\prime }\right)$ ;

18: else

19: ${\pi }_m^{\prime }={\pi }^{\prime }$ and go to next step;

20: end if

21: end if

22: if $L_{\max }\left({\omega }^1,t^{\prime }\right)\ge y$ then

23: find ${\omega }^2={\omega }^2\left(N^{\prime },t^{\prime }\right)$ ;

24: if $L_{\max }\left({\omega }^2,t^{\prime }\right)<y$ then

25: ${\pi }^{\ast }=\left({\pi }^{\ast },{\omega }^2\right)$ and go to the next step;

26: else

27: ${\pi }^{\ast }={\pi }_m\text{'}$ and the algorithm stops.

28: end if

29: end if

30: end if

31: end if

As a result of the algorithm 1.3, a set of schedules $\mathrm{\Phi }\left(N,t\right)$ is constructed, for the set of jobs $N$ starting at time $t$ , for which inequality $1\le \mid \mathrm{\Phi }\left(N,t\right)\mid \le n$ true. We should note that the set $\mathrm{\Phi }\left(N,t\right)$ for Example 1.1 consists of two schedules, although set $\mathrm{\Omega }\left(N,t\right)$ consists of $2^{\frac{n}{2}}$ schedules:

$${\pi }_{1^{\prime }}=\left(\mathrm{1,2,3,4},\dots ,n-1,n\right),$$ E31

$${\pi }_{2^{\prime }}=\left(\mathrm{2,1,4,3},\dots ,n,n-1\right).$$ E32

Lemma 1.5 The complexity of the algorithm 1.3 does not exceed $O\left(n^{3}logn\right)$ operations.

Proof: At each iteration of the main step of the algorithm 1.3 we find schedules ${\omega }^1$ and, if necessary, ${\omega }^2$ , which requires $O\left(nlogn\right)$ operations according to lemma 1.2, and also schedule $\theta$ in $O\left(n^{2}logn\right)$ operations. As ${\omega }^1$ and ${\omega }^2$ consist of at least one job, then at any iteration of the algorithm one or more jobs are added to the schedule ${\pi }^{\ast }$ , or the algorithm stops at last schedule ${\pi }^{\prime }$ . Therefore, the total number of iterations is at most $n$ . Thus, it takes no more than $O\left(n^{3}logn\right)$ operations to execute algorithm 1.3.

Theorem 1.5 If case if (9) is true for each job of the set $N$ , then the schedule ${\pi }^{\ast }$ , constructed by algorithm 1.3, is optimal according to the criterion $L_{\max }$ . Moreover, for any schedule $\pi \in \mathrm{\Pi }\left(N\right)$ there exists a schedule ${\pi }^{\prime }\in \mathrm{\Phi }\left(N,t\right)$ such that $L_{\max }\left({\pi }^{\prime }\right)\le L_{\max }\left(\pi \right)$ and $C_{\max }\left({\pi }^{\prime }\right)\le C_{\max }\left(\pi \right)$ .

Proof: According to Theorem 1.2, there exists an optimal (by $L_{\max }$ ) schedule from set $\mathrm{\Omega }\left(N,t\right)$ . According to Lemma 1.3, all schedules of the set $\mathrm{\Omega }\left(N,t\right)$ start with a partial schedule $\omega \left(N,t\right)$ .

Let ${\pi }_0=\omega \left(N,t\right)$ . After $k$ , $k\ge 0$ , main steps of algorithm 1.3 we have a partial schedule ${\pi }_k$ . Suppose there is an optimal (by $L_{\max }$ ) schedule starting with ${\pi }_k$ . We denote $N^{\prime }=N\backslash \left\{{\pi }_k\right\}$ and $t^{\prime }=C_{\max }\left({\pi }_k\right)$ .

If ${\pi }_{k+1}=\left({\pi }_k,{\omega }^1\right)$ , where ${\omega }^1={\omega }^1\left(N^{\prime }{t}^{\prime }\right)$ , then either $L_{\max }\left({\omega }^1,t^{\prime }\right)\le L_{\max }\left({\pi }_k\right)$ , or $L_{\max }\left({\pi }_k\right)<L_{\max }\left({\omega }^1,t^{\prime }\right)<y$ , that is, current value of the criterion and the maximum lateness will “appear” on next steps of the algorithm 1.3. That is, $\theta \left(N^{\prime },t^{\prime },y^{\prime }\right)=\varnothing$ , where $y^{\prime }=L_{\max }\left({\omega }^1,t^{\prime }\right)$ . If $\theta =\theta \left(N^{\prime },t^{\prime },y^{\prime }\right)\ne \varnothing$ , then we improve the current maximum lateness value: ${\pi }^{\prime }=\left({\pi }_k,\theta \right)$ and $y=L_{\max }\left({\pi }^{\prime }\right)=L_{\max }\left({\omega }^1,t^{\prime }\right)$ . The schedule ${\pi }^{\prime }$ is added to the set of schedules $\mathrm{\Phi }\left(N,t\right)$ . Moreover, according to Theorem 1.3 jobs of set $\left\{{\omega }^1\right\}$ precede jobs of set $N^{\prime }\backslash \left\{{\omega }^1\right\}$ . Thus, the schedule ${\omega }^1$ alert(without artificial idle times of the machine) would be the best continuation for ${\pi }_k$ .

If ${\pi }_{k+1}=\left({\pi }_k,{\omega }^2\right)$ , where ${\omega }^2={\omega }^2\left(N^{\prime },t^{\prime }\right)$ , that is, according to algorithm 1.3 $L_{\max }\left({\omega }^2,t^{\prime }\right)<L_{\max }\left({\pi }^{\prime }\right)\le L_{\max }\left({\omega }^1,t^{\prime }\right)$ . In this case the continuation ${\omega }^2$ is “better” than ${\omega }^1$ . Hence, the partial schedule ${\pi }_{k+1}$ is a part of some optimal schedule.

Repeating our proof no more than $n$ times, we come to optimality (for $L_{\max }$ ) of the schedule ${\pi }^{\ast }$ .

The set of schedules $\mathrm{\Phi }\left(N,t\right)$ contains at most $n$ schedules, since at each main step of the algorithm in the set $\mathrm{\Phi }\left(N,t\right)$ at most one schedule is “added,” and this step is executed no more than $n$ times.

Suppose there is a schedule $\pi \in \mathrm{\Pi }\left(N\right),\pi \notin \mathrm{\Phi }\left(N,t\right),$ such that either $C_{\max }\left(\pi \right)\le C_{\max }\left({\pi }^{\prime }\right)$ and $L_{\max }\left(\pi \right)\ge L_{\max }\left({\pi }^{\prime }\right)$ , or $C_{\max }\left(\pi \right)\ge C_{\max }\left({\pi }^{\prime }\right)$ and $L_{\max }\left(\pi \right)\le L_{\max }\left({\pi }^{\prime }\right)$ for each schedule ${\pi }^{\prime }\in \mathrm{\Phi }\left(N,t\right)$ . Moreover, in each pair of inequalities at least one inequality is strict. According to Theorem 1.1, there is a schedule ${{\pi }^{\prime }}^{\prime }\in \mathrm{\Omega }\left(N,t\right)$ such that $L_{\max }\left({{\pi }^{\prime }}^{\prime }\right)\le L_{\max }\left(\pi \right)$ and $C_{\max }\left({{\pi }^{\prime }}^{\prime }\right)\le C_{\max }\left(\pi \right)$ . If ${{\pi }^{\prime }}^{\prime }\in \mathrm{\Phi }\left(N,t\right)$ . Thus, it becomes obvious that our assumption is not correct. Let ${{\pi }^{\prime }}^{\prime }\in \mathrm{\Omega }\left(N,t\right)\backslash \mathrm{\Phi }\left(N,t\right)$ . Algorithm 1.3 shows that the structure of each schedule ${\pi }^{\prime }\in \mathrm{\Phi }\left(N,t\right)$ can be represented as a sequence of partial schedules ${\pi }^{\prime }=\left({\omega }_0^{\prime },{\omega }_1^{\prime },{\omega }_2^{\prime },\dots ,{\omega }_{k^{\prime }}^{\prime }\right),$ where ${\omega }_0^{\prime }=\omega \left(N,t\right)$ , and ${\omega }_i^{\prime }$ is either ${\omega }^1\left(N_i^{\prime },C_i^{\prime }\right),$ or ${\omega }^2\left(N_i^{\prime },C_i^{\prime }\right),$ and $N_i^{\prime }=N\backslash \left\{{\omega }_0^{\prime },\dots ,{\omega }_{i-1}^{\prime }\right\}$ , $C_i^{\prime }=C_{\max }\left(\left({\omega }_0^{\prime },\dots ,{\omega }_{i-1}^{\prime }\right),t\right),i=1,2,\dots ,k^{\prime }$ . The schedule ${{\pi }^{\prime }}^{\prime }$ has the same structure according to the definition of the set $\mathrm{\Omega }\left(N,t\right)$ , that is, $\pi =\left({{\omega }^{\prime }}_0^{\prime },{{\omega }^{\prime }}_1^{\prime },{{\omega }^{\prime }}_2^{\prime },\dots ,{{\omega }^{\prime }}_{{k^{\prime }}^{\prime }}^{\prime }\right),$ possibly ${k^{\prime }}^{\prime }\ne k^{\prime },$ where ${{\omega }^{\prime }}_0^{\prime }={\omega }_0^{\prime }=\omega \left(N,t\right),{{\omega }^{\prime }}_i^{\prime }$ is equal to either ${\omega }^1\left({N^{\prime }}_i^{\prime },{C^{\prime }}_i^{\prime }\right),$ or ${\omega }^2\left({N^{\prime }}_i^{\prime },{C^{\prime }}_i^{\prime }\right),$ a ${N^{\prime }}_i^{\prime }=N\backslash \left\{{{\omega }^{\prime }}_0^{\prime },\dots ,{{\omega }^{\prime }}_{i-1}^{\prime }\right\}$ , ${C^{\prime }}_i^{\prime }=C_{\max }\left(\left({{\omega }^{\prime }}_0^{\prime },\dots ,{{\omega }^{\prime }}_{i-1}^{\prime }\right),t\right),i=1,2,\dots ,{k^{\prime }}^{\prime }$ .

We assume that the first $k$ partial schedules ${{\pi }^{\prime }}^{\prime }$ and ${\pi }^{\prime }$ are equal, that is, ${{\omega }^{\prime }}_i^{\prime }={\omega }_i^{\prime }={\omega }_i,i=0,1,\dots ,k-1,{{\omega }^{\prime }}_k^{\prime }\ne {\omega }_k^{\prime }.$ If $y=L_{\max }\left({\omega }_0,\dots ,{\omega }_{k-1}\right),$ let us construct a schedule $\theta$ using algorithm 1.2, $\theta =\theta \left(N_k,C_k,y\right).$ If $\theta =\varnothing ,$ then according to algorithm 1.3, ${\omega }_k^{\prime }={\omega }^1\left(N_k,C_k\right)$ . Because of ${{\omega }^{\prime }}_k^{\prime }\ne {\omega }_k^{\prime },$ schedule ${{\omega }^{\prime }}_k^{\prime }={\omega }^2\left(N_k,C_k\right).$ Objective function value ( $L_{\max }$ ) can be reached on a job from the set $N_k,$ since $\theta =\varnothing .$ The whole structure of the algorithm 1.3 construct in such a way that up to the “critical” job (according to $L_{\max }$ ) order the jobs as “tightly” as possible, therefore we complete the schedule ${\omega }^1$ , after which $C_{\max }\left({\pi }^{\prime }\right)\le C_{\max }\left({{\pi }^{\prime }}^{\prime }\right)$ and $L_{\max }\left({\pi }^{\prime }\right)\le L_{\max }\left({{\pi }^{\prime }}^{\prime }\right)$ . If $\theta \ne \varnothing ,$ then for schedules ${\pi }^{\prime }$ and ${{\pi }^{\prime }}^{\prime }$ $C_{\max }\left({\pi }^{\prime }\right)\le C_{\max }\left({{\pi }^{\prime }}^{\prime }\right)$ and $L_{\max }\left({\pi }^{\prime }\right)=L_{\max }\left({{\pi }^{\prime }}^{\prime }\right)$ . Thus, for any schedule ${{\pi }^{\prime }}^{\prime }\in \mathrm{\Omega }\left(N,t\right)\backslash \mathrm{\Phi }\left(N,t\right)$ exists schedule ${\pi }^{\prime }\in \mathrm{\Phi }\left(N,t\right)$ such that $C_{\max }\left({\pi }^{\prime }\right)\le C_{\max }\left({{\pi }^{\prime }}^{\prime }\right)$ and $L_{\max }\left({\pi }^{\prime }\right)\le L_{\max }\left({{\pi }^{\prime }}^{\prime }\right)$ . Hence, for any schedule $\pi \in \mathrm{\Pi }\left(N\right)$ there exists schedule ${\pi }^{\prime }\in \mathrm{\Phi }\left(N,t\right)$ such that $L_{\max }\left({\pi }^{\prime }\right)\le L_{\max }\left(\pi \right)$ and $C_{\max }\left({\pi }^{\prime }\right)\le C_{\max }\left(\pi \right)$ . The theorem is proved.

Figure 1 schematically shows the considered schedule.

Figure 1.

The set of Pareto-optimal schedules.

For the set of schedules $\mathrm{\Phi }\left(N,t\right)=\left\{{\pi }_1^{\prime },{\pi }_2^{\prime },\dots ,{\pi }_m^{\prime }\right\}$ , $m\le n$ , we conditions (5)–(6) are true.

The schedule ${\pi }_1^{\prime }$ is optimal in terms of speed ( $C_{\max }$ ), and ${\pi }_m^{\prime }$ is optimal in terms of the maximum lateness (by $L_{\max }$ ) if the jobs of the set $N$ satisfy the conditions (9).

4. Conclusions

Single machine scheduling problem with given release dates and two objective functions is considered in this chapter, which is $\mathit{NP}$ -hard in the strong sense. A number of new polynomially and pseudo-polynomially solvable subcases of the problem were found. For a case when

$$d_1\le \dots \le d_n,d_1-r_1-p_1\ge \dots \ge d_n-r_n-p_n,$$ E33

an algorithm for constructing a Pareto-optimal set of schedules by criteria $C_{\max }$ and $L_{\max }$ is developed. It is proved that the complexity of the algorithm does not exceed $O\left(n^{3}logn\right)$ operations.

An experimental study of the algorithm showed that it can be used to construct optimal schedules (by $L_{\max }$ ) even for instances not satisfying the conditions (33).

Acknowledgments

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