Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines

Abstract

In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.

1 Introduction

Finding optimal schedules is the primary goal of scheduling and therefore the main stream of research often deals with sufficient conditions of optimality that play the key role in the design of solution algorithms and in proving their correctness. The new trend is the study of the structural properties of optimal solutions. The practical aspects of this research direction are discussed in the recent paper by Lin and Wang (2007) which presents necessary and sufficient conditions of optimality for some classes of scheduling problems. As stated in Lin and Wang (2007), the optimality conditions may be useful for

• developing efficient algorithms that verify whether a given solution is optimal (such algorithms may be faster than the algorithms which construct optimal solutions);

• finding several (or all) optimal solutions;

• multi-objective hierarchical optimization (finding a characterization of all optimal solutions for the primary criterion and then optimizing the other one);

• developing new solution algorithms.

The most recent application of optimality conditions is related to solving inverse scheduling problems, which has become an important research area (see surveys Ahuja and Orlin 2001; Heuberger 2004). In an inverse scheduling problem, there is given a target solution, which may be non-optimal for initial values of problem parameters. The objective is to adjust problem parameters (e.g., to modify job weights) to make the target solution optimal. A typical approach for solving inverse problems is based on necessary and sufficient conditions of optimality which are used to produce a mathematical programming formulation of the inverse problem.

In this paper, we study a range of scheduling models with unit time operations. Given are m identical parallel machines and a set $J=\{1,2,\ldots ,n\}$ of n jobs with processing times $p_{j}=1, j\in J$. Each job j has to be processed by one machine; it cannot start before some integer time $r_{j}\ge 0$ and it is desirable to complete it before a given due date $d_{j}$. A schedule $\mathbf {C}=(C_{j})_{j=1}^{n}$ assigns to each job j a finishing time $C_{j}$ (or starting time $S_{j}=C_{j}-1$). $\mathbf {C}$ is feasible if $r_{j}\le C_{j}-1$ for each job j and the number of jobs processed simultaneously at any time is at most m. We assume that all data are integer. The objective is to find a feasible schedule $\mathbf {C}$ which minimizes a given non-decreasing function $F\left( \mathbf {C,w}\right)$ depending on job completion times and job weights $\mathbf {w}=(w_{j})_{j=1}^{n}$, which are assumed to be positive. The objective functions considered in this paper are

(a):

total weighted completion time $\sum _{j=1}^{n}w_{j}C_{j}$;

(b):

the weighted number of late jobs $\sum w_{j}U_{j}\left( C_{j}\right)$, where $U_{j}\left( C_{j}\right)$ is the unit penalty for completing job j after its due date $d_{j}, U_{j}\left( C_{j}\right) =1$ if $C_{j}>d_{j}$ and $U_{j}\left( C_{j}\right) =0$, otherwise;

(c):

the weighted tardiness $\sum w_{j}T_{j}\left( C_{j}\right)$, where $T_{j}\left( C_{j}\right) =\max \{C_{j}-d_{j}, 0\}$ is the tardiness of job j.

The first function is strictly increasing while the last two functions are non-decreasing. In the last two cases we classify all jobs as early or late. Early jobs satisfy condition $C_{j}\le d_{j}$ and they incur a zero cost.

Using standard three field notation, the scheduling problems we consider are denoted as $P|r_{j},p_{j}=1|F\left( \mathbf {C,w}\right)$, where the first field represents identical parallel machines, the second field specifies job requirements and the third field is the objective function of type (a), (b) or (c). We replace P by 1 in the first field if there is a single machine ($m=1$). We drop $r_{j}$ from the second field if all jobs are available simultaneously ($r_{j}=0$ for all $j\in J$) and drop $\mathbf {w}$ from the third field if all jobs have the same weight ($w_{j}=1$ for all $j\in J$).

Our primary objective is to produce the necessary and sufficient conditions of optimality for versions (a)-(c) of problem $P|r_{j},p_{j}=1|F\left( \mathbf {C,w}\right)$. Our study complements the earlier results for the following problems: $1||L_{\max }$, $1||\sum w_{j}C_{j}$, $F2||C_{\max }$, $1||\sum U_{j}$ (Lin and Wang 2007), and $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$ (Dourado et al. 2009). Notice that in the first problem $L_{\max }$ denotes the maximum lateness objective function, $L_{\max }=\max _{j\in J}\{C_{j}-d_{j}\}$; in the third problem, F2 in the first field denotes the two-machine flow shop problem.

In this paper we study the problems with unit time jobs. We give a characterization of the block structure of optimal schedules (Sect. 2) and derive the necessary and sufficient conditions of optimality for the general problem $P|r_{j},p_{j}=1|F\left( {{\mathbf {C,w}}}\right)$. We show in Sect. 2.3 that verifying these conditions results in detecting negative cycles in a specially defined network $\overline{N}(\mathbf {C})$ of the transportation problem. The number of nodes of that network is $\nu =\left\lceil \frac{n}{m}\right\rceil$ and the network can be constructed in $O\left( m\nu ^{2}\right) =O\left( \frac{n^{2}}{m}\right)$ time.

In the subsequent sections, we explore the properties of network $\overline{N}(\mathbf {C})$ for the following problems:

• $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ (Sect. 3),

• $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$ (Sect. 4) and its special case $P|p_{j}=1|\sum w_{j}U_{j}$ (Sect. 5),

• $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$ (Sect. 6) and its special cases $P|r_{j},p_{j}=1|\sum T_{j}$ (Sect. 7) and $P|p_{j}=1|\sum T_{j}$ (Sect. 8).

Taking into account special features of the above problems, we derive stronger conditions than those known for a general transportation problem. For each problem we also give an insight into the underlying structure of the graph $\overline{N}(\mathbf {C})$ and specify the simplest types of cycles which are sufficient to consider in the optimality conditions: two-node cycles for problems $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ and $P|p_{j}=1|\sum T_{j}$, chain cycles for problems $P|p_{j}=1|\sum w_{j}U_{j}$ and $P|r_{j},p_{j}=1|\sum T_{j}$, spiral cycles for problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$ and for its unweighted case $P|r_{j},p_{j}=1|\sum U_{j}$, see Sect. 2.3 for the definitions of special cycles. Conclusions and possible directions for future research are presented in Sect. 9.

Notice that conditions we formulate for problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$ are different from the previously known, e.g., those presented in Dourado et al. (2009). In particular, we give a precise characterization of spiral cycles that should be examined in the underlying network. As the new conditions are more explicit and precise, they allow us to develop a fast algorithm for verifying optimality of a given solution (see Appendix 3).

Verifying the optimality of a given schedule $\mathbf {C}$ is one of the important application areas of our study. Instead of finding an optimal solution $\mathbf {C}^{*}$ by using a traditional scheduling algorithm and comparing $F\left( {\mathbf {C,w}}\right)$ and $F\left( \mathbf {C}^{*} ,\mathbf {w}\right)$, the necessary and sufficient conditions can be applied directly to $\mathbf {C}$ without constructing an optimal solution $\mathbf {C}^{*}$. We discuss the computational aspects of the optimality check for the problems under study at the end of the corresponding section, providing technical details in appendices. As we show, the new algorithms based on the necessary and sufficient conditions outperform those that find optimal schedules.

2 General structural properties of feasible schedules

In this section we discuss the general structural properties of feasible schedules. Depending on the objective function, it might be necessary to start jobs as early as possible if the function is strictly increasing, or the jobs can be postponed within some limits if the function is non-decreasing. For example, in any optimal schedule for problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ the maximum number of available jobs is allocated to each unit time interval $[t,t+1[$ starting with $t=\min _{j\in J}\{r_{j}\}$. In the case of problems $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$ and $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$, an optimal schedule can often be modified by reshuffling and postponing early jobs without changing their “early” status; the resulting schedule still has the same value of the objective function.

In order to develop a uniform approach, we propose in Sect. 2.1 the concept of an earliest start schedule, which provides a convenient framework for formulating the necessary and sufficient conditions of optimality. Then in Sect. 2.2 we demonstrate how an arbitrary schedule with postponed jobs can be modified into an earliest start schedule.

2.1 Earliest start schedules

For non-decreasing objective functions, we are particularly interested in so-called earliest start schedules which contain the maximum number of jobs in each unit time interval $[t,t+1[, t\ge \min _{j\in J}\{r_{j}\}$. For such a schedule $\mathbf {C}$, there exists a partition of the job set J into disjoint sets $B_{1},B_{2},\ldots ,B_{\kappa }$, called block sets, and a partition of the time line into corresponding block intervals $\mathcal {T} _{1},\mathcal {T}_{2},\ldots ,\mathcal {T}_{\kappa }$, where $\mathcal {T}_{i}$ consists of $l_i$ consecutive time slots $[t,t+1[$,

$$\begin{aligned} t\in \mathcal {T}_{i}=\left\{ t_{i},t_{i}+1,\ldots ,t_{i}+l_{i}-1\right\} \end{aligned}$$

associated with the block set $B_{i}$. The pair $\left( B_{i},\mathcal {T} _{i}\right)$ is a block of length $l_{i}$ if

(i):

its starting time $t_{i}$ is equal to a minimum release date among all jobs from $B_{i}, t_{i}=\min \{r_{j}|j\in B_{i}\}$;

(ii):

it includes all jobs j with $t_{i}\le r_{j}\le t_{i}+l_{i}-1$ and none of such jobs is included in any subsequent block;

(iii):

each time interval $[t,t+1[, t\in \mathcal {T}_{i}$, with the exception of the last one, contains exactly m jobs, while the last unit time interval contains at most m jobs.

The first condition implies that block $\left( B_{i},\mathcal {T}_{i}\right)$ starts at the earliest possible start time $t_{i}$. Moreover, all jobs j scheduled in $[t_{i},t_{i}+1[$ have $r_{j}=t_{i}$. The second condition is the separating rule for two consecutive blocks. It ensures that the jobs that follow $\left( B_{i},\mathcal {T}_{i}\right)$ cannot be moved to time intervals $\mathcal {T}_{i}$. The third condition characterizes the structure of a block; it states that each unit time slot should be saturated.

The blocks are numbered in the order they appear in the schedule: $t_{1} <t_{2}<\cdots <t_{\kappa }$. For a block set $B_{i}$, its length is $l_{i}=\left\lceil \frac{\left| B_{i}\right| }{m}\right\rceil$. An earliest start schedule can be constructed by Algorithm ‘Calculate Blocks’ presented in Appendix 1. At the beginning the algorithm considers the time slot $[ t,t+1[$ defined by the minimal release time t. If the number z of jobs which can be scheduled in this time slot is at most m, then these jobs define the first block $\left( B_{i},\mathcal {T}_{i}\right) , i=1$, with $\mathcal {T}_{1}=\{t\}$. Otherwise the block contains more than m jobs and it is obtained by considering the subsequent time intervals $[ t,t+1[$ one by one, adding each time to the block set $B_{i}$ those jobs which are released at time t and assigning the maximum number of jobs to $[t,t+1[$. Whenever the number of available jobs is m or less, the block $\left( B_{i},\mathcal {T}_{i}\right)$ is finalized and the new block is started. In addition to the schedule, the algorithm also calculates a function $h:\mathcal {T}\rightarrow \left\{ 1,\ldots ,m\right\}$, where $\mathcal {T}$ is the union of all sets $\mathcal {T}_{i}$ and h(t) is the number of jobs scheduled in $[t,t+1[$ for each $t\in \mathcal {T}$. The algorithm can be implemented in $O(n\log n)$ time by sorting the jobs in non-decreasing order of their release dates in the beginning. Clearly schedule $\mathbf {C}$ constructed by Algorithm ‘Calculate Blocks’ is an earliest start schedule since the number of jobs h(t) scheduled at time t is equal to m except for, probably, the last time interval of a block, which may contain less jobs.

The following example illustrates the algorithm.

Example 1

Consider an instance of the problem $P|r_{j},p_{j}=1|F\left( \mathbf {C},\mathbf {w}\right)$ with $m=2$ machines, $n=14$ jobs and a non-decreasing objective function F of job completion times. For the release dates presented in the table

j	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$r_{j}$	0	0	1	1	0	4	4	4	5	6	7	7	7	8

the Algorithm ‘Calculate Blocks’ finds the block sets $B_{1}=\left\{ 1,2,3,4,5\right\} , B_{2}=\left\{ 6,7,8,9\right\} , B_{3}=\left\{ 10\right\} , B_{4}=\left\{ 11,12,13,14\right\}$ and their starting times $t_{1}=0, t_{2}=4, t_{3}=6, t_{4}=7$. The corresponding sets $\mathcal {T}_{j}$ are $\mathcal {T}_{1}=\left\{ 0,1,2\right\} , \mathcal {T}_{2}=\left\{ 4,5\right\} , \mathcal {T} _{3}=\left\{ 6\right\} , \mathcal {T}_{4}=\left\{ 7,8\right\}$ and the number of jobs h(t) scheduled in $[ t,t+1[$ is

t	0	1	2	3	4	5	6	7	8
$h\left( t\right)$	2	2	1	$-$	2	2	1	2	2

A feasible earliest start schedule $\mathbf {C}$ with block sets $B_{1},B_{2},B_{3}$ and $B_{4}$ is shown in Fig. 1. The jobs which start exactly at their release dates are dashed; the remaining jobs start after their release dates.

Fig. 1

The Gantt chart of schedule $\mathbf {C}$ found by Algorithm ‘Calculate Blocks’

If a schedule $\mathbf {C}$ is given by a list of unit time intervals and a list of jobs allocated to them, then conditions (i)–(iii) can be verified for all time slots in $O\left( n\right)$ time by scanning the time slots of $\mathbf {C}$ three times.

In the first scan, the algorithm identifies time-values $\tau _{1},\tau _{2},\ldots ,\tau _{k}$ with the property: all jobs that start at $\tau _{u}, 1\le u\le k$, have their release times equal to $\tau _{u}$. Clearly, the identified $\tau$ values satisfy property (i) of the block definition, and therefore they get a label of a ‘t-candidate.’

In the second scan, the algorithm removes from the list of ‘t-candidates’ those values which do not satisfy property (ii): a ‘t-candidate’ $\tau _{u}$ cannot define the starting time of a block if there is a job j starting after $\tau _{u}$ ($S_{j}>\tau _{u}$) which is related to an earlier block ($r_{j}<\tau _{u}$). To check condition (ii) efficiently, the ‘t-candidates’ are scanned right to left updating $\rho$ accordingly.

The third scan is performed to verify property (iii) for the remaining ‘t-candidates.’

The formal description of this approach is presented in Appendix 1 as Algorithm ‘Earliest Start Schedule Verification.’ Its time complexity is O(n): there are no more than n unit time slots and they are scanned three times. The first two scans each consider n values of $r_{j}$; the third scan counts the number of jobs assigned to each time slot, which total number is n. Notice that as a by-product, the algorithm returns the t values, which define the decomposition of an earliest start schedule into the blocks.

2.2 Transforming an arbitrary schedule into an earliest start schedule

In this section we show that if a given schedule $\mathbf {C}$ for problem $P|r_{j},p_{j}=1|F$ does not belong to the class of earliest start schedules, it can be transformed into an earliest start schedule $\mathbf {C}^{\prime }$ without increasing any of the completion times:

$$\begin{aligned} C_{j}^{\prime }\le C_{j}\text { for all }j\in J. \end{aligned}$$

(1)

This can be achieved as follows. Algorithm ‘Calculate Blocks’ is applied first in order to define the structure of the earliest start schedule, namely the time intervals $\mathcal {T}$ and the number of jobs allocated to them $h(t), t\in \mathcal {T}$. Time intervals $[t,t+1[, t\in \mathcal {T}$, are considered one by one, starting with the earliest one. All jobs allocated in the original schedule to those time intervals are kept. If their number is less than h(t), the required number of additional jobs is moved from later time intervals to $[t,t+1[$; the preference is given to the jobs with the smallest release dates. The formal description of such an algorithm (entitled as ‘Left Shift$\left( \mathbf {C}\right)$’) and its analysis are presented in Appendix 1. We also discuss implementation details which result in the $O(n\log n)$ time complexity.

The following proposition establishes a link between a given optimal schedule and the earliest start optimal schedule.

Proposition 1

A schedule $\mathbf {C}$ is optimal for problem $P|r_{j},p_{j}=1|F\left( \mathbf {C},\mathbf {w}\right)$ with a non-decreasing objective function F, if and only if it can be transformed by Algorithm ‘Left Shift $\left( \mathbf {C}\right)$’ into an optimal earliest start schedule $\mathbf {C}^{\prime }=\left( C_{1}^{\prime } ,\ldots ,C_{n}^{\prime }\right)$ without changing the value of the objective function.

Proof

Due to the properties of Algorithm ‘Left Shift $\left( \mathbf {C}\right)$,’ schedules $\mathbf {C}$ and $\mathbf {C}^{\prime }$ satisfy inequalities (1). This implies that for a non-decreasing objective function F,

$$\begin{aligned} F\left( \mathbf {C}^{\prime },\mathbf {w}\right) \le F\left( \mathbf {C} ,\mathbf {w}\right) . \end{aligned}$$

(2)

If $\mathbf {C}$ is optimal, then condition (2) should hold as equality since a strict inequality contradicts optimality of $\mathbf {C}$. On the other hand, if $\mathbf {C}$ can be transformed into an optimal earliest start schedule $\mathbf {C}^{\prime }$ without changing the objective function value, then clearly $\mathbf {C}$ must be optimal. $\square$

Due to the described relationship between an arbitrary schedule $\mathbf {C}$ and an earliest start schedule $\mathbf {C}^{\prime }$, in the subsequent sections we deal with earliest start schedules only. The optimality conditions which we formulate can be applied to each block separately, since no job from a block can be moved to a previous block.

Notice that if a given schedule does not belong to the class of earliest start schedules, then one can first apply Algorithm ‘Left Shift $\left( \mathbf {C}\right)$’ checking condition (2) for the resulting schedule $\mathbf {C}^{\prime }$. If $F\left( \mathbf {C}^{\prime },\mathbf {w}\right) <F\left( \mathbf {C},\mathbf {w}\right)$, then schedule $\mathbf {C}$ cannot be optimal; if $F\left( \mathbf {C}^{\prime } ,\mathbf {w}\right) =F\left( \mathbf {C},\mathbf {w}\right)$ then one needs to verify the optimality of the earliest start schedule $\mathbf {C}^{\prime }$ applying the necessary and sufficient conditions to it.

2.3 Earliest start schedule and associated compressed network

Consider problem $P|r_{j},p_{j}=1|F\left( \mathbf {C,w}\right)$ with a separable objective function $F=\sum w_{j}f_{j}(C_{j})$, where each function $f_{j}(C_{j})$ is non-decreasing. For a given earliest start schedule $\mathbf {C}$ consisting of a single block, the total number of time intervals is

$$\begin{aligned} \nu =\left\lceil \frac{n}{m}\right\rceil , \end{aligned}$$

so that $\mathcal {T}=\{0,1,\ldots ,\nu -1\}$, and for each time $t\in \mathcal {T}$ there are exactly h(t) jobs allocated to $[t,t+1[$:

$$\begin{aligned} h(t)=\left\{ \begin{array} [c]{ll} m, &{} 0\le t\le \nu -2,\\ n-m\left( \nu -1\right) \le m, &{} t=\nu -1. \end{array} \right. \end{aligned}$$

It is well known that a scheduling problem with unit time jobs can be reformulated as a transportation problem. Any feasible schedule corresponds to a feasible flow in the associated network and the objective value of the schedule equals the cost of delivering the flow. This implies that the necessary and sufficient conditions of optimality of a given schedule are equivalent to non-existence of a negative cycle in the corresponding residual network.

Formally, the transportation problem is defined by network $N\left( \mathbf {C}\right) =\left( V,A(\mathbf {C}),\eta \right)$,

$$\begin{aligned} V&=\left\{ 1,\ldots ,n\right\} \cup \{I_{t}|t\in \mathcal {T}\},\\ A(\mathbf {C})&=\left\{ \left( j,I_{t}\right) ~|~j\text { is assigned or can be assigned to }I_{t}\right\} . \end{aligned}$$

Here, the vertex set V consists of job nodes $\left\{ 1,\ldots ,n\right\}$, each of which has a supply of 1, and interval nodes $\left\{ I_{t}~|~t\in \mathcal {T}\right\}$ with demand h(t). The arc set $A(\mathbf {C})$ consists of the arcs $\left( j,I_{t}\right)$ defined for each feasible allocation of job j to interval $[t,t+1[, t\ge r_{j}$. The cost of an arc $\left( j,I_{t}\right)$ represents the cost of allocating job j to time interval $[t,t+1[$:

$$\begin{aligned} \eta _{jt}=w_{j}\times f_{j}(t+1) \end{aligned}$$

and its capacity is 1. Depending on the type of the objective function,

$$\begin{aligned} \eta _{jt}=\left\{ \begin{array}{ll} w_{j}\times (t+1), &{}\quad \text {if }\quad F=\sum w_{j}C_{j},\\ w_{j}\times U_{j}\left( t+1\right) , &{}\quad \text {if }\quad F=\sum w_{j}U_{j},\\ w_{j}\times T_{j}\left( t+1\right) , &{}\quad \text {if }\quad F=\sum w_{j}T_{j}. \end{array} \right. \end{aligned}$$

For a given solution $\mathbf {C}$, a residual network $N^{r}\left( \mathbf {C}\right) =\left( V,A^{r}(\mathbf {C}),\xi \right)$ has the same vertex set V, while the arc set $A^{r}(\mathbf {C})$ and the costs $\xi$ are defined as follows:

$$\begin{aligned}&A^{r}(\mathbf {C}) =\left\{ \left( I_{t},j\right) ~|~j\text { is allocated in }\mathbf {C}\text { to }[t,t+1[\right\} \\&\cup \left\{ \left( j,I_{t}\right) ~|~j\text { is not allocated in }\mathbf {C}\text { to }[t,t+1[\text {, }t\ge r_{j}\right\} ;\\&\xi _{tj} =-w_{j}\times f_{j}(t+1)\text { for arcs }\left( I_{t},j\right) ,\\&\xi _{jt} =w_{j}\times f_{j}(t+1)\text { for arcs }\left( j,I_{t}\right) . \end{aligned}$$

Example 2

Consider problem $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$ with $m=2$ machines and $n=5$ jobs with release dates, due dates and weights presented in the table:

j	1	2	3	4	5
$r_{j}$	0	0	1	1	0
$d_{j}$	2	1	2	3	1
$w_{j}$	1	1	1	1	1

Observe that the release dates are the same as those of the first 5 jobs of Example 1 processed as one block. The transportation network $N(\mathbf {C})$ is shown in Fig. 2a and the residual network corresponding to the schedule given by the first block of Fig. 1 is presented in Fig. 2b. The numbers at the arcs indicate the arc costs.

Fig. 2

a Network $N\left( \mathbf {C}\right)$ for jobs $\{1,2,3,4,5\}$ of Example 2 and b residual network $N^{r}\left( \mathbf {C}\right)$ for the schedule given by block $B_{1}$ of Fig. 1

Reformulating the well-known network flow theorem (see, e.g., Ahuja et al. 1993) we conclude that an earliest start schedule $\mathbf {C}$ is optimal for problem $P|r_{j},p_{j}=1|\sum w_{j}f_{j}(C_{j})$ if and only if the corresponding residual network $N^{r}\left( \mathbf {C} \right) =\left( V,A^{r}(\mathbf {C}),\xi \right)$ constructed for each block of $\mathbf {C}$ contains no negative cycle.

A cycle in the residual network $N^{r}(\mathbf {C})$ is of the form $I_{t_{1}},j_{1},I_{t_{2}},j_{2}, \ldots ,I_{t_{\kappa }},j_{\kappa },I_{t_{1}}$. The arcs are alternating between an arc from an interval node $I_{t}$ to a job node j and from a job node to an interval node.

It is convenient to compress the residual network $N^{r}(\mathbf {C})$ into a network $\widetilde{N}(\mathbf {C})$ by eliminating the job nodes; this results in multiple arcs connecting the interval nodes. We denote the nodes in $\widetilde{N}(\mathbf {C})$ by $t\in \{0,1,\ldots ,\nu -1\}$. For any two nodes t and $t^{\prime }$ we have an arc from t to $t^{\prime }$ with length $\xi _{tj}+\xi _{jt^{\prime }}$, where $\xi _{tj}+\xi _{jt^{\prime }}$ is the change of the objective function $\sum w_{j}f_{j}(C_{j})$ when job j is moved from $[ t,t+1[$ to $[t^{\prime },t^{\prime }+1[$. Such an arc replaces the two alternating arcs $I_{t}\rightarrow j\rightarrow I_{t^{\prime }}$ in $N^{r}(\mathbf {C})$. It is important to notice that the length $\ell _{\left( t,t^{\prime }\right) }$ of the arc from t to $t^{\prime }$ depends not only on t and $t^{\prime }$, but on job j allocated in $\mathbf {C}$ to $[t,t+1[$. Since there are h(t) jobs allocated to each time interval, there are h(t) arcs $(t,t^{\prime })$ for $t^{\prime }>t$ since any job allocated to $[ t,t+1[$ can be moved to a later time slot $[t^{\prime },t^{\prime }+1[$. However, for $t^{\prime }<t$ there can be less than h(t) arcs since not every job allocated to $[t,t+1[$ can be moved to an earlier time slot $[ t^{\prime },t^{\prime }+1[$.

For the three objective functions we consider, the cost of the arc $(t,t^{\prime })$, associated with job j allocated to $[t,t+1[$, is given by

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=\left\{ \begin{array} [c]{ll} w_{j}\times (t^{\prime }-t), &{}\quad \text {if }\quad F=\sum w_{j}C_{j};\\ w_{j}\times \left( U_{j}\left( t^{\prime }+1\right) -U_{j}\left( t+1\right) \right) , &{}\quad \text {if }\quad F=\sum w_{j}U_{j};\\ w_{j}\times \left( T_{j}\left( t^{\prime }+1\right) -T_{j}\left( t+1\right) \right) , &{}\quad \text {if }\quad F=\sum w_{j}T_{j}. \end{array} \right. \end{aligned}$$

Fig. 3

Two compressed networks for Example 2: a $\widetilde{N}\left( \mathbf {C}\right)$ and b $\overline{N}\left( \mathbf {C}\right)$

Example 3

Consider again the instance from Example 2. The corresponding residual network is presented in Fig. 2b and it contains a negative cycle $I_{0},~1,~I_{1} ,~4,~I_{2},~5,~I_{0}$ (its arcs are in bold) of length $-w_{1}\max \left\{ 1-2,0\right\} +w_{1}\max \left\{ 2-2,0\right\} -w_{4}\max \left\{ 2-3,0\right\} +w_{4}\max \left\{ 3-3,0\right\} -w_{5}\max \left\{ 3-1,0\right\} +w_{5}\max \left\{ 1-1,0\right\} =-2w_{5}=-2$. This negative cycle characterizes that the series of the following moves leads to a schedule with a smaller value of $\sum w_{j}T_{j}$:

• moving job 1 from time interval [ 0, 1[ to time interval [1, 2[,

• moving job 4 from time interval [ 1, 2[ to time interval [2, 3[,

• moving job 5 from time interval [ 2, 3[ to time interval [0, 1[.

The compressed residual network is shown in Fig. 3a, and the corresponding negative cycle (marked by bold arcs) is 0, 1, 2, 0.

We distinguish between right and left arcs in $\widetilde{N}(\mathbf {C})$. Arc $(t,t^{\prime })$ is a left arc if it is directed from t to a vertex corresponding to an earlier time slot $t^{\prime }, t^{\prime }<t$; for a right arc $(t,t^{\prime }), t^{\prime }>t$.

Consider a pair of time-nodes t and $t^{\prime }$, corresponding to time intervals $[t,t+1[$ and $[t^{\prime },t^{\prime }+1[$. Since our aim is to detect negative cycles or to prove that none exists, we can compress network $\widetilde{N}(\mathbf {C})$ further by eliminating multiple arcs of larger costs. Instead of keeping multiple arcs $(t,t^{\prime })$ and multiple arcs $(t^{\prime },t)$, we can keep just one arc in each direction that has the smallest cost.

Denote the resulting network by $\overline{N}(\mathbf {C})$. For Example 2, the corresponding network $\overline{N} (\mathbf {C})$ is shown in Fig. 3b. Let $J_{t}$ be the set of jobs assigned in $\mathbf {C}$ to time interval $[t,t+1[$. Then the cost (or the length) of the right arc $(t,t^{\prime }), t<t^{\prime }$, originating from t is defined as

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=\min \limits _{j\in J_{t}}\left\{ w_{j}\times \left[ f_{j}\left( t^{\prime }+1\right) -f_{j}\left( t+1\right) \right] \right\} . \end{aligned}$$

In particular, for $F=\sum w_{j}C_{j}$

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=\min \limits _{j\in J_{t}}\left\{ w_{j}\right\} \times (t^{\prime }-t), \end{aligned}$$

(3)

for $F=\sum w_{j}U_{j}$

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }{=}\left\{ \begin{array}{ll} \min \limits _{j\in J_{t}}\left\{ w_{j}\right\} , &{} \text {if }\quad t+1\le d_{j}<t^{\prime }+1\text { for all }j\in J_{t}\text {,}\\ 0, &{} \text {otherwise;} \end{array} \right. \end{aligned}$$

(4)

for $F=\sum w_{j}T_{j}$

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=\min \limits _{j\in J_{t}}\left\{ w_{j}\times \left[ T_{j}\left( t^{\prime }+1\right) -T_{j}\left( t+1\right) \right] \right\} . \end{aligned}$$

Considering left arcs $(t,t^{\prime }), t>t^{\prime }$, originating from t, we need to take into account the release dates of the jobs from $J_{t}$ since not all of them can be moved to an earlier time slot $[t^{\prime },t^{\prime }+1[$. Let $J_{\left( t,t^{\prime }\right) }$ denote a subset of jobs from $J_{t}$, which can be re-allocated to $[t^{\prime },t^{\prime }+1[$ without violating their release dates:

$$\begin{aligned} J_{(t,t^{\prime })}=\left\{ j\in J_{t}|r_{j}\le t^{\prime }\right\} . \end{aligned}$$

Then the left arc $\left( t,t^{\prime }\right)$ exists if $J_{\left( t,t^{\prime }\right) }\ne \emptyset$ and its length is defined as

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=-\max \limits _{j\in J_{\left( t,t^{\prime }\right) }}\left\{ w_{j}\left[ f_{j}\left( t+1\right) -f_{j}\left( t^{\prime }+1\right) \right] \right\} . \end{aligned}$$

In particular, for $F=\sum w_{j}C_{j}$

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=-\max \limits _{j\in J_{\left( t,t^{\prime }\right) }}\left\{ w_{j}\right\} \times (t-t^{\prime }), \end{aligned}$$

(5)

for $F=\sum w_{j}U_{j}$

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=\left\{ \begin{array} [c]{ll} 0, &{}\quad \text {if }t^{\prime }+1>d_{j}\text { or }t+1\le d_{j}\\ &{}\quad \text {for all }j\in J_{\left( t,t^{\prime }\right) , }\\ -\max \nolimits _{\begin{array}{c} j\in J_{\left( t,t^{\prime }\right) },\\ t^{\prime }+1\le d_{j}<t+1 \end{array}}\left\{ w_{j}\right\} ,&\quad \text {otherwise;} \end{array} \right. \end{aligned}$$

for $F=\sum w_{j}T_{j}$

$$\begin{aligned} \ell _{\left( t,t^{\prime }\right) }=-\max \limits _{j\in J_{\left( t,t^{\prime }\right) }}\left\{ w_{j}\left[ T_{j}\left( t+1\right) -T_{j}\left( t^{\prime }+1\right) \right] \right\} . \end{aligned}$$

It is easy to make sure that if residual network $N^{r}\left( \mathbf {C} \right)$ and the corresponding compressed network $\overline{N} (\mathbf {C})$ contain a negative cycle with repeated node t, then the cycle can be decomposed into two cycles and at least one of them is negative. Clearly, it is sufficient to consider the cycles without repeated time-values. Thus the necessary and sufficient optimality conditions can be formulated as follows.

Theorem 1

A schedule $\mathbf {C}$ for a given instance of $P|r_{j},p_{j}=1|\sum w_{j}f_{j}(C_{j})$ is optimal if and only if

• 1. transforming $\mathbf {C}$ into an earliest start schedule does not change the objective value;

• 2. for each block of the resulting earliest start schedule, the corresponding compressed network $\overline{N}(\mathbf {C})$ contains no negative cycle.

We estimate the size of the compressed network $\overline{N}(\mathbf {C})$ and the time complexity of constructing it assuming that a given earliest start schedule $\mathbf {C}$ has n jobs assigned to m machines and it consists of a single block. The number of nodes of $\overline{N}(\mathbf {C})$ is $\nu =\left\lceil \frac{n}{m}\right\rceil$. Each pair of nodes t and $t^{\prime }$ are connected by at most two arcs $(t,t^{\prime })$ and $(t^{\prime },t)$, so that the total number of arcs is $O\left( \nu ^{2}\right)$. For each right arc $(t,t^{\prime })$, its cost can be found in O(m) time since $|J_{t}|\le m$, and for each left arc $(t,t^{\prime })$, its cost can also be found in O(m) time since $|J_{(t,t^{\prime })}|\le m$. Thus the overall time complexity of constructing $\overline{N}(\mathbf {C})$ is $O\left( m\nu ^{2}\right) =O\left( \frac{n^{2}}{m}\right)$.

In the subsequent sections we show that, depending on the type of the problem, Condition 2 of Theorem 1 can be reformulated so that instead of checking the non-negative condition for all possible cycles only special types of cycles can be considered, namely two-node cycles, chain cycles and spiral cycles. Each of these cycles has exactly one arc of negative length denoted by $(t,\tau )$; it originates in the right-most node t of the cycle and contains no more than one positive arc; all other arcs have zero lengths. If the cycle contains a positive arc, that arc has end-node t.

A two-node cycle consists of two arcs $(t,\tau )$ and $(\tau ,t)$, see Fig. 4.

Fig. 4

Two-node cycle

Fig. 5

Chain cycles: a right-chain cycle and b left-chain cycle

Fig. 6

Spiral cycle

Table 1 The simplest cycles which are sufficient to consider in optimality conditions

A chain cycle consists of an arc in one direction and a chain of arcs in the opposite direction. A right-chain cycle starts with the negative left arc $(t,\tau )$ and then proceeds with a chain R of right arcs from $\tau$ to t, see Fig. 5a. A left-chain cycle starts with the negative left arc $(t,\tau )$, proceeds then with a chain L of left arcs to the left-most node of the cycle and returns to the origin t via one right arc, see Fig. 5b.

A spiral cycle is defined as the one satisfying the following five properties.

Property 1: :

The cycle contains exactly one negative arc $(t,\tau )$, all other left arcs have zero length.

Property 2: :

No left arc, except for possibly $(t,\tau )$, spans over a node which appears in the remaining part of the cycle after that arc.

Property 3: :

No right arc spans over a node which appears in the remaining part of the cycle after that arc.

Property 4: :

The right-most node of the cycle is t.

Property 5: :

All right arcs have zero length except for the last right arc terminating in t which may be of positive length or of zero length.

An example of a spiral cycle is shown in Fig. 6. In general, a spiral cycle contains alternating left chains $L_{1}, L_{2}, \ldots , L_{s}$ and right chains $R_{1}, R_{2}, \ldots , R_{s}$: the negative left arc $(t,\tau )$ is followed by $L_{1}, R_{1}, L_{2}, R_{2}, \ldots , L_{s}, R_{s}$ terminating in t, see Fig. 6. $L_{1}$ is a left chain originating in $\tau$; the first arc of $R_{1}$ spans over all nodes of $L_{1}$; the first arc of $L_{2}$ spans over all nodes of $L_{1}\cup R_{1}$. For each $k=2,\ldots ,s$, the first arc of $L_{k}$ spans over all nodes of $L_{1}, R_{1}, L_{2}, R_{2}, \ldots , L_{k-1}, R_{k-1}$ and the first arc of $R_{k}$ spans over all nodes of $L_{1}, R_{1}, L_{2}, R_{2}$, ..., $L_{k-1}, R_{k-1}, L_{k}$. The last chain $R_{s}$ consists of right arcs terminating in the origin t.

Notice that a two-node cycle is a special case of a chain cycle, which in its turn is a special case of a spiral cycle.

The main outcomes of our study are summarized in Table 1, where we list the types of cycles that should be examined in a compressed residual network $\overline{N}(\mathbf {C})$, representing a one-block earliest start schedule. Notice that for problem $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$ and its special case $P|p_{j}=1|\sum w_{j}T_{j}$ there exist instances for which even the simplest negative cycles have several negative arcs so that they do not fall in any of the above three categories of cycles. We do not give a characterization of negative cycles for these two problems since the usage of such a result is likely to be very limited. For example, using those conditions in the optimality check would incur cycles with one negative arc, cycles with pairs of negative arcs and even more complex cycles with various combinations of negative arcs.

For all other problems and their special cases, we first prove the result establishing the type of a simplest negative cycle. Then we show that the result cannot be improved by providing an example that there exists an instance of the problem with only one negative cycle and it is of the type established in the corresponding theorem. Such instances are not needed for two-node cycles indeed.

In what follows we consider the three objective functions $\sum w_{j}C_{j}, \sum w_{j}U_{j}$ and $\sum T_{j}$ and prove the relevant statement about the type of the cycle for each problem. We then explore how the identified types of cycles can be used in order to speed up the optimality check.

3 Problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$

In this section we consider the problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ with the weighted completion time objective. We show that the optimality conditions for this problem can be simplified by limiting consideration to two-node cycles only. Moreover, the reduced network $\overline{N}(\mathbf {C})$ can be compressed further by eliminating transitive arcs, so that the resulting network $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ contains no more than $2\left( \nu -1\right)$ arcs; its left arcs form an out-tree and the right arcs form an in-tree. As a result, the optimality check problem can be solved in O(n) time, an improvement in comparison with the $O(n\log n)$ time algorithm for finding an optimal schedule.

Theorem 2

A compressed residual network $\overline{N}(\mathbf {C})$, representing a one-block earliest start schedule for a given instance of problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$, contains a negative cycle if and only if it contains a negative two-node cycle.

Proof

Clearly, the formulated condition is sufficient. In order to prove that it is also necessary, assume that there exists an instance of problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ such that all two-node cycles are non-negative while there exists a negative cycle with three or more nodes. Let this cycle additionally have the smallest number of nodes. We show that there exists a negative cycle with a smaller number of nodes.

Denote by $t_{1}$ the left-most node of the cycle. The cycle starts with a positive arc $(t_{1},t_{2})$, proceeds with a series of arcs, which we denote by $\alpha$, leading to node $t_{3}$ and terminates at the origin $t_{1}$ with a negative arc $(t_{3},t_{1})$. The length of the positive arc $(t_{1},t_{2})\$is $w_{j_{1}}(t_{2}-t_{1})$, where job $j_{1}$ is selected in accordance with (3) so that

$$\begin{aligned} w_{j_{1}}=\min \limits _{j\in J_{t_{1}}}\left\{ w_{j}\right\} ; \end{aligned}$$

the length of the negative arc $(t_{3},t_{1})$ is $-w_{j_{3}}(t_{3}-t_{1})$, where job $j_{3}$ is selected in accordance with (5) so that

$$\begin{aligned} w_{j_{3}}=\max \limits _{j\in J_{\left( t_{3},t_{1}\right) }}\left\{ w_{j}\right\} . \end{aligned}$$

(6)

Thus the length of the original cycle is

$$\begin{aligned} \ell =w_{j_{1}}(t_{2}-t_{1})+\ell _{\alpha }-w_{j_{3}}(t_{3}-t_{1} ), \end{aligned}$$

(7)

where $\ell _{\alpha }$ is the length of fragment $\alpha$.

First we derive an auxiliary inequality for $w_{j_{1}}$ and $w_{j_{3}}$. Due to the assumption, the cycle consisting of two arcs $\left( t_{3} ,t_{1}\right)$ and $(t_{1},t_{3})$ is non-negative. Since its length is $(-w_{j_{3}}+w_{j_{1}})(t_{3}-t_{1})$, we conclude that

$$\begin{aligned} -w_{j_{3}}+w_{j_{1}}\ge 0. \end{aligned}$$

(8)

Consider the following two cases, depending on the location of $t_{2}$ and $t_{3}$. If $t_{2}<t_{3}$, cycle $\left( \left( t_{1},t_{2}\right) ,\alpha ,\left( t_{3},t_{1}\right) \right)$ is of the form shown in Fig. 7a. Since there exists arc $\left( t_{3},t_{1}\right)$ in $\overline{N}(\mathbf {C})$, the set of jobs $J_{\left( t_{3},t_{1}\right) }$, which can be re-allocated from $[t_{3},t_{3}+1[$ to $[t_{1},t_{1}+1[$ is non-empty, and therefore the set $J_{\left( t_{3},t_{2}\right) }$ is also non-empty for $t_{2}>t_{1}$. Hence we can introduce the arc $\left( t_{3},t_{2}\right)$ and consider a cycle with less nodes, namely $\left( \alpha ,\left( t_{3},t_{2}\right) \right)$, see Fig.  7b. The length of $\left( t_{3},t_{2}\right)$ is associated with some job $j_{3}^{\prime }, w_{j_{3}^{\prime }}=\max \limits _{j\in J_{\left( t_{3} ,t_{2}\right) }}\left\{ w_{j}\right\}$, and due to $J_{\left( t_{3} ,t_{2}\right) }\supseteq J_{\left( t_{3},t_{1}\right) }$,

$$\begin{aligned} w_{j_{3}^{\prime }}\ge w_{j_{3}}. \end{aligned}$$

(9)

Fig. 7

Replacing negative cycle $\left( \left( t_{1},t_{2}\right) ,\alpha ,\left( t_{3},t_{1}\right) \right)$ by $\left( \alpha ,\left( t_{3},t_{2}\right) \right)$ if $t_{1}<t_{2}<t_{3}$

Comparing the length of the original cycle $\ell$ given by (7) with the length of the new cycle $\ell ^{\prime } =\ell _{\alpha }-w_{j_{3}^{\prime }}(t_{3}-t_{2})$ we conclude that if $\ell <0$, the new cycle is also negative:

$$\begin{aligned} \ell ^{\prime }-\ell&=\left[ \ell _{\alpha }-w_{j_{3}^{\prime }}(t_{3} -t_{2})\right] \\&\quad -\left[ w_{j_{1}}(t_{2}-t_{1})+\ell _{\alpha }-w_{j_{3}} (t_{3}-t_{1})\right] \\&\le -w_{j_{3}}(t_{3}-t_{2})-\left[ w_{j_{1} }(t_{2}-t_{1})-w_{j_{3}}(t_{3}-t_{1})\right] \\&=\left( w_{j_{3}}-w_{j_{1} }\right) (t_{2}-t_{1}) \le 0. \end{aligned}$$

In the above formula, the first inequality is due to (9), while the second inequality follows from (8). Thus we have detected a negative cycle with a less number of nodes which contradicts the assumption that the initial negative cycle has the smallest number of nodes.

If $t_{2}>t_{3}$, as shown in Fig. 8a, introduce the positive arc $\left( t_{3},t_{2}\right)$ and consider a cycle with less nodes, namely $\left( \left( t_{3},t_{2}\right) ,\alpha \right)$, see Fig.  8b. The length of $\left( t_{3},t_{2}\right)$ is associated with some job $j_{3}^{\prime \prime }, w_{j_{3}^{\prime \prime } }=\min \limits _{j\in J_{t_{3}}}\left\{ w_{j}\right\}$, see (3). Comparing the latter formula with (6) we conclude that

$$\begin{aligned} w_{j_{3}^{\prime \prime }}=\min \limits _{j\in J_{t_{3}}}\left\{ w_{j}\right\} \le \min \limits _{j\in J_{(t_{3},t_{1})}}\left\{ w_{j}\right\} \le \max _{j\in J_{(t_{3},t_{1})}}\left\{ w_{j}\right\} = w_{j_{3}} \end{aligned}$$

(10)

(notice that $J_{t_{3}}\supseteq J_{\left( t_{3},t_{1}\right) }$ and the last equality corresponds to (6)).

Denoting by $\ell ^{\prime \prime }$ the length of the cycle shown in Fig.  8b, we obtain

$$\begin{aligned} \ell ^{\prime \prime }-\ell= & {} \left[ w_{j_{3}^{\prime \prime }}\left( t_{2}-t_{3}\right) +\ell _{\alpha }\right] \\&-\left[ w_{j_{1}}(t_{2} -t_{1})+\ell _{\alpha }-w_{j_{3}}(t_{3}-t_{1})\right] \\\le & {} w_{j_{3}}\left( t_{2} -t_{3}\right) -\left[ w_{j_{1}}(t_{2}-t_{1})-w_{j_{3}}(t_{3}-t_{1})\right] \\= & {} \left( w_{j_{3}}-w_{j_{1}}\right) \left( t_{2}-t_{1}\right) \le 0, \end{aligned}$$

so that $\ell ^{\prime \prime }<0$ for $\ell <0$. In the above formula, the first inequality is due to (10), while the second inequality follows from (8). Again we have detected a negative cycle with a less number of nodes which contradicts the assumption that the initial negative cycle has the smallest number of nodes. $\square$

Fig. 8

Replacing negative cycle $\left( \left( t_{1},t_{2}\right) ,\alpha ,\left( t_{3},t_{1}\right) \right)$ by $\left( \left( t_{3},t_{2}\right) ,\alpha \right)$ if $t_{1}<t_{3}<t_{2}$

Notice that due to the definition of $\overline{N}(\mathbf {C})$, a right arc exists for any pair of nodes, while left arc $\left( t,\tau \right)$ exists only if $J_{\left( t,\tau \right) }\ne \emptyset$. Therefore in order to enumerate all two-node cycles one can consider left arcs one by one, complementing each left arc with its right arc counterpart. Moreover, we prove that transitive left arcs in $\overline{N}(\mathbf {C})$ are not needed.

Theorem 3

Consider network $\overline{N}_{\mathrm {TransRem} }(\mathbf {C})$ obtained from $\overline{N}(\mathbf {C})$ by removing transitive left arcs and removing all right arcs which do not have a left counterpart. Denote the set of left arcs in $\overline{N}_{\mathrm {TransRem}} (\mathbf {C})$ by $A_{\mathrm {left}}(\mathbf {C})$. Then $\overline{N}(\mathbf {C})$ does not contain a negative cycle if and only if inequality

$$\begin{aligned} \min \limits _{j\in J_{\tau }}\left\{ w_{j}\right\} \ge \max \limits _{j\in J_{\left( t,\tau \right) }}\left\{ w_{j}\right\} . \end{aligned}$$

(11)

is satisfied for each $(t,\tau )\in A_{\mathrm {left}}(\mathbf {C}), \tau <t$.

Proof

Necessity Clearly, relation (11) formulated for a left arc $(t,\tau )$ is an equivalent representation of the condition that the cycle defined by nodes t and $\tau$ is non–negative, see formulae (3) and (5).

Sufficiency To prove that conditions (11) defined for $(t,\tau )\in A_{\mathrm {left}}(\mathbf {C})$, are sufficient, consider $t_{1}<t_{2}<t_{3}$ assuming that the left arcs $\left( t_{2} ,t_{1}\right) , \left( t_{3},t_{2}\right)$ exist together with the transitive left arc $\left( t_{3},t_{1}\right)$. The associated positive arcs are $\left( t_{1},t_{2}\right) , \left( t_{2},t_{3}\right)$ and $\left( t_{1},t_{3}\right)$. We show that if (11) holds for the pair of nodes $t_{1},t_{2}$ and for the pair $t_{2},t_{3}$, then (11) also holds for the pair of nodes $t_{1},t_{3}$.

Indeed, conditions (11) for $t_{1},t_{2}$ and for $t_{2},t_{3}$ are of the form:

$$\begin{aligned} \min \limits _{j\in J_{t_{1}}}\left\{ w_{j}\right\}&\ge \max \limits _{j\in J_{\left( t_{2},t_{1}\right) }}\left\{ w_{j}\right\} ,\\ \min \limits _{j\in J_{t_{2}}}\left\{ w_{j}\right\}&\ge \max \limits _{j\in J_{\left( t_{3},t_{2}\right) }}\left\{ w_{j}\right\} . \end{aligned}$$

The right-hand side of the first inequality is greater than or equal to the left-hand side of the second inequality since $J_{\left( t_{2},t_{1}\right) }\subseteq J_{t_{2}}$:

$$\begin{aligned} \max \limits _{j\in J_{\left( t_{2},t_{1}\right) }}\left\{ w_{j}\right\} \ge \min _{j\in J_{\left( t_{2},t_{1}\right) }}\left\{ w_{j}\right\} \ge \min \limits _{j\in J_{t_{2}}}\left\{ w_{j}\right\} . \end{aligned}$$

The right-hand side of the second inequality can be bounded as

$$\begin{aligned} \max \limits _{j\in J_{\left( t_{3},t_{2}\right) }}\left\{ w_{j}\right\} \ge \max \limits _{j\in J_{\left( t_{3},t_{1}\right) }}\left\{ w_{j}\right\} \end{aligned}$$

since $J_{\left( t_{3},t_{2}\right) }\supseteq J_{\left( t_{3} ,t_{1}\right) }$.

We conclude that

$$\begin{aligned} \min \limits _{j\in J_{t_{1}}}\left\{ w_{j}\right\} \ge \max \limits _{j\in J_{\left( t_{3},t_{1}\right) }}\left\{ w_{j}\right\} , \end{aligned}$$

which implies that condition (11) also holds for the pair of nodes $t_{1},t_{3}$. $\square$

Proposition 2

The set of left arcs $A_{\mathrm {left}}(\mathbf {C})$ in $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ is an out-tree.

Proof

Suppose the proposition does not hold, i.e., there exists in $A_{\mathrm {left}}(\mathbf {C})$ a pair of left arcs $(t_{2},t_{1} )$ and $(t_{3},t_{1})$ with the same end-node, $t_{1}<t_{2}<t_{3}$. This implies that $J_{\left( t_{2},t_{1}\right) }\ne \emptyset$ and $J_{\left( t_{3},t_{1}\right) }\ne \emptyset$. It follows from the latter condition that $J_{\left( t_{3},t_{2}\right) }\ne \emptyset$ since the jobs that can be re-allocated from $[t_{3},t_{3}+1[$ to $[t_{1},t_{1}+1[$ can also be re-allocated to $[t_{2},t_{2}+1[$. Then there exists arc $(t_{3},t_{2})$ in $\overline{N}(\mathbf {C})$ and therefore the set of arcs $A_{\mathrm {left} }(\mathbf {C})$ in network $\overline{N}_{\mathrm {TransRem}}(\mathbf {C} )$ (without transitive arcs) cannot contain $\left( t_{3},t_{1}\right)$, a contradiction. $\square$

Example 4

The following table describes an instance of problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ with $n=18$ jobs and $m=2$ machines:

j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
$r_{j}$	0	0	0	0	2	2	3	1	3	2	5	5	5	4	7	5	6	7
$C_{j}$	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8	8	9	9

A feasible schedule $\mathbf {C}$ for this problem is shown in Fig. 9. The jobs which start exactly at their release dates are dashed; the remaining jobs start after their release dates.

The left arcs $A_{\mathrm {left}}(\mathbf {C})$ of graph $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ with transitive arcs removed are shown in Fig. 10. The set $A_{\mathrm {left}}(\mathbf {C})$ consists of $\left( 8,7\right) , \left( 7,6\right) , \left( 6,5\right) , \left( 6,4\right) , \left( 4,3\right) , \left( 3,2\right) , \left( 3,1\right) , \left( 1,0\right)$, which form an out-tree.

The proof of Proposition 2 justifies the following O(n)-time algorithm for constructing left arcs $A_{\mathrm {left}} (\mathbf {C})$ of network $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ without transitive arcs. It first connects consecutive nodes into left chains and then defines for the right-most node of each chain an arc ending in that node with the origin in the subsequent chain, giving preference to the left-most possible origin. Having constructed the set $A_{\mathrm {left} }(\mathbf {C})$ of left arcs, the corresponding right arcs can be produced also in O(n) time. Since $|A_{\mathrm {left}}(\mathbf {C})|=\nu -1$, there are $\nu -1$ two-node cycles, which can be enumerated in $O(\nu )$ time, so that the overall time complexity of the optimality check is O(n). We provide the details of this approach in Appendix 2.

Fig. 9

Gantt chart of a feasible schedule $\mathbf {C}$ of Example  4

Fig. 10

Left arcs $A_{\mathrm {left}}(\mathbf {C)}$ of graph $\overline{N}_{\mathrm {TransRem} }(\mathbf {C})$ without transitive arcs for a feasible schedule $\mathbf {C}$ of Example 4

4 Problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$

This section explores the most general, spiral cycles.

Theorem 4

A compressed residual network $\overline{N}(\mathbf {C})$, representing a one-block earliest start schedule for problem $P|r_{j} ,p_{j}=1|\sum w_{j}U_{j}$, contains a negative cycle if and only if it contains a negative spiral cycle.

Proof

Consider an arbitrary negative cycle that starts with a negative arc $(t,\tau )$. We show that then there exists a negative cycle such that the five properties formulated in the definition of a spiral cycle are satisfied.

In order to prove Property 1 (the cycle contains exactly one negative arc $(t,\tau )$) we demonstrate that a negative cycle with the smallest number of nodes cannot contain more than one negative arc. Suppose a negative cycle has several negative arcs $(t_{1},\tau _{1}), (t_{2},\tau _{2}), \ldots , (t_{y},\tau _{y}), y\ge 2$. Without loss of generality we assume that arc $(t_{1},\tau _{1})$ has the right-most origin $t_{1}$ among all negative arcs, i.e., $t_{1}>\max \left\{ t_{2},\ldots ,t_{y}\right\}$. Notice that no nodes are repeated in the cycle. Denoting the path from $\tau _{1}$ to $t_{y}$ by $\alpha$ and the path from $\tau _{y}$ to $t_{1}$ by $\beta$, the cycle can be represented in the form $\left( \left( t_{1},\tau _{1}\right) ,\alpha ,\left( t_{y},\tau _{y}\right) ,\beta \right)$, where fragment $\alpha$ can be empty. The three possible types of that cycle are illustrated in Fig. 11a–c depending on the relationship between $\tau _{1}, t_{y}$ and $\tau _{y}$. Let the lengths of arcs $\left( t_{1},\tau _{1}\right)$ and $\left( t_{y},\tau _{y}\right)$ be $-w_{j_{1}}$ and $-w_{j_{y}}$, where $j_{1}$ and $j_{y}$ are late jobs allocated to $[t_{1},t_{1}+1[$ and $[t_{y},t_{y}+1[$, respectively.

Fig. 11

Negative cycle $\left( \left( t_{1},\tau _{1}\right) ,~\alpha ,~\left( t_{y},\tau _{y}\right) ,~\beta \right)$

Since the cycle passes through $t_{y}$ before it returns to $t_{1}$ and $t_{y}<t_{1}$, there should be an arc $\left( e,f\right)$ belonging to fragment $\beta$ that straddles node $t_{y}$, so that

$$\begin{aligned} e<t_{y}<f, \end{aligned}$$

and we can represent fragment $\beta$ as $\left( \beta ^{\prime },\left( e,f\right) ,\beta ^{\prime \prime }\right)$, see Fig. 12. Notice that the case $e=\tau _{y}$ implies $\beta ^{\prime }=\emptyset$ and the case $f=t_{1}$ implies $\beta ^{\prime \prime }=\emptyset$. Let the job corresponding to arc (e, f) be q so that the length of the arc is

$$\begin{aligned} \ell _{(e,f)}=\left\{ \begin{array} [c]{ll} w_{q}, &{}\quad \mathrm {if~}\quad e<d_{q}\le f,\\ 0, &{}\quad \mathrm {otherwise.} \end{array} \right. \end{aligned}$$

(12)

Fig. 12

Negative cycle with fragment $\beta$ decomposed into $\left( \beta ^{\prime },\left( e,f\right) ,\beta ^{\prime \prime }\right)$

Since fragment $\beta$ does not contain negative arcs, all its three components are non-negative:

$$\begin{aligned} \ell _{\beta ^{\prime }}&\ge 0,\\ \ell _{\left( e,f\right) }&\ge 0,\\ \ell _{\beta ^{\prime \prime }}&\ge 0. \end{aligned}$$

Here $\ell _{\beta ^{\prime }}, \ell _{\left( e,f\right) }$ and $\ell _{\beta ^{\prime \prime }}$ denote the lengths of $\beta ^{\prime }, \left( e,f\right) ,\beta ^{\prime \prime }$, respectively.

Consider instead of the original cycle two new cycles: $Cycle_{I}=\Big (\left( t_{y},\tau _{y}\right) ,\beta ^{\prime },\left( e,t_{y}\right) \Big )$ and $Cycle_{II}=\left( \left( t_{1},\tau _{1}\right) ,\right. \left. \alpha ,\left( t_{y},f\right) ,\beta ^{\prime \prime }\right)$. Notice that

$$\begin{aligned} \ell _{(e,t_{y})}\le \ell _{(e,f)} \end{aligned}$$

since $t_{y}<f$. Moreover

$$\begin{aligned} \ell _{(t_{y},f)}=0 \end{aligned}$$

since $J_{t_{y}}$ contains a late job (it defines the cost of the negative left arc $(t_{y},\tau _{y})$). Thus we have

$$\begin{aligned} \ell _{(e,t_{y})}+\ell _{(t_{y},f)}\le \ell _{(e,f)}. \end{aligned}$$

Denoting the length of the original cycle by $\ell _{O}$ and the lengths of the two new cycles by $\ell _{I}$ and $\ell _{II}$ we obtain:

$$\begin{aligned} \ell _{I}+\ell _{II}\le \ell _{O}<0. \end{aligned}$$

(13)

Thus at least one of the new cycles is negative. This contradicts the assumption that the initial negative cycle has the smallest number of nodes.

We turn now to Property 2: no left arc, except for possibly $(t,\tau )$, spans over a node which appears in the remaining part of the cycle after that arc. Suppose for a negative cycle satisfying Property 1 there exists a 0-length left arc (f, g) which spans over node h that appears on the path from g to t, so that $g<h<f$, see Fig. 13. If there are several nodes of type h we select the right-most one. In that figure, solid lines represent arcs and dotted lines represent the fragments of the cycle which may consists of several arcs. Introduce new left arc (f, h), which length is zero since there is only one negative left arc $(t,\tau )$. Replacing the fragment of the cycle from f to h by the arc (f, h), we remove 0-length left arcs and non-negative right arcs. Hence the resulting cycle is negative, but with less left arcs spanning over other nodes on the path to t. Repeating this transformation we eventually obtain a cycle satisfying Property 2.

Fig. 13

Negative cycle with left arc (f, g) spanning over node h on the path from g to t

The proof of Property 3 (no right arc spans over a node which appears in the remaining part of the cycle after that arc) is similar to the proof of Property 2: consider a right arc (f, g) which spans over node h that appears on the path from g to t, so that $f<h<g$, and replace the fragment of the cycle from f to h by the arc (f, h) with $\ell _{(f,h)}\le \ell _{(f,g)}$.

The same idea can be used to prove Property 4 (t is the right-most node of the cycle) using t instead of h in the above arguments.

Finally, consider Property 5: all right arcs have zero length except for the last right arc terminating in t which may be of positive length or of zero length. Let there exists a negative cycle satisfying Properties 1–4, but not satisfying Property 5. Let the origin of the negative arc be t and let the first positive arc be (e, f), where $f<t$ due to Property 4. Again we introduce a new arc (e, t). For the positive arc (e, f) all jobs from $J_{e}$ are early and they become late if re-allocated to $[f,f+1[, \ell _{(e,f)}=\min _{j\in J_{e}}\{w_{j}\}$, see (4). Then the same holds for (e, t), which implies

$$\begin{aligned} \ell _{(e,t)}=\min _{j\in J_{e}}\{w_{j}\}=\ell _{(e,f)}. \end{aligned}$$

Thus replacing the fragment from e to t by arc (e, t) results in a negative cycle with less nodes and no more than one positive arc $\left( e,t\right)$. $\square$

Clearly, spiral cycles have a more complex structure in comparison with two-node cycles and chain cycles. We demonstrate by means of Example 5 below that the result of Theorem 4 cannot be strengthened for problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$, and spiral cycles cannot be replaced by simpler counterparts. Since the instance below deals with the case of unit weights, $w_{j}=1$ for all $j\in J$, the result of Theorem 4 cannot be strengthened for problem $P|r_{j},p_{j}=1|\sum U_{j}$.

Example 5

Consider an instance of the problem $P|r_{j},p_{j}=1|\sum U_{j}$ for which a negative spiral cycle exists but there are no negative cycles of simpler types. In that example, there is one machine and $n=8$ jobs with job characteristics given by the table:

j	1	2	3	4	5	6	7	8
$r_{j}$	0	1	2	2	1	0	6	3
$d_{j}$	7	6	5	4	5	6	8	4
$C_{j}$	1	2	3	4	5	6	7	8

Figure 14 represents a spiral negative cycle for this instance. Notice that (7, 3) is the unique negative arc in the graph and its length is $-1$. In order to construct a negative cycle with that arc we need to find a 0-length path from 3 to 7. Due to the release date and due date restrictions, there is only one path with that property shown in Fig. 14. Thus there is only one negative cycle and that cycle belongs to the spiral category.

Fig. 14

A unique negative cycle for Example 5 belonging to the spiral category

Notice that for problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$ with non-unit weights, the last arc terminating in $t=7$ may have a positive weight. In particular, if in Example 5, condition $1<w_{7}<w_{8}$ holds and $d_{7}=8$ is replaced by $d_{7}=7$, then the spiral cycle shown in Fig. 14 has positive arc (6, 7) of length $w_{7}$. The cycle, however, is still negative; its length is $-w_{8}+w_{7}$.

The algorithm for optimality check is presented in Appendix 3. Although the algorithm does not limit its search to spiral cycles, still it outperforms the fastest algorithm for finding the optimal solution for $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$.

5 Problem $P|p_{j}=1|\sum w_{j}U_{j}$

We consider now the special case when all jobs are available simultaneously ($r_{j}=0$ for $j\in J$) and show that for this case it is sufficient to consider simpler cycles of chain type.

Theorem 5

A compressed residual network $\overline{N}(\mathbf {C})$, representing a one-block earliest start schedule for problem $P|p_{j}=1|\sum w_{j}U_{j}$, contains a negative cycle if and only if it contains a negative right-chain cycle.

Proof

Since problem $P|p_{j}=1|\sum w_{j}U_{j}$ is a special case of $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$, we can use the result of Theorem 4 and consider only negative spiral cycles. Let z be the left-most node of such a cycle. Consider a negative arc $(t,\tau )$ of the cycle, which corresponds to moving some job $j\in J_{(t,\tau )}$ to time interval $[\tau ,\tau +1[$. Since all release dates are zero, arc $(t,\tau )$ can be replaced by arc (t, z) which corresponds to moving the same job j to time interval $[z,z+1[$, the length of the new arc being no larger than that of $(t,\tau )$. Since the remaining part of the spiral cycle from z to t is a right chain with 0-length arcs except for the last arc, which can be positive, the new cycle with the shortcut (t, z) is a right-chain cycle $t,z,\ldots ,t$ of negative length. $\square$

The result formulated in Theorem 5 cannot be strengthened for the unweighted version $P|p_{j}=1|\sum U_{j}$, as the following example illustrates.

Example 6

Consider an instance of the problem $P|p_{j}=1|\sum U_{j}$ with one machine and three jobs with due dates $d_{1}=2, d_{2}=3, d_{3}=1$, and a schedule given by job sequence (1, 2, 3). The corresponding graph, shown in Fig. 15, contains a unique negative cycle (2, 0, 1, 2) of length $-1$; it is a right-chain cycle; all two-node cycles are non-negative.

Fig. 15

A unique negative cycle for Example  6 belonging to the right-chain category

Fig. 16

Decomposition of $\overline{N}(\mathbf {C})$ for Example 7 into four zero-components

In what follows we show that network $\overline{N}(\mathbf {C})$ can be reduced by removing some nodes and arcs. Recall that the network reduction has been performed in Sect. 3 for problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ where it has been shown that transitive arcs are not needed.

We start with decomposing $\overline{N}(\mathbf {C})$ into so called zero-components. A zero-$component\, Z_{i}, 1\le i\le \gamma$, consists of consecutive nodes $\underline{\tau }_{i}, \underline{\tau } _{i}+1,\ldots ,\overline{\tau }_{i}$, each of which can be reached from the start-node $\underline{\tau }_{i}$ via a chain of 0-length right arcs. For two zero-components $Z_{i}$ and $Z_{j}, i<j$, there is no 0-length right arc $(\tau ^{\prime },\tau ^{\prime \prime })$ connecting $\tau ^{\prime }\in Z_{i}$ and $\tau ^{\prime }\in Z_{j}$. Notice that $Z_{i}$ may consist of a single node, i.e., $\underline{\tau }_{i}=\overline{\tau }_{i}$.

• Zero-component $Z_{i}$ is the last one (i.e., $\overline{\tau }_{i} =\nu -1$), if one of the jobs of $Z_{i}$ has a due date no smaller than $\nu$ or if $Z_{i}$ contains a late job; in both cases such a job can be moved to any later time slot at a zero cost, so that all right arcs originating from the corresponding node are of zero length.

• Zero-component $Z_{i}$ is not the last one (i.e., $\overline{\tau } _{i}<\nu -1$), if all jobs scheduled in the time-slots $\underline{\tau }_{i}, \underline{\tau }_{i}+1,$ ..., $\overline{\tau }_{i}$ are early and their maximum due date is equal to $\overline{\tau }_{i}+1$.

The following example illustrates the decomposition of $\overline{N}(\mathbf {C})$ into zero-components.

Example 7

Consider an instance of the problem $P|p_{j}=1|\sum w_{j}U_{j}$ with $m=3$ machines and $n=24$ jobs with parameters given by the table:

In the table we separate job triples, which are processed in the same unit time slot, by vertical lines. A schedule with four zero-components marked by rectangles is shown in Fig. 16; the start- and end-nodes of the components are as follows:

$$\begin{aligned} \begin{array}{cc} \underline{\tau }_{1}=0; &{} \overline{\tau }_{1}=0;\\ \underline{\tau }_{2}=1; &{} \overline{\tau }_{2}=3;\\ \underline{\tau }_{3}=4; &{} \overline{\tau }_{3}=4;\\ \underline{\tau }_{4}=5; &{} \overline{\tau }_{4}=7. \end{array} \end{aligned}$$

Decomposition of a schedule into zero-components can be performed by scanning the nodes $\tau =0,1,\ldots ,\nu -1$ left to right, identifying for a current zero-component $Z_{i}$ the furthest node from the start-node reachable by a chain of 0-length right arcs. We provide a formal description of procedure ‘Decomposition’ in Appendix 4 and show that its time complexity is O(n).

Based on zero-components $Z_{1}, Z_{2}, \ldots , Z_{\gamma }$, we define the notion of an essential cycle and prove that only essential cycles need to be considered in the optimality conditions. For all zero-components $Z_{i}$ except for the last one ($1\le i\le \gamma -1$) introduce characteristic $w_{i}^{*}$ as the smallest w value among the jobs of that component:

$$\begin{aligned} w_{i}^{*}=\min \left\{ w_{j}~|~\underline{\tau }_{i}+1\le C_{j} \le \overline{\tau }_{i}+1\right\} . \end{aligned}$$

(14)

Let $\tau _{i}^{*}$ be the node associated with $w_{i}^{*}$, i.e. $[\tau _{i}^{*},\tau _{i}^{*}+1[$ is the time slot where the job with weight $w_{i}^{*}$ is scheduled. A right-chain cycle is essential if it is of the form $t,\underline{\tau }_{i},\ldots ,\tau _{i}^{*},t$ and consists of

• a negative arc $(t,\underline{\tau }_{i})$ with t belonging to the last component $Z_{\gamma }$ and $\underline{\tau }_{i}\$being a start-node of the zero-component $Z_{i}, 1\le i\le \gamma$,

• a chain of right arcs of zero length from $\underline{\tau }_{i}$ to $\tau _{i}^{*}$, all belonging to $Z_{i}$,

• a final arc $(\tau _{i}^{*},t)$ terminating at t.

Notice that if $1\le i<\gamma$, then the final arc $(\tau _{i}^{*},t)$ is of positive length and if $i=\gamma$, then that arc is of zero length. Essential cycles of Example 7 are shown in Fig. 17.

Fig. 17

Essential cycles of Example 7

Theorem 6

Network $\overline{N}(\mathbf {C})$ contains a negative cycle if and only if it contains a negative essential cycle.

Proof

Due to Theorem 5 we can consider only negative right-chain cycles. Let t be the right-most node of such cycle and $(t,\tau )$ be its negative arc. This implies that time interval $[t,t+1[$ contains a late job and therefore t belongs to the last zero-component $Z_{\gamma }$.

By the definition of a zero-component, any right arc from a node of one component to a node of another component is of positive length. Since there is no more than one positive arc in a right-chain cycle, the origin t is followed by the nodes of one zero-component only, say $Z_{i}, 1\le i\le \gamma$. Thus a negative right-chain cycle can be represented as $t,\tau _{i}^{\prime },\ldots ,\tau _{i}^{\prime \prime },t$, where the zero length path $\tau _{i}^{\prime },\ldots ,\tau _{i}^{\prime \prime }$ consists of right arcs within $Z_{i}$. Notice that for a special case with $\tau _{i}^{\prime } =\tau _{i}^{\prime \prime }$ we get a two-node cycle. We show that the length of the essential cycle $t, \underline{\tau }_{i}, \ldots , \tau _{i}^{*}, t$ is no larger than that of an arbitrary negative right-chain cycle $t,\tau _{i}^{\prime },\ldots ,\tau _{i}^{\prime \prime },t$ with $\tau _{i}^{\prime },\ldots ,\tau _{i}^{\prime \prime }$ belonging to $Z_{i}$. Indeed, the left arcs of the two cycles satisfy $\ell _{(t,\underline{\tau }_{i})}\le \ell _{(t,\tau _{i}^{\prime })}$ since $\underline{\tau }_{i}<\tau _{i}^{\prime }$; the internal paths within $Z_{i}\$are of zero length for both cycles, i.e., $\ell _{(\underline{\tau }_{i},\ldots ,\tau _{i}^{*})}=\ell _{(\tau _{i}^{\prime },\ldots ,\tau _{i}^{*})}=0$, while for the final arcs condition $\ell _{(\tau _{i}^{*},t)}=w_{i}^{*}\le \ell _{(\tau _{i}^{\prime \prime },t)}$ holds due to the definition (14) of $w_{i}^{*}$. $\square$

We illustrate how the formulated optimality condition can be used for the optimality check in Appendix 4; the resulting algorithm has time complexity O(n), an improvement in comparison with the $O(n\log n)$-time algorithm for finding an optimal schedule for problem $P|p_{j}=1|\sum w_{j}U_{j}$ (Brucker and Kravchenko 2006; Dessouky et al. 1990).

6 Problem $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$

Consider problem $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$ with the weighted tardiness objective function. It appears that the negative cycles for problem $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$ are more complicated than those introduced in Sect. 2.3 (two-node cycles, chain cycles or spiral cycles). In fact there may exist instances for which the simplest negative cycles have more than one negative arc - a major distinctions from the three types of cycles with one negative arc.

Fig. 18

A graph for Example 8 with the unique negative cycle containing two negative arcs

Example 8

Consider an instance of the problem $P|r_{j} ,p_{j}=1|\sum w_{j}T_{j}$ with one machine and $n=4$ jobs given by the table

j	1	2	3	4
$r_{j}$	0	0	0	0
$d_{j}$	1	2	2	3
$w_{j}$	5	20	10	10
$C_{j}$	1	2	3	4

Figure 18 represents the corresponding graph; the unique negative cycle (3, 2, 0, 3) is marked by bold arcs and it contains two negative arcs (3, 2) and (2, 0).

Notice that the instance presented in Example 8 has zero release dates for all jobs, which implies that for problem $P|p_{j} =1|\sum w_{j}T_{j}$ we also cannot limit our consideration to the three types of cycles defined above. In this paper we do not introduce new cycle types with several negative arcs; it is likely that the resulting rather complicated optimality conditions would have limited application.

In what follows we discuss how solution optimality can be checked using Theorem 1. Recall that Theorem 1 provides the necessary and sufficient optimality conditions for the most general problem $P|r_{j},p_{j}=1|\sum w_{j}f_{j}(C_{j})$ with an arbitrary separable objective function. In order to verify the optimality of a given solution $\mathbf {C}$, we first apply the $O(n\log n)$-time Algorithm ‘Left Shift$\left( \mathbf {C}\right)$.’ Then the reduced graph $\overline{N}(\mathbf {C})$ is constructed in $O\left( \frac{n^{2}}{m}\right)$ time, as described in Sect. 2.3. It has $\nu =\left\lceil \frac{n}{m}\right\rceil$ nodes and a arcs, $a<\nu ^{2}$. Since the fastest algorithms for negative cycle detection are of time complexity $O\left( \nu a\right)$ (Cherkassky and Goldberg 1999), which is $O\left( \frac{n^{3}}{m^{3}}\right)$ in our case, schedule optimality can be verified in $O\left( \frac{n^{3}}{m^{3}}+\frac{n^{2}}{m}\right)$ time - an improvement in comparison with the straightforward $O(n^{3})$ approach based on finding an optimal solution to problem $P|r_{j},p_{j}=1|\sum w_{j}T_{j}$ via solving the associated assignment problem.

7 Problem $P|r_{j},p_{j}=1|\sum T_{j}$

We consider now the equal weight special case ($w_{j}=1$ for $j\in J$) and show that for this case it is sufficient to consider simpler cycles of chain type.

Theorem 7

A compressed residual network $\overline{N}(\mathbf {C})$, representing a one-block earliest start schedule for problem $P|r_{j},p_{j}=1|\sum T_{j}$, contains a negative cycle if and only if it contains a negative left-chain cycle.

Proof

Consider a negative cycle O with the smallest number of nodes. We prove that such a cycle satisfies Properties 1–4 of the definition of a spiral cycle and instead of Property 5, it satisfies a stronger property, namely

Property 5 $^{\prime }$: there is no right arc (e, f) with the end-node f to the left of t.

Properties 1–4 combined with $5^{\prime }$ imply that a negative cycle with the smallest number of nodes is a left-chain cycle.

The proof of Properties 1–4 follows the same ideas as the proof of Theorem 4 for problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$; we present that proof in Appendix 5. Consider now Property $5^{\prime }$.

Let (e, f) be the first right arc with $f<t$. We denote the fragment of cycle O from $\tau$ to e by $\alpha$ and the fragment of the schedule from f to t by $\beta$, see Fig. 19. Notice that by the definition of the spiral cycle

$$\begin{aligned} e&\le \tau <f,\\ \ell _{\alpha }&=0,\nonumber \\ \ell _{\beta }&\ge 0,\nonumber \end{aligned}$$

(15)

see also Fig. 6.

Fig. 19

Negative cycle for problem $P|r_{j},p_{j}=1|\sum T_{j}$ that does not satisfy Property $5^{\prime }$

Let j be a job in $J_{(t,\tau )}$ with the smallest due date, so that the length of arc $(t,\tau )$ is defined via that job,

$$\begin{aligned} \ell _{(t,\tau )}=-\left( t+1-\max \left\{ d_{j},\tau +1\right\} \right) . \end{aligned}$$

Notice that

$$\begin{aligned} d_{j}<t+1; \end{aligned}$$

(16)

otherwise the length of the arc $(t,\tau )$ is not negative. Similarly, let k be a job in $J_{e}$ with the largest due date, so that the length of arc (e, f) is defined via that job,

$$\begin{aligned} \ell _{(e,f)}=\max \left\{ f+1-\max \left\{ d_{k},e+1\right\} ,~0\right\} . \end{aligned}$$

Introduce an artificial right arc (e, t) and replace the fragment $(e,f), \beta$ of cycle O by a single arc (e, t). The length of the new cycle is

$$\begin{aligned} \ell _{(t,\tau )}+\ell _{\alpha }+\ell _{(e,t)}= & {} -\left( t+1-\max \left\{ d_{j},\tau +1\right\} \right) \\&+0+\max \left\{ t+1-\max \left\{ d_{k} ,e+1\right\} ,~0\right\} . \end{aligned}$$

Clearly, if $d_{k}>t+1$, then the last term in the above expression is 0, so that the resulting cycle is negative and it satisfies Property 5$^{\prime }$. Also, if $\max \left\{ d_{j},\tau +1\right\} <d_{k}\le t+1$, then the resulting cycle is negative and it satisfies Property $5^{\prime }$ as well:

$$\begin{aligned} \ell _{(t,\tau )}+\ell _{\alpha }+\ell _{(e,t)}= & {} -\left( t+1-\max \left\{ d_{j},\tau +1\right\} \right) \\&+0+\left( t+1-\max \left\{ d_{k},e+1\right\} \right) \\= & {} \max \left\{ d_{j},\tau +1\right\} -\max \left\{ d_{k},e+1\right\} \\< & {} d_{k}-\max \left\{ d_{k},e+1\right\} \le 0. \end{aligned}$$

Thus in what follows we assume

$$\begin{aligned} d_{k}\le \max \left\{ d_{j},\tau +1\right\} . \end{aligned}$$

(17)

We show that introducing an artificial left arc (t, f) and replacing in the original cycle O the fragment $(t,\tau ), \alpha , (e,f)$ by that arc we obtain a modified cycle M with less nodes which length $\ell _{M}$ is negative. To this end, we calculate the difference $\ell _{M}-\ell _{O}$ using the formula

$$\begin{aligned} \ell _{M}-\ell _{O}= & {} \left( \ell _{(t,f)}+\ell _{\beta }\right) -\left( \ell _{(t,\tau )}+\ell _{\alpha }+\ell _{(e,f)}+\ell _{\beta }\right) \\= & {} \ell _{(t,f)}-\ell _{(t,\tau )}-\ell _{(e,f)}. \end{aligned}$$

Let i be a job in $J_{(t,f)}$ with the smallest due date, so that the length of arc (t, f) is defined via that job,

$$\begin{aligned} \ell _{(t,f)}=-\left( t+1-\max \left\{ d_{i},f+1\right\} \right) . \end{aligned}$$

Notice that $J_{(t,\tau )}\subseteq J_{(t,f)}$ and, as defined earlier for $J_{(t,\tau )}, j$ is the job with the smallest due date among $J_{(t,\tau )}$. It follows that $d_{i}\le d_{j}$ so that

$$\begin{aligned} \ell _{(t,f)}\le -\left( t+1-\max \left\{ d_{j},f+1\right\} \right) . \end{aligned}$$

We consider the following cases with respect to $d_{j}$.

(1):

The case of $d_{j}\ge t+1$ is eliminated due to (16).

(2):

If $f+1\le d_{j}<t+1$, then

$$\begin{aligned} \ell _{(t,f)}&\le -\left( t+1-\max \left\{ d_{j},f{+}1\right\} \right) =-\left( t{+}1-d_{j}\right) ,\\ -\ell _{(t,\tau )}&=t+1-d_{j}, \end{aligned}$$

and hence

$$\begin{aligned} \ell _{M}-\ell _{O}\le & {} -\left( t+1-d_{j}\right) +\left( t+1-d_{j}\right) -\ell _{(e,f)}\\= & {} -\ell _{(e,f)}\le 0. \end{aligned}$$

(3):

If $\tau +1<d_{j}<f+1$, then due to $d_{i}\le d_{j}$,

$$\begin{aligned} \ell _{(t,f)}= & {} -\left( t-f\right) ,\\ -\ell _{(t,\tau )}= & {} t+1-d_{j},\\ -\ell _{(e,f)}= & {} -\max \left\{ f+1-\max \left\{ d_{k},e+1\right\} ,~0\right\} . \end{aligned}$$

Notice that

$$\begin{aligned} \max \left\{ d_{k},e+1\right\}\le & {} \max \left\{ d_{j},\tau +1,e+1\right\} \\= & {} \max \left\{ d_{j},\tau +1\right\} =d_{j}, \end{aligned}$$

where we first use inequality (17), then (15), while the last equality holds due to the assumption of case (3). Hence

$$\begin{aligned}&-\ell _{(e,f)}\\&\quad =-\left( f+1\right) +\max \left\{ d_{k},e+1\right\} \le -\left( f+1\right) +d_{j}. \end{aligned}$$

We conclude that

$$\begin{aligned}&\ell _{M}-\ell _{O}\le -\left( t-f\right) \\&\quad +\left( t+1-d_{j}\right) -\left( f+1\right) +d_{j}=0. \end{aligned}$$

(4):

Finally, if $d_{j}\le \tau +1$, then $d_{k} \le \tau +1$ by (17) and

$$\begin{aligned} \ell _{(t,f)}= & {} -\left( t-f\right) ,\\ -\ell _{(t,\tau )}= & {} t-\tau ,\\ -\ell _{(e,f)}= & {} -\left( f+1-\max \left\{ d_{k},e+1\right\} \right) \\\le & {} -(f+1)+\max \left\{ \tau +1,e+1\right\} \\= & {} -(f+1)+(\tau +1)=\tau -f. \end{aligned}$$

Here we use (15) for $\max \left\{ \tau +1,e+1\right\}$. It follows that

$$\begin{aligned} \ell _{M}-\ell _{O}\le -\left( t-f\right) +\left( t-\tau \right) +\left( \tau -f\right) =0. \end{aligned}$$

Thus Property 5$^{\prime }$ is proved which, together with Properties 1–4 implies that the negative cycle with the smallest number of nodes belongs to the class of left-chain cycles. $\square$

The algorithm to check the optimality of a given schedule is presented in Appendix 6. Its time complexity is $O(n\log n)$ provided that an earliest start schedule is given, and it reduces to O(n) if all jobs are available simultaneously ($r_{j}=0$ for all $j\in J$).

We now demonstrate that there are instances of problem $P|r_{j},p_{j}=1|\sum T_{j}$ for which negative left-chain cycles exist but there are no negative cycles of a simpler type, namely, two-node cycles.

Example 9

Consider an instance of the problem $P|r_{j} ,p_{j}=1|\sum T_{j}$ with $m=1$ and $n=4$ given by the table

j	1	2	3	4
$r_{j}$	0	0	1	2
$d_{j}$	4	2	3	3
$C_{j}$	1	2	3	4

Figure 20 represents a unique negative cycle for this instance which is a left-chain cycle. It is easy to verify that all two-node cycles are non-negative.

Fig. 20

A unique negative cycle for Example 9 of the left-chain type

8 Problem $P|p_{j}=1|\sum T_{j}$

In problem $P|p_{j}=1|\sum T_{j}$ all jobs are available simultaneously ($r_{j}=0, j\in J$) and have unit weights. We first show that the necessary and sufficient conditions for problem $P|r_{j},p_{j}=1|\sum T_{j}$ can be simplified so that only two-node cycles are considered.

Theorem 8

A compressed residual network $\overline{N}(\mathbf {C})$, representing a one-block earliest start schedule for problem $P|p_{j}=1|\sum T_{j}$, contains a negative cycle if and only if it contains a negative two-node cycle.

Proof

Due to Theorem 7, if the graph for problem $P|r_{j},p_{j}=1|\sum T_{j}$ contains a negative cycle, it also contains a negative left-chain cycle. Given an arbitrary negative left-chain cycle we replace the whole left chain by a single arc. Since the length of that arc is no larger than that of the initial negative arc and the remaining removed left arcs are of zero lengths, we obtain a negative two-node cycle. $\square$

Notice that unlike problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$, the transitive arcs cannot be eliminated, as the following example shows.

Example 10

Consider an instance of the problem $P|p_{j}=1|\sum T_{j}$ with one machine and three jobs with the due dates $d_{1}=2, d_{2}=2, d_{3}=1$. The schedule $\mathbf {C}$ is given by $C_{1}=1, C_{2}=2$ and $C_{3}=3$. If the transitive arcs (2, 0) and (0, 2) are not considered, then the two-node cycle consisting of arcs (1, 0) and (0, 1) is of length 0, another two-node cycle consisting of arcs (2, 1) and (1, 2) is of length $-1+1=0$. The two-node cycle consisting of transitive arcs (2, 0) and (0, 2) is, however, negative: $-2+1=-1.$

Observe that the algorithm for optimality check for problem $P|p_{j}=1|\sum T_{j}$ follows from the algorithm for the more general problem $P|r_{j},p_{j}=1|\sum T_{j}$ presented in Appendix 6. The time complexity of the latter algorithm is O(n) for an earliest start schedule. Since in the case of $r_{j}=0$ for all $j\in J$, Algorithm ‘Left Shift$\left( \mathbf {C}\right)$’ transforms a given schedule into an earliest start schedule in O(n) time, the optimality check for problem $P|p_{j}=1|\sum T_{j}$ can be performed in O(n) time for an arbitrary schedule.

9 Conclusions

In this paper we have studied the necessary and sufficient optimality conditions for various problems with parallel identical machines and unit job processing times. The formulated conditions deal with a specially defined network $\overline{N}(\mathbf {C})$ and they are based on detecting negative cycles. For each problem we give an insight into the underlying structure of the graph $\overline{N}(\mathbf {C})$ and specify the simplest types of cycles which need to be considered in the optimality conditions: two-node cycles, chain cycles and spiral cycles. The summary of the cycle types for different versions of problem $P|r_{j},p_{j}=1|F\left( \mathbf {C,w}\right)$ is provided in Table 1 in Sect. 2.3.

The special features of the cycles allow us to develop efficient algorithms for verifying optimality of a given schedule. We describe the ideas of the optimality check algorithms after formulating the optimality conditions for each problem and present all technical details in the appendices. The summary of the results is presented in Table 2 where we compare the time complexity of traditional algorithms for finding optimal schedules with the complexity of our optimality check algorithms.

Table 2 Time complexity of finding optimal solutions and performing the optimality check

In the table we assume that an earliest start schedule consisting of a single block is given (which can be verified in O(n) time by the algorithm from Appendix 1). Otherwise an initial schedule can be converted into an earliest start schedule by Algorithm ‘Left Shift’ from Appendix 1; after that the optimality check can be performed for each block considered separately. Notice that Algorithm ‘Left Shift’ requires $O(n\log n)$ time if release dates are arbitrary and O(n) time if all jobs are available simultaneously ($r_{j}=0$ for all $j\in J$). This implies that ‘Left Shift’ does not affect the O(n) time complexity of the algorithms for problems $P|p_{j}=1|\sum w_{j}U_{j}$ and $P|p_{j}=1|\sum T_{j}$; for other problems the time complexity should be increased by $O(n\log n)$ if the initial schedule does not belong to the class of earliest start schedules.

While we have illustrated only one application of the necessary and sufficient optimality conditions, they might be beneficial for solving other problems as well. Further applications of the optimality conditions may involve the development of new algorithms for finding alternative optimal solutions different from those produced by the known algorithms or algorithms for finding several optimal schedules. Another application area is hierarchical optimization, where it is required to select among solutions optimal for one criterion those solutions which minimize the secondary criterion. Finally, the optimality conditions play an important role in inverse scheduling (Heuberger 2004) where a target schedule is given and it is required to modify the problem parameters to make the target solution optimal. Developing optimality conditions for other scheduling problems and exploring their usage in the application areas listed above can be a subject of further research.

Appendices

Appendix 1: Earliest start schedule construction and verification

We present the pseudocodes of the algorithms described in Sects. 2.1, 2.2. The first algorithm constructs an earliest start schedule in $O(n\log n)$ time. The second algorithm verifies in O(n) time whether a given schedule belongs to the class of earliest start schedules. The third one transforms in $O(n\log n)$ time a given schedule into an earliest start schedule, if it does not belong to this class.

Algorithm ‘Calculate Blocks’

1.1 Algorithm ‘Earliest Start Schedule Verification’

Algorithm ‘Left Shift $\left( \mathbf {C}\right)$ ’

The overall running time of Algorithm ‘Left Shift$\left( \mathbf {C}\right)$’ is $O\left( n\log n\right)$. Indeed, the most time consuming step is the $O(n\log n)$-time Algorithm ‘Calculate Blocks’ needed to calculate h(t). For efficient implementation of the remaining steps, an auxiliary data structure $\mathbf {H}$ is used to list the jobs in non-decreasing order of the release dates; in addition the pointers are introduced to locate jobs in list $\mathbf {H}$ and in the schedule $\mathbf {C}$ in constant time. In schedule $\mathbf {C}$, moving a single job requires constant time. In the list $\mathbf {H}$, marking a job in $\mathbf {H}$ as ‘deleted’ requires O(1) time, if pointers are used. Maintaining a special additional pointer and incrementing it throughout the algorithm, all steps of identifying the first non-deleted job f in $\mathbf {H}$ require O(n) time.

Appendix 2: Verifying solution optimality for $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$

Given an earliest start schedule, construct left arcs $A_{\mathrm {left} }(\mathbf {C})$ of network $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ without transitive arcs, to complement them with the corresponding right arcs and to verify conditions (11) for $\nu -1$ pairs of nodes t and $\tau$. We first provide the details of the algorithm for constructing $A_{\mathrm {left}}(\mathbf {C})$ and then analyze it, together with the remaining steps of the optimality check. As before, we assume that $\mathbf {C}$ consists of one block of $\nu =\left\lceil \frac{n}{m}\right\rceil$ unit time intervals.

Algorithm ‘Construct Left Arcs $A_{\mathrm {left}}(\mathbf {C})$ of $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ ’

Clearly, each for-loop of the algorithm scans the nodes of $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ once performing for each time slot t at most m operations on the jobs allocated to it. Thus the above algorithm can be implemented in $O\left( \nu m\right) =O\left( n\right)$ time.

For each left arc of the constructed out-tree, the length of its right arc counterpart can be found by (3). Since the number of left arcs in the out-tree is $\nu -1$, the lengths of all right arcs of $\overline{N}_{\mathrm {TransRem}}(\mathbf {C})$ can be found in $O\left( \nu m\right) =O\left( n\right)$ time as well.

Verifying conditions (11) for $\nu -1$ pairs of nodes t and $\tau$ requires $O(\nu )$ time, if the lengths of arcs $(t,\tau )$ and $(\tau ,t)$ have been determined. Thus the overall time complexity of the optimality check for problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$ is O(n). Notice that for problem $P|r_{j},p_{j}=1|\sum w_{j}C_{j}$, an optimal solution can be found in $O\left( n\log n\right)$ time by scheduling at each decision point an available job with the largest $w_{j}$ value.

Appendix 3: Verifying solution optimality for $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$

The fastest algorithm for solving problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$ is due to Dourado et al. (2009) and it is of time complexity $O\left( \frac{n^{2}\log m}{m}+n\log n\right)$. We show that the optimality check can be performed by a slightly faster algorithm of time complexity $O\left( \frac{n^{2}}{m}+n\right)$.

By Theorem 4, it is sufficient to explore whether there exists a negative spiral cycle for a given earliest start schedule. Our approach consists of three stages, where the first two stages deal with pre-processing. We assume that graph $\overline{N}(\mathbf {C})$ is constructed and its set of nodes corresponds to time intervals $\mathcal {T=}\{0,1,\ldots ,\nu -1\}$.

Stage 1.:

Determine for each $\tau \in \mathcal {T}$ the left-most node $\lambda (\tau )$ reachable from $\tau$ via a 0-length left chain, and the right-most node $\mu (\tau )$ reachable from $\tau$ via a 0-length right chain.

Stage 2.:

Determine for each $\tau \in \mathcal {T}$ the left-most node $a(\tau )$ and the right-most node $b(\tau )$ reachable from $\tau$ via a 0-length path consisting of alternating left chains and right chains.

Stage 3.:

The negative arcs are considered one by one. For each arc $(t,\tau )$ of length $\ell _{(t,\tau )}<0$, one of the two conditions happen: $a(\tau )\le \tau <t\le b(\tau )$ or $a(\tau )\le \tau <b(\tau )<t$. In the former case there exists a negative cycle consisting of $(t,\tau )$ and a 0-length path from $\tau$ to t. In the latter case the algorithm finds the shortest path from $\tau$ to t as the smallest w value of one of the jobs processed in $[a(\tau ),b(\tau )]$. We denote that value by $w_{[a(\tau ),b(\tau )]}$,

$$\begin{aligned} w_{[a(\tau ),b(\tau )]}=\min \left\{ w_{j}|j\in J_{z},~a(\tau )\le z\le b(\tau )\right\} . \end{aligned}$$

(18)

If $\ell _{(t,\tau )}+w_{[a(\tau ),b(\tau )]}<0$, then there exists a negative cycle consisting of the negative arc $(t,\tau )$, a 0-length path with the nodes belonging to $[a(\tau ),b(\tau )]$ and a positive arc of length $w_{[a(\tau ),b(\tau )]}$.

Graph $\overline{N}(\mathbf {C})$ can be constructed in $O\left( \frac{n^{2} }{m}\right)$ time, see Sect. 2.3. As we show below, the complexities of the subsequent three stages are $O\left( \frac{n^{2}}{m^{2} }+n\right) , O\left( \frac{n^{2}}{m^{2}}\right)$ and $O\left( \frac{n^{2}}{m^{2}}+n\right)$, respectively, so that the overall time complexity is $\left( \frac{n^{2}}{m}+n\right)$.

We start with the formal description of the procedure of Stage 1. It first determines for each $\tau \in \mathcal {T}$ the set of nodes $\mathcal {L}(\tau )$ to the left of $\tau$ connected with $\tau$ by 0-length left arcs. The values $\lambda (\tau )$ are defined one by one for $\tau =0,1,\ldots ,\nu -1$. If $\lambda (0),\lambda (1),\ldots ,\lambda (\tau -1)$ are known, then $\lambda (\tau )$ is the smallest value among $\lambda (\tau ^{\prime })$, where $\tau ^{\prime } \in \mathcal {L}(\tau )$, or $\lambda (\tau )=\tau$ if there are no 0-length left arcs originating from $\tau$.

Finding $\mu$ values is similar, but there is one point of difference: the 0-length right arcs originating from $\tau$ are defined via early jobs from $J_{\tau }$ that can be moved to the right to the time slots no later than their due dates; however, if there is at least one late job $J_{\tau }$, then all right arcs originating from $\tau$ are of 0 length. Formally, this procedure is described as follows.

Stage 1: ‘Calculate $\lambda (\tau )$ and $\mu (\tau )$ for all $\tau \in T$ ’

Step 1 incurs O(n) time, while the loops of Steps 3–5 and 7–9 require $O(\nu ^{2})=O\left( \frac{n^{2}}{m^{2}}\right)$ time.

The procedure for Stage 2 is based on the definition of a spiral cycle, see Sect. 2.3. The origin t of the negative left arc $\left( t,\tau \right)$ is not fixed, but node $\tau$ is fixed. The output for a given $\tau$ is the widest possible range of nodes $a(\tau ), a(\tau )+1,\ldots ,b(\tau )$ reachable via 0-length paths.

Stage 2: ‘Calculate $a(\tau )$ and $b(\tau )$ for all $\tau \in T$ ’

For a fixed $\tau$, finding $a(\tau )$ and $b(\tau )$ incurs scanning no more than $\nu$ nodes. Hence the overall time complexity of finding $a(\tau )$ and $b(\tau )$ for all $\tau \in \mathcal {T}$ is $O(\nu ^{2})=O\left( \frac{n^{2} }{m^{2}}\right)$.

The key step of Stage 3 is calculating $w_{\left[ \tau _{1},\tau _{2}\right] }$ by (18) for all possible ranges $\tau _{1}\le \tau _{2}$. Clearly, if $w_{[\tau _{1},\tau _{2}-1]}$ and $w_{[\tau _{2},\tau _{2}]}$ are known, then

$$\begin{aligned} w_{[\tau _{1},\tau _{2}]}=\min \left\{ w_{[\tau _{1},\tau _{2}-1]},~w_{[\tau _{2},\tau _{2}]}\right\} . \end{aligned}$$

(19)

Thus the procedure of Stage 3 can be formulated as follows.

Stage 3 ‘Spiral Cycle Check’

Steps 1–3 incur $O(\nu m)=O(n)$ time to calculate $w_{[\tau ,\tau ]}$, while Steps 4–8 incur $O(\nu ^{2})$ time to calculate $w_{[\tau _{1},\tau _{2}]}$ for all $\tau _{1}<\tau _{2}$. The total number of arcs $(t,\tau )$ examined in Steps 9–12 is $O(\nu ^{2})=O\left( \frac{n^{2}}{m^{2}}\right)$. For arc ($t,\tau )$, verifying conditions of Steps 10–11 takes O(1) time. Thus the overall time complexity of Stage 3 is $O\left( \frac{n^{2}}{m^{2}}+n\right)$.

Appendix 4: Verifying solution optimality for $P|p_{j}=1|\sum w_{j}U_{j}$

The fastest algorithm for solving problem $P|p_{j}=1|\sum w_{j}U_{j}$ is of time complexity $O\left( n\log n\right)$, see Brucker and Kravchenko (2006), Dessouky et al. (1990). We show that the optimality check can be performed in O(n) time based on Theorem 6.

First we notice that since in problem $P|p_{j}=1|\sum w_{j}U_{j}$ all jobs are available simultaneously, algorithm ‘Left Shift$\left( \mathbf {C}\right)$’ which transforms a given schedule into an earliest start schedule takes O(n) time rather than $O(n\log n)$. In what follows we consider an earliest start schedule with time slots $\mathcal {T}=\{0,1,\ldots ,\nu -1\}$.

Instead of constructing the whole graph $\overline{N}(\mathbf {C})$ with $O\left( \frac{n^{2}}{m^{2}}\right)$ arcs, we identify the zero-components $Z_{1}, Z_{2},$..., $Z_{\gamma }$ using procedure ‘Decomposition’ described below, and then perform the optimality check based on Theorem 6.

Decomposition is performed by considering the nodes $\mathcal {T} =\{0,1,\ldots ,\nu -1\}$ left to right identifying for a current zero-component the furthest node from the start-node reachable by a chain of 0-length right arcs.

Procedure ‘Decomposition’

Notice that if condition of Step 5 holds, then the right arcs $(\tau ,\tau ^{\prime })$ are of zero length for each node $\tau ^{\prime }\in \{\tau +1,\tau +2,\ldots ,d_{\tau }^{\max }-1\}$ and hence all nodes $\tau ^{\prime }$ should be included in the current zero-component.

The time complexity of procedure ‘Decomposition’ is O(n): it enumerates no more than $\nu =\left\lceil \frac{n}{m}\right\rceil$ nodes $\tau _{i}, 0\le \tau \le \nu -1$ performing each time O(m) operations to check in Step 3 whether a late job in $J_{\tau }$ exists, or to find $d_{\tau }^{\max }$ in Step 4, and no more than one update of $\overline{\tau }_{i}$.

The algorithm for the optimality check enumerates essential cycles each of which starts in a node of the last zero-component $Z_{\gamma }$, reaches via a negative arc a start-node $\underline{\tau }_{i}$ of a zero-component $Z_{i}, 1\le i\le \gamma$, and returns back to the origin via right arcs. In order to perform the search efficiently, the algorithm uses auxiliary procedure ‘Find Most Negative Arcs’ which determines for each node $\tau \in \{0,1,\ldots ,\nu -1\}$ a negative arc $(T(\tau ),\tau )$ with the origin $T(\tau )$ belonging to the last zero-component ($T(\tau )\in Z_{\gamma }$) such that the length of that arc, denoted by a negative value $-W(\tau )$ ($W(\tau )>0$), has the most negative value among other arcs originating from $t\in Z_{\gamma }:$

$$\begin{aligned} W(\tau )=\max _{t\in Z_{\gamma }}\{w_{j}|j\in J_{t}^{\mathrm {late}},t\in Z_{\gamma }\}. \end{aligned}$$

Here $J_{t}^{\mathrm {late}}$ is the set of late jobs scheduled in $[t,t+1[, J_{t}^{\mathrm {late}}=\{j\in J_{t}~|~d_{j}\le t\}$. If there is no negative arc $(t,\tau )$ with the origin in $Z_{\gamma }$, we indicate this by setting $T(\tau )=0$ and $W(\tau )=0$. We describe the procedure for finding the values $T(\tau )$ and $W(\tau )$ after the main algorithm.

Suppose $T(\tau )$ and $W(\tau )$ are defined for all $\tau \in \{0,1,\ldots ,\nu -1\}$. In the main algorithm we first verify whether there exists a negative essential cycle with all nodes belonging to the last zero-component $Z_{\gamma }$. This happens if there exists a negative arc leading to $\underline{\tau }_{\gamma }$, i.e., if $W(\underline{\tau }_{\gamma })\ne 0$. The corresponding essential cycle consists then of the negative arc $(T(\underline{\tau }_{\gamma }),\underline{\tau }_{\gamma })$ of length $-W(\underline{\tau }_{\gamma })<0$ and 0-length right arcs all belonging to $Z_{\gamma }$ returning back to $T(\underline{\tau }_{\gamma })$.

In the remaining part of the algorithm we consider all but last zero-components $Z_{i}, i=1,\ldots ,\gamma -1$, and verify whether there exists a negative essential cycle passing via the start-node $\underline{\tau }_{i}$ of $Z_{i}$. To this end we identify the most negative arc $(T(\underline{\tau }_{i}),\underline{\tau }_{i})$ of length $-W(\underline{\tau }_{i})$ leading from a node of the last zero-component $Z_{\gamma }$ to $\underline{\tau }_{i}$ and a positive arc of the smallest length $w_{i}^{*}$ defined by (14) from a node of $Z_{i}$ to $Z_{\gamma }$. If $-W(\underline{\tau }_{i})+w_{i}^{*}<0$, then the corresponding essential cycle consisting of $(T(\underline{\tau } _{i}),\underline{\tau }_{i}), 0$-length right arcs belonging to $Z_{i}$ and a positive arc returning back to $T(\underline{\tau }_{i})$ is negative. Otherwise all essential cycles passing via $\underline{\tau }_{i}$ are non-negative since $(T(\underline{\tau }_{i}),\underline{\tau }_{i})$ is the most negative arc leading to $\underline{\tau }_{i}$. Formally the main algorithm can be described as follows.

Algorithm ‘Optimality Check for $P|p_{j}=1|\sum w_{j}U_{j}$ ’

Step 1 involves procedure ‘Decomposition’ of time complexity O(n). Step 2 uses the O(n)-time Procedure ‘Find Most Negative Arcs’ presented and analyzed below. Steps 3–7 are dominated by Step 5 which involves $O(\nu m)=O(n)$ jobs belonging to $Z_{1}\cup Z_{2}\cup \cdots \cup Z_{\gamma -1}$. Thus the overall time complexity for checking optimality of a solution to problem $P|p_{j}=1|\sum w_{j}U_{j}$ is O(n).

We now describe Procedure ‘Find Most Negative Arcs’ used in Step 2. It starts with setting up the initial values $W(\tau ):=0$ and $T(\tau ):=0$ for each $\tau =0,1,\ldots ,\nu -1$. In the first part of the algorithm (Steps 2–7) we identify negative arcs $(t,\tau )$ originating from all possible nodes $t\in Z_{\gamma }$ of the last zero-component by considering late jobs $j\in J_{t}^{\mathrm {late}}$ of the corresponding time slot $[t,t+1[$. A late job j induces negative arcs $(t,\tau ), (t,\tau -1)$, ..., (t, 0) of the same length $-w_{j}$, where

$$\begin{aligned} \tau =d_{j}-1. \end{aligned}$$

(20)

For a fast implementation, we set up values $W(\tau )$ and $T(\tau )$ for nodes $\tau$ defined by (20) (Steps 2–7) and leave W and T values for $\tau -1, \tau -2, \ldots , 0$ to be updated in Steps 8–10. For those updates we use the property that for a negative arc $(t,\tau )$ there also exist negative arcs $(t,\tau -1), \ldots , (t,0)$ of the same length. We scan nodes $\tau$ right to left comparing $W(\tau -1)$ and $W(\tau )$. Whenever $W(\tau -1)<W(\tau )$, the updates are performed for $\tau -1$ so that eventually we obtain for $\tau -1$ the required values $T(\tau -1)$ and $W(\tau -1)$ which define the most negative arc for it.

Procedure ‘Find Most Negative Arcs’

Step 1 and Steps 8–10 deal with $\nu$ time-slots performing O(1) operations for each of them. Steps 2–7 consider O(n) jobs of $J_{t}^{\mathrm {late}}, t\in Z_{\gamma }$, the number of updates for each job being O(1). Thus the overall time-complexity of the procedure is O(n).

Appendix 5: Spiral cycle properties for problem $P|r_{j},p_{j}=1|\sum T_{j}$

In this appendix we present a proof that for problem $P|r_{j},p_{j}=1|\sum T_{j}$, a negative cycle with the smallest number of nodes satisfies Properties 1–4 from the definition of a spiral cycle; the proof of the modified Property 5$^{\prime }$, which is stronger than Property 5, is presented in Sect. 7.

Proof

We use the same idea as in the proof of Theorem 4 for problem $P|r_{j},p_{j}=1|\sum w_{j}U_{j}$; the differences in the proofs are due to the formulae for calculating arc lengths which are problem specific.

The proof of Property 1 of Theorem 4 needs no changes up to formula (12): the length of the arc (e, f) should be replaced when considering objective $\sum T_{j}$ instead of $\sum w_{j}U_{j}$. For $\sum T_{j}$, the length of that arc is defined by job q which has the largest due date among the jobs in $J_{e}$:

$$\begin{aligned} d_{q}=\max _{j\in J_{e}}\{d_{j}\} \end{aligned}$$

and the value is

$$\begin{aligned} \ell _{(e,f)}=\left\{ \begin{array} [c]{ll} 0, &{} \quad \mathrm {if~}\quad d_{q}\ge f+1,\\ f+1-\max \left\{ d_{q},e+1\right\} , &{}\quad \mathrm {otherwise.} \end{array} \right. \end{aligned}$$

Depending on the value of $d_{q}$ we have the following cases.

If $d_{q}\ge t_{y}+1$, then $\ell _{(e,t_{y})}=0$ and we obtain a two-node negative cycle consisting of arcs $(t_{y},e)$ and $(e,t_{y})$. Notice that $\ell _{(t_{y},e)}<0$ since there is a late job in $J_{t_{y}}$. Alternatively, if $d_{q}<t_{y}+1$, then

$$\begin{aligned} \ell _{(e,t_{y})}&=t_{y}+1-\max \left\{ d_{q},e+1\right\} ,\\ \ell _{(t_{y},f)}&\le f-t_{y}, \end{aligned}$$

where the last condition may hold as inequality since there may exist a job in $J_{t_{y}}$ with a due date larger than $t_{y}+1$. Thus

$$\begin{aligned} \ell _{(e,t_{y})}+\ell _{(t_{y},f)}\le f+1-\max \left\{ d_{q},e+1\right\} =\ell _{(e,f)}, \end{aligned}$$

so that condition (13) holds and Property 1 is proved.

The proof of Properties 2-4 is the same as in Theorem 4. $\square$

Appendix 6: Verifying solution optimality for $P|r_{j},p_{j}=1|\sum T_{j}$

Without loss of generality we assume that

$$\begin{aligned} r_{j}\le d_{j}\le \nu \end{aligned}$$

(21)

for all jobs $j\in J$. Indeed, if $d_{j}>\nu$ for some job j, the value of $d_{j}$ can be re-set to $\nu$ without affecting the objective value $\sum T_{j}$. If $d_{j}<r_{j}$ for some job j, the value of $d_{j}$ can be re-set to $r_{j}$ which decreases the objective value $\sum T_{j}$ by $r_{j}-d_{j}$, a constant that does not depend on the job sequence and does not affect the optimality of a schedule.

In order to formulate a fast algorithm for optimality check we first re-formulate the optimality conditions of Theorem 7 and then describe the optimality check algorithm.

Theorem 9

For a negative left arc, let $J_{(t,\tau )}^{{{\mathrm {late}}}}$ be a set of late jobs that can be moved from $[t,t+1[$ to $[\tau ,\tau +1[$ and $j^{*}$ be a job from that set with the smallest due date $d_{j^{*}}$,

$$\begin{aligned} d_{j^{*}}=\min \left\{ d_{j}|j\in J_{(t,\tau )}^{\mathrm {late}}\right\} . \end{aligned}$$

Let $a(\tau )$ be the left-most node reachable from $\tau$ via a left chain $\tau ,\ldots ,a(\tau )$ of zero length and $d_{[a(\tau ),\tau ]}$ be the maximum due date among the jobs allocated to $a(\tau ),a(\tau )+1,\ldots ,\tau$,

$$\begin{aligned} d_{[a(\tau ),\tau ]}=\max _{a(\tau )\le z\le \tau }\left\{ d_{j}|j\in J_{z}\right\} . \end{aligned}$$

(22)

There exists a negative cycle with a negative left arc $(t,\tau )$ if and only if s

$$\begin{aligned} d_{[a(\tau ),\tau ]}>\max \{\tau +1,d_{j^{*}}\}. \end{aligned}$$

(23)

Proof

Let $j^{\prime }$ be the job that delivers maximum in (22) and let $\tau ^{\prime }, a(\tau )\le \tau ^{\prime }\le \tau$, be a time slot where job $j^{\prime }$ is scheduled, $j^{\prime }\in J_{\tau ^{\prime }}$. Consider the left-chain cycle $(t,\tau ,\ldots ,\tau ^{\prime },t)$ consisting of the negative arc $(t,\tau )$, a 0-length left chain from $\tau$ to $\tau ^{\prime }$ followed by the right arc $(\tau ^{\prime },t$). The components of that cycle have the lengths:

$$\begin{aligned}&\ell _{(t,\tau )}=-\left( t+1-\max \left\{ \tau +1,d_{j^{*}}\right\} \right) ,\\&\ell _{(\tau ,\ldots ,\tau ^{\prime })}=0,\\&\ell _{(\tau ^{\prime },t)}=t+1-\max \left\{ \tau ^{\prime }+1,d_{j^{\prime } }\right\} , \end{aligned}$$

so that the length of the cycle is

$$\begin{aligned} \ell _{(t,\tau ,\ldots ,\tau ^{\prime },t)}=\max \left\{ \tau +1,d_{j^{*} }\right\} -\max \left\{ \tau ^{\prime }+1,d_{j^{\prime }}\right\} . \end{aligned}$$

If (23) holds, then

$$\begin{aligned} \max \{\tau +1,d_{j^{*}}\}<d_{j^{\prime }} \end{aligned}$$

and hence

$$\begin{aligned} \ell _{(t,\tau ,\ldots ,\tau ^{\prime },t)}<d_{j^{\prime }}-\max \left\{ \tau ^{\prime }+1,d_{j^{\prime }}\right\} \le 0, \end{aligned}$$

i.e., (23) is a sufficient condition.

To prove that (23) is a necessary condition, suppose it does not hold for the negative arc $(t,\tau )$, i.e.,

$$\begin{aligned} d_{j^{\prime }}\le \max \{\tau +1,d_{j^{*}}\}~~\text {for any }j^{\prime }\in J_{\tau ^{\prime }}\text {, }a(\tau )\le \tau ^{\prime }\le \tau . \end{aligned}$$

(24)

We show that all left-chain cycles are non-negative, which in combination with Theorem 7 implies that all possible cycles with arc $(t,\tau )$ are non-negative. Indeed, if $\tau ^{\prime }+1\le d_{j^{\prime }}$, then

$$\begin{aligned} \ell _{(t,\tau ,\ldots ,\tau ^{\prime },t)}=\max \left\{ \tau +1,d_{j^{*} }\right\} -d_{j^{\prime }} \ge 0, \end{aligned}$$

where the last inequality is by (24). Otherwise,

$$\begin{aligned} \ell _{(t,\tau ,\ldots ,\tau ^{\prime },t)}= & {} \max \left\{ \tau +1,d_{j^{*} }\right\} -\left( \tau ^{\prime }+1\right) \\\ge & {} \left( \tau +1\right) -\left( \tau ^{\prime }+1\right) \ge 0. \end{aligned}$$

$\square$

The following corollary serves as the basis for our optimality check algorithm.

Corollary 1

Let $(t_{1},\tau )$ and $(t_{2},\tau )$ be two negative arcs with the same end-node $\tau$, and let $j_{1}^{*}$ and $j_{2}^{*}$ be two late jobs associated with these arcs, i.e., $j_{1}^{*}$ and $j_{2}^{*}$ are scheduled in $[t_{1},t_{1}+1[$ and $[t_{2},t_{2}+1[$, respectively, and they define the lengths of the corresponding arcs. If

$$\begin{aligned} d_{j_{1}^{*}}\le d_{j_{2}^{*}} \end{aligned}$$

and $j^{*}=j_{1}^{*}$ does not satisfy the conditions of Theorem 9, then both left-chain cycles with arc $(t_{1},\tau )$ and with arc $(t_{2},\tau )$ are non-negative.

Proof

Since condition (23) does not hold for $j^{*}=j_{1}^{*}$,

$$\begin{aligned} d_{[a(\tau ),\tau ]}\le \max \{\tau +1,d_{j_{1}^{*}}\}. \end{aligned}$$

Moreover, $\max \{\tau +1,d_{j_{1}^{*}}\}\le \max \{\tau +1,d_{j_{2}^{*}} \}$, so that condition (23) does not hold for $j^{*} =j_{2}^{*}$ as well. Hence by Theorem 9 no negative left-chain cycles exist with arc $(t_{1},\tau )$ or with arc $(t_{2},\tau )$. $\square$

Consider a single-block earliest start schedule with $\nu =\left\lceil \frac{n}{m}\right\rceil$ unit time slots $\mathcal {T}=\{0,1,\ldots ,\nu -1\}$. Corollary 1 provides the order in which negative arcs $(t,\tau )$ should be explored: late jobs $J^{\mathrm {late}}=\{j|d_{j} <C_{j}\}$ should be considered in the non-decreasing order of their due dates, so that we can eliminate non-perspective late jobs if a job with a smaller due date does not satisfy (23). Let the jobs in $J^{\mathrm {late}}$ be renumbered in the non-decreasing order of due dates. The late job $j^{*}=1$ has the smallest due date among $J^{\mathrm {late}}$ and t is its starting time, $t=C_{j^{*}}-1$. All negative left arcs which lengths depend on $d_{j^{*}}$ are of the form $(t,\tau )$ with the end-node $\tau$ belonging to the set $\mathcal {U}_{j^{*}}\cup \mathcal {V}_{j^{*}}$, where $\mathcal {U}_{j^{*}}=\{r_{j^{*}},r_{j^{*}}+1,\ldots ,d_{j^{*}}-1\}$ and $\mathcal {V}_{j^{*}}=\{d_{j^{*}},d_{j^{*}}+1,\ldots ,t-1\}$. Since

$$\begin{aligned} \max \{\tau +1,d_{j^{*}}\}=\left\{ \begin{array} [c]{ll} d_{j^{*}}, &{}\quad \text {if }\quad \tau \in \mathcal {U}_{j^{*}},\\ \tau +1, &{}\quad \text {if }\quad \tau \in \mathcal {V}_{j^{*}}, \end{array} \right. \end{aligned}$$

condition (23) can be re-written as

$$\begin{aligned} d_{[a(\tau ),\tau ]}&>d_{j^{*}}~\qquad \, \text {for }\quad \tau \in \mathcal {U}_{j^{*}}, \end{aligned}$$

(25)

$$\begin{aligned} d_{[a(\tau ),\tau ]}&>\tau +1~\quad \text {for }\quad \tau \in \mathcal {V} _{j^{*}}. \end{aligned}$$

(26)

If (25) does not hold for $\tau \in \mathcal {U}_{j^{*}}$ and (26) does not hold for $\tau \in \mathcal {V}_{j^{*}}$, then by Corollary 1 no negative left-chain cycle, originating from t or from another node, can pass via $\tau \in \mathcal {U}_{j^{*}} \cup \mathcal {V}_{j^{*}}$ and hence nodes $\mathcal {U}_{j^{*}} \cup \mathcal {V}_{j^{*}}$ can be excluded from further consideration. We perform a similar analysis with the next job $j^{*}=2$ that has the second smallest due date among late jobs. The algorithm continues until all late jobs $j^{*}\in J^{\mathrm {late}}$ are examined.

The formal description of the algorithm is presented below. We assume that the values $d_{[a(\tau ),\tau ]}$ are known for all $\tau , 0\le \tau \le \nu -1$; the procedure for finding these values is formulated later on.

Algorithm ‘Optimality Check for $P|r_{j},p_{j}=1|\sum T_{j}$ ’

Notice that the set $\mathcal {U}_{j^{*}}$ may be empty; then condition (25) is not checked in Step 5.

We introduce and analyze the O(n) Procedure ‘Calculate $d_{[a(\tau ),\tau ]}$ values’ later on. Here we explain how Steps 3–13 can be implemented in $O(n\log \frac{n}{m})$ time assuming that the initial schedule is the earliest start schedule. We also show that the time complexity reduces to O(n) if all jobs are available simultaneously ($r_{j}=0$ for all $j\in J$).

In Step 3 all values $\left\{ d_{j}|j\in J^{\mathrm {late}}\right\}$ belong to set $\mathcal {T}=\{0,1,\ldots ,\nu -1\}$ due to assumption (21); therefore algorithm ‘Distribution Counting’ (Knuth 1998) can be used to sort the numbers in O(n) time.

For efficient implementation of Steps 4–13 we maintain disjoint sets of prohibited $\tau$-nodes which have already been eliminated, specifying each such set by its first and last nodes. Eliminating nodes $\mathcal {W}_{1}$ for job $j^{*}=1$ results in the first prohibited set $I_{1}=\mathcal {W}_{1}$. Eliminating nodes $\mathcal {W}_{2}$ for job $j^{*}=2$ results in another prohibited set $I_{2}=\mathcal {W}_{2}$ located to the right of $I_{1}$, if the left node of $\mathcal {W}_{2}$ is larger than the right node of $I_{1}$, or in an extended set $I_{1}$, otherwise. Notice that the case that the right node of $\mathcal {W}_{2}$ is smaller than the left node of $I_{1}$ does not happen: if it was a case, then the whole set $\mathcal {W}_{2}$ would be located to the left of $\mathcal {W}_{1}$, and hence two elements of those sets could not satisfy $d_{1}\le d_{2}, d_{1}\in \mathcal {W}_{1}$ and $d_{2}\in \mathcal {W}_{2}$.

Fig. 21

Calculating d values

Suppose that after j iterations jobs $1,2,\ldots ,j$ have been examined and h disjoint prohibited intervals $I_{1},I_{2},\ldots ,I_{h}$ have been produced, $h\le j$. It can be shown by induction that the most recent job j with the largest due date $d_{j}$ belongs to $I_{h}$. Consider the next job $j+1$ and the nodes $\mathcal {W}_{j+1}$ that should be eliminated. Eliminating nodes $\mathcal {W}_{j+1}$ results in

(i):

another prohibited set $I_{h+1}=\mathcal {W}_{j+1}$ located to the right of $I_{h}$,

(ii):

or in an extended set $I_{h}$.

The case that the right node of $\mathcal {W}_{j+1}$ is smaller than the left node of $I_{h}$ could not happen: if it was a case, then elements $d_{j+1}\in \mathcal {W}_{j+1}$ and $d_{j}\in I_{h}$ of those sets could not satisfy $d_{j}\le d_{j+1}$.

During the course of the algorithm, no more than $\nu$ new disjoint sets $I_{h}$ are created (in accordance with (i)) and extended (in accordance with (ii)). Creating a new set takes O(1): it incurs only one comparison of the left end of $\mathcal {W}_{j+1}$ with the right end of $I_{h}$. Extending set $I_{h}$ and its possible merger with several preceding sets involves finding the position of the left end of $\mathcal {W}_{j+1}$ with respect to $I_{1},I_{2},\ldots ,I_{h}$, which can be done in $O(\log \nu )$ time, and creating one extended set, which can be done in O(1) time. Thus the total number of updates associated with sets of eliminated nodes $\mathcal {W} _{1},\mathcal {W}_{2},\ldots ,\mathcal {W}_{z}$ is $O(z\log \nu )$ or $O(n\log \nu )$ since $z\le n$.

The loops of Steps 6–8 and 9–11 consider a separate $\tau$ value no more than once, so that the time complexity of those two loops is $O(\nu )$. Thus the overall time complexity of the optimality check is $O(n\log \frac{n}{m})$, or $O(n\log n)$ in the worst case, when the number of machines is $m=1$.

Notice that if the jobs are available simultaneously ($r_{j}=0$ for all $j\in J$), the time complexity reduces to O(n) since all sets $\mathcal {W} _{1},\mathcal {W}_{2},\ldots ,\mathcal {W}_{z}$ have the same left end 0, so that there is always only one prohibited interval $I_{1}$ with the left end at 0.

It remains to formulate the procedure that finds the values $d_{[a(\tau ),\tau ]}$ for all $\tau \in \mathcal {T}$. Suppose we have determined the values $d_{[a(i),i]}$ for all $i=0,1,\ldots ,\tau -1$ and we are calculating $d_{[a(\tau ),\tau ]}$. By (22), calculating $d_{[a(\tau ),\tau ]}$ involves enumerating the following nodes $z, a(\tau )\le z\le \tau$:

(a):

node $\tau$ itself;

(b):

each node i reachable from $\tau$ via a left arc $(\tau ,i)$ of zero length;

(c):

each node reachable from i via a 0-length left chain.

We illustrate the nodes that appear in (a)-(c) in Fig. 21. In that figure, solid arcs represent 0-length left arcs of type (b) and dotted arcs represent 0-length left chains of type (c). Notice that if $\tau ^{\prime }\in [a(\tau ^{\prime \prime }),\tau ^{\prime \prime }]$ for some $\tau ^{\prime \prime }$, then $a(\tau ^{\prime \prime })$ cannot lie to the right of $a(\tau ^{\prime })$ since there exists a 0-length chain from $\tau ^{\prime \prime }$ to $\tau ^{\prime }$ and then from $\tau ^{\prime }$ to $a(\tau ^{\prime })$. This implies

$$\begin{aligned} a(\tau ^{\prime \prime })\le a(\tau ^{\prime })\le \tau ^{\prime }\le \tau ^{\prime \prime }\ \text {for }\tau ^{\prime }\in [a(\tau ^{\prime \prime }),\tau ^{\prime \prime }]. \end{aligned}$$

(27)

Furthermore, if $i\in [a(j),j]$ for some j, then a(j) cannot lie to the right of a(i) since there exists a 0-length chain from j to i and then from i to a(i); this implies $[a(i),i]\subset [a(j),j]$.

If the set $J_{\tau }^{\mathrm {early}}$ of early jobs scheduled in $[\tau ,\tau +1[$ is empty, then the nodes of type (b) and (c) do not exist. Otherwise all nodes $\tau ^{\prime }$ that satisfy (b) form the set $\{\lambda (\tau ),\lambda (\tau )+1,\ldots ,\tau -1\}$, where $\lambda (\tau )$ is the left-most node reachable from $\tau$ via a 0-length left arc,

$$\begin{aligned} \lambda (\tau )=\min _{j\in J_{\tau }^{\mathrm {early}}}\{r_{j}\}. \end{aligned}$$

Assuming that the values $d_{[a(i),i]}$ have been determined for all $i=0,1,\ldots ,\tau -1$, we can find $d_{[a(\tau ),\tau ]}$ by the formula:

$$\begin{aligned} d_{[a(\tau ),\tau ]}=\max \left\{ \max _{j\in J_{\tau }}\{d_{j}\},\max _{i\in \{\lambda (\tau ),\lambda (\tau )+1,\ldots ,\tau -1\}}d_{[a(i),i]}\right\} , \end{aligned}$$

where the first term considers node $\tau$ of case (a) and the second term enumerates nodes $i\in \{\lambda (\tau ),\lambda (\tau )+1,\ldots ,\tau -1\}$ of types (b) and (c).

In the procedure presented below, $d_{[a(0),0]}$ receives the initial value $\max _{j\in J_{0}}\{d_{j}\}$, where $J_{0}$ is the set of jobs scheduled in [0, 1[. Each next value $d_{[a(\tau ),\tau ]}$ is pre-set initially to $\max _{j\in J_{\tau }}\{d_{j}\}$ and it is then adjusted by considering the values $d_{[a(i),i]}$ for $i=\tau -1, \tau -2,~\ldots , \lambda (\tau )$. In our implementation, we do not enumerate all these i values explicitly. Instead, having examined $i=\tau -1$ and the corresponding value $d_{[a(\tau -1),\tau -1]}$, we skip $i=\tau -2, \tau -3, \ldots , a(\tau -1)$ since, by definition,

$$\begin{aligned} d_{[a(\tau -1),\tau -1]}=\max _{a(\tau -1)\le z\le \tau -1}\left\{ d_{j}|j\in J_{z}\right\} , \end{aligned}$$

and proceed with $i=a(\tau -1)-1$. Formally this approach can be formulated as follows.

Procedure ‘Calculate $d_{[a(\tau ),\tau ]}$ values for all $\tau \in T$ ’

Steps 1 and 3 consider $\tau =0,1,\ldots ,\nu -1$ and incur $O(\nu m)=O(n)$ time. In what follows we demonstrate that once the value $d_{[a(i^{*}),i^{*}]}$ is calculated for some $i=i^{*}$, that value may be involved in the subsequent calculations only once.

Consider the smallest value $\tau ^{\prime }, \tau ^{\prime }>i^{*}$, for which $i=i^{*}$ is used for updating $d_{[a(\tau ^{\prime }),\tau ^{\prime }]}$ in Step 5. This happens if $i^{*}\in [a(\tau ^{\prime }),\tau ^{\prime }]$ and there is a 0-length left arc $(\tau ^{\prime },i^{*})$. The next attempt to use $i=i^{*}$ may happen whenever another node $\tau ^{\prime \prime }$ is considered, $\tau ^{\prime \prime }>\tau ^{\prime }$, for which there exists a 0-length left arc $(\tau ^{\prime \prime },\tau ^{\prime })$. Notice that by inequality (27),

$$\begin{aligned} a(\tau ^{\prime \prime })\le a(\tau ^{\prime })\le i^{*}\le \tau ^{\prime } \le \tau ^{\prime \prime }\ \text {for }\tau ^{\prime }\in [a(\tau ^{\prime \prime }),\tau ^{\prime \prime }]. \end{aligned}$$

In Step 5, $d_{[a(\tau ^{\prime \prime }),\tau ^{\prime \prime }]}$ is updated with $d_{[a(\tau ^{\prime }),\tau ^{\prime }]}$. By definition, $d_{[a(\tau ^{\prime }),\tau ^{\prime }]}$ is the maximum due date among the jobs allocated to $\{a(\tau ^{\prime }),a(\tau ^{\prime })+1,\ldots ,i^{*},\ldots \tau ^{\prime } \}$. Therefore, in Step 6 the i value is decreased from $i=\tau ^{\prime }$ to $i=a(\tau ^{\prime })-1$ skipping all nodes $\{a(\tau ^{\prime } ),a(\tau ^{\prime })+1,\ldots ,i^{*},\ldots \tau ^{\prime }\}$, including $i^{*}$. Thus the total number of values $d_{[a(i),i]}$ involved in Step 5 in all iterations is $O(\nu )$, and the overall time complexity of Procedure ‘Calculate $d_{[a(\tau ),\tau ]}$’ is O(n). This concludes the justification that the main algorithm for the optimality check is of time complexity $O(n\log n)$ and O(n) for problems $P|r_{j},p_{j}=1|\sum T_{j}$ and $P|p_{j}=1|\sum T_{j}$, respectively.