# The Nonpermutation Flowshop Scheduling Problem: Adjustment and Bounding Procedures

Authors: Anis Gharbi; Mohamed Labidi; Mohamed Aly Louly
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We consider the makespan minimization in a flowshop environment where the job sequence does not have to be the same for all the machines. Contrarily to the classical permutation flowshop scheduling problem, this strongly NP-hard problem received very scant attention in the literature. In this paper, some improved single-machine-based adjustment procedures are proposed, and a new two-machine-based one is introduced. Based on these adjustments, new lower and upper bounding schemes are derived. Our experimental analysis shows that the proposed procedures provide promising results.


---

## Body

## 1. Introduction

In this paper, we focus on the following scheduling problem: a set ofn jobs (
1
,
…
,
n
) has to be processed on a set of m machines M
1
,
M
2
,
…
,
M
m in that order. That is, each job has to be processed first on machine M
1, then on machine M
2, and so on until performing its last operation on machine M
m. Each operation O
i
j
(
i
=
1
,
…
,
m and j
=
1
,
…
,
n
) requires an integer and deterministic processing time p
i
j. The objective is to find a feasible schedule which minimizes the makespan. We also make the following common assumptions.(i)
Each job can be processed at most on one machine at the same time.
(ii)
Each machine can process only one job at a time.
(iii)
No preemption is allowed; that is, the processing of an operation cannot be interrupted.
(iv)
All jobs are independent and are available for processing at time zero.
(v)
The machines are continuously available.In studying flowshop scheduling problems, it is usually assumed that the sequence in which each machine processes the jobs is identical on all machines. A sequence of this type is called apermutation sequence. Almost all of the research has been focused on the development of procedures to obtain permutation schedules. The main reason is probably that, in the general case involving m machines and n jobs, the total number of feasible schedules tends to (
n
!
)
m, whereas with the assumption of no job passing, the number of feasible solutions is reduced to n
!. However, identifying the best permutation schedule itself becomes very difficult, as the problem size grows bigger. Obviously, finding an optimal solution when sequence changes are permitted is more complex. Figures 1 and 2 depict the optimal solutions of the permutation and the nonpermutation flowshop instance with 3 jobs and 4 machines whose data are provided in Table 1.Table 1
Data of a 3-job-4-machine flowshop instance.
M
1
M
2
M
3
M
4
1
1
1
3
2
2
1
4
3
3
3
4
1
1
3Figure 1
Optimal permutation schedule.Figure 2
Optimal nonpermutation schedule.Several authors emphasized the worth of considering nonpermutation schedules in real life flowshop environments [1, 2]. In particular, Potts et al. [3] exhibit a family of instances for which the value of the optimal permutation schedule is worse than that of the optimal nonpermutation schedule by a factor of more than 1
/
2
m
+
1
/
2. This is a nonnegligible gap since it can reach 50% for a 4-machine flowshop instance. Also, Sviridenko [4] proposed a new approximation algorithm which delivers a permutation schedule with makespan at most O
(
m
log
⁡
m
) times of the optimal nonpermutation schedule. In this paper, we consider the nonpermutation case where the job sequence is not necessarily identical on all the machines. Using the notation of Graham et al. [5], this problem is denoted by F
|
|
C
max
⁡.Although theF
|
|
C
max
⁡ is solvable to optimality in polynomial time when m
=
2 [6], it is known to be N
P-hard in the strong sense when m
≥
3 [7]. The F
|
|
C
max
⁡ has several interesting practical applications since in several manufacturing environments (such as in glass industry, textile, and microelectronic chip), jobs have unidirectional flow with identical flow pattern.The paper is organized as follows. In Section2, we provide a literature survey of the nonpermutation flowshop as well as two closely related problems: the permutation flowshop and the jobshop scheduling problems. In Section 3, we recall several adjustment procedures from the literature and we investigate new ones. The main purpose of adjustments is to reduce the time windows of operations, mainly to achieve a better efficiency for enumerative approaches. New bounding strategies based on these adjustments are introduced in Section 4. Our experimental results are presented in Section 5. Finally, we conclude our paper by providing a synthesis of our research and indicating some directions for future research.


## 2. Literature Survey on Shop Scheduling Problems

In this section, we provide a brief overview of the existing research on the nonpermutation flowshop scheduling problem together with two closely related and much more studied problems: the permutation flowshop and the jobshop scheduling problems. Furthermore, we emphasize the most important relationships between the permutation and the nonpermutation flowshop scheduling problems.


### 2.1. The Flowshop Scheduling Problem

Since the nonpermutation flowshop scheduling problem received very scant attention in the literature, we devote this section to the case where we have identical job sequence on each machine. This problem is commonly referred to asF
m
|
prmu
|
C
max
⁡.Johnson [6] demonstrated that the two-machine problem can be solved in O
(
n
log
⁡
n
) time by the following sequencing rule. First schedule the jobs with p
1
j
≤
p
2
j in order of nondecreasing p
1
j; then schedule the remaining jobs in order of nonincreasing p
2
j. Unfortunately, the problem is no longer polynomial for larger values of m. Indeed, Garey et al. [7] showed that F
3
|
prmu
|
C
max
⁡ is strongly N
P-hard.TheF
|
prmu
|
C
max
⁡ has received an impressive interest by scheduling researchers. Indeed, the first proposed branch-and-bound algorithms have been developed by Ignall and Schrage [8] and Lomnicki [9]. In addition, several exact approaches have been devised by Grabowski [10], Carlier and Rebaï [11], and Cheng et al. [12]. All these algorithms, except the latter, can solve only instances of very limited size. Also, an effective branch-and-bound algorithm is proposed by Haouari and Ladhari [13].Many algorithms have been designed to find near optimal schedule in reasonable time. These algorithms can be classified as either constructive or based on local search. There are several constructive heuristics available (for a comprehensive review, see [14]). Nawaz et al.’s algorithm [15] (NEH) is currently considered as the most efficient constructive heuristic among others for the permutation flowshop problem. In addition, a new local search paradigm based on a truncated branch-and-bound strategy, and calledbranch-and-bound-based local search, has been implemented for the F
|
prmu
|
C
max
⁡ by Haouari and Ladhari [16] and shown to yield approximate solutions of excellent quality.The permutation flowshop problem has been tackled by several metaheuristics like simulated annealing (SA) (see [17]) and tabu search (see [18, 19]).


### 2.2. The Jobshop Scheduling Problem

In jobshop environment, each job has its own routing on machines. The jobshop problem, denoted byJ
|
|
C
max
⁡, is not only N
P-hard, but even among the members of this class, it belongs to the worst in practice. A notorious problem with 10 jobs and 10 machines given by Fisher and Thompson [20] remained unsolved for more than 25 years. Interested readers can find various jobshop-related complexity results in Brucker et al. [21–23].Several exact approaches have been proposed for the jobshop problem. In particular, an interesting branch-and-bound algorithm was proposed by Carlier and Pinson [24]. It was the first algorithm to solve optimally the notorious 10-job-10-machine jobshop problem of Fisher and Thompson [20]. This algorithm has been followed by Brucker et al. [25] and Brinkkötter and Brucker [26]. The efficiency of these algorithms relies on the concept of immediate selections leading to effective adjustments.Among the heuristics, one of the most successful approaches is the shifting bottleneck proposed by Adams et al. [27]. Numerous enhancements of this method have been proposed by Dauzere-Peres and Lasserre [28], Balas et al. [29], and Wenqi and Aihua [30].Several tabu search approaches have been designed for the jobshop problem such as Nowicki and Smutnicki [19] and Armentano and Scrich [31]. Nowicki and Smutnicki [32] presented a new algorithm for the jobshop problem using tabu search. The computational experiments showed that the algorithm not only finds shorter makespan than the best approximation approaches, but also runs in shorter time.


### 2.3. Permutation versus Nonpermutation Flowshop Scheduling Problems

In this section, we recall the main relationships and differences between permutation and nonpermutation flowshops. First, it is worth noting that both problems are symmetric. That is, the value of the optimal makespan of the original problem (denoted by the forward problem) is equal to that of its symmetric problem (denoted by the backward problem) that is obtained by reversing the routing of the jobs; that is, the jobs are first processed onM
m, then on M
m
-
1, and so on. Now, we state the following property which is proposed by Conway et al. [33].Property 1.
ForF
|
|
C
max
⁡, there exists an optimal solution having the same processing permutation on the first two machines.To see Property1, consider any solution where different orders exist on the first two machines. Then, there must be a pair of adjacent jobs, say a and b, on the first machine permutation that appear in reverse order in the permutation on the second. But these two jobs can be reversed on the first machine without increasing the start time (and thus the completion time) of any job on the second machine. Inductively, we can repeat this pairwise switching process until the permutation on the first machine is made to agree with the (original) order on the second. An immediate consequence of Property 1 is that the F
2
|
|
C
max
⁡ and the F
2
|
perm
|
C
max
⁡ are equivalent. That is, in the case of two-machine flowshop, there exists an optimal schedule which is a permutation. Consequently, the F
2
|
|
C
max
⁡ is solvable in polynomial time using Johnson’s algorithm [6]. Moreover, due to the symmetry of the F
|
|
C
max
⁡, the following property holds.Property 2.
ForF
|
|
C
max
⁡, there exists an optimal solution having the same processing permutation on the last two machines.According to the two above properties, one can deduce that there is an optimal solution which has the same permutation on the machines for the problemF
3
|
|
C
max
⁡. In other terms, the F
3
|
|
C
max
⁡ and F
3
|
perm
|
C
max
⁡ are equivalent.Garey et al. [7] showed that the problems of nonpermutation and permutation flowshop become N
P-hard in the strong sense when the number of machines is larger than 3. However, there are several polynomially solvable special cases of F
m
|
|
C
max
⁡ that result from imposing certain inequalities on the processing times. For instance, Johnson [6] observed that if max
⁡
j
p
2
j
≤
max
⁡
{
min
⁡
j
p
1
j
,
min
⁡
j
p
3
j
} holds in an F
3
|
|
C
max
⁡ instance, then the second machine is nonbottleneck, and the optimal algorithm for problem F
2
|
|
C
max
⁡ can be suitably adapted. Monma and Rinnooy Kan [34] provide a survey of these types of results.Now, consider the two-machine flowshop and assume that a time delay (or time lag) is incurred by the transfer of the jobs from the first machine to the second one. The obtained problem, denoted byF
2
|
l
j
|
C
max
⁡, is proven to be solvable in O
(
n
log
⁡
n
) time in the permutation case [35], whereas it turns to be N
P-hard in the general case [36]. Dell’Amico [37] proved that the nonpermutation case remains N
P-hard even if preemption is allowed. It is worth noting that Rebaine [38] evaluated the worst-case performance ratio between the optimal permutation and nonpermutation schedule. He observed that, even in the restricted case of two machines and unit execution time operations, the two models may generate different optimal values for the makespan. More specifically, he showed that, in the two-machine case, the performance ratio between the two optimal solutions is bounded by 2. When the operations of the n jobs are restricted to be unit execution time, this ratio is reduced to 2
-
(
3
/
(
n
+
2
)
) for the two-machine case and is m for the m-machine case.If we consider the case wheren
=
2, the optimal permutation schedule is trivially computed by taking the best permutation among the two possible ones. The problem turns to be slightly more complicated but is still polynomially solvable, if a nonpermutation optimal schedule is to be determined. Indeed, Benson and Dror [39] proved that the two-job nonpermutation flowshop is solved in O
(
n
) time.


## 2.1. The Flowshop Scheduling Problem

Since the nonpermutation flowshop scheduling problem received very scant attention in the literature, we devote this section to the case where we have identical job sequence on each machine. This problem is commonly referred to asF
m
|
prmu
|
C
max
⁡.Johnson [6] demonstrated that the two-machine problem can be solved in O
(
n
log
⁡
n
) time by the following sequencing rule. First schedule the jobs with p
1
j
≤
p
2
j in order of nondecreasing p
1
j; then schedule the remaining jobs in order of nonincreasing p
2
j. Unfortunately, the problem is no longer polynomial for larger values of m. Indeed, Garey et al. [7] showed that F
3
|
prmu
|
C
max
⁡ is strongly N
P-hard.TheF
|
prmu
|
C
max
⁡ has received an impressive interest by scheduling researchers. Indeed, the first proposed branch-and-bound algorithms have been developed by Ignall and Schrage [8] and Lomnicki [9]. In addition, several exact approaches have been devised by Grabowski [10], Carlier and Rebaï [11], and Cheng et al. [12]. All these algorithms, except the latter, can solve only instances of very limited size. Also, an effective branch-and-bound algorithm is proposed by Haouari and Ladhari [13].Many algorithms have been designed to find near optimal schedule in reasonable time. These algorithms can be classified as either constructive or based on local search. There are several constructive heuristics available (for a comprehensive review, see [14]). Nawaz et al.’s algorithm [15] (NEH) is currently considered as the most efficient constructive heuristic among others for the permutation flowshop problem. In addition, a new local search paradigm based on a truncated branch-and-bound strategy, and calledbranch-and-bound-based local search, has been implemented for the F
|
prmu
|
C
max
⁡ by Haouari and Ladhari [16] and shown to yield approximate solutions of excellent quality.The permutation flowshop problem has been tackled by several metaheuristics like simulated annealing (SA) (see [17]) and tabu search (see [18, 19]).


## 2.2. The Jobshop Scheduling Problem

In jobshop environment, each job has its own routing on machines. The jobshop problem, denoted byJ
|
|
C
max
⁡, is not only N
P-hard, but even among the members of this class, it belongs to the worst in practice. A notorious problem with 10 jobs and 10 machines given by Fisher and Thompson [20] remained unsolved for more than 25 years. Interested readers can find various jobshop-related complexity results in Brucker et al. [21–23].Several exact approaches have been proposed for the jobshop problem. In particular, an interesting branch-and-bound algorithm was proposed by Carlier and Pinson [24]. It was the first algorithm to solve optimally the notorious 10-job-10-machine jobshop problem of Fisher and Thompson [20]. This algorithm has been followed by Brucker et al. [25] and Brinkkötter and Brucker [26]. The efficiency of these algorithms relies on the concept of immediate selections leading to effective adjustments.Among the heuristics, one of the most successful approaches is the shifting bottleneck proposed by Adams et al. [27]. Numerous enhancements of this method have been proposed by Dauzere-Peres and Lasserre [28], Balas et al. [29], and Wenqi and Aihua [30].Several tabu search approaches have been designed for the jobshop problem such as Nowicki and Smutnicki [19] and Armentano and Scrich [31]. Nowicki and Smutnicki [32] presented a new algorithm for the jobshop problem using tabu search. The computational experiments showed that the algorithm not only finds shorter makespan than the best approximation approaches, but also runs in shorter time.


## 2.3. Permutation versus Nonpermutation Flowshop Scheduling Problems

In this section, we recall the main relationships and differences between permutation and nonpermutation flowshops. First, it is worth noting that both problems are symmetric. That is, the value of the optimal makespan of the original problem (denoted by the forward problem) is equal to that of its symmetric problem (denoted by the backward problem) that is obtained by reversing the routing of the jobs; that is, the jobs are first processed onM
m, then on M
m
-
1, and so on. Now, we state the following property which is proposed by Conway et al. [33].Property 1.
ForF
|
|
C
max
⁡, there exists an optimal solution having the same processing permutation on the first two machines.To see Property1, consider any solution where different orders exist on the first two machines. Then, there must be a pair of adjacent jobs, say a and b, on the first machine permutation that appear in reverse order in the permutation on the second. But these two jobs can be reversed on the first machine without increasing the start time (and thus the completion time) of any job on the second machine. Inductively, we can repeat this pairwise switching process until the permutation on the first machine is made to agree with the (original) order on the second. An immediate consequence of Property 1 is that the F
2
|
|
C
max
⁡ and the F
2
|
perm
|
C
max
⁡ are equivalent. That is, in the case of two-machine flowshop, there exists an optimal schedule which is a permutation. Consequently, the F
2
|
|
C
max
⁡ is solvable in polynomial time using Johnson’s algorithm [6]. Moreover, due to the symmetry of the F
|
|
C
max
⁡, the following property holds.Property 2.
ForF
|
|
C
max
⁡, there exists an optimal solution having the same processing permutation on the last two machines.According to the two above properties, one can deduce that there is an optimal solution which has the same permutation on the machines for the problemF
3
|
|
C
max
⁡. In other terms, the F
3
|
|
C
max
⁡ and F
3
|
perm
|
C
max
⁡ are equivalent.Garey et al. [7] showed that the problems of nonpermutation and permutation flowshop become N
P-hard in the strong sense when the number of machines is larger than 3. However, there are several polynomially solvable special cases of F
m
|
|
C
max
⁡ that result from imposing certain inequalities on the processing times. For instance, Johnson [6] observed that if max
⁡
j
p
2
j
≤
max
⁡
{
min
⁡
j
p
1
j
,
min
⁡
j
p
3
j
} holds in an F
3
|
|
C
max
⁡ instance, then the second machine is nonbottleneck, and the optimal algorithm for problem F
2
|
|
C
max
⁡ can be suitably adapted. Monma and Rinnooy Kan [34] provide a survey of these types of results.Now, consider the two-machine flowshop and assume that a time delay (or time lag) is incurred by the transfer of the jobs from the first machine to the second one. The obtained problem, denoted byF
2
|
l
j
|
C
max
⁡, is proven to be solvable in O
(
n
log
⁡
n
) time in the permutation case [35], whereas it turns to be N
P-hard in the general case [36]. Dell’Amico [37] proved that the nonpermutation case remains N
P-hard even if preemption is allowed. It is worth noting that Rebaine [38] evaluated the worst-case performance ratio between the optimal permutation and nonpermutation schedule. He observed that, even in the restricted case of two machines and unit execution time operations, the two models may generate different optimal values for the makespan. More specifically, he showed that, in the two-machine case, the performance ratio between the two optimal solutions is bounded by 2. When the operations of the n jobs are restricted to be unit execution time, this ratio is reduced to 2
-
(
3
/
(
n
+
2
)
) for the two-machine case and is m for the m-machine case.If we consider the case wheren
=
2, the optimal permutation schedule is trivially computed by taking the best permutation among the two possible ones. The problem turns to be slightly more complicated but is still polynomially solvable, if a nonpermutation optimal schedule is to be determined. Indeed, Benson and Dror [39] proved that the two-job nonpermutation flowshop is solved in O
(
n
) time.


## 3. Adjustment Procedures

The nonpermutation flowshop problem may be represented using a disjunctive graph: two operationsi and j, executed by the same machine, cannot be simultaneously processed. Therefore with each pair (
i
,
j
) of operations, we associate a pair of disjunctive arcs [
i
,
j
]
=
(
i
,
j
)
,
(
j
,
i
). The problem is then modelled by a disjunctive graph G
=
(
C
,
D
), where C
=
(
X
,
U
) is a conjunctive graph (two operations belonging to the same job are represented by a conjunctive arc) and D is a set of disjunctions.Figure3 depicts a disjunctive graph of a 3-job-3-machine instance. The pair (a
,
b) denotes the processing of job a on machine b. Two dummy operations 0 and * are included which represent the source and the sink node, respectively. The minimum starting time denoted by r
j of an operation j is equal to the longest weighted path from 0 to j in the disjunctive graph G. Similarly for each operation j the tail q
j is the length of the longest weighted path from j to * in G.Figure 3
Disjunctive graph of a3
×
3 flowshop.In the sequel, we assume that the makespan is fixed to a trial valueC. The problem amounts to checking whether a feasible schedule with makespan less than or equal to C exists. For that purpose, a deadline d
j
=
C
-
q
j is associated with each operation j.The main purpose of adjustments is to reduce the time windows[
r
j
,
d
j
]. This kind of elimination rule has been widely studied over the last two decades, especially for solving jobshop scheduling problems. The importance of the adjustment rules is twofold. They are used in the branch-and-bound algorithm for discarding infeasible nodes, and they permit the adjustment of the release dates and deadlines, so that the lower bounds are tightened. The major breakthrough of adjustment procedures has been achieved by Carlier and Pinson [24] who solved the famous Muth and Thompson 10 × 10 jobshop instance for the first time.A nonpermutation flowshop can be viewed as a particular case of the jobshop scheduling problem. Therefore, we can apply the same adjustment procedures of this last problem to the nonpermutation flowshop. Interestingly, if an adjustment of an operation is performed, then the sets of its predecessors(
Pred
) and successors (
Succ
) according to the conjunctive graph can be adjusted using the following global adjustment algorithm (Algorithm 1; r
j
¯ and d
j
¯ denote the adjusted values of r
j and d
j, resp.).Algorithm 1:Global_Adjustment_Algorithm.
(1) For each operation(
i
)
(2)  Computer
-
i and d
-
i.
(3)  If(
r
-
i
>
r
i
) then
(4)    LetSucc
⁡
(
i
)
=
{
S
1
,
S
2
,
…
,
S
k
} the set of successors of operation i.
(5)    For(
h
=
1
,
…
,
k
-
1
)
(6)     If(
r
-
S
h
+
p
S
h
>
r
S
h
+
1
) then r
-
S
h
+
1
=
r
-
S
h
+
p
S
h.
(7)     If(
r
-
S
h
+
p
S
h
>
d
-
S
h
) then the instance is infeasible.
(8)    end (For)
(9)  end (If)
(10)   If(
d
-
i
<
d
i
) then
(11)    LetPred
⁡
(
i
)
=
{
R
1
,
R
2
,
…
,
R
k
} the set of predecessors of operation i
(12)    For(
h
=
k
,
…
,
2
)
(13)      If(
d
-
R
h
-
p
R
h
<
d
R
h
-
1
) then d
-
R
h
-
1
=
d
-
R
h
-
p
R
h.
(14)If  (
r
-
R
h
+
p
R
h
>
d
-
R
h
) then the instance is infeasible.
(15)    end (For)
(16)   end (If)
(17) end (For)
(18) If for all operations we haver
-
i
=
r
i and d
-
i
=
d
i then STOP. Otherwise, set r
i
=
r
-
i; d
i
=
d
-
i and go to line (1).


### 3.1. Adjustments from the Literature

In this section, we describe the most relevant adjustment procedures proposed in the literature.


#### 3.1.1. Disjunction-Based Adjustment

Clearly, if two operationsi and j are such that r
j
+
p
j
+
p
i
>
d
i then i cannot be scheduled after j. In this case, a disjunctive arc (
i
,
j
) can be fixed, which means that i is processed before j in any feasible schedule [24]. Therefore, the release date of job j can be adjusted to r
¯
j
=
max
⁡
(
r
j
,
r
i
+
p
i
). Similarly, the deadline of job i can be adjusted to d
¯
i
=
min
⁡
(
d
i
,
d
j
-
p
j
). More generally, after determining all the disjunctive arcs using the above rule, the release date and the deadline of each job j can be adjusted to r
¯
j
=
max
⁡
i
∈
pred
(
j
)
⁡
(
r
j
,
r
i
+
p
i
) and d
¯
i
=
min
⁡
j
∈
succ
(
i
)
⁡
(
d
i
,
d
j
-
p
j
), where pred
(
j
) and succ
(
i
) denote the sets of predecessors of j and the sets of successors of i, respectively. Obviously, the instance is infeasible if r
¯
j
+
p
j
>
d
¯
j or the obtained graph contains a cycle. Carlier and Pinson [40] proposed an algorithm allowing the determination of all immediate selections in a disjunctive graph in O
(
n
log
⁡
n
) steps.Example 1.
Consider the 5-job instance defined by Table2. We have d
3
-
p
3
=
29
<
r
1
+
p
1
=
30. Therefore, a disjunctive arc (
3,1
) should be added to the graph. Similarly, since d
5
-
p
5
=
11
<
r
1
+
p
1, then job 5 should be processed before job 1 in any feasible schedule. By applying the same rule to each job pair, we obtain the graph depicted in Figure 4. Accordingly, the release dates can be adjusted as follows:
(1)
r
1
¯
=
max
⁡
(
r
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
20
,
r
2
¯
=
max
⁡
(
r
2
,
r
1
¯
+
p
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
35
,
r
3
¯
=
r
3
=
0
,
r
4
¯
=
max
⁡
(
r
4
,
r
1
¯
+
p
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
35
,
r
5
¯
=
r
5
=
0
.Table 2
Data of the 5-job instance of Example1.
Jobs
1
2
3
4
5
r
j
15
33
0
26
0
p
j
15
1
2
8
20
d
j
46
44
31
48
31Figure 4
Disjunctive graph of the 5-job instance of Example1.The deadlines can be adjusted (decreased) in a similar way. The corresponding procedures are symmetric to those derived for the release dates. The procedure is reiterated until no adjustment can be performed.Brucker et al. [41] proposed an extension of the procedure developed by Carlier and Pinson [24] in order to fix additional disjunctive arcs. This procedure referred to as “3-set condition” may be described as follows. Assume that all the arcs derived from Carlier and Pinson procedure are fixed. Suppose that j
→
i. Let k be an operation such that r
j
+
p
j
+
p
i
+
p
k
>
d
k, r
j
+
p
j
+
p
k
+
p
i
>
d
i, and r
k
+
p
k
+
p
j
+
p
i
>
d
i; then k can be scheduled neither before j, nor between j and i, nor after i. Consequently, j cannot be processed before i in any feasible schedule, and a disjunctive arc (
i
,
j
) can therefore be fixed.


#### 3.1.2. Preemption-Based Adjustment

Carlier and Pinson [42] presented an algorithm for adjusting release dates and deadlines in the jobshop problem. This algorithm is based on Jackson’s preemptive schedule (JPS) for the one-machine problem. JPS provides the optimal solution for the 1
|
r
j
,
q
j
,
pmtn
|
C
max
⁡ in O
(
n
log
⁡
n
) time. It is constructed as follows. At the first moment t where the machine and at least one operation are available, the operation with the maximal tail is scheduled. This operation is processed either up to its completion or until a more urgent job (i.e., with larger tail) becomes available. Then, t is updated and the procedure is iterated until all operations are scheduled [43].In the following, we describe the procedure of Carlier and Pinson [42] for adjusting the release date r
c of a given operation c. Let U
B denote an upper bound of the optimal makespan and assume that Jackson’s preemptive schedule has been built until time t
=
r
c. Let p
k
+ denote the remaining processing times in the preemptive schedule. Then, r
c can be adjusted as follows.(i)
ComputeK
c
=
j
∈
J
∣
q
j
≥
q
c and K
c
+
=
j
∈
K
c
∣
p
j
+
>
0.
(ii)
Take the operations ofk
c
+ in increasing order of q
j and find the first j
1 such that r
c
+
p
c
+
∑
j
∈
k
c
+
∣
q
j
⩾
q
j
1
p
j
+
+
q
j
1
>
U
B (if any exists).
(iii)
DefineK
c
*
=
j
∈
k
c
+
∣
q
j
≥
q
j
1.
(iv)
Setr
c
¯
=
max
⁡
j
∈
K
c
*
⁡
C
j (C
j is the completion time of job j).Carlier and Pinson [42] presented an O
(
n
2
) algorithm for adjusting all release dates. Brucker et al. [25] improved this complexity by proposing an O
(
max
⁡
n
log
⁡
n
,
f
) algorithm, where f is the number of new disjunctive arcs. The idea relies on the dual version of JPS which, starting from d
=
max
⁡
j
∈
J
⁡
d
j, calculates a schedule from right to left by applying the following dual rule. At each time t which is given by a deadline or a release date of an operation, schedule backwards an incompletely scheduled operation j with d
j
≥
t and r
j
=
max
⁡
i
∈
J
⁡
r
i
∣
d
i
≥
t. Such a schedule is referred to as backwards Jackson preemptive schedule (BJPS). The release date of a given operation c can be adjusted using the following procedure.Earliest_Possible_Completion_AlgorithmStep
1. Calculate JPS up to r
c.Step
2. Calculate BJPS without c in [
r
c
,
d
] using the remaining processing times.Step
3. Schedule operation c from left to right within the idle periods of [
r
c
,
d
]. Let s
c be the completion time of operation c and set r
c
¯
=
s
c
-
p
c.Similarly, the deadline of a given operationc can be adjusted by applying the dual version of the above algorithm.Latest_Possible_Completion_AlgorithmStep
1. Calculate BJPS up to d
c.Step
2. Calculate JPS without c in [
min
⁡
j
∈
J
⁡
r
j
,
d
c
] using the remaining processing times.Step
3. Schedule operation c from right to left within the idle periods of [
min
⁡
j
∈
J
⁡
r
j
,
d
c
]. Let s
c
′ be the starting time of operation c and set d
c
¯
=
s
c
′
+
p
c.Example1 (continued). Figures 5 and 6 depict the preemption-based adjustment of the release date and the deadline of job 1, respectively. We have r
1
¯
=
s
1
-
p
1
=
37
-
15
=
22 and d
1
¯
=
s
1
′
+
p
1
=
24
+
15
=
39.Figure 5
Preemption-based adjustment ofr
1 (Example 1).Figure 6
Preemption-based adjustment ofd
1 (Example 1).


### 3.2. New Adjustment Procedures

In this section, we introduce new adjustment procedures and show that they outperform those described in the previous section.


#### 3.2.1. Improved Disjunction-Based Procedure

Recall that the disjunction-based adjustment rule consists in settingr
¯
j
=
max
⁡
i
∈
pred
(
j
)
⁡
(
r
j
,
r
i
+
p
i
) and d
¯
j
=
min
⁡
i
∈
succ
(
j
)
⁡
(
d
j
,
d
i
-
p
i
) for all j
∈
J. Interestingly, this adjustment rule can be improved in the following way.(i)
A jobi is defined as an immediate predecessor of j if there exists an arc (
i
,
j
) in the disjunctive graph.
(ii)
A jobi is defined as a predecessor of j if there exists a path (
i
,
…
,
j
) in the disjunctive graph.LetP
j denote the set of all the predecessors of j. Clearly, job j has to wait until all the jobs of P
j have been processed. Let C
max
⁡
(
P
j
) denote the minimum completion time of all jobs of P
j. Therefore, the minimum starting time of j is at least equal to max
⁡
(
r
j
,
C
max
⁡
(
P
j
)
). It is worth noting that C
max
⁡
(
P
j
) corresponds to the optimal makespan of the 1
|
r
j
|
C
max
⁡ problem defined on P
j. The 1
|
r
j
|
C
max
⁡ is solvable in O
(
n
log
⁡
n
) time by ranking jobs in nondecreasing order of their release dates. Clearly, since C
max
⁡
(
P
j
)
>
max
⁡
i
∈
P
j
⁡
(
r
i
+
p
i
), then this adjustment rule dominates the classical one proposed by Carlier and Pinson [24].Similarly, the deadline of jobj can be adjusted by setting d
-
j
=
min
⁡
(
d
j
,
max
⁡
i
∈
S
j
⁡
d
i
-
C
max
⁡
(
S
j
)
), where S
j denotes the set of all the successors of j, and C
max
⁡
(
S
j
) is the optimal makespan of 1
|
r
j
|
C
max
⁡ problem defined on S
j by setting r
j
=
max
⁡
i
∈
S
j
⁡
d
i
-
d
j.


#### 3.2.2. Semipreemption-Based Procedure

In this section, we develop a new adjustment rule which dominates the preemptive version while having the same complexity. The proposed procedure is similar, in spirit, to JPS in the sense that we apply the same algorithm with a small distinction. The idea of semipreemption has been introduced in Haouari and Gharbi [44].First, by remarking that the latest starting time of any jobj
∈
J is d
j
-
p
j, and its earliest finishing time is r
j
+
p
j, we can state the following observation.Observation 1.
Assume that there exists a jobj such that r
j
+
p
j
>
d
j
-
p
j. Then, in any nonpreemptive schedule, there is a part of job j which must be processed during the interval [
d
j
-
p
j
,
r
j
+
p
j
].According to the above observation, each jobj satisfying r
j
+
p
j
>
d
j
-
p
j is composed of a fixed and a free part. Its fixed part is the amount of time 2
p
j
-
(
d
j
-
r
j
) which must be processed in [
d
j
-
p
j
,
r
j
+
p
j
], and its free part is the amount of time p
j
′
=
d
j
-
(
r
j
+
p
j
) which has to be processed in [
r
j
,
d
j
-
p
j
]
∪
[
r
j
+
p
j
,
d
j
]. The other jobs are composed only of a free processing part p
j
′
=
p
j which has to be processed in [
r
j
,
d
j
]. Let Jackson’s semipreemptive schedule (JSPS) denote Jackson’s preemptive schedule applied on the modified instance where each job is replaced by two jobs which designate its free part and fixed part, respectively. Clearly, the preemption-based adjustment is improved if JPS is replaced by JSPS.Example 2.
Consider the 5-job instance defined by Table3.Table 3
Data of the 5-job instance of Example2.
Jobs
1
2
3
4
5
r
j
5
2
4
14
1
p
j
11
2
11
6
14
d
j
50
49
41
46
27We remark thatr
5
+
p
5
>
d
5
-
p
5. Then, job 5 has a fixed part (
5
′
) in [
13,15
] with processing time equal to 2 and a free part in [
1,27
] with processing time equal to 12. The modified instance is depicted in Table 4.Table 4
Modified instance of Example2.
Jobs
1
2
3
4
5
5′
r
j
5
2
4
14
1
13
p
j
11
2
11
6
12
2
d
j
50
49
41
46
27
15Figure7 displays the semipreemption-based adjustment of the release date of job 1. We have r
¯
1
=
s
1
-
p
1
=
18
-
11
=
7.Figure 7
Semipreemption-based adjustment ofr
1 (Example 2).The procedure is reiterated until no adjustment can be performed. The obtained adjusted release dates and deadlines are depicted in Table5.Table 5
Semipreemptive-based adjusted data of Example2.
Jobs
1
2
3
4
5
r
-
j
15
2
15
15
1
p
j
11
2
11
6
14
d
-
j
50
49
41
46
22It is worth noting that no adjustment can be made on this instance using the classical preemptive-based procedure.


#### 3.2.3. Two-Machine-Based Adjustment Procedure

First, we observe that there exists an optimalF
|
|
C
max
⁡ schedule such that there is no idle time on the first machine. That is, no job finishes processing on M
1 later than ∑
‍
p
1
j. Therefore, the deadlines on M
1 can be adjusted by setting d
-
1
j
=
min
⁡
(
d
1
j
,
∑
‍
p
1
j
) for all j
∈
J. In a similar way, using the symmetry of the F
|
|
C
max
⁡ the release dates on the last machine can be adjusted by setting r
-
m
j
=
max
⁡
(
r
m
j
,
C
-
∑
‍
p
m
j
).Now, we introduce a new approach for adjusting the deadlines on the second machine. Recall that there exists an optimal schedule such that the sequences onM
1 and M
2 are the same. Consider a particular job j
* and let σ
* denote the sequence (or permutation) of J
∖
j
* whichmaximizesthe makespan on M
2. Let C
j
* denote the completion time of j
* on M
2 and let C
-
max
⁡
(
σ
*
) denote an upper bound on the completion time of σ
* on M
2. Clearly, we have C
j
*
≤
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
2
j
*. Consequently, the deadline of j
* on machine M
2 can be adjusted to d
-
2
j
*
=
min
⁡
d
2
j
*
,
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
2
j
*.In what follows, we show how to computeC
-
max
⁡
(
σ
*
). Let σ
j
0 denote a permutation such that j
0 is the job that starts processing on M
2 after its last idle period (see Figure 8). Denote by t
i
j and C
i
j the starting time and the completion time of job j on machine M
i, respectively. Clearly, we have C
1
j
0
=
t
2
j
0.Figure 8
Illustration of the permutationσ
j
0.LetS and S
′ denote the set of jobs that are scheduled before and after j
0 in σ
j
0, respectively. Denote by x
j the variable that equals 1 if j
∈
S and 0 otherwise. We have
(2)
C
max
⁡
σ
j
0
=
∑
‍
j
∈
J
∖
j
0
p
1
j
x
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
∖
j
0
p
2
j
1
-
x
j
=
∑
j
∈
J
∖
j
0
p
1
j
-
p
2
j
x
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
∖
j
0
p
2
j
.ClearlyC
max
⁡
(
σ
j
0
) is maximized by setting x
j
=
1 for all j satisfying p
1
j
>
p
2
j and x
j
=
0 otherwise. Let C
max
⁡
(
σ
j
0
*
) denote the corresponding makespan and J
′
=
j
∈
J
:
p
1
j
>
p
2
j. We have C
max
⁡
(
σ
j
0
*
)
=
∑
j
∈
J
′
∖
j
0
(
p
1
j
-
p
2
j
)
+
p
1
j
0
+
p
2
j
0
+
∑
j
∈
J
∖
j
0
p
2
j.Two cases have to be considered.(i)
Ifj
0
∈
J
′ then
(3)
C
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
p
1
j
-
p
1
j
0
-
∑
‍
j
∈
J
′
p
2
j
-
p
2
j
0
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
p
2
j
-
p
2
j
0
=
∑
‍
j
∈
J
′
p
1
j
+
∑
‍
j
∈
J
p
2
j
-
∑
‍
j
∈
J
′
p
2
j
+
p
2
j
0
≤
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
j
0
∈
J
′
p
2
j
0
.
(ii)
Ifj
0
∉
J
′ then
(4)
C
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
p
1
j
-
∑
‍
j
∈
J
′
p
2
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
p
2
j
-
p
2
j
0
≤
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
j
0
∉
J
′
p
1
j
0
.Consequently, an upper bound C
-
max
⁡
(
σ
j
0
*
) on C
max
⁡
(
σ
j
0
*
) is obtained by
(5)
C
-
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
max
⁡
j
0
∉
J
′
p
1
j
0
,
max
⁡
j
0
∈
J
′
p
2
j
0
.Finally,C
-
max
⁡
(
σ
*
)
=
max
⁡
j
0
∈
J
⁡
C
-
max
⁡
(
σ
j
0
*
) is an upper bound on the completion time of all possible permutations on M
2. Using appropriate data structure, all the deadlines on M
2 can be adjusted in O
(
n
) time.Thanks to the symmetry of the problem, the release dates onM
m
-
1 can be adjusted by setting r
-
m
-
1
,
j
=
max
⁡
(
r
m
-
1
,
j
;
C
-
C
-
max
⁡
(
σ
*
)
), where C
-
max
⁡
(
σ
*
) is computed on the two-machine flowshop problem defined on M
m and M
m
-
1.Example 3.
Consider the 5-job-4-machine instance depicted in Table6 and let C
=
85. The values of the releases dates and the deadlines before performing any adjustment are depicted in Tables 7 and 8, respectively.Table 6
Data of 5-job-4-machine instance of Example3.
1
2
3
4
5
M
1
6
20
2
9
20
M
2
9
13
5
11
10
M
3
15
1
8
6
4
M
4
2
4
4
8
3Table 7
Initial values of release dates of Example3.
Jobs
1
2
3
4
5
M
1
0
0
0
0
0
M
2
6
20
2
9
20
M
3
15
33
7
20
30
M
4
30
34
15
26
34Table 8
Initial values of deadlines of Example3.
Jobs
1
2
3
4
5
M
1
59
67
68
60
62
M
2
68
80
73
71
78
M
3
83
81
81
77
82
M
4
85
85
85
85
85First, we have(6)
d
-
1
j
=
min
⁡
d
1
j
,
∑
‍
p
1
j
=
57
,
r
-
4
j
=
max
⁡
r
4
j
,
C
-
∑
‍
p
4
j
=
64
hhhhhhhhhhhhihhhhhh
∀
j
∈
J
.
Now, we have J
′
=
2,5 and C
-
max
⁡
(
σ
*
)
=
55. Therefore, the deadline of job 2 on M
2 can be adjusted to
(7)
d
-
22
=
min
⁡
d
22
,
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
22
=
min
⁡
80
,
max
⁡
57,55
+
13
=
70
.
Similarly, the deadline of job 5 on M
2 is adjusted to d
-
25
=
68 (instead of 78). The adjusted release dates on M
3 obtained by the two-machine-based procedure are the following:
(8)
r
-
31
=
40
;
r
-
32
=
43
;
r
-
33
=
40
;
r
-
34
=
44
,
r
-
35
=
40
.


## 3.1. Adjustments from the Literature

In this section, we describe the most relevant adjustment procedures proposed in the literature.


### 3.1.1. Disjunction-Based Adjustment

Clearly, if two operationsi and j are such that r
j
+
p
j
+
p
i
>
d
i then i cannot be scheduled after j. In this case, a disjunctive arc (
i
,
j
) can be fixed, which means that i is processed before j in any feasible schedule [24]. Therefore, the release date of job j can be adjusted to r
¯
j
=
max
⁡
(
r
j
,
r
i
+
p
i
). Similarly, the deadline of job i can be adjusted to d
¯
i
=
min
⁡
(
d
i
,
d
j
-
p
j
). More generally, after determining all the disjunctive arcs using the above rule, the release date and the deadline of each job j can be adjusted to r
¯
j
=
max
⁡
i
∈
pred
(
j
)
⁡
(
r
j
,
r
i
+
p
i
) and d
¯
i
=
min
⁡
j
∈
succ
(
i
)
⁡
(
d
i
,
d
j
-
p
j
), where pred
(
j
) and succ
(
i
) denote the sets of predecessors of j and the sets of successors of i, respectively. Obviously, the instance is infeasible if r
¯
j
+
p
j
>
d
¯
j or the obtained graph contains a cycle. Carlier and Pinson [40] proposed an algorithm allowing the determination of all immediate selections in a disjunctive graph in O
(
n
log
⁡
n
) steps.Example 1.
Consider the 5-job instance defined by Table2. We have d
3
-
p
3
=
29
<
r
1
+
p
1
=
30. Therefore, a disjunctive arc (
3,1
) should be added to the graph. Similarly, since d
5
-
p
5
=
11
<
r
1
+
p
1, then job 5 should be processed before job 1 in any feasible schedule. By applying the same rule to each job pair, we obtain the graph depicted in Figure 4. Accordingly, the release dates can be adjusted as follows:
(1)
r
1
¯
=
max
⁡
(
r
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
20
,
r
2
¯
=
max
⁡
(
r
2
,
r
1
¯
+
p
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
35
,
r
3
¯
=
r
3
=
0
,
r
4
¯
=
max
⁡
(
r
4
,
r
1
¯
+
p
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
35
,
r
5
¯
=
r
5
=
0
.Table 2
Data of the 5-job instance of Example1.
Jobs
1
2
3
4
5
r
j
15
33
0
26
0
p
j
15
1
2
8
20
d
j
46
44
31
48
31Figure 4
Disjunctive graph of the 5-job instance of Example1.The deadlines can be adjusted (decreased) in a similar way. The corresponding procedures are symmetric to those derived for the release dates. The procedure is reiterated until no adjustment can be performed.Brucker et al. [41] proposed an extension of the procedure developed by Carlier and Pinson [24] in order to fix additional disjunctive arcs. This procedure referred to as “3-set condition” may be described as follows. Assume that all the arcs derived from Carlier and Pinson procedure are fixed. Suppose that j
→
i. Let k be an operation such that r
j
+
p
j
+
p
i
+
p
k
>
d
k, r
j
+
p
j
+
p
k
+
p
i
>
d
i, and r
k
+
p
k
+
p
j
+
p
i
>
d
i; then k can be scheduled neither before j, nor between j and i, nor after i. Consequently, j cannot be processed before i in any feasible schedule, and a disjunctive arc (
i
,
j
) can therefore be fixed.


### 3.1.2. Preemption-Based Adjustment

Carlier and Pinson [42] presented an algorithm for adjusting release dates and deadlines in the jobshop problem. This algorithm is based on Jackson’s preemptive schedule (JPS) for the one-machine problem. JPS provides the optimal solution for the 1
|
r
j
,
q
j
,
pmtn
|
C
max
⁡ in O
(
n
log
⁡
n
) time. It is constructed as follows. At the first moment t where the machine and at least one operation are available, the operation with the maximal tail is scheduled. This operation is processed either up to its completion or until a more urgent job (i.e., with larger tail) becomes available. Then, t is updated and the procedure is iterated until all operations are scheduled [43].In the following, we describe the procedure of Carlier and Pinson [42] for adjusting the release date r
c of a given operation c. Let U
B denote an upper bound of the optimal makespan and assume that Jackson’s preemptive schedule has been built until time t
=
r
c. Let p
k
+ denote the remaining processing times in the preemptive schedule. Then, r
c can be adjusted as follows.(i)
ComputeK
c
=
j
∈
J
∣
q
j
≥
q
c and K
c
+
=
j
∈
K
c
∣
p
j
+
>
0.
(ii)
Take the operations ofk
c
+ in increasing order of q
j and find the first j
1 such that r
c
+
p
c
+
∑
j
∈
k
c
+
∣
q
j
⩾
q
j
1
p
j
+
+
q
j
1
>
U
B (if any exists).
(iii)
DefineK
c
*
=
j
∈
k
c
+
∣
q
j
≥
q
j
1.
(iv)
Setr
c
¯
=
max
⁡
j
∈
K
c
*
⁡
C
j (C
j is the completion time of job j).Carlier and Pinson [42] presented an O
(
n
2
) algorithm for adjusting all release dates. Brucker et al. [25] improved this complexity by proposing an O
(
max
⁡
n
log
⁡
n
,
f
) algorithm, where f is the number of new disjunctive arcs. The idea relies on the dual version of JPS which, starting from d
=
max
⁡
j
∈
J
⁡
d
j, calculates a schedule from right to left by applying the following dual rule. At each time t which is given by a deadline or a release date of an operation, schedule backwards an incompletely scheduled operation j with d
j
≥
t and r
j
=
max
⁡
i
∈
J
⁡
r
i
∣
d
i
≥
t. Such a schedule is referred to as backwards Jackson preemptive schedule (BJPS). The release date of a given operation c can be adjusted using the following procedure.Earliest_Possible_Completion_AlgorithmStep
1. Calculate JPS up to r
c.Step
2. Calculate BJPS without c in [
r
c
,
d
] using the remaining processing times.Step
3. Schedule operation c from left to right within the idle periods of [
r
c
,
d
]. Let s
c be the completion time of operation c and set r
c
¯
=
s
c
-
p
c.Similarly, the deadline of a given operationc can be adjusted by applying the dual version of the above algorithm.Latest_Possible_Completion_AlgorithmStep
1. Calculate BJPS up to d
c.Step
2. Calculate JPS without c in [
min
⁡
j
∈
J
⁡
r
j
,
d
c
] using the remaining processing times.Step
3. Schedule operation c from right to left within the idle periods of [
min
⁡
j
∈
J
⁡
r
j
,
d
c
]. Let s
c
′ be the starting time of operation c and set d
c
¯
=
s
c
′
+
p
c.Example1 (continued). Figures 5 and 6 depict the preemption-based adjustment of the release date and the deadline of job 1, respectively. We have r
1
¯
=
s
1
-
p
1
=
37
-
15
=
22 and d
1
¯
=
s
1
′
+
p
1
=
24
+
15
=
39.Figure 5
Preemption-based adjustment ofr
1 (Example 1).Figure 6
Preemption-based adjustment ofd
1 (Example 1).


## 3.1.1. Disjunction-Based Adjustment

Clearly, if two operationsi and j are such that r
j
+
p
j
+
p
i
>
d
i then i cannot be scheduled after j. In this case, a disjunctive arc (
i
,
j
) can be fixed, which means that i is processed before j in any feasible schedule [24]. Therefore, the release date of job j can be adjusted to r
¯
j
=
max
⁡
(
r
j
,
r
i
+
p
i
). Similarly, the deadline of job i can be adjusted to d
¯
i
=
min
⁡
(
d
i
,
d
j
-
p
j
). More generally, after determining all the disjunctive arcs using the above rule, the release date and the deadline of each job j can be adjusted to r
¯
j
=
max
⁡
i
∈
pred
(
j
)
⁡
(
r
j
,
r
i
+
p
i
) and d
¯
i
=
min
⁡
j
∈
succ
(
i
)
⁡
(
d
i
,
d
j
-
p
j
), where pred
(
j
) and succ
(
i
) denote the sets of predecessors of j and the sets of successors of i, respectively. Obviously, the instance is infeasible if r
¯
j
+
p
j
>
d
¯
j or the obtained graph contains a cycle. Carlier and Pinson [40] proposed an algorithm allowing the determination of all immediate selections in a disjunctive graph in O
(
n
log
⁡
n
) steps.Example 1.
Consider the 5-job instance defined by Table2. We have d
3
-
p
3
=
29
<
r
1
+
p
1
=
30. Therefore, a disjunctive arc (
3,1
) should be added to the graph. Similarly, since d
5
-
p
5
=
11
<
r
1
+
p
1, then job 5 should be processed before job 1 in any feasible schedule. By applying the same rule to each job pair, we obtain the graph depicted in Figure 4. Accordingly, the release dates can be adjusted as follows:
(1)
r
1
¯
=
max
⁡
(
r
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
20
,
r
2
¯
=
max
⁡
(
r
2
,
r
1
¯
+
p
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
35
,
r
3
¯
=
r
3
=
0
,
r
4
¯
=
max
⁡
(
r
4
,
r
1
¯
+
p
1
,
r
3
¯
+
p
3
,
r
5
¯
+
p
5
)
=
35
,
r
5
¯
=
r
5
=
0
.Table 2
Data of the 5-job instance of Example1.
Jobs
1
2
3
4
5
r
j
15
33
0
26
0
p
j
15
1
2
8
20
d
j
46
44
31
48
31Figure 4
Disjunctive graph of the 5-job instance of Example1.The deadlines can be adjusted (decreased) in a similar way. The corresponding procedures are symmetric to those derived for the release dates. The procedure is reiterated until no adjustment can be performed.Brucker et al. [41] proposed an extension of the procedure developed by Carlier and Pinson [24] in order to fix additional disjunctive arcs. This procedure referred to as “3-set condition” may be described as follows. Assume that all the arcs derived from Carlier and Pinson procedure are fixed. Suppose that j
→
i. Let k be an operation such that r
j
+
p
j
+
p
i
+
p
k
>
d
k, r
j
+
p
j
+
p
k
+
p
i
>
d
i, and r
k
+
p
k
+
p
j
+
p
i
>
d
i; then k can be scheduled neither before j, nor between j and i, nor after i. Consequently, j cannot be processed before i in any feasible schedule, and a disjunctive arc (
i
,
j
) can therefore be fixed.


## 3.1.2. Preemption-Based Adjustment

Carlier and Pinson [42] presented an algorithm for adjusting release dates and deadlines in the jobshop problem. This algorithm is based on Jackson’s preemptive schedule (JPS) for the one-machine problem. JPS provides the optimal solution for the 1
|
r
j
,
q
j
,
pmtn
|
C
max
⁡ in O
(
n
log
⁡
n
) time. It is constructed as follows. At the first moment t where the machine and at least one operation are available, the operation with the maximal tail is scheduled. This operation is processed either up to its completion or until a more urgent job (i.e., with larger tail) becomes available. Then, t is updated and the procedure is iterated until all operations are scheduled [43].In the following, we describe the procedure of Carlier and Pinson [42] for adjusting the release date r
c of a given operation c. Let U
B denote an upper bound of the optimal makespan and assume that Jackson’s preemptive schedule has been built until time t
=
r
c. Let p
k
+ denote the remaining processing times in the preemptive schedule. Then, r
c can be adjusted as follows.(i)
ComputeK
c
=
j
∈
J
∣
q
j
≥
q
c and K
c
+
=
j
∈
K
c
∣
p
j
+
>
0.
(ii)
Take the operations ofk
c
+ in increasing order of q
j and find the first j
1 such that r
c
+
p
c
+
∑
j
∈
k
c
+
∣
q
j
⩾
q
j
1
p
j
+
+
q
j
1
>
U
B (if any exists).
(iii)
DefineK
c
*
=
j
∈
k
c
+
∣
q
j
≥
q
j
1.
(iv)
Setr
c
¯
=
max
⁡
j
∈
K
c
*
⁡
C
j (C
j is the completion time of job j).Carlier and Pinson [42] presented an O
(
n
2
) algorithm for adjusting all release dates. Brucker et al. [25] improved this complexity by proposing an O
(
max
⁡
n
log
⁡
n
,
f
) algorithm, where f is the number of new disjunctive arcs. The idea relies on the dual version of JPS which, starting from d
=
max
⁡
j
∈
J
⁡
d
j, calculates a schedule from right to left by applying the following dual rule. At each time t which is given by a deadline or a release date of an operation, schedule backwards an incompletely scheduled operation j with d
j
≥
t and r
j
=
max
⁡
i
∈
J
⁡
r
i
∣
d
i
≥
t. Such a schedule is referred to as backwards Jackson preemptive schedule (BJPS). The release date of a given operation c can be adjusted using the following procedure.Earliest_Possible_Completion_AlgorithmStep
1. Calculate JPS up to r
c.Step
2. Calculate BJPS without c in [
r
c
,
d
] using the remaining processing times.Step
3. Schedule operation c from left to right within the idle periods of [
r
c
,
d
]. Let s
c be the completion time of operation c and set r
c
¯
=
s
c
-
p
c.Similarly, the deadline of a given operationc can be adjusted by applying the dual version of the above algorithm.Latest_Possible_Completion_AlgorithmStep
1. Calculate BJPS up to d
c.Step
2. Calculate JPS without c in [
min
⁡
j
∈
J
⁡
r
j
,
d
c
] using the remaining processing times.Step
3. Schedule operation c from right to left within the idle periods of [
min
⁡
j
∈
J
⁡
r
j
,
d
c
]. Let s
c
′ be the starting time of operation c and set d
c
¯
=
s
c
′
+
p
c.Example1 (continued). Figures 5 and 6 depict the preemption-based adjustment of the release date and the deadline of job 1, respectively. We have r
1
¯
=
s
1
-
p
1
=
37
-
15
=
22 and d
1
¯
=
s
1
′
+
p
1
=
24
+
15
=
39.Figure 5
Preemption-based adjustment ofr
1 (Example 1).Figure 6
Preemption-based adjustment ofd
1 (Example 1).


## 3.2. New Adjustment Procedures

In this section, we introduce new adjustment procedures and show that they outperform those described in the previous section.


### 3.2.1. Improved Disjunction-Based Procedure

Recall that the disjunction-based adjustment rule consists in settingr
¯
j
=
max
⁡
i
∈
pred
(
j
)
⁡
(
r
j
,
r
i
+
p
i
) and d
¯
j
=
min
⁡
i
∈
succ
(
j
)
⁡
(
d
j
,
d
i
-
p
i
) for all j
∈
J. Interestingly, this adjustment rule can be improved in the following way.(i)
A jobi is defined as an immediate predecessor of j if there exists an arc (
i
,
j
) in the disjunctive graph.
(ii)
A jobi is defined as a predecessor of j if there exists a path (
i
,
…
,
j
) in the disjunctive graph.LetP
j denote the set of all the predecessors of j. Clearly, job j has to wait until all the jobs of P
j have been processed. Let C
max
⁡
(
P
j
) denote the minimum completion time of all jobs of P
j. Therefore, the minimum starting time of j is at least equal to max
⁡
(
r
j
,
C
max
⁡
(
P
j
)
). It is worth noting that C
max
⁡
(
P
j
) corresponds to the optimal makespan of the 1
|
r
j
|
C
max
⁡ problem defined on P
j. The 1
|
r
j
|
C
max
⁡ is solvable in O
(
n
log
⁡
n
) time by ranking jobs in nondecreasing order of their release dates. Clearly, since C
max
⁡
(
P
j
)
>
max
⁡
i
∈
P
j
⁡
(
r
i
+
p
i
), then this adjustment rule dominates the classical one proposed by Carlier and Pinson [24].Similarly, the deadline of jobj can be adjusted by setting d
-
j
=
min
⁡
(
d
j
,
max
⁡
i
∈
S
j
⁡
d
i
-
C
max
⁡
(
S
j
)
), where S
j denotes the set of all the successors of j, and C
max
⁡
(
S
j
) is the optimal makespan of 1
|
r
j
|
C
max
⁡ problem defined on S
j by setting r
j
=
max
⁡
i
∈
S
j
⁡
d
i
-
d
j.


### 3.2.2. Semipreemption-Based Procedure

In this section, we develop a new adjustment rule which dominates the preemptive version while having the same complexity. The proposed procedure is similar, in spirit, to JPS in the sense that we apply the same algorithm with a small distinction. The idea of semipreemption has been introduced in Haouari and Gharbi [44].First, by remarking that the latest starting time of any jobj
∈
J is d
j
-
p
j, and its earliest finishing time is r
j
+
p
j, we can state the following observation.Observation 1.
Assume that there exists a jobj such that r
j
+
p
j
>
d
j
-
p
j. Then, in any nonpreemptive schedule, there is a part of job j which must be processed during the interval [
d
j
-
p
j
,
r
j
+
p
j
].According to the above observation, each jobj satisfying r
j
+
p
j
>
d
j
-
p
j is composed of a fixed and a free part. Its fixed part is the amount of time 2
p
j
-
(
d
j
-
r
j
) which must be processed in [
d
j
-
p
j
,
r
j
+
p
j
], and its free part is the amount of time p
j
′
=
d
j
-
(
r
j
+
p
j
) which has to be processed in [
r
j
,
d
j
-
p
j
]
∪
[
r
j
+
p
j
,
d
j
]. The other jobs are composed only of a free processing part p
j
′
=
p
j which has to be processed in [
r
j
,
d
j
]. Let Jackson’s semipreemptive schedule (JSPS) denote Jackson’s preemptive schedule applied on the modified instance where each job is replaced by two jobs which designate its free part and fixed part, respectively. Clearly, the preemption-based adjustment is improved if JPS is replaced by JSPS.Example 2.
Consider the 5-job instance defined by Table3.Table 3
Data of the 5-job instance of Example2.
Jobs
1
2
3
4
5
r
j
5
2
4
14
1
p
j
11
2
11
6
14
d
j
50
49
41
46
27We remark thatr
5
+
p
5
>
d
5
-
p
5. Then, job 5 has a fixed part (
5
′
) in [
13,15
] with processing time equal to 2 and a free part in [
1,27
] with processing time equal to 12. The modified instance is depicted in Table 4.Table 4
Modified instance of Example2.
Jobs
1
2
3
4
5
5′
r
j
5
2
4
14
1
13
p
j
11
2
11
6
12
2
d
j
50
49
41
46
27
15Figure7 displays the semipreemption-based adjustment of the release date of job 1. We have r
¯
1
=
s
1
-
p
1
=
18
-
11
=
7.Figure 7
Semipreemption-based adjustment ofr
1 (Example 2).The procedure is reiterated until no adjustment can be performed. The obtained adjusted release dates and deadlines are depicted in Table5.Table 5
Semipreemptive-based adjusted data of Example2.
Jobs
1
2
3
4
5
r
-
j
15
2
15
15
1
p
j
11
2
11
6
14
d
-
j
50
49
41
46
22It is worth noting that no adjustment can be made on this instance using the classical preemptive-based procedure.


### 3.2.3. Two-Machine-Based Adjustment Procedure

First, we observe that there exists an optimalF
|
|
C
max
⁡ schedule such that there is no idle time on the first machine. That is, no job finishes processing on M
1 later than ∑
‍
p
1
j. Therefore, the deadlines on M
1 can be adjusted by setting d
-
1
j
=
min
⁡
(
d
1
j
,
∑
‍
p
1
j
) for all j
∈
J. In a similar way, using the symmetry of the F
|
|
C
max
⁡ the release dates on the last machine can be adjusted by setting r
-
m
j
=
max
⁡
(
r
m
j
,
C
-
∑
‍
p
m
j
).Now, we introduce a new approach for adjusting the deadlines on the second machine. Recall that there exists an optimal schedule such that the sequences onM
1 and M
2 are the same. Consider a particular job j
* and let σ
* denote the sequence (or permutation) of J
∖
j
* whichmaximizesthe makespan on M
2. Let C
j
* denote the completion time of j
* on M
2 and let C
-
max
⁡
(
σ
*
) denote an upper bound on the completion time of σ
* on M
2. Clearly, we have C
j
*
≤
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
2
j
*. Consequently, the deadline of j
* on machine M
2 can be adjusted to d
-
2
j
*
=
min
⁡
d
2
j
*
,
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
2
j
*.In what follows, we show how to computeC
-
max
⁡
(
σ
*
). Let σ
j
0 denote a permutation such that j
0 is the job that starts processing on M
2 after its last idle period (see Figure 8). Denote by t
i
j and C
i
j the starting time and the completion time of job j on machine M
i, respectively. Clearly, we have C
1
j
0
=
t
2
j
0.Figure 8
Illustration of the permutationσ
j
0.LetS and S
′ denote the set of jobs that are scheduled before and after j
0 in σ
j
0, respectively. Denote by x
j the variable that equals 1 if j
∈
S and 0 otherwise. We have
(2)
C
max
⁡
σ
j
0
=
∑
‍
j
∈
J
∖
j
0
p
1
j
x
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
∖
j
0
p
2
j
1
-
x
j
=
∑
j
∈
J
∖
j
0
p
1
j
-
p
2
j
x
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
∖
j
0
p
2
j
.ClearlyC
max
⁡
(
σ
j
0
) is maximized by setting x
j
=
1 for all j satisfying p
1
j
>
p
2
j and x
j
=
0 otherwise. Let C
max
⁡
(
σ
j
0
*
) denote the corresponding makespan and J
′
=
j
∈
J
:
p
1
j
>
p
2
j. We have C
max
⁡
(
σ
j
0
*
)
=
∑
j
∈
J
′
∖
j
0
(
p
1
j
-
p
2
j
)
+
p
1
j
0
+
p
2
j
0
+
∑
j
∈
J
∖
j
0
p
2
j.Two cases have to be considered.(i)
Ifj
0
∈
J
′ then
(3)
C
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
p
1
j
-
p
1
j
0
-
∑
‍
j
∈
J
′
p
2
j
-
p
2
j
0
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
p
2
j
-
p
2
j
0
=
∑
‍
j
∈
J
′
p
1
j
+
∑
‍
j
∈
J
p
2
j
-
∑
‍
j
∈
J
′
p
2
j
+
p
2
j
0
≤
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
j
0
∈
J
′
p
2
j
0
.
(ii)
Ifj
0
∉
J
′ then
(4)
C
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
p
1
j
-
∑
‍
j
∈
J
′
p
2
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
p
2
j
-
p
2
j
0
≤
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
j
0
∉
J
′
p
1
j
0
.Consequently, an upper bound C
-
max
⁡
(
σ
j
0
*
) on C
max
⁡
(
σ
j
0
*
) is obtained by
(5)
C
-
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
max
⁡
j
0
∉
J
′
p
1
j
0
,
max
⁡
j
0
∈
J
′
p
2
j
0
.Finally,C
-
max
⁡
(
σ
*
)
=
max
⁡
j
0
∈
J
⁡
C
-
max
⁡
(
σ
j
0
*
) is an upper bound on the completion time of all possible permutations on M
2. Using appropriate data structure, all the deadlines on M
2 can be adjusted in O
(
n
) time.Thanks to the symmetry of the problem, the release dates onM
m
-
1 can be adjusted by setting r
-
m
-
1
,
j
=
max
⁡
(
r
m
-
1
,
j
;
C
-
C
-
max
⁡
(
σ
*
)
), where C
-
max
⁡
(
σ
*
) is computed on the two-machine flowshop problem defined on M
m and M
m
-
1.Example 3.
Consider the 5-job-4-machine instance depicted in Table6 and let C
=
85. The values of the releases dates and the deadlines before performing any adjustment are depicted in Tables 7 and 8, respectively.Table 6
Data of 5-job-4-machine instance of Example3.
1
2
3
4
5
M
1
6
20
2
9
20
M
2
9
13
5
11
10
M
3
15
1
8
6
4
M
4
2
4
4
8
3Table 7
Initial values of release dates of Example3.
Jobs
1
2
3
4
5
M
1
0
0
0
0
0
M
2
6
20
2
9
20
M
3
15
33
7
20
30
M
4
30
34
15
26
34Table 8
Initial values of deadlines of Example3.
Jobs
1
2
3
4
5
M
1
59
67
68
60
62
M
2
68
80
73
71
78
M
3
83
81
81
77
82
M
4
85
85
85
85
85First, we have(6)
d
-
1
j
=
min
⁡
d
1
j
,
∑
‍
p
1
j
=
57
,
r
-
4
j
=
max
⁡
r
4
j
,
C
-
∑
‍
p
4
j
=
64
hhhhhhhhhhhhihhhhhh
∀
j
∈
J
.
Now, we have J
′
=
2,5 and C
-
max
⁡
(
σ
*
)
=
55. Therefore, the deadline of job 2 on M
2 can be adjusted to
(7)
d
-
22
=
min
⁡
d
22
,
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
22
=
min
⁡
80
,
max
⁡
57,55
+
13
=
70
.
Similarly, the deadline of job 5 on M
2 is adjusted to d
-
25
=
68 (instead of 78). The adjusted release dates on M
3 obtained by the two-machine-based procedure are the following:
(8)
r
-
31
=
40
;
r
-
32
=
43
;
r
-
33
=
40
;
r
-
34
=
44
,
r
-
35
=
40
.


## 3.2.1. Improved Disjunction-Based Procedure

Recall that the disjunction-based adjustment rule consists in settingr
¯
j
=
max
⁡
i
∈
pred
(
j
)
⁡
(
r
j
,
r
i
+
p
i
) and d
¯
j
=
min
⁡
i
∈
succ
(
j
)
⁡
(
d
j
,
d
i
-
p
i
) for all j
∈
J. Interestingly, this adjustment rule can be improved in the following way.(i)
A jobi is defined as an immediate predecessor of j if there exists an arc (
i
,
j
) in the disjunctive graph.
(ii)
A jobi is defined as a predecessor of j if there exists a path (
i
,
…
,
j
) in the disjunctive graph.LetP
j denote the set of all the predecessors of j. Clearly, job j has to wait until all the jobs of P
j have been processed. Let C
max
⁡
(
P
j
) denote the minimum completion time of all jobs of P
j. Therefore, the minimum starting time of j is at least equal to max
⁡
(
r
j
,
C
max
⁡
(
P
j
)
). It is worth noting that C
max
⁡
(
P
j
) corresponds to the optimal makespan of the 1
|
r
j
|
C
max
⁡ problem defined on P
j. The 1
|
r
j
|
C
max
⁡ is solvable in O
(
n
log
⁡
n
) time by ranking jobs in nondecreasing order of their release dates. Clearly, since C
max
⁡
(
P
j
)
>
max
⁡
i
∈
P
j
⁡
(
r
i
+
p
i
), then this adjustment rule dominates the classical one proposed by Carlier and Pinson [24].Similarly, the deadline of jobj can be adjusted by setting d
-
j
=
min
⁡
(
d
j
,
max
⁡
i
∈
S
j
⁡
d
i
-
C
max
⁡
(
S
j
)
), where S
j denotes the set of all the successors of j, and C
max
⁡
(
S
j
) is the optimal makespan of 1
|
r
j
|
C
max
⁡ problem defined on S
j by setting r
j
=
max
⁡
i
∈
S
j
⁡
d
i
-
d
j.


## 3.2.2. Semipreemption-Based Procedure

In this section, we develop a new adjustment rule which dominates the preemptive version while having the same complexity. The proposed procedure is similar, in spirit, to JPS in the sense that we apply the same algorithm with a small distinction. The idea of semipreemption has been introduced in Haouari and Gharbi [44].First, by remarking that the latest starting time of any jobj
∈
J is d
j
-
p
j, and its earliest finishing time is r
j
+
p
j, we can state the following observation.Observation 1.
Assume that there exists a jobj such that r
j
+
p
j
>
d
j
-
p
j. Then, in any nonpreemptive schedule, there is a part of job j which must be processed during the interval [
d
j
-
p
j
,
r
j
+
p
j
].According to the above observation, each jobj satisfying r
j
+
p
j
>
d
j
-
p
j is composed of a fixed and a free part. Its fixed part is the amount of time 2
p
j
-
(
d
j
-
r
j
) which must be processed in [
d
j
-
p
j
,
r
j
+
p
j
], and its free part is the amount of time p
j
′
=
d
j
-
(
r
j
+
p
j
) which has to be processed in [
r
j
,
d
j
-
p
j
]
∪
[
r
j
+
p
j
,
d
j
]. The other jobs are composed only of a free processing part p
j
′
=
p
j which has to be processed in [
r
j
,
d
j
]. Let Jackson’s semipreemptive schedule (JSPS) denote Jackson’s preemptive schedule applied on the modified instance where each job is replaced by two jobs which designate its free part and fixed part, respectively. Clearly, the preemption-based adjustment is improved if JPS is replaced by JSPS.Example 2.
Consider the 5-job instance defined by Table3.Table 3
Data of the 5-job instance of Example2.
Jobs
1
2
3
4
5
r
j
5
2
4
14
1
p
j
11
2
11
6
14
d
j
50
49
41
46
27We remark thatr
5
+
p
5
>
d
5
-
p
5. Then, job 5 has a fixed part (
5
′
) in [
13,15
] with processing time equal to 2 and a free part in [
1,27
] with processing time equal to 12. The modified instance is depicted in Table 4.Table 4
Modified instance of Example2.
Jobs
1
2
3
4
5
5′
r
j
5
2
4
14
1
13
p
j
11
2
11
6
12
2
d
j
50
49
41
46
27
15Figure7 displays the semipreemption-based adjustment of the release date of job 1. We have r
¯
1
=
s
1
-
p
1
=
18
-
11
=
7.Figure 7
Semipreemption-based adjustment ofr
1 (Example 2).The procedure is reiterated until no adjustment can be performed. The obtained adjusted release dates and deadlines are depicted in Table5.Table 5
Semipreemptive-based adjusted data of Example2.
Jobs
1
2
3
4
5
r
-
j
15
2
15
15
1
p
j
11
2
11
6
14
d
-
j
50
49
41
46
22It is worth noting that no adjustment can be made on this instance using the classical preemptive-based procedure.


## 3.2.3. Two-Machine-Based Adjustment Procedure

First, we observe that there exists an optimalF
|
|
C
max
⁡ schedule such that there is no idle time on the first machine. That is, no job finishes processing on M
1 later than ∑
‍
p
1
j. Therefore, the deadlines on M
1 can be adjusted by setting d
-
1
j
=
min
⁡
(
d
1
j
,
∑
‍
p
1
j
) for all j
∈
J. In a similar way, using the symmetry of the F
|
|
C
max
⁡ the release dates on the last machine can be adjusted by setting r
-
m
j
=
max
⁡
(
r
m
j
,
C
-
∑
‍
p
m
j
).Now, we introduce a new approach for adjusting the deadlines on the second machine. Recall that there exists an optimal schedule such that the sequences onM
1 and M
2 are the same. Consider a particular job j
* and let σ
* denote the sequence (or permutation) of J
∖
j
* whichmaximizesthe makespan on M
2. Let C
j
* denote the completion time of j
* on M
2 and let C
-
max
⁡
(
σ
*
) denote an upper bound on the completion time of σ
* on M
2. Clearly, we have C
j
*
≤
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
2
j
*. Consequently, the deadline of j
* on machine M
2 can be adjusted to d
-
2
j
*
=
min
⁡
d
2
j
*
,
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
2
j
*.In what follows, we show how to computeC
-
max
⁡
(
σ
*
). Let σ
j
0 denote a permutation such that j
0 is the job that starts processing on M
2 after its last idle period (see Figure 8). Denote by t
i
j and C
i
j the starting time and the completion time of job j on machine M
i, respectively. Clearly, we have C
1
j
0
=
t
2
j
0.Figure 8
Illustration of the permutationσ
j
0.LetS and S
′ denote the set of jobs that are scheduled before and after j
0 in σ
j
0, respectively. Denote by x
j the variable that equals 1 if j
∈
S and 0 otherwise. We have
(2)
C
max
⁡
σ
j
0
=
∑
‍
j
∈
J
∖
j
0
p
1
j
x
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
∖
j
0
p
2
j
1
-
x
j
=
∑
j
∈
J
∖
j
0
p
1
j
-
p
2
j
x
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
∖
j
0
p
2
j
.ClearlyC
max
⁡
(
σ
j
0
) is maximized by setting x
j
=
1 for all j satisfying p
1
j
>
p
2
j and x
j
=
0 otherwise. Let C
max
⁡
(
σ
j
0
*
) denote the corresponding makespan and J
′
=
j
∈
J
:
p
1
j
>
p
2
j. We have C
max
⁡
(
σ
j
0
*
)
=
∑
j
∈
J
′
∖
j
0
(
p
1
j
-
p
2
j
)
+
p
1
j
0
+
p
2
j
0
+
∑
j
∈
J
∖
j
0
p
2
j.Two cases have to be considered.(i)
Ifj
0
∈
J
′ then
(3)
C
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
p
1
j
-
p
1
j
0
-
∑
‍
j
∈
J
′
p
2
j
-
p
2
j
0
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
p
2
j
-
p
2
j
0
=
∑
‍
j
∈
J
′
p
1
j
+
∑
‍
j
∈
J
p
2
j
-
∑
‍
j
∈
J
′
p
2
j
+
p
2
j
0
≤
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
j
0
∈
J
′
p
2
j
0
.
(ii)
Ifj
0
∉
J
′ then
(4)
C
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
p
1
j
-
∑
‍
j
∈
J
′
p
2
j
+
p
1
j
0
+
p
2
j
0
+
∑
‍
j
∈
J
p
2
j
-
p
2
j
0
≤
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
j
0
∉
J
′
p
1
j
0
.Consequently, an upper bound C
-
max
⁡
(
σ
j
0
*
) on C
max
⁡
(
σ
j
0
*
) is obtained by
(5)
C
-
max
⁡
σ
j
0
*
=
∑
‍
j
∈
J
′
(
p
1
j
-
p
2
j
)
+
∑
‍
j
∈
J
p
2
j
+
max
⁡
max
⁡
j
0
∉
J
′
p
1
j
0
,
max
⁡
j
0
∈
J
′
p
2
j
0
.Finally,C
-
max
⁡
(
σ
*
)
=
max
⁡
j
0
∈
J
⁡
C
-
max
⁡
(
σ
j
0
*
) is an upper bound on the completion time of all possible permutations on M
2. Using appropriate data structure, all the deadlines on M
2 can be adjusted in O
(
n
) time.Thanks to the symmetry of the problem, the release dates onM
m
-
1 can be adjusted by setting r
-
m
-
1
,
j
=
max
⁡
(
r
m
-
1
,
j
;
C
-
C
-
max
⁡
(
σ
*
)
), where C
-
max
⁡
(
σ
*
) is computed on the two-machine flowshop problem defined on M
m and M
m
-
1.Example 3.
Consider the 5-job-4-machine instance depicted in Table6 and let C
=
85. The values of the releases dates and the deadlines before performing any adjustment are depicted in Tables 7 and 8, respectively.Table 6
Data of 5-job-4-machine instance of Example3.
1
2
3
4
5
M
1
6
20
2
9
20
M
2
9
13
5
11
10
M
3
15
1
8
6
4
M
4
2
4
4
8
3Table 7
Initial values of release dates of Example3.
Jobs
1
2
3
4
5
M
1
0
0
0
0
0
M
2
6
20
2
9
20
M
3
15
33
7
20
30
M
4
30
34
15
26
34Table 8
Initial values of deadlines of Example3.
Jobs
1
2
3
4
5
M
1
59
67
68
60
62
M
2
68
80
73
71
78
M
3
83
81
81
77
82
M
4
85
85
85
85
85First, we have(6)
d
-
1
j
=
min
⁡
d
1
j
,
∑
‍
p
1
j
=
57
,
r
-
4
j
=
max
⁡
r
4
j
,
C
-
∑
‍
p
4
j
=
64
hhhhhhhhhhhhihhhhhh
∀
j
∈
J
.
Now, we have J
′
=
2,5 and C
-
max
⁡
(
σ
*
)
=
55. Therefore, the deadline of job 2 on M
2 can be adjusted to
(7)
d
-
22
=
min
⁡
d
22
,
max
⁡
∑
‍
p
1
j
,
C
-
max
⁡
(
σ
*
)
+
p
22
=
min
⁡
80
,
max
⁡
57,55
+
13
=
70
.
Similarly, the deadline of job 5 on M
2 is adjusted to d
-
25
=
68 (instead of 78). The adjusted release dates on M
3 obtained by the two-machine-based procedure are the following:
(8)
r
-
31
=
40
;
r
-
32
=
43
;
r
-
33
=
40
;
r
-
34
=
44
,
r
-
35
=
40
.


## 4. Bounding Procedures

In this section, we introduce lower and upper bounding procedures for the nonpermutation flowshop problem. These procedures are derived from the adjustments described in Section3.


### 4.1. Lower Bounds

A simple and efficient way of deriving a good lower bound for theF
|
|
C
max
⁡ consists in relaxing the capacities of all the machines but one denoted by M
k. The obtained problem is a one machine problem with release dates and delivery times denoted by 1
|
r
j
,
q
j
|
C
max
⁡, where r
j
=
∑
i
≺
k
p
i
j and q
j
=
∑
i
≻
k
p
i
j.Although the latter problem is stronglyN
P-hard, it is efficiently solved using the branch-and-bound algorithm developed by Carlier [45]. Let C
max
⁡
*
(
M
k
) denote the optimal makespan of the 1
|
r
j
,
q
j
|
C
max
⁡ problem defined on M
k. A valid lower bound for the F
|
|
C
max
⁡ is
(9)
L
B
0
=
max
⁡
1
≤
k
≤
m
C
max
⁡
*
(
M
k
)
.It is worth noting thatL
B
0 is considered as a good lower bound in the context of jobshop scheduling problem. Moreover, it constitutes a fundamental component in several effective heuristics, such as the well-known shifting bottleneck procedure [27]. In the sequel, we introduce an interesting way of deriving a stronger lower bound using the developed adjustment procedures.LetU
B denote an upper bound on the optimal makespan and let C
∈
[
L
B
0
,
U
B
-
1
] denote a trial value of the makespan. With each operation O
i
j is associated a release date r
i
j, a delivery time q
i
j, and a deadline d
i
j
=
C
-
q
i
j. Clearly, if after performing the adjustment procedure the instance is identified to be infeasible, then C
+
1 is a valid lower bound on the optimal makespan. Consequently, a bisection search on [
L
B
0
,
U
B
-
1
] combined with the proposed adjustment procedure provides a lower bound denoted by L
B
1 which dominates L
B
0. The computation of L
B
1 can be described as follows.Compute
L
B
1Step
1. Set C
-
=
L
B
0, C
+
=
U
B
-
1.Step
2. Let C
=
(
C
-
+
C
+
)
/
2.Step
3. Set d
j
=
C
-
q
j for all j
∈
J.Step
4. Apply an adjustment procedure to the instance obtained in step 3. If the instance is infeasible, then set C
-
=
C
+
1. Otherwise, set C
+
=
C
-
1.Step
5. If C
-
=
C
+, then stop and set L
B
1
=
C. Else, go to step 2.In the computation ofL
B
1, we implemented the new proposed adjustment procedures. The value of U
B is equal to the makespan of the schedule obtained by applying the longest processing time (LPT) dispatching rule. It consists in scheduling in the first available machine, the available operation with longest processing time.


### 4.2. Heuristics

In this section we describe how we can use the adjustment procedures in order to construct an upper bound for the nonpermutation flowshop scheduling problem.


#### 4.2.1. HeuristicH
1

We are interested in building a nonpreemptive schedule with makespan less than or equal to a trial valueC
∈
[
L
B
,
U
B
-
1
]. First, we set d
i
j
=
C
-
q
i
j and we adjust the release dates and the deadlines using an adjustment procedure. An operation such that d
i
j
=
r
i
j
+
p
i
j is referred to as a fixed operation and is considered as already scheduled. Let L denote the list of the free (nonfixed) first operations of each job, sorted according to the nondecreasing order of their release dates. The ties are settled according to the nondecreasing order of deadlines, then by the nondecreasing order of processing times. At each iteration, we use an adjustment procedure to check whether the first operation O
i
j
0 can be scheduled at its release date. In this case, we set d
i
j
0
=
r
i
j
0
+
p
i
j
0. The list L is then updated by the adjustment procedure.Now, assume that the adjustment procedure yields an infeasibility. That is, schedulingj
0 at this position is not the right decision. Therefore, we have to skip operation O
i
j
0 and move to the next operation in the list. Note that in this case the minimum starting time of O
i
j
0 is r
i
j
0
+
1. Obviously, there may be no possible operation to be scheduled at the current iteration. In this case, finding a schedule with makespan less than or equal to the trial value C is assumed as impossible. So we have to move on to C
+
1 and so on. The algorithm stops when a feasible schedule is constructed.Example 4.
Consider the 4-job-3-machine instance whose data are depicted in Table9.Table 9
Data of 4-job-3-machine instance of Example4.
M
1
M
2
M
3
1
1
86
36
2
2
55
30
3
38
16
76
4
11
62
32Assume thatL
B
=
252 and U
B
=
287 (U
B is a makespan obtained by LPT dispatching rule and it is depicted in Figure 9).Figure 9
Schedule of Example4 according to LPT rule.Assume that we are interested in constructing a schedule with makespan equal to 254. The listL contains only the first free operations in each machine. Thus, L
=
O
11
,
O
12
,
O
14
,
O
13. At the first iteration, operation O
11 is scheduled at time r
11
=
0. That is, the deadline is set to d
11
=
1. The current data is updated by applying the adjustment procedures. Thus, we have L
=
O
12
,
O
14
,
O
13
,
O
21. In the second iteration, the operation O
12 is scheduled to finish at d
12
=
3. Next, we apply the adjustment procedures. Thus, we have L
=
O
21
,
O
14
,
O
13
,
O
22. Assume that operation O
21 is scheduled at r
21
=
1 at the third iteration. That is, its deadline is set to d
21
=
87.Applying the adjustment procedures to the obtained instance yields an infeasibility. That is, the minimum starting time ofO
21 is equal to 2, and scheduling operation O
21 at the third iteration is not the right choice. Consequently, we move to the next operation, and we have L
=
O
14
,
O
13
,
O
21 and so on. The obtained schedule is depicted in Figure 10. Its makespan is equal to 254.Figure 10
Schedule provided byH
1 for Example 4.


#### 4.2.2. HeuristicH
2

Using the symmetry of the problem, a second heuristic can be obtained by applyingH
1 to the symmetric F
|
|
C
max
⁡ instance (backward).Example4 (continued).Assume that L
B
=
252 and U
B
=
254. We are interested in constructing a schedule with makespan equal to 253. The list of the free jobs is L
=
O
11
,
O
12
,
O
14
,
O
13. At the first iteration, operation O
11 is scheduled at time r
11
=
0. That is, the deadline is set to d
11
=
36. Applying the adjustment procedures to the obtained instance yields an infeasibility. That is, the minimum starting time of O
11 is equal to 1. Consequently, scheduling operation O
11 at the first iteration is not the right choice and we move to the next operation, and so on. The obtained schedule is depicted in Figure 11. Its makespan is equal to 253.Figure 11
Schedule provided byH
2 for Example 4.


#### 4.2.3. HeuristicH
3

For each value ofC, we first consider the forward instance and try to construct a feasible schedule. In case of failure, the backward instance is considered. We move on to C
+
1 only if a failure has been obtained for both forward and backward instance. Note that the obtained value of the makespan is equal to the minimum between those obtained by H
1 and H
2. However, our experimental results show that the required computational effort is substantially reduced.


#### 4.2.4. HeuristicH
4

In order to reduce the computational effort, a bisection search on the trial valueC is embedded within H
3. The value of C lies in the interval [
L
B
1
,
U
B
] where U
B denotes the makespan obtained by LPT dispatching rule. It is worth noting that if a failure is obtained for a given value C then all the values less than C will not be considered. However, it may be possible to obtain a feasible schedule if a smaller value of C is considered. Therefore, it is possible that H
4 yields a solution which is worse than that obtained by H
3. Our experimental results show that H
4 often exhibits a good trade-off between the decrease of the computation time and the decrease of the solution’s quality.


#### 4.2.5. HeuristicH
5

A randomization component is included inH
4 by selecting the operation that has to be scheduled randomly between the two first operations in the list L. In case of failure for a given value of C, the randomized procedure is performed until a feasible schedule is obtained or the maximum number of iterations is reached. In our experiments, we fixed the maximum number of iterations to 40. Also, a CPU time limit of 600 seconds has been fixed for H
5.


## 4.1. Lower Bounds

A simple and efficient way of deriving a good lower bound for theF
|
|
C
max
⁡ consists in relaxing the capacities of all the machines but one denoted by M
k. The obtained problem is a one machine problem with release dates and delivery times denoted by 1
|
r
j
,
q
j
|
C
max
⁡, where r
j
=
∑
i
≺
k
p
i
j and q
j
=
∑
i
≻
k
p
i
j.Although the latter problem is stronglyN
P-hard, it is efficiently solved using the branch-and-bound algorithm developed by Carlier [45]. Let C
max
⁡
*
(
M
k
) denote the optimal makespan of the 1
|
r
j
,
q
j
|
C
max
⁡ problem defined on M
k. A valid lower bound for the F
|
|
C
max
⁡ is
(9)
L
B
0
=
max
⁡
1
≤
k
≤
m
C
max
⁡
*
(
M
k
)
.It is worth noting thatL
B
0 is considered as a good lower bound in the context of jobshop scheduling problem. Moreover, it constitutes a fundamental component in several effective heuristics, such as the well-known shifting bottleneck procedure [27]. In the sequel, we introduce an interesting way of deriving a stronger lower bound using the developed adjustment procedures.LetU
B denote an upper bound on the optimal makespan and let C
∈
[
L
B
0
,
U
B
-
1
] denote a trial value of the makespan. With each operation O
i
j is associated a release date r
i
j, a delivery time q
i
j, and a deadline d
i
j
=
C
-
q
i
j. Clearly, if after performing the adjustment procedure the instance is identified to be infeasible, then C
+
1 is a valid lower bound on the optimal makespan. Consequently, a bisection search on [
L
B
0
,
U
B
-
1
] combined with the proposed adjustment procedure provides a lower bound denoted by L
B
1 which dominates L
B
0. The computation of L
B
1 can be described as follows.Compute
L
B
1Step
1. Set C
-
=
L
B
0, C
+
=
U
B
-
1.Step
2. Let C
=
(
C
-
+
C
+
)
/
2.Step
3. Set d
j
=
C
-
q
j for all j
∈
J.Step
4. Apply an adjustment procedure to the instance obtained in step 3. If the instance is infeasible, then set C
-
=
C
+
1. Otherwise, set C
+
=
C
-
1.Step
5. If C
-
=
C
+, then stop and set L
B
1
=
C. Else, go to step 2.In the computation ofL
B
1, we implemented the new proposed adjustment procedures. The value of U
B is equal to the makespan of the schedule obtained by applying the longest processing time (LPT) dispatching rule. It consists in scheduling in the first available machine, the available operation with longest processing time.


## 4.2. Heuristics

In this section we describe how we can use the adjustment procedures in order to construct an upper bound for the nonpermutation flowshop scheduling problem.


### 4.2.1. HeuristicH
1

We are interested in building a nonpreemptive schedule with makespan less than or equal to a trial valueC
∈
[
L
B
,
U
B
-
1
]. First, we set d
i
j
=
C
-
q
i
j and we adjust the release dates and the deadlines using an adjustment procedure. An operation such that d
i
j
=
r
i
j
+
p
i
j is referred to as a fixed operation and is considered as already scheduled. Let L denote the list of the free (nonfixed) first operations of each job, sorted according to the nondecreasing order of their release dates. The ties are settled according to the nondecreasing order of deadlines, then by the nondecreasing order of processing times. At each iteration, we use an adjustment procedure to check whether the first operation O
i
j
0 can be scheduled at its release date. In this case, we set d
i
j
0
=
r
i
j
0
+
p
i
j
0. The list L is then updated by the adjustment procedure.Now, assume that the adjustment procedure yields an infeasibility. That is, schedulingj
0 at this position is not the right decision. Therefore, we have to skip operation O
i
j
0 and move to the next operation in the list. Note that in this case the minimum starting time of O
i
j
0 is r
i
j
0
+
1. Obviously, there may be no possible operation to be scheduled at the current iteration. In this case, finding a schedule with makespan less than or equal to the trial value C is assumed as impossible. So we have to move on to C
+
1 and so on. The algorithm stops when a feasible schedule is constructed.Example 4.
Consider the 4-job-3-machine instance whose data are depicted in Table9.Table 9
Data of 4-job-3-machine instance of Example4.
M
1
M
2
M
3
1
1
86
36
2
2
55
30
3
38
16
76
4
11
62
32Assume thatL
B
=
252 and U
B
=
287 (U
B is a makespan obtained by LPT dispatching rule and it is depicted in Figure 9).Figure 9
Schedule of Example4 according to LPT rule.Assume that we are interested in constructing a schedule with makespan equal to 254. The listL contains only the first free operations in each machine. Thus, L
=
O
11
,
O
12
,
O
14
,
O
13. At the first iteration, operation O
11 is scheduled at time r
11
=
0. That is, the deadline is set to d
11
=
1. The current data is updated by applying the adjustment procedures. Thus, we have L
=
O
12
,
O
14
,
O
13
,
O
21. In the second iteration, the operation O
12 is scheduled to finish at d
12
=
3. Next, we apply the adjustment procedures. Thus, we have L
=
O
21
,
O
14
,
O
13
,
O
22. Assume that operation O
21 is scheduled at r
21
=
1 at the third iteration. That is, its deadline is set to d
21
=
87.Applying the adjustment procedures to the obtained instance yields an infeasibility. That is, the minimum starting time ofO
21 is equal to 2, and scheduling operation O
21 at the third iteration is not the right choice. Consequently, we move to the next operation, and we have L
=
O
14
,
O
13
,
O
21 and so on. The obtained schedule is depicted in Figure 10. Its makespan is equal to 254.Figure 10
Schedule provided byH
1 for Example 4.


### 4.2.2. HeuristicH
2

Using the symmetry of the problem, a second heuristic can be obtained by applyingH
1 to the symmetric F
|
|
C
max
⁡ instance (backward).Example4 (continued).Assume that L
B
=
252 and U
B
=
254. We are interested in constructing a schedule with makespan equal to 253. The list of the free jobs is L
=
O
11
,
O
12
,
O
14
,
O
13. At the first iteration, operation O
11 is scheduled at time r
11
=
0. That is, the deadline is set to d
11
=
36. Applying the adjustment procedures to the obtained instance yields an infeasibility. That is, the minimum starting time of O
11 is equal to 1. Consequently, scheduling operation O
11 at the first iteration is not the right choice and we move to the next operation, and so on. The obtained schedule is depicted in Figure 11. Its makespan is equal to 253.Figure 11
Schedule provided byH
2 for Example 4.


### 4.2.3. HeuristicH
3

For each value ofC, we first consider the forward instance and try to construct a feasible schedule. In case of failure, the backward instance is considered. We move on to C
+
1 only if a failure has been obtained for both forward and backward instance. Note that the obtained value of the makespan is equal to the minimum between those obtained by H
1 and H
2. However, our experimental results show that the required computational effort is substantially reduced.


### 4.2.4. HeuristicH
4

In order to reduce the computational effort, a bisection search on the trial valueC is embedded within H
3. The value of C lies in the interval [
L
B
1
,
U
B
] where U
B denotes the makespan obtained by LPT dispatching rule. It is worth noting that if a failure is obtained for a given value C then all the values less than C will not be considered. However, it may be possible to obtain a feasible schedule if a smaller value of C is considered. Therefore, it is possible that H
4 yields a solution which is worse than that obtained by H
3. Our experimental results show that H
4 often exhibits a good trade-off between the decrease of the computation time and the decrease of the solution’s quality.


### 4.2.5. HeuristicH
5

A randomization component is included inH
4 by selecting the operation that has to be scheduled randomly between the two first operations in the list L. In case of failure for a given value of C, the randomized procedure is performed until a feasible schedule is obtained or the maximum number of iterations is reached. In our experiments, we fixed the maximum number of iterations to 40. Also, a CPU time limit of 600 seconds has been fixed for H
5.


## 4.2.1. HeuristicH
1

We are interested in building a nonpreemptive schedule with makespan less than or equal to a trial valueC
∈
[
L
B
,
U
B
-
1
]. First, we set d
i
j
=
C
-
q
i
j and we adjust the release dates and the deadlines using an adjustment procedure. An operation such that d
i
j
=
r
i
j
+
p
i
j is referred to as a fixed operation and is considered as already scheduled. Let L denote the list of the free (nonfixed) first operations of each job, sorted according to the nondecreasing order of their release dates. The ties are settled according to the nondecreasing order of deadlines, then by the nondecreasing order of processing times. At each iteration, we use an adjustment procedure to check whether the first operation O
i
j
0 can be scheduled at its release date. In this case, we set d
i
j
0
=
r
i
j
0
+
p
i
j
0. The list L is then updated by the adjustment procedure.Now, assume that the adjustment procedure yields an infeasibility. That is, schedulingj
0 at this position is not the right decision. Therefore, we have to skip operation O
i
j
0 and move to the next operation in the list. Note that in this case the minimum starting time of O
i
j
0 is r
i
j
0
+
1. Obviously, there may be no possible operation to be scheduled at the current iteration. In this case, finding a schedule with makespan less than or equal to the trial value C is assumed as impossible. So we have to move on to C
+
1 and so on. The algorithm stops when a feasible schedule is constructed.Example 4.
Consider the 4-job-3-machine instance whose data are depicted in Table9.Table 9
Data of 4-job-3-machine instance of Example4.
M
1
M
2
M
3
1
1
86
36
2
2
55
30
3
38
16
76
4
11
62
32Assume thatL
B
=
252 and U
B
=
287 (U
B is a makespan obtained by LPT dispatching rule and it is depicted in Figure 9).Figure 9
Schedule of Example4 according to LPT rule.Assume that we are interested in constructing a schedule with makespan equal to 254. The listL contains only the first free operations in each machine. Thus, L
=
O
11
,
O
12
,
O
14
,
O
13. At the first iteration, operation O
11 is scheduled at time r
11
=
0. That is, the deadline is set to d
11
=
1. The current data is updated by applying the adjustment procedures. Thus, we have L
=
O
12
,
O
14
,
O
13
,
O
21. In the second iteration, the operation O
12 is scheduled to finish at d
12
=
3. Next, we apply the adjustment procedures. Thus, we have L
=
O
21
,
O
14
,
O
13
,
O
22. Assume that operation O
21 is scheduled at r
21
=
1 at the third iteration. That is, its deadline is set to d
21
=
87.Applying the adjustment procedures to the obtained instance yields an infeasibility. That is, the minimum starting time ofO
21 is equal to 2, and scheduling operation O
21 at the third iteration is not the right choice. Consequently, we move to the next operation, and we have L
=
O
14
,
O
13
,
O
21 and so on. The obtained schedule is depicted in Figure 10. Its makespan is equal to 254.Figure 10
Schedule provided byH
1 for Example 4.


## 4.2.2. HeuristicH
2

Using the symmetry of the problem, a second heuristic can be obtained by applyingH
1 to the symmetric F
|
|
C
max
⁡ instance (backward).Example4 (continued).Assume that L
B
=
252 and U
B
=
254. We are interested in constructing a schedule with makespan equal to 253. The list of the free jobs is L
=
O
11
,
O
12
,
O
14
,
O
13. At the first iteration, operation O
11 is scheduled at time r
11
=
0. That is, the deadline is set to d
11
=
36. Applying the adjustment procedures to the obtained instance yields an infeasibility. That is, the minimum starting time of O
11 is equal to 1. Consequently, scheduling operation O
11 at the first iteration is not the right choice and we move to the next operation, and so on. The obtained schedule is depicted in Figure 11. Its makespan is equal to 253.Figure 11
Schedule provided byH
2 for Example 4.


## 4.2.3. HeuristicH
3

For each value ofC, we first consider the forward instance and try to construct a feasible schedule. In case of failure, the backward instance is considered. We move on to C
+
1 only if a failure has been obtained for both forward and backward instance. Note that the obtained value of the makespan is equal to the minimum between those obtained by H
1 and H
2. However, our experimental results show that the required computational effort is substantially reduced.


## 4.2.4. HeuristicH
4

In order to reduce the computational effort, a bisection search on the trial valueC is embedded within H
3. The value of C lies in the interval [
L
B
1
,
U
B
] where U
B denotes the makespan obtained by LPT dispatching rule. It is worth noting that if a failure is obtained for a given value C then all the values less than C will not be considered. However, it may be possible to obtain a feasible schedule if a smaller value of C is considered. Therefore, it is possible that H
4 yields a solution which is worse than that obtained by H
3. Our experimental results show that H
4 often exhibits a good trade-off between the decrease of the computation time and the decrease of the solution’s quality.


## 4.2.5. HeuristicH
5

A randomization component is included inH
4 by selecting the operation that has to be scheduled randomly between the two first operations in the list L. In case of failure for a given value of C, the randomized procedure is performed until a feasible schedule is obtained or the maximum number of iterations is reached. In our experiments, we fixed the maximum number of iterations to 40. Also, a CPU time limit of 600 seconds has been fixed for H
5.


## 5. Computational Results

In this section, we present an empirical analysis of the performance of the proposed lower and upper bounds that are derived from our adjustment procedures. The algorithms were coded in C and compiled with Visual C++ 6.0. All the computational experiments were carried out on a Pentium IV 3.2 GHz Personal Computer with 1 GB RAM.


### 5.1. Test Generation

We carried out a series of experiments on 240 test problems that were randomly generated in the following way. The processing times are drawn from the discrete uniform distribution on[
1,100
]. The number of jobs n is taken equal to 10,20,30,40,50,60,70, and 80. The number of machines m is taken equal to 4, 5, and 6. We combined these problem characteristics to obtain 24 classes of instances. For each class, 10 instances are generated.


### 5.2. Performance of the Lower Bounds

In order to assess the impact of the proposed adjustment procedures in the computation of a lower bound, we performed a thorough comparison between the one-machine-based lower boundL
B
0 and the adjustment-based lower bound L
B
1. The objective of this analysis is to determine how many times L
B
1 improved L
B
0 and how important is this improvement. For that purpose, we first computed, for each class of instances, the percentage of times (
Opt
0
) where L
B
0 provides the optimal makespan, that is, L
B
0
=
U
B, where U
B denotes the best value of the makespan provided by our five heuristics. Clearly, L
B
1 is not computed for these instances since there is no room for improving L
B
0. Then, we computed for the remaining instances the percentage of times (
Imp
) where L
B
1 outperformed L
B
0. The importance of this improvement is emphasized in the following way. For the instances where an improvement of L
B
0 occurred, we compared the reduced gap U
B
-
L
B
1 with respect to the initial gap U
B
-
L
B
0 by computing the relative gap reduction defined as 100
(
L
B
1
-
L
B
0
)
/
(
U
B
-
L
B
0
). We reported the average gap reduction (
Red
avg
), the maximum gap reduction (
Red
max
⁡
), and the percentage of times (
Opt
1
) where the reduced gap reached 100%; that is, the optimal makespan is provided by L
B
1. Finally, the average CPU time (in seconds) required by L
B
1 is computed. At this point, it is worth noting that the CPU time of L
B
0 is always less than 0.001 sec and has not been reported.The results of our analysis are reported in Tables10, 11, and 12. These tables provide strong evidence of the dominance of our adjustment-based lower bound. Indeed, we observe that, in all problem classes, L
B
1 was able to improve L
B
0. Moreover, this improvement often occurred in more than 70% of the cases (14 out of 24 classes) and reached 100% in some few cases. In addition, the average gap reduction is in most cases larger than 30% and the maximal gap reduction exceeds 70% in 87.5% of the problem classes (21 out of 24). We observe that this gap reduction is more important for smaller values of m. Indeed, for m
=
4, the average gap reduction is always more than about 70% and the maximal gap reduction is equal to 100% in all problem classes except one. Furthermore, except for m
=
6, the bound L
B
1 was often able to provide the optimal makespan. Finally, we observe that the adjustment-based lower bound is very fast, since the average CPU time never exceeds 3.5 sec.Table 10
Performance of the lower bounds form = 4.
n
Opt
0
Imp
Redavg
Red
max
⁡
Opt
1
Time
10
30
85.71
76.32
100
50
0.04
20
50
40
71.15
92.31
0
0.06
30
50
60
73.22
100
66.67
0.17
40
70
66.67
100
100
100
0.28
50
50
40
100
100
100
0.59
60
50
60
100
100
100
1.05
70
40
50
69.89
100
66.67
1.09
80
60
50
72.5
100
50
1.49Table 11
Performance of the lower bounds form = 5.
n
Opt
0
Imp
Redavg
Red
max
⁡
Opt
1
Time
10
20
100
48.92
100
28.57
0.02
20
20
100
36.24
100
12.5
0.08
30
10
88.89
21.91
100
12.5
0.20
40
10
77.78
47.77
100
14.27
0.53
50
10
100
46.56
100
22.22
0.67
60
30
71.43
26.02
100
20
1.46
70
30
71.43
40.59
77.78
0
2.03
80
50
80
61.17
100
25
2.79Table 12
Performance of the lower bounds form = 6.
n
Opt
0
Imp
Redavg
Red
max
⁡
Opt
1
Time
10
10
77.78
21.51
46.42
0
0.04
20
0
70
34.49
78.12
0
0.19
30
10
88.89
8.40
14.28
0
0.43
40
10
44.45
11.52
25.32
0
0.95
50
0
80
27.92
85.71
0
1.35
60
20
50
36.87
85
0
2.09
70
30
57.14
23.79
85.71
0
2.88
80
30
85.71
20.19
100
16.68
3.44


### 5.3. Performance of the Heuristics

The results of a comparison of our five heuristics are depicted in Tables13, 14, and 15. For each heuristic, we provide the following.(i)
Gap: the average gap with respect to the lower boundL
B
1, where the gap of the heuristic H
i
(
i
=
1
,
…
,
5
) with makespan U
B
i is defined as 100
(
U
B
i
-
L
B
1
)
/
L
B
1.
(ii)
Time: the average CPU time
(iii)
Opt: the percentage of times where the provided solution is proven optimal (i.e., the provided makespan is equal toL
B
1)Table 13
Performance of the heuristics form = 4.
n
10
20
30
40
50
60
70
80
H
1
Gap
3.57
2.15
1.29
0.50
0.72
0.36
0.31
0.09
Time
0.76
6.65
24.78
39.09
119.40
115.96
208.47
229.45
Opt
50
10
30
60
40
60
40
50
H
2
Gap
3.88
3.08
1.00
0.49
0.80
0.77
0.80
0.56
Time
0.71
9.03
15.80
23.74
236.01
218.44
379.63
507.28
Opt
40
20
50
50
40
50
40
50
H
3
Gap
2.69
2.04
0.84
0.22
0.51
0.33
0.20
0.07
Time
0.92
10.56
29.25
34.45
256.20
140.97
271.56
260.30
Opt
60
30
60
70
60
80
50
70
H
4
Gap
3.50
2.99
2.03
0.52
0.97
0.47
0.55
0.44
Time
0.33
3.25
13.91
35.38
95.81
185.55
360.32
628.47
Opt
50
30
20
60
60
70
50
50
H
5
Gap
1.62
0.95
0.66
0.25
0.46
0.29
0.48
0.22
Time
2.72
26.90
159.39
149.75
290.63
314.27
482.18
599.55
Opt
60
50
60
90
60
80
50
30Table 14
Performance of the heuristics form = 5.
n
10
20
30
40
50
60
70
80
H
1
Gap
5.79
7.18
5.73
3.08
1.77
1.68
1.34
0.84
Time
1.66
31.35
134.53
222.54
300.07
681.81
1391.61
881.23
Opt
20
10
10
0
10
40
20
30
H
2
Gap
4.94
5.29
6.35
3.44
1.27
1.36
1.82
0.94
Time
1.62
25.63
170.30
213.26
319.76
606.98
1228.84
1652.91
Opt
20
10
10
0
10
20
10
50
H
3
Gap
3.86
4.43
4.93
2.36
0.73
0.91
1.23
0.55
Time
2.10
35.78
233.55
285.89
291.89
851.41
1882.48
1485.87
Opt
30
20
10
0
20
40
20
60
H
4
Gap
5.15
6.21
5.35
3.34
1.38
1.26
1.59
0.90
Time
0.53
6.38
24.17
59.67
152.74
281.72
537.82
907.04
Opt
20
20
10
0
10
40
10
40
H
5
Gap
2.90
3.17
3.99
2.40
0.96
1.32
1.40
1.12
Time
9.58
108.53
376.25
529.69
560
498.20
590.75
600
Opt
40
30
20
20
20
40
20
0Table 15
Performance of the heuristics form = 6.
n
10
20
30
40
50
60
70
80
H
1
Gap
9.47
7.67
6.91
5.14
3.80
1.62
2.76
2.68
Time
3.78
53.16
253.38
728.58
1063.13
1228.46
3719.93
6279.36
Opt
0
0
0
0
0
20
20
20
H
2
Gap
9.61
7.43
7.31
5.12
4.57
2.04
2.56
2.72
Time
4.28
49.41
242.64
628.18
1192.89
1173.98
2274.25
5679.16
Opt
0
0
0
10
0
0
20
40
H
3
Gap
7.99
6.49
6.23
4.48
3.33
1.27
2.32
2.18
Time
5.85
83.94
412.25
1180.35
1563.44
1476.98
4525.30
7984.64
Opt
0
0
0
10
0
20
30
40
H
4
Gap
9.75
8.29
6.90
5.45
4.72
2.55
2.81
2.78
Time
0.87
10.34
40.37
106.24
217.00
453.18
922.69
1491.32
Opt
0
0
0
10
0
10
20
20
H
5
Gap
6.39
4.84
5.61
5.05
5.01
3.43
3.31
5.04
Time
16.85
223.17
554.18
553.06
594.42
576.12
600
600
Opt
10
0
10
10
0
10
0
0We observe thatH
1 and H
2 exhibit a similar performance but are outperformed by H
3. We note that the obtained value of the makespan provided by H
3 is equal to the minimum between those obtained by H
1 and H
2. However, our experimental results show that the required computational effort is substantially reduced.The comparison ofH
3 with H
4 shows that the bisection search performed by H
4 allows a substantial decrease of the CPU time while it slightly deteriorates the quality of the obtained solution. H
4 often exhibits a good trade-off between the decrease of the computation time and the decrease of the solution’s quality. In addition, H
5 outperforms all the other heuristics for small value of n
(
n
≤
50
) by providing a small average gap. However it requires much more CPU time.For all the heuristics, we observe that the average gap increases when the number of machines increases (especially form
=
6) and decreases when the number of jobs increases. Furthermore, for the case where m
=
4, we remark that the average gap is in most cases less than 1%. The maximum number of occurrences where the average gap is less than 1% is reached for H
5 which is often able to provide the optimal solution.


## 5.1. Test Generation

We carried out a series of experiments on 240 test problems that were randomly generated in the following way. The processing times are drawn from the discrete uniform distribution on[
1,100
]. The number of jobs n is taken equal to 10,20,30,40,50,60,70, and 80. The number of machines m is taken equal to 4, 5, and 6. We combined these problem characteristics to obtain 24 classes of instances. For each class, 10 instances are generated.


## 5.2. Performance of the Lower Bounds

In order to assess the impact of the proposed adjustment procedures in the computation of a lower bound, we performed a thorough comparison between the one-machine-based lower boundL
B
0 and the adjustment-based lower bound L
B
1. The objective of this analysis is to determine how many times L
B
1 improved L
B
0 and how important is this improvement. For that purpose, we first computed, for each class of instances, the percentage of times (
Opt
0
) where L
B
0 provides the optimal makespan, that is, L
B
0
=
U
B, where U
B denotes the best value of the makespan provided by our five heuristics. Clearly, L
B
1 is not computed for these instances since there is no room for improving L
B
0. Then, we computed for the remaining instances the percentage of times (
Imp
) where L
B
1 outperformed L
B
0. The importance of this improvement is emphasized in the following way. For the instances where an improvement of L
B
0 occurred, we compared the reduced gap U
B
-
L
B
1 with respect to the initial gap U
B
-
L
B
0 by computing the relative gap reduction defined as 100
(
L
B
1
-
L
B
0
)
/
(
U
B
-
L
B
0
). We reported the average gap reduction (
Red
avg
), the maximum gap reduction (
Red
max
⁡
), and the percentage of times (
Opt
1
) where the reduced gap reached 100%; that is, the optimal makespan is provided by L
B
1. Finally, the average CPU time (in seconds) required by L
B
1 is computed. At this point, it is worth noting that the CPU time of L
B
0 is always less than 0.001 sec and has not been reported.The results of our analysis are reported in Tables10, 11, and 12. These tables provide strong evidence of the dominance of our adjustment-based lower bound. Indeed, we observe that, in all problem classes, L
B
1 was able to improve L
B
0. Moreover, this improvement often occurred in more than 70% of the cases (14 out of 24 classes) and reached 100% in some few cases. In addition, the average gap reduction is in most cases larger than 30% and the maximal gap reduction exceeds 70% in 87.5% of the problem classes (21 out of 24). We observe that this gap reduction is more important for smaller values of m. Indeed, for m
=
4, the average gap reduction is always more than about 70% and the maximal gap reduction is equal to 100% in all problem classes except one. Furthermore, except for m
=
6, the bound L
B
1 was often able to provide the optimal makespan. Finally, we observe that the adjustment-based lower bound is very fast, since the average CPU time never exceeds 3.5 sec.Table 10
Performance of the lower bounds form = 4.
n
Opt
0
Imp
Redavg
Red
max
⁡
Opt
1
Time
10
30
85.71
76.32
100
50
0.04
20
50
40
71.15
92.31
0
0.06
30
50
60
73.22
100
66.67
0.17
40
70
66.67
100
100
100
0.28
50
50
40
100
100
100
0.59
60
50
60
100
100
100
1.05
70
40
50
69.89
100
66.67
1.09
80
60
50
72.5
100
50
1.49Table 11
Performance of the lower bounds form = 5.
n
Opt
0
Imp
Redavg
Red
max
⁡
Opt
1
Time
10
20
100
48.92
100
28.57
0.02
20
20
100
36.24
100
12.5
0.08
30
10
88.89
21.91
100
12.5
0.20
40
10
77.78
47.77
100
14.27
0.53
50
10
100
46.56
100
22.22
0.67
60
30
71.43
26.02
100
20
1.46
70
30
71.43
40.59
77.78
0
2.03
80
50
80
61.17
100
25
2.79Table 12
Performance of the lower bounds form = 6.
n
Opt
0
Imp
Redavg
Red
max
⁡
Opt
1
Time
10
10
77.78
21.51
46.42
0
0.04
20
0
70
34.49
78.12
0
0.19
30
10
88.89
8.40
14.28
0
0.43
40
10
44.45
11.52
25.32
0
0.95
50
0
80
27.92
85.71
0
1.35
60
20
50
36.87
85
0
2.09
70
30
57.14
23.79
85.71
0
2.88
80
30
85.71
20.19
100
16.68
3.44


## 5.3. Performance of the Heuristics

The results of a comparison of our five heuristics are depicted in Tables13, 14, and 15. For each heuristic, we provide the following.(i)
Gap: the average gap with respect to the lower boundL
B
1, where the gap of the heuristic H
i
(
i
=
1
,
…
,
5
) with makespan U
B
i is defined as 100
(
U
B
i
-
L
B
1
)
/
L
B
1.
(ii)
Time: the average CPU time
(iii)
Opt: the percentage of times where the provided solution is proven optimal (i.e., the provided makespan is equal toL
B
1)Table 13
Performance of the heuristics form = 4.
n
10
20
30
40
50
60
70
80
H
1
Gap
3.57
2.15
1.29
0.50
0.72
0.36
0.31
0.09
Time
0.76
6.65
24.78
39.09
119.40
115.96
208.47
229.45
Opt
50
10
30
60
40
60
40
50
H
2
Gap
3.88
3.08
1.00
0.49
0.80
0.77
0.80
0.56
Time
0.71
9.03
15.80
23.74
236.01
218.44
379.63
507.28
Opt
40
20
50
50
40
50
40
50
H
3
Gap
2.69
2.04
0.84
0.22
0.51
0.33
0.20
0.07
Time
0.92
10.56
29.25
34.45
256.20
140.97
271.56
260.30
Opt
60
30
60
70
60
80
50
70
H
4
Gap
3.50
2.99
2.03
0.52
0.97
0.47
0.55
0.44
Time
0.33
3.25
13.91
35.38
95.81
185.55
360.32
628.47
Opt
50
30
20
60
60
70
50
50
H
5
Gap
1.62
0.95
0.66
0.25
0.46
0.29
0.48
0.22
Time
2.72
26.90
159.39
149.75
290.63
314.27
482.18
599.55
Opt
60
50
60
90
60
80
50
30Table 14
Performance of the heuristics form = 5.
n
10
20
30
40
50
60
70
80
H
1
Gap
5.79
7.18
5.73
3.08
1.77
1.68
1.34
0.84
Time
1.66
31.35
134.53
222.54
300.07
681.81
1391.61
881.23
Opt
20
10
10
0
10
40
20
30
H
2
Gap
4.94
5.29
6.35
3.44
1.27
1.36
1.82
0.94
Time
1.62
25.63
170.30
213.26
319.76
606.98
1228.84
1652.91
Opt
20
10
10
0
10
20
10
50
H
3
Gap
3.86
4.43
4.93
2.36
0.73
0.91
1.23
0.55
Time
2.10
35.78
233.55
285.89
291.89
851.41
1882.48
1485.87
Opt
30
20
10
0
20
40
20
60
H
4
Gap
5.15
6.21
5.35
3.34
1.38
1.26
1.59
0.90
Time
0.53
6.38
24.17
59.67
152.74
281.72
537.82
907.04
Opt
20
20
10
0
10
40
10
40
H
5
Gap
2.90
3.17
3.99
2.40
0.96
1.32
1.40
1.12
Time
9.58
108.53
376.25
529.69
560
498.20
590.75
600
Opt
40
30
20
20
20
40
20
0Table 15
Performance of the heuristics form = 6.
n
10
20
30
40
50
60
70
80
H
1
Gap
9.47
7.67
6.91
5.14
3.80
1.62
2.76
2.68
Time
3.78
53.16
253.38
728.58
1063.13
1228.46
3719.93
6279.36
Opt
0
0
0
0
0
20
20
20
H
2
Gap
9.61
7.43
7.31
5.12
4.57
2.04
2.56
2.72
Time
4.28
49.41
242.64
628.18
1192.89
1173.98
2274.25
5679.16
Opt
0
0
0
10
0
0
20
40
H
3
Gap
7.99
6.49
6.23
4.48
3.33
1.27
2.32
2.18
Time
5.85
83.94
412.25
1180.35
1563.44
1476.98
4525.30
7984.64
Opt
0
0
0
10
0
20
30
40
H
4
Gap
9.75
8.29
6.90
5.45
4.72
2.55
2.81
2.78
Time
0.87
10.34
40.37
106.24
217.00
453.18
922.69
1491.32
Opt
0
0
0
10
0
10
20
20
H
5
Gap
6.39
4.84
5.61
5.05
5.01
3.43
3.31
5.04
Time
16.85
223.17
554.18
553.06
594.42
576.12
600
600
Opt
10
0
10
10
0
10
0
0We observe thatH
1 and H
2 exhibit a similar performance but are outperformed by H
3. We note that the obtained value of the makespan provided by H
3 is equal to the minimum between those obtained by H
1 and H
2. However, our experimental results show that the required computational effort is substantially reduced.The comparison ofH
3 with H
4 shows that the bisection search performed by H
4 allows a substantial decrease of the CPU time while it slightly deteriorates the quality of the obtained solution. H
4 often exhibits a good trade-off between the decrease of the computation time and the decrease of the solution’s quality. In addition, H
5 outperforms all the other heuristics for small value of n
(
n
≤
50
) by providing a small average gap. However it requires much more CPU time.For all the heuristics, we observe that the average gap increases when the number of machines increases (especially form
=
6) and decreases when the number of jobs increases. Furthermore, for the case where m
=
4, we remark that the average gap is in most cases less than 1%. The maximum number of occurrences where the average gap is less than 1% is reached for H
5 which is often able to provide the optimal solution.


## 6. Conclusion

In this paper, we present new adjustment and bounding procedures for the nonpermutation flowshop scheduling problem. We improve the main proposed adjustment procedures of the literature and develop new ones. The resulting adjustments have been efficiently used to derive lower and upper bounds for the problem. Our experimental results show that the developed bounds provide good results especially for small values of the number of machines. In particular, a heuristic based on randomization and bisection search seems to exhibit promising performance.This research can be extended by incorporating all the new adjustment procedures and the developed lower and upper bounds in a branch-and-bound algorithm. Another avenue of future investigation is to apply the adjustment procedures to the permutation flowshop and the jobshop scheduling problems.



---

*Source: 273567-2014-11-26.xml*