Proceedings of 2017 4th International Conference on

Control, Decision and Information Technologies (CoDIT'17) / April 5-7, 2017, Barcelona, Spain

A branch-and-bound algorithm for the two-machine

flow-shop problem with time delays

Mohamed Amine Mkadem, Aziz Moukrim and Mehdi Serairi

Sorbonne universités, Université de technologie de Compiègne, CNRS,
UMR 7253 Heudiasyc - CS 60 319 - 60 203 Compiègne cedex.
Email: {mohamed-amine.mkadem, aziz.moukrim, mehdi.serairi}@hds.utc.fr

Abstract—We address the flow-shop scheduling problem with machines and F 2|pi,j = 1, lj ∈ {0, T }|Cmax for which a
two machines and time delays in order to minimize the makespan, polynomial-time algorithm was proposed by [11].
i.e, the maximum completion time. We propose an exact algorithm
based on a branch-and-bound enumeration scheme, for which we As far as we know, the main contributions for F 2|lj |Cmax
introduce a heuristic method based on a local search technique are those of [3] and [11], in which a set of lower bounds
and three dominance rules. Finally, we present a computer was proposed. Heuristic approaches were also investigated by
simulation of the branch-and-bound algorithm, which was carried [3]. Precisely, [3] introduced four constructive heuristics and a
out on a set of 360 instances. The results show that our branch- Tabu Search algorithm. It should be noted that [3] implemented
and-bound method outperforms the state of the art exact method. an exact method based on the branch-and-bound method of
Keywords: Two-machine flow-shop, time delays, makespan, [1], which was originally made for the job-shop problem.
exact method, branch-and-bound. Indeed, each F 2|lj |Cmax instance can be modeled as a job-
shop instance with n jobs and n + 2 machines, in which each
job j in J must be executed on three machines. j must be
I. I NTRODUCTION assigned first to machine 1 during p1,j time units. Then, it
In this paper, we tackle the flow-shop scheduling problem is executed during lj time units on machine j + 1. Finally,
with two machines and time delays, denoted by F 2|lj |Cmax . j is scheduled on the machine n + 2 during p2,j time units.
Let us consider an instance I = (J, p1 , l, p2 ) of F 2|lj |Cmax , The implemented version of [3] consists in applying all of his
where: lower bounds and approximation procedures at the root node
of the branch-and-bound method of [1].
• J = {1, 2, ..., n} is a set of n jobs. The objective of this paper consists in proposing a branch-
• p1 and p2 are the vectors of processing times on the and-bound algorithm for F 2|lj |Cmax . We introduce a set of
first and the second machine, respectively. lower bounds, an upper bound and three dominance rules.

• l is the vector of time delays. The remainder of this paper is organized as follows. In
Section 2, we provide a detailed description of the branch-
Each job j has two operations O1,j and O2,j . The first opera- and-bound algorithm. Computational experiments on a set
tion O1,j must be executed during p1,j time units on the first of randomly generated instances are reported in Section 3.
machine M1 . The second operation O2,j has to be executed Finally, some concluding remarks are given in Section 4.
during p2,j time units on the second machine M2 . A feasible
schedule is such that at most one operation is processed at
a time on a given machine. In addition, the operations are II. T HE B RANCH - AND -B OUND A LGORITHM
executed without preemption, where interruption and switching In what follows, the makespan value of a schedule S is
of operations are not allowed. Finally, for each job j in J a denoted by Cmax (S) and the optimal makespan value of an
time delay of at minimum lj time units must separate the end ∗
instance I is given by Cmax (I). Furthermore, the starting time
of operation O1,j and the start of O2,j . The objective consists of Ok,j in a schedule S is given by tk,j (S), j in J; k in {1, 2}
in finding a feasible schedule that minimizes the makespan, and Jσ represents the set of jobs that constitute a job sequence
usually denoted by Cmax . σ. Moreover, we denote by Ωσ the set of all schedules where
F 2|lj |Cmax is NP-hard in the strong sense even with unit- the job sequence σ is fixed first on M1 .
time operations [12]. Specific cases were discussed in the In this section, we present an exact method for F 2|lj |Cmax
literature and were proved to be NP-hard in the strong sense. based on a branch-and-bound enumeration scheme. We adopt
For example, we recall the following problems: F 2|p1,j = the same branching scheme as in [8] and [9]. To that aim, let
p2,j , lj |Cmax [4], F 2|p1,j = p2,j = 1, lj |Cmax [12] and us introduce the following observation.
F 2|p1,j = p2,j , lj ∈ {0, T }|Cmax [11]. Moreover, [3] tackled
the preemptive flow-shop problem F 2|pmtn, lj |Cmax and Observation 1: Let σ be a fixed job sequence on M1 that
showed that this problem is NP-complete. However, there exist contains all jobs of J. The schedules of Ωσ in which the
well solvable cases: the well-known F 2||Cmax problem where jobs are executed on M2 according to the nondecreasing order
the time delays are equal to zero [5], F 2π|lj |Cmax [6] where of their arrival times (i.e. t1,j (S) + p1,j + lj , S in Ωσ ) are
feasible schedules have the same processing order on both dominant.

978-1-5090-6465-6/17/$31.00 ©2017 European Union 0690 -1-

 Proceedings of 2017 4th International Conference on
Control, Decision and Information Technologies (CoDIT'17) / April 5-7, 2017, Barcelona, Spain

According to this observation, our branch-and-bound enu- We start by the O(n) basic lower bound that was proposed
merates job sequences on M1 as follows. At a given node by [11].
Nσ1 of the search tree of the branch-and-bound, a partial job n
X n
X
sequence σ1 of LNσ1 jobs is fixed on M1 , where LNσ1 is the LB1 = max( p1,j + min (lj + p2,j ), p2,j +
1≤j≤n
level of the node Nσ1 . Note that the level of the root node j=1 j=1 (1)
is zero, one for the root sons, and so on. In order to reduce min (lj + p1,j ), max (p1,j + lj + p2,j )).
1≤j≤n 1≤j≤n
the number of explored nodes in the search tree, we invoke at
each node Nσ1 the following features:
The second lower bound was introduced by [3]. In this
lower bound, it is supposed that all jobs are executed at t = 0
• A preprocessing procedure.
on M1 . We obtain then a single-machine scheduling problem
• Several lower bounds. with release dates rj = p1,j + lj and processing times pj =
p2,j , j in J. If we denote by Ir the obtained instance, LB2 =
• An upper bound based on a local search technique ∗
Cmax (Ir ) is a valid lower bound on the F 2|lj |Cmax original
applied on the current sub-sequence. instance. This lower bound can be determined in O(n log n)-
time by scheduling the jobs in a nondecreasing order of rj , j
• Dominance rules. in J. Similarly, if we consider the reversed instance in which
the operations are done in the reverse order on each machine,
If these features fail to prune the current node Nσ1 , then
we yield a symmetric lower bound called LB3 .
a son node is created from Nσ1 for each unscheduled job j
where j is fixed after σ1 . Note that we adopt the depth-first Before proceeding further, let us consider the following
node selection strategy. proposition.
Proposition 1: ([3]) Given an instance I = (J, p1 , l, p2 ) of
A. Preprocessing procedure F 2|lj |Cmax , if it holds that:

We introduce here a preprocessing procedure based on [2] lj ≤ min (p1,i + li ), ∀j ∈ J, (2)

1≤i≤n
that aims to fix some precedence relationships between jobs
then there exists a permutation schedule that is optimal for I.
on each machine. In fact, a quick increase of the fixed set
of precedence relationships between jobs is important for the The author of [3] introduced a lower bound based on the
quality of the branch-and-bound method for many reasons. At above proposition. A new instance I¯ = (J, p1 , ¯l, p2 ) is derived
first, we can limit the branching scheme by discarding nodes from the original instance I, where the time delays are relaxed
that contradict with the determined relationships. Moreover, by setting ¯lj = min(lj , min1≤i≤n (li +p1,i )), j in J. Obviously,
the lower bounds could be enhanced by exploiting the addi- I¯ verifies condition (2). Therefore, there exists a permutation
tional information. schedule that is optimal for I, ¯ which can be determined in
O(n log n)-time using Mitten algorithm [6]. As consequence,
Interestingly, in each partial schedule S obtained at a given LB4 = Cmax ∗ ¯ is a valid lower bound on I.
(I)
node Nσ1 of the search tree, we define for each operation of
job j in J on Mk two sets of jobs ϕk,j and ψk,j , k in {1, 2}. In the following, we recall two lower bounds of [7] for
Note that ϕk,j (resp. ψk,j ) contains the jobs of J that precede F 2|lj |Cmax . These latter are based on the next proposition.
(resp. follow) j on Mk . Proposition 2: ([11]) Given an instance I = (J, p1 , l, p2 )
The preprocessing method is based on the following of F 2|lj |Cmax , if it holds that:
lemma: lj ≤ min (li + max(p1,i , p2,i )), ∀j ∈ J, (3)
1≤i≤n
Lemma 1: ([2]) Let us consider a partial schedule S of an
then there exists a permutation schedule that is optimal for I.
instance I of F 2|lj |Cmax that is obtained at the node Nσ1
and U B an upper bound on I. For each pair of jobs (i, j) in
From an instance I of F 2|lj |Cmax , we derive a new
(J\{Jσ1 })2 , if it holds that: ˜ p1 , ˜l, p2 ), where ˜lj = min(lj , min1≤i≤n (li +
instance I(J,
max(p1,i , p2,i ))). Since I˜ verifies condition (3), LB5 =
X X
p1,k + p1,j + lj + p2,j + p2,i + p2,k ≥ U B, ∗
Cmax ˜ is a valid lower bound on I. This lower bound can
(I)
k∈ϕ1,j k∈ψ2,i
be computed in O(n log n)-time using Mitten algorithm [6].
then i must precede j on M2 . Moreover, if it is true that: Interestingly, the last lower bound can be improved by
X X considering the following observation.
p1,k + p1,i + p1,j + lj + p2,j + p2,k ≥ U B,
k∈ϕ1,i k∈ψ2,j Observation 2: Let I = (J, p1 , l, p2 ) and I 0 =
(J , p01 , l0 , p02 ) be two F 2|lj |Cmax instances, where J 0 ⊂ J
0

then j must be executed before i on M1 . and for all j in J 0 , p01,j ≤ p1,j , p02,j ≤ p2,j and lj0 ≤ lj . It
∗ ∗
holds that Cmax (I) ≥ Cmax (I 0 ). Thus, a lower bound on I 0
is a valid lower bound on instance I.
B. Lower bounds
Proof: We observe that from an optimal
0
schedule of
We incorporate in our branch-and-bound the most compet- instance I, we
0
draw a feasible schedule S of instance I 0 such
∗
itive lower bounds of the literature. that Cmax (S ) ≤ Cmax (I).

0691 -2-
 Proceedings of 2017 4th International Conference on
Control, Decision and Information Technologies (CoDIT'17) / April 5-7, 2017, Barcelona, Spain

Given an instance I of F 2|lj |Cmax , we define a lower Algorithm 1 Local search exploration
bound called LB6 of [7] that consists in invoking LB5 on Require: Sub-sequence σ1
n sub-instances of I. Starting by I, the next sub-instance is Ensure: U B
made after removing the job with the minimum value of lj + 1: Using the heuristics of [3], complete the job sequence σ1
max(p1,j , p2,j ), j in J, from the current instance. in order to have a schedule S of Ωσ1 . Let σ be the obtained
job sequence on M1 .
2: Complete S in such a way that the second operations of
C. Time delays adjustments all jobs are scheduled according to Observation 1. Let π
In this section, we focus on the partial schedule obtained be the obtained job sequence on M2 .
at a given node Nσ1 of the search tree. First, we show how 3: U B ← +∞ ;
the time delays of the scheduled jobs are updated. Then, we 4: while U B > Cmax (S) do
describe how the previous lower bounds are invoked in the 5: U B ← Cmax (S);
internal nodes of the branch-and-bound search tree. To that 6: Starting from π, determine the job sequence σ on M1
aim, let σ = σ1 ⊕ σ2 be a job sequence of all jobs on M1 by scheduling the jobs according to Observation 1.
where σ1 is a fixed sub-sequence and σ2 is an arbitrary one of 7: Starting from σ, determine the job sequence π on M2
J \ Jσ1 . Let βj be the starting time on M2 of j in Jσ1 if the by scheduling the jobs according to Observation 1.
jobs of Jσ1 are scheduled on M2 with respect to their arrival 8: Update the feasible schedule S.
times. 9: end while

Proposition 3: At a given node Nσ1 and for all S in Ωσ1 ,

the time delay of each job j in J can be updated as follows: E. Dominance rules
We introduce here three new dominance rules that allow to

σ1 βj − t1,j (S) − p1,j , if j ∈ Jσ1
lj = (4) discard nodes from additional expansions in order to reduce
lj , otherwise.
the computational burden of the proposed branch-and-bound
algorithm. The three dominance rules are given by the follow-
Proof: Let us consider a node Nσ1 and a schedule S of ing three lemmas.
Ωσ1 . We show that t2,j (S) ≥ βj , for all j in Jσ1 . Therefore,
the time delay that is observed by job j is at least βj −t1,j (S)− Lemma 2: Consider an instance I of F 2|lj |Cmax and two
p1,j . jobs i and j where p1,j +lj ≤ p1,i +li , li ≤ lj +p2,j and p1,j ≤
p2,j . If there exists a schedule where i and j are adjacent on
In order to use the above described lower bounds inside M1 , then j must be executed first.
the search tree, we consider the following two instances.
0
Proof: The aim of this proof is to construct a schedule
• Iσu1 σ1
= (J, p1 , l , p2 ). S of Ω(σ1 ⊕j⊕i) from an arbitrary schedule S of Ω(σ1 ⊕i⊕j) in
0
a way that Cmax (S) = Cmax (S ). We identify two cases:
• Iσr1 = (Jσ2 , p1 , l, p2 ).
0
Case 1: j precedes i on M2
From Observation 1 and Proposition 3, the following S is derived from S by simply interchanging i and j on
corollary holds: M1 and 0
by keeping the same execution order on M2 , where
t2,k (S ) = t2,k (S), for all k in J. Therefore, it is true that
0 0
Corollary 1: Given a valid lower bound LB on t1,i (S) = t1,j (S ), t1,i (S ) + p1,i = t1,j (S) + p1,j and
F 2|lj |Cmax instances and a node Nσ1 of the search 0
t1,j (S) + p1,j + lj ≤ t2,j (S). Since t1,k (S ) = t1,k (S) for
tree, it yields that for each schedule S of Ωσ1 : all k in J\{i, j}, each job of J\{i, j} is available on M2
X before its starting time. Moreover, it holds that:
Cmax (S) ≥ max(LB(Iσu1 ), p1,j + LB(Iσr1 )). (5) 0
j∈Jσ1 t1,j (S ) + p1,j + lj ≤ t1,j (S) + p1,j + lj
0
≤ t2,j (S) = t2,j (S )
D. Upper bounds
and
In the following, we describe a new heuristic algorithm, 0
t1,i (S ) + p1,i + li = t1,j (S) + p1,j + li .
which is intended to be used on each node of the branch-
and-bound search tree. This heuristic is based on a local Since li ≤ lj + p2,j , we get:
search exploration of the partial sub-sequences. At a given 0
node Nσ1 of the search tree, we complete the fixed sub- t1,i (S ) + p1,i + li ≤ t1,j (S) + p1,j + lj + p2,j
sequence σ1 to obtain a complete job sequence σ by invoking ≤ t2,j (S) + p2,j
the constructive heuristics of [3]. From σ, we schedule on M2 0

the jobs according to the nondecreasing order of their arrival ≤ t2,i (S ).

times as in Observation 1. Then by considering the obtained From the above remarks, we conclude that all jobs are available
job sequence on M2 , σ is updated according to the arrival for processing on M2 before their starting times in S .
0

times of the jobs. This process is iterated until no amelioration

is detected on the makespan between two successive iterations. 0
Case 2: i precedes j on M2
A pseudo-code of the procedure is described in Algorithm 1. S is derived from S by simply interchanging i and j on M1

0692 -3-
 Proceedings of 2017 4th International Conference on
Control, Decision and Information Technologies (CoDIT'17) / April 5-7, 2017, Barcelona, Spain

and by0 shifting left j on M2 to locally precede i in a way that 0

on M2 before its starting time. Since p1,j + lj ≤ p1,i + li , it
t2,j (S ) = t2,i (S). Therefore, it is true that t1,i (S) = t1,j (S ), holds that:
0
t1,i (S )+p1,i = t1,j (S)+p1,j and t1,i (S)+p1,i +li ≤ t2,i (S). 0
t1,j (S ) + p1,j + lj = t1,i (S) + p1,j + lj
0 0
Since t1,k (S ) = t1,k (S) and t2,k (S ) ≥ t2,k (S) for all k in
J\{i, j}, each job of J\{i, j} is available on M2 before its ≤ t1,i (S) + p1,i + li
starting time. Since p1,j + lj ≤ p1,i + li , it holds that: ≤ t2,i (S)
0
0 ≤ t2,j (S ).
t1,j (S ) + p1,j + lj = t1,i (S) + p1,j + lj
≤ t1,i (S) + p1,i + li Moreover, since li ≤ lj + p2,j − p2,i , we have that:
0 0
≤ t2,i (S) = t2,j (S ). t1,i (S ) + p1,i + li = t1,j (S) + p1,j + li
Moreover, we have that: ≤ t1,j (S) + p1,j + lj + p2,j − p2,i
0
0
t1,i (S ) + p1,i + li
0
= t1,j (S ) + p1,j + p1,i + li ≤ t2,j (S) + p2,j − p2,i = t2,i (S ).
= t1,i (S) + p1,j + p1,i + li From the above remarks, we conclude that all jobs are available
0
≤ t2,i (S) + p1,j . for processing on M2 before their starting times in S .
Since p1,j ≤ p2,j , we get: Let us consider the following notation. We denote by
0
0 0
I(S , S, t, C) the difference between the total idle time value
0
t1,i (S ) + p1,i + li ≤ t2,i (S) + p2,j = t2,j (S ) + p2,j observed on M2 from time t to the instant C in S and that
0
≤ t2,i (S ). in S.
0

From the above remarks, we conclude that all jobs are available Lemma 4: Let us consider two partial schedules S and S
for processing on M2 before their starting times in S .
0 that are obtained at two nodes Nσ1 and Nσ0 of the search
1
tree, respectively, such that Jσ1 = Jσ0 . Moreover, let C be the
Lemma 3: Consider a valid job sequence σ on M1 that 1
maximum makespan value observed on all schedules of Ωσ1
is composed from a fixed sub-sequence σ1 and followed by and Ωσ0 . If it holds that:
an arbitrary one called σ2 . If there are two jobs i, j in Jσ2 1
0
where p1,j ≤ p1,i , p2,i ≤ p2,j , p1,j + lj ≤ p1,i + li and I(S , S, t, C) ≥ 0, ∀t ∈ {0, ..., C}, (6)
p2,j + lj ≥ p2,i + li , then j must precede i on M1 .
then the node Nσ1 can be fathomed. In this case, we say that
Proof: Let S be an arbitrary schedule of Ωσ1 ⊕(i) where 0
σ1 dominates σ1 .
job i is executed directly
0
after σ1 on M1 . From S, we
can derive a schedule S of Ωσ1 ⊕(j) without increasing the Proof:
0
It should be noted that if (6) holds then
makespan. We identify two cases: Cmax (S ) ≤ Cmax (S). Otherwise, it contradicts with the
0
assumption that I(S , S, Cmax (S), C) ≥ 0. In this proof,
Case 1: j precedes i on M2
0 we proceed as follows.0 We schedule iteratively the jobs of
In this case, S is derived from S by simply interchanging i
J\Jσ1 in S and in S , then we prove that (6) is true for
and j on M1 0and by keeping the same execution order on M2 , 0

where t2,k (S ) = t2,k (S), for all k in J. Then, it is obvious the obtained schedules. Let Sj (resp. Sj ) be the partial
0
0 0
that t1,i (S) = t1,j (S ) and t1,i (S ) + p1,i = t1,j (S) + p1,j . schedule obtained from S (resp. S ) after scheduling the job
0
Since p1,j ≤ p1,i , it is true that t1,k (S ) ≤ t1,k (S), for all j of J\Jσ1 at the position |σ1 | + 1 on M1 . We denote by
0

k in J\{i}. Therefore, each job of J\{i} is available on M2 γj = t1,j (Sj ) + p1,j + lj = t1,j (Sj ) + p1,j + lj the arrival
0
before its starting time. Moreover, it holds that: time of job j on M2 and τ (resp. τ ) represents the minimal
0 time such that the total idle time observed between γj and
0 0
t1,i (S ) + p1,i + li = t1,j (S) + p1,j + li . τ (resp. τ ) on M2 in S (resp. S ) is equal to p2,j . The job
0
Since li ≤ lj + p2,j , we get: sequences on M2 of Sj and Sj are obtained as follows. We
0
start by removing all jobs that are scheduled between γj and τ
0 0
t1,i (S ) + p1,i + li ≤ t1,j (S) + p1,j + lj + p2,j (resp. τ ) on M2 in S (resp. S ). Then, we process j followed
0
≤ t2,j (S) + p2,j by the removed jobs from S (resp. S ) continuously0
such that
≤ t2,i (S ).
0
they end their processing at time τ (resp. τ ) on M2 in Sj
0
(resp. Sj ). Since j is processed after γj on M2 , we observe
From the above remarks, we conclude that all jobs are available
0
0
that the idle time value of Sj (resp. Sj ) is equal to the idle
for processing on M2 before their starting times in S . 0
time value of S (resp. S ) minus p2,j time units. Therefore,
0
Case 2: i precedes
0
j on M2 Sj and Sj verify that:
In this case, S is derived from S by simply interchanging i and 0 0
j on M1 and on M2 , where the same jobs are executed between I(Sj , Sj , t, C) = I(S , S, t, C) ≥ 0, ∀t ∈ {0, ..., γj }.
0 0
i and j as in S. Then, it holds that t1,i (S) = t1,j (S ), t1,i (S )+
0 0 Moreover, we notice that the schedule is the same in Sj and
p1,i = t1,j (S) + p1,j , t2,i (S) = t2,j (S ) and t2,i (S ) + p2,i = 0 0 0
in S (resp. in Sj and in S ) after the instant max(τ, τ ).
t2,j (S) + p2,j . For each job k in J\{i, j}, we observe that
0 0 Therefore, it holds that:
t1,k (S ) ≤ t1,k (S) since p1,j ≤ p1,i and t2,k (S ) ≥ t2,k (S) 0 0
since p2,j ≥ p2,i . Therefore, each job of J\{i, j} is available I(Sj , Sj , t, C) ≥ 0, ∀t ∈ {max(τ, τ ), ..., C}.

0693 -4-
 Proceedings of 2017 4th International Conference on
Control, Decision and Information Technologies (CoDIT'17) / April 5-7, 2017, Barcelona, Spain

Interestingly,
0
if the second machine for one of the two sched- The number of jobs tested for each class was taken to be
ules Sj and Sj is not idle during an interval [t1 , t2 ], then equal to 10, 30, 50, 100, 150 and 200. For each pair of class and
0
I(Sj , Sj , t, C) consists in determining the difference between number of jobs, 10 instances were randomly generated. All
a constant and a non-increasing value for all t in [t1 , t2 ]. algorithms were coded in C++ and compiled under CentOS
0
Therefore, I(Sj , Sj , t, C) is monotonic in the interval [t1 , t2 ]. 6.6. Moreover, the implementation of the no-good list was
0 done using a hash table. We used the code of Bernstein (see
Consequently, we prove that I(Sj , Sj , t, C) is monotonic in the http://burtleburte.net/bob/hash/doobs.html) since his methods
0 0
interval [γj , max(τ, τ )]. In addition, since I(Sj , Sj , γj , C) ≥ are efficient in term of computational time. The experiments
0 0
0 and I(Sj , Sj , max(τ, τ ), C) ≥ 0, it holds that: were conducted on an Intel(R) Xeon(R) @ 2.60GHz processor
0 0
except for the literature exact method that was done on a
I(Sj , Sj , t, C) ≥ 0, ∀t ∈ {γj , ..., max(τ, τ )}. PC486 with a clock at 33 Mhertz running under MS_DOS.
This process is reiterated for each job of J\Jσ1 . In the following, we evaluate the performance of the differ-
ent components of the branch-and-bound algorithm. Hereafter,
In order to apply the above dominance rule in an efficient we denote by LBbest the maximum lower bound value of
way, we implement the no-good list technique of [10]. The no- LB1 , LB2 , LB3 and LB6 . We implemented three versions
good list consists in recording the most dominant job sequence of the branch-and-bound algorithm:
for each set of jobs. At first, the no-good list is empty. Then,
the dominant job sequences are stored while exploring internal • B&Bv1 : Only LBbest and the preprocessing proce-
nodes of the search tree. For each dominant job sequence σ, dure are applied.
we add the following data: the set of jobs Jσ , the job sequence
σ and the idle time periods on the second machine. • B&Bv2 : The heuristic method, LBbest and the pre-
processing procedure are invoked in each node.
Now suppose that a new node Nσ is developed by our
branch-and-bound method. At first, we verify the existence of • B&Bv3 : All the proposed components are activated
a job sequence π in the no-good list such that Jπ = Jσ . If no in each node.
job sequence is found, then σ is stored in the no-good list and We compare the performance of these versions to the branch-
the node Nσ is developed. Otherwise, we verify the existence and-bound algorithm of [3] denoted B&BDell . Note that
of a dominance relationship between the two job sequences π we set a time limit of 2000 seconds for each instance. We
and σ where three cases are possible: summarize in Table II for each version the number of unsolved
instances within the given time limit (USI), the average number
• π does not dominate σ and then the node Nσ is
of the explored nodes for the solved instances (Nodes) and the
developed.
average computational time in seconds for the solved instances
• π dominates σ and then Nσ is pruned. (Time).
• σ dominates π and then the no-good list is updated From Table II, we made the following observations:
and Nσ is developed.
• B&Bv3 provides a better performance than B&Bv1
For a better convergence of the branch-and-bound method, we and B&Bv2 with only 2 unsolved instances.
apply a neighborhood function that aims to improve the job • B&Bv2 outperforms B&Bv1 . The use of the heuristic
sequence σ. It consists in scheduling the jobs of Jσ on M2 method allows us to solve 5 additional instances for
according to the nondecreasing order of their arrival times. Class C.
Then by considering the obtained job sequence on M2 , σ is
updated according to the arrival times of the jobs. This process • The same remark is observed when we incorporate
is iterated until no amelioration is detected on the makespan the dominance rules within the branch-and-bound. The
between two successive iterations. If the obtained job sequence number of unsolved instances drops by 3 instances
dominates the older one, then the node Nσ can be pruned. comparing to B&Bv2 .
Interestingly, B&Bv3 outperforms B&BDell with only 2
III. C OMPUTATIONAL RESULTS unsolved instances compared to 4 for B&BDell . These two
We present in this section the computational results of the methods exhibit the same performance on all classes except
branch-and-bound algorithm. We performed the tests on a set for Class C where B&Bv3 solves two more instances.
of six classes of instances that was proposed by [3]. For each
class, the processing times on M1 and M2 and the time delays IV. C ONCLUSION
were randomly generated between [1..α], [1..β] and [1..γ],
In this paper, we presented an exact method based on a
respectively. The details of these classes are provided in Table
branch-and-bound scheme for F 2|lj |Cmax . First, we proposed
I.
a heuristic method and developed three dominance rules. Also,
TABLE I. C LASSES GENERATION an experimental study of the exact algorithm was given. In
particular, our branch-and-bound outperforms the state of the
[3] art exact method and solves 358 instances among 360 possible
A B C D E F
α 100 100 100 200 100 200 ones.
β 100 100 100 200 200 100
γ 100 200 500 100 100 100 Future research needs to be focused on improving the per-
formance of the proposed branch-and-bound by investigating

0694 -5-
 Proceedings of 2017 4th International Conference on
Control, Decision and Information Technologies (CoDIT'17) / April 5-7, 2017, Barcelona, Spain

TABLE II. T HE BRANCH - AND -B OUND ALGORITHM PERFORMANCE

B&BDell B&Bv1 B&Bv2 B&Bv3

Class Size USI Nodes Time USI Nodes Time USI Nodes Time USI Nodes Time
10 0 0.00 0.08 0 0.00 0.04 0 0.00 0.01 0 0.00 0.01
30 0 0.00 0.33 1 0.00 0.03 1 0.00 0.01 0 3128.00 8.98
50 0 1.00 25.60 0 0.00 0.03 0 0.00 0.02 0 0.00 0.01
Class A
100 0 1.00 54.13 0 0.00 0.02 0 0.00 0.02 0 0.00 0.02
150 0 0.00 4.51 0 0.00 0.03 0 0.00 0.04 0 0.00 0.03
200 0 0.00 11.74 0 0.00 0.05 0 0.00 0.06 0 0.00 0.05
AVG 0 0.33 16.06 1 0.00 0.03 1 0.00 0.02 0 421.33 1.51
10 0 8.40 13.62 0 73.30 0.02 0 66.70 0.03 0 14.10 0.01
30 0 1.00 3.81 0 102.30 0.27 0 2.40 0.02 0 2.30 0.01
50 0 1.00 13.79 0 7.60 0.02 0 0.10 0.01 0 0.10 0.01
Class B
100 0 1.00 46.52 0 7.40 0.08 0 0.00 0.02 0 0.00 0.02
150 0 1.00 330.00 0 0.00 0.04 0 0.00 0.04 0 0.00 0.04
200 0 1.00 695.61 0 0.00 0.07 0 0.00 0.07 0 0.00 0.07
AVG 0 2.23 183.90 0 31.77 0.08 0 11.53 0.03 0 2.75 0.03
10 0 10.20 7.20 0 70.10 0.03 0 52.30 0.02 0 30.00 0.02
30 2 23.60 19.5 3 23429.71 97.22 2 837.62 3.46 0 7232.10 44.97
50 1 1.00 8.57 2 9483.37 137.39 1 16.66 0.08 1 14.66 0.08
Class C
100 0 3.10 140.72 1 333.44 10.64 0 0.60 0.04 0 0.20 0.02
150 0 1.00 285.24 2 574.00 35.91 0 0.00 0.05 0 0.00 0.04
200 1 1.00 915.59 1 315.55 22.44 1 0.00 0.01 1 0.00 0.08
AVG 4 6.65 229.47 9 5701.03 50.60 4 151.19 0.61 2 1213.99 7.54
10 0 0.00 0.08 0 0.10 0.01 0 0.00 0.01 0 0.00 0.01
30 0 0.00 0.15 0 0.00 0.01 0 0.00 0.02 0 0.00 0.01
50 0 0.00 0.23 0 0.00 0.02 0 0.00 0.02 0 0.00 0.01
Class D
100 0 0.00 1.18 0 0.20 0.02 0 0.20 0.03 0 0.10 0.02
150 0 0.00 2.87 0 0.00 0.02 0 0.00 0.03 0 0.00 0.02
200 0 1.00 650.65 0 0.00 0.03 0 0.00 0.03 0 0.00 0.03
AVG 0 0.17 109.19 0 0.05 0.02 0 0.03 0.02 0 0.01 0.02
10 0 0.00 0.56 0 0.00 0.02 0 0.00 0.04 0 0.00 0.03
30 0 1.00 3.12 0 0.00 0.01 0 0.00 0.04 0 0.00 0.03
50 0 0.00 0.29 0 0.20 0.02 0 0.10 0.02 0 0.00 0.04
Class E
100 0 0.00 1.49 0 0.00 0.02 0 0.00 0.02 0 0.00 0.04
150 0 0.00 3.31 0 0.00 0.03 0 0.00 0.03 0 0.00 0.05
200 0 1.00 563.20 0 0.00 0.04 0 0.00 0.04 0 0.00 0.04
AVG 0 0.33 95.32 0 0.03 0.02 0 0.01 0.03 0 0.00 0.04
10 0 0.00 0.06 0 2.60 0.02 0 2.00 0.04 0 0.90 0.02
30 0 1.00 3.36 0 0.00 0.02 0 0.00 0.01 0 0.00 0.02
50 0 0.00 0.21 0 0.00 0.01 0 0.00 0.02 0 0.00 0.03
Class F
100 0 0.00 1.11 0 0.00 0.02 0 0.00 0.02 0 0.00 0.02
150 0 0.00 3.35 0 0.00 0.02 0 0.00 0.03 0 0.00 0.03
200 0 0.00 29.35 0 0.00 0.04 0 0.00 0.04 0 0.00 0.06
AVG 0 0.17 6.24 0 0.43 0.02 0 0.33 0.02 0 0.15 0.03

new dominance properties and developing lower bound meth- [4] M. Dell’Amico and R. J. M. Vaessens. In Flow and open shop
ods. Moreover, new classes of instances should be investigated scheduling on two machines with transportation times and machine-
where the time delays are very large compared to processing independant processing times is NP-hard. Dipartimento di Economia
politica, Università di Modena, 1996.
times. Indeed, we noticed that the lower bounds perform badly
[5] S. M. Johnson. Optimal two- and three-stage production schedules with
in this case. setup times included. Naval Research Logistics Quarterly, 1(1):61–68,
1954.
[6] L. G. Mitten. Sequencing n jobs on two machines with arbitrary time
ACKNOWLEDGEMENTS lags. Management Science, 5(3):293–298, 1959.
[7] M. A. Mkadem, A. Moukrim, and M. Serairi. Lower bounds for the
This work is carried out in the framework of the Labex two-machine flow shop problem with time delays. In A. Fink, A. Fü-
MS2T, which was funded by the French Government, through genschuh, and M. J. Geiger, editors, Operations Research Proceedings
the program Investments for the future managed by the Na- 2016. Springer International Publishing, 2017.
tional Agency for Research (Reference ANR-11-IDEX-0004- [8] A. Moukrim, D. Rebaine, and M. Serairi. A branch and bound algorithm
for the two-machine flowshop problem with unit-time operations and
02). It is also partially supported by the ATHENA project time delays. RAIRO - Operations Research, 48(2):235–254, 2014.
(ANR-13-BS02-0006-02). [9] M. K. Msakni, W. Khallouli, M. Al-Salem, and T. Ladhari. Minimizing
the total completion time in a two-machine flowshop problem with time
delays. Engineering Optimization, 48(7):1164–1181, 2016.
R EFERENCES [10] T. Schiex and G. Verfaillie. Nogood recording for static and dynamic
constraint satisfaction problems. In Proceedings of 1993 IEEE Confer-
[1] P. Brucker, B. Jurisch, and B. Sievers. A branch and bound algorithm ence on Tools with Al (TAI-93), pages 48–55, Nov 1993.
for the job-shop scheduling problem. Discrete Applied Mathematics, [11] W. Yu. The two-machine flow shop problem and the one-machine total
49(1):107 – 127, 1994. tardiness problem. PhD thesis, Eindhoven University of Technology,
[2] J. Carlier and E. Pinson. A practical use of jackson’s preemptive The Netherlands, 1996.
schedule for solving the job shop problem. Annals of Operations [12] W. Yu, H. Hoogeveen, and J.K. Lenstra. Minimizing makespan in a
Research, 26(1-4):269 – 287, 1990. two-machine flow shop with delays and unit-time operations is np-hard.
[3] M. Dell’Amico. Shop problems with two machines and time lags. Journal of Scheduling, 7(5):333 – 348, 2004.
Operations Research, 44(5):777–787, 1996.

0695 -6-