A mixed integer linear programming modelling for the

flexible cyclic jobshop problem

Félix Quinton, Idir Hamaz, Laurent Houssin

To cite this version:

Félix Quinton, Idir Hamaz, Laurent Houssin. A mixed integer linear programming modelling for the
flexible cyclic jobshop problem. Annals of Operations Research, Springer Verlag, 2020, 285, pp.335-
352. ฀10.1007/s10479-019-03387-9฀. ฀hal-02318936฀

HAL Id: hal-02318936

https://hal.laas.fr/hal-02318936
Submitted on 26 Nov 2019

HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est

archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents
entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non,
lished or not. The documents may come from émanant des établissements d’enseignement et de
teaching and research institutions in France or recherche français ou étrangers, des laboratoires
abroad, or from public or private research centers. publics ou privés.
Noname manuscript No.
(will be inserted by the editor)

A mixed integer linear programming modelling for the

flexible cyclic jobshop problem

Félix Quinton · Idir Hamaz · Laurent

Houssin

Received: date / Accepted: date

Abstract This paper addresses the Cyclic Jobshop Problem in a flexible context.
The flexibility feature means that machines are able to perform several kinds of tasks.
Hence, a solution of the scheduling problem does not only concern the starting times of
the elementary tasks, but also the assignment of these tasks to a unique machine. The
objective considered in this paper is the minimisation of the cycle time of a periodic
schedule. We formulate the problem as a Mixed Integer Linear Problem and propose
a Benders decomposition method along with a heuristic procedure to speed up the
solving of large instances. It consists in reducing the number of machines available for
each task. Results of numerical experiments on randomly generated instances show that
the MILP modelling has trouble solving difficult instances, while our decomposition
method is more efficient for solving such instances. Our heuristic procedure provides
good estimates for difficult instances.

1 Introduction

This paper tackles the Flexible Cyclic Jobshop Scheduling Problem (FCJSP). We pro-
pose a Mixed Integer Linear Problem (MILP) formulation for the FCJSP along with a
Benders decomposition algorithm adapted for the FCJSP. We also introduce a heuristic
procedure to ease the solving of large instances.
In scheduling theory, the Jobshop Scheduling Problem (JSP) refers to a scheduling
problem where tasks are grouped in jobs and executed on specific machines. The JSP
is standard problem that have been extensively studied (Błażewicz et al. (1996)), and
proven to be NP-hard (Garey and Johnson (1979)). Numerous metaheuristics have been
proposed to ease the solving of the JSP (Dell’Amico and Trubian (1993), Schutten
(1998)). However, it is inefficient when scheduling infinitely many repetitions of the

Félix Quinton, Laurent Houssin

LAAS-CNRS, Université de Toulouse, CNRS, UPS, Toulouse, France
E-mail: [email protected]
Idir Hamaz
LIRMM UMR 5506
Université de Montpellier, 34932 Montpelier Cedex 5, France
same set of jobs, as it would require to schedule each job individually, leading to an
immense number of variables in the modelling, which would consequently be very hard
to solve.

This issue can be solved by modelling the problem as a Cyclic Jobshop Schedul-
ing Problem (CJSP), which consist in indefinitely repeating a given set of activities
(Draper et al. (1999), Kim and Lee (2018)). The CJSP has been proven to be NP-
complete (Carlier and Chrétienne (1988)), and can be expressed as a MILP (Brucker
and Kampmeyer (2008b), Hanen (1994), Roundy (1992), and Serafini and Ukovich
(1989)). Two objectives are commonly considered for the CJSP : the minimisation of
the cycle time (Hanen (1994)), noted α, which is defined as the time between two iter-
ations of the same task, and the minimisation of the Work In Process (WIP) (Korbaa
et al. (2002)), which is the number of occurrences of a job processed simultaneously.
In this paper, we will consider the minimisation of the cycle time.

The Flexible Jobshop Scheduling Problem (FJSP) is a generalisation of the JSP,

where each task can be executed on several machines with various execution times.
This problem can be solved using a MILP (Gomes et al. (2005), Thomalla (2001)) but,
due to the complexity of the problem (Xia and Wu (2005)), heuristics approaches such
as tabu search (Saidi-Mehrabad and Fattahi (2007)), ant colony optimisation (Rossi
and Dini (2007)), or genetic algorithms (Gao et al. (2008)) are very popular.

Despite the richness of the literature about CJSP and FJSP, few papers tackle the
FCJSP. Jalilvand-Nejad and Fattahi (2015) proposed a MILP for the FCJSP where the
objective is to minimise the total cost of production in an assembly line environment.
The authors also provide a simulated annealing algorithm and a genetic algorithm to
solve large-scales problems. In Elmi and Topaloglu (2017), the authors proposed an ant
colony algorithm to solve a cyclic jobshop robotic cell scheduling problem (CJRSP).
In this problem, the realisation of a job requires the objects to be moved from one
machine to another by a robot in order to perform the tasks involved in this job.
Bożejko et al. (2016) also provide a solution for the CJRSP with two machines and
one robot. In Bożejko et al. (2017), a parallel algorithm is used to determine the cycle
time of a FJSCP in a graph modelling and the uathors proved several properties on
the relationship between the optimal cycle time and the characteristics of the paths in
the graph. Zhang et al. (2015) proposed a Mixed Integer Problem (MIP) formulation
for the FCJSP with time window constraints and resource capacity constraints.

This paper is organized as follows. In section 2, we introduce the Basic Cyclic

Scheduling Problem (BCSP). The basic notations of cyclic scheduling and a linear
model for the BCSP are given, and an example is introduced. Section 3 presents the
Cyclic Jobshop Scheduling Problem (CJSP). We introduce the notion of machines and
resource constraints, and present a linear modelization for the CJSP proposed by Hanen
(1994). In Section 4 we introduce flexible machines i.e. machines able to perform several
different tasks and define the Flexible Cyclic Jobshop Scheduling Problem (FCJSP). We
propose a MILP for this problem and discuss the addition of several set of constraints
to speed up the solving. We also propose a Benders decomposition algorithm adapted
to the FCJSP and a heuristic procedure to tackle long solving time for large instances.
Numerical instances are presented in Section 5.
Fig. 1 Gantt diagrams displaying feasible schedules for tasks 1 and 2 depending on the height
of precedence constraint C = (1, 2, 4, H1,2 ) : A. H1,2 = 0, B. H1,2 = 1, C. H1,2 = −1, D.
H1,2 = 2

2 Basic cyclic scheduling problem

The Basic Cyclic Scheduling Problem (BCSP) is a generalisation of the basic scheduling
problem where a schedule of elementary tasks i ∈ T = {1, ..., n} is infinitely repeated.
This problem has been studied a lot since it has applications in many fields such
as parallel processing (Hanen and Munier (1995)), staff scheduling (Karp and Orlin
(1981)), or robotic scheduling (Ioachim and Soumis (1995),Kats and Levner (1996)).
Hamaz et al. (2018a) studied the a BCSP where the processing times are affected by
an uncertainty effect.
To specify a BCSP, we are given a set of elementary tasks i ∈ T and their respective
execution time pi . Also, we define ti (k) ≥ 0 the starting time of occurrence k of
task i ∈ T . The order in which the tasks are to be executed is fixed by precedence
constraints. A precedence constraint indicating that task i must be completed before
starting the execution fo task j can be expressed as a quadruplet (i, j, pi , Hi,j ), where
Hi,j is called the height of the precedence constraint and represents the occurrence
shift between tasks i and j. In simple terms, it states that the k + Hi,j -th occurrence
of task j cannot start before the end of the k-th occurrence of task i. Mathematically,
it states that :
tj (k + Hi,j ) ≥ pi + ti (k).

Example 1 : Let us consider the precedence constraint C = (1, 2, 4, H1,2 ). Also, we fix

p2 = 3. If H1,2 = 0, it follows from C that t2 (k) ≥ 4 + t1 (k). Then a feasible schedule
for task 1 and 2 is displayed in Figure 1 A. Note that in Figure 1, the label of each
task shows the number of the task and the occurrence it belongs to. If H1,2 = 1, it
follows from C that t2 (k +1) ≥ 4+ t1 (k). A feasible schedule for task 1 and 2 is showed
in Figure 1 B. Now let us consider the case H1,2 = −1. From C we can derive that
t2 (k − 1) ≥ 4 + t1 (k). A feasible schedule for task 1 and 2 is displayed in Figure 1 C.
Finally, Figure 1 D. displays a feasible schedule if H1,2 = 2.
The BCSP can be represented as an oriented weighed graph where each vertex
represent an elementary task i ∈ T and the weight of the edges are the couple (pi , Hij )
such as the set of edges E reproduce the set of precedence constraints. We add fictive
tasks s end e to represent the start and the end of an occurrence.
Let us denote ti = ti (0), i ∈ T . In this study, the objective considered is the
minimisation of the cycle time α, which is the time between two occurrences of the
same task. Consequently, it is defined by the equations :

ti (k) = αk + ti ∀i ∈ T .

There are two methods to solve the BCSP. The first is based on graph and consists
in finding the maximum mean cycle in the graph i.e the cycle C maximising

P
(i,j )∈C pi
α (C ) = P .
(i,j )∈C Hij

This cycle is called critical path and an application to BSCP has been proposed by
Levner and Kats (1998). This method has also been used by Chretienne et al. (1991)
to solve a BCSP with deadlines,
The second method consist in using mathematical programming. The BCSP can
be expressed as a linear problem as follows (Kampmeyer (2006)).

min α

s.t.

α ≥ pi , ∀i ∈ T (1a)
tj + αHi,j ≥ ti + pi , ∀(i, j ) ∈ E (1b)
ti ≥ 0 , ∀i ∈ T . (1c)

In this modelling, the set of constraints (1a) correspond to non-reentrance con-

straints which ensure that the k-th occurence of any elementary task i ∈ T always
precedes its k + 1-th occurence. Constraints (1b) express the precedence constraints.

Example 2 : Table I reports the data of a BCSP instance with 7 elementary tasks. The
graph representing this example is presented in Figure 2. After solving this BCSP, we
find an optimal cycle time of α = 9.5. A Gantt diagram displaying the optimal solution
of the BCSP instance is presented in Figure 3.

Table 1 An example for the BCSP

Task 1 2 3 4 5 6 7
Time 5 4 5 5 4 3 5
Fig. 2 Graph representation of the BCSP instance introduced in Example 2.
(5, 0) (4, 0) (5, 0)
1 2 3 4
(0, 0) (5, 0)

s f

(0, 0) (5, 0)

5 6 7
(4, 0) (3, 0)

(0, 2)

Fig. 3 Optimal solution for the BCSP instance introduced in Example 2.

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38
Time

1 1 1

2 2 2

3 3 3

4 4 4

5 5 5

6 6 6

7 7 7

α = 9.5

3 Cyclic jobshop scheduling problem

In the cyclic jobshop scheduling problem (CJSP), each elementary task i ∈ T is as-
signed to a machine ri ∈ R = {1, ..., R}, with R < n. In the CJSP, elementary tasks
linked by precedence constraints constitute jobs. For instance, in a manufacturing con-
text, a job might represent the manufacturing process of a product as a whole, while
an elementary task represents only one step of the manufacturing process.
Due to its numerous applications in large-scale production scheduling, the CJSP
has received at lot of attention from the research community. Hanen (1994) proposed
a MILP for this problem and proved some of its properties.Brucker et al. (2012) also
proposed a MILP for a CJSP with transportation by a single robotic cell. Draper
et al. (1999) proposed an alternative formulation to solve CJSP problems as constraint
satisfaction problems. Hamaz et al. (2018b) studied the CJSP with uncertain processing
time. Houssin (2011) proposed an exact method to solve a CJSP using (max, plus)
algebra. Also, several methods have been proposed to solve a CJSP with blocking,
such as Petri-net modelling (Song and Lee (1998)), tabu search algorithm (Brucker and
Kampmeyer (2008a)), and an hybrid algorithm based on particle swarm optimisation
and simulated annealing (Jamili et al. (2011)).
The inclusion of machines in the CJSP leads to a lack of resources, since the tasks
are competing for the working time of the machines. This lack of resources is represented
by disjunction constraints, which state that for a pair of tasks (i, j ) ∈ T 2 , i =
6 j, that
must be executed on the same machine, i.e. ri = rj , an occurrence of tasks i and an
occurrence of j, cannot be executed at the same time. In the following of this paper,
we will denote by D = {(i, j )|R(i) ∩ R(j ) =6 ∅} the set of pairs of tasks linked by
disjunction constraints.
Mathematically, the disjunction between two tasks (i, j ) ∈ T 2 , i = 6 j is modelled
with the two following disjunction constraints (2).

(
tj (k + Ki,j ) ≥ ti (k) + pi
(2)
ti (k + Kj,i ) ≥ tj (k) + pj .

Where Kij (resp. Kji ) is the height of the disjunction constraint, i.e. the occurrence
shift between task i and j (resp. j and i). It has been proven by Hanen (1994) that a
feasible schedule for a CJSP must satisfy :

Kij + Kji = 1 ∀(i, j ) ∈ D. (3)

Note that in this problem the variables are the cycle time α, the starting times of
each elementary tasks (t)i∈T , and the heights of the disjunctive constraints, (K )(i,j )∈D .
A feature of the CJSP is the Work In Process (WIP). It corresponds to the max-
imum number of occurrences of a job processed simultaneously. Mathematically, the
role of the WIP can be modelled as the height of the precedence constraint from fictive
task e to fictive task s, and can be explained by the equation :

s(k) ≥ e(k − W IP ).

Some papers focused on the minimisation of the WIP (Hillion and Proth (1989), Korbaa
et al. (2002)). In these papers, the heights of the precedence constraints Hij , (i, j ) ∈ E
are variables and the objective consist in a linear function of those heights. However
in our study, we focus on the minimisation of the cycle time α, so the WIP and the
Hij , (i, j ) ∈ E are given. Modelling of the CJSP for the minimisation of the cycle time
α with know heights as been proposed by Hanen (1994) and is used by Brucker et al.
(2012) to solve a CJSP with transportation.
A CJSP can be solved by writing the problem as a MILP, which can be solved
using mathematical programming, or using a dedicated Branch-and-Bound procedure
(Fink et al. (2012), Hanen (1994)).
To introduce the MILP modelling of the CJSP proposed by Hanen (1994), we first
introduce a Mixed Integer Non Linear Programming (MINLP) modelling also presented
in Hanen (1994):

min α
s.t.

α ≥ pi , ∀i ∈ T (4a)
tj + αHi,j ≥ ti + pi , ∀(i, j ) ∈ E (4b)
tj + αK (i, j ) ≥ ti + pi , ∀(i, j ) ∈ D (4c)
K (i, j ) + K (j, i) = 1, ∀(i, j ) ∈ D (4d)
K (i, j ) ∈ Z, ∀(i, j ) ∈ D (4e)
ti ≥ 0 , ∀i ∈ T . (4f)

In this model, constraints (4a) are the non-reentrance constraints and constraints
(4b) are the precedence constraints. Constraints (4c) express the disjunction constraints
as defined in (2), while constraints (4d) express the disjunctive heights property of the
CJSP enunciated by Hanen (1994) and introduced in (3). Non linearity appears in
constraints (4c) as the product of variables α and K (i, j ), (i, j ) ∈ D.
As integer non linear programming is very unpractical, we want to linearize the
1
model. Hanen (1994) proposes to define the variable τ = α and for all i ∈ T , the
ti
variable ui = α . Then CJSP can then be as a MILP in the following form Hanen
(1994):

max τ

s.t.

1
τ ≤ , ∀i ∈ T (5a)
pi
uj + Hi,j ≥ ui + τ pi , ∀(i, j ) ∈ E (5b)
uj + K (i, j ) ≥ ui + τ pi , ∀(i, j ) ∈ D (5c)
K (i, j ) + K (j, i) = 1, ∀(i, j ) ∈ D (5d)
K (i, j ) ∈ Z, ∀(i, j ) ∈ D (5e)
ui ≥ 0 , ∀i ∈ T . (5f)

Example 3 : In Table 2, we introduce an updated version of Example 2 presenting a

CJSP with 4 machines. This example is represented as a graph in Figure 4, displaying
only the disjunctive constraints for robot M3 for cleanliness purposes. Note that tasks
1 to 4 form job 1 while tasks 5 to 7 form job 2. Solving this CJSP, we find an optimal
cycle time α = 13. A Gantt diagramm displaying the optimal solution for this CJSP
is presented in Figure 5.

Table 2 An example for the CJSP

Task 1 2 3 4 5 6 7
Time 5 4 5 5 4 3 5
Robot M1 M1 M3 M1 M2 M4 M3
Fig. 4 Graph representation of the CJSP instance introduced in Example 3.
(5, 0) (4, 0) (5, 0)
1 2 3 4
(0, 0) (5, 0)

(5
,K
73
s e

)
(5
,K
(0, 0) (5, 0)

37
)
5 6 7
(4, 0) (3, 0)

(0, 2)

Fig. 5 Optimal solution for the CJSP instance introduced in Example 3.

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
Time

M1 1 2 1 4 2 1

M2 5 5 5

M3 7 3 7 3

M4 6 6

α = 13

4 Flexible cyclic jobshop scheduling problem

The flexible cyclic jobshop scheduling problem (FCJSP) is a CJSP where the elemen-
tary tasks are flexible. This means that the execution of a task i ∈ T , is assigned to
exactly one machine r in a set of machines that is a subset of the set of machines R
specific to task i. This subset is denoted R(i) ⊂ R. We model the assignement of a
task i ∈ T to a machine r ∈ R(i) as a decision variable mi,r defined as follows :

∀i ∈ T , ∀r ∈ R(i),
(
1 if task i is assigned to machine r
mi,r =
0 otherwise.

Each assignment of a task i ∈ T to a machine r ∈ R(i) is associated with a given

execution time denoted pir . Also, because we do not know a priori on which machine
each task will be assigned, we do not know the set (i, j ) ∈ T 2 , i 6= j, R(i, j ) 6= ∅ of
pairs of tasks which are connected by a disjunctive constraint.

Example 4 : In Table 4, we have updated Example 3 so that it fits the FCJSP. Each
task can be assigned to a subset of 3 out of 4 machines. Note that the new possibilities
come with a higher execution time.
Table 3 An example for the FCJSP

Task 1 2 3 4
Robot M1 M2 M4 M1 M2 M3 M2 M3 M4 M1 M2 M3
Time 5 6 6 4 5 6 7 5 6 4 7 5
Task 5 6 7
Robot M1 M2 M3 M1 M3 M4 M1 M2 M3
Time 4 4 5 3 4 2 5 7 5

4.1 MIP model

In this section, we propose a MILP modelling for the FCJSP. A first model was proposed
in Quinton et al. (2018). Let R(i, j ) = R(i) ∩ R(j ), ∀i, j ∈ T the set of machines
available both for tasks i and j. Recall that E denotes the set of precedence constraints
and that D denotes the set of disjunctive constraints.
The MILP for the FCJSP can be formulated as :

max τ
s.t.
X mi,r
τ ≤ , ∀i ∈ T (6a)
pi,r
r∈R(i)
X
uj + Hi,j ≥ ui + pi,r yi,r , ∀(i, j ) ∈ E (6b)
r∈R(i)

P1 (2 − mi,r − mj,r ) + uj + Ki,j ≥ ui + pi,r yi,r , ∀(i, j ) ∈ D, ∀r ∈ R(i, j ) (6c)

X
yi,r = τ, ∀i ∈ T (6d)
r∈R(i)

yi,r ≤ mi,r , ∀i ∈ T , ∀r ∈ R(i) (6e)

yi,r ≥ 0, ∀i ∈ T , ∀r ∈ R(i) (6f)
X
mi,r = 1, ∀i ∈ T (6g)
r∈M (i)

K (i, j ) + K (j, i) = 1, ∀(i, j ) ∈ D (6h)

τ ≥0 (6i)
ui ≥ 0 , ∀i ∈ T (6j)
K (i, j ) ∈ Z, ∀(i, j ) ∈ D (6k)
mi,r ∈ {0, 1}, ∀i ∈ T , ∀r ∈ R(i). (6l)

Constraints (6a) correspond to non-reentrance constraints. They ensure that the

k-th occurence of any elementary task i ∈ T always precedes its k + 1-th occurence.
As constraints (6g) ensure that exactly one mi,r is equal to 1 for all tasks, these non-
reentrance constraints are equivalent to the non-reentrance constraints from the CJSP
(5a).
Constraints (6b) set the precedence constraints, i.e. the order in which tasks have
to be executed. There is one precedence constraint for each couple of tasks (i, j ) ∈ E.
As the assignment of task i ∈ T to a machine r ∈ R(i) set the execution time of
Fig. 6 Solution for the FCJSP example.
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
Time

M1 2 7 2 7 2

M2 5 5 5

M3 3 4 3 4

M4 1 6 1 6 1 6

α = 10

i to pi,r , we want only the effective execution time to be taken into account in the
precedence constraints. To that end, we introduce the yi,r variables, which are defined
by constraints (6d) to (6f) such that :

∀i ∈ T , ∀r ∈ R(i),
(
τ if task i is assigned to machine r
yi,r =
0 otherwise.

Indeed, let i ∈ T , r ∈ R(i), if mi,r = 0, constraints (6e) and (6f) force yi,r = 0. As
constraints (6g) ensure that for each task i ∈ T , there is exactly one r ∈ R(i) such that
mi,r = 1, constraints (6d) together with constraints (6e) ensure that the corresponding
yi,r has to be equal to τ . Therefore, for any precedence constraint (i, j ) ∈ E, the model
only take into account the execution time pi,r if task i is executed on machine r ∈ R(i).
Constraints (6c) represents the disjunctive constraints, ensuring that two tasks are
not executed at the same time period on the same machine. There is one disjunction
constraint for each couple of tasks (i, j ) ∈ D and machine r ∈ R(i, j ), and we want those
constraints to be activated only when tasks i and j are assigned to the same machine r
as otherwise, the couple of tasks (i, j ) does not generate any lack of resources. The P1
term allows us to deactivate the disjunctive constraints for which tasks i and j are not
executed on the same machine r ∈ R(i, j ) i.e. the constraints for which mi,r + mj,r < 2.
We set :
P1 = max pi,r .
i∈T
r∈R(i)

Constraints (6g) ensure that every task i ∈ T is assigned to exactly one machine
r ∈ R(i). Constraints (6h) state the usual constraints for the CJSP, introduced by
Hanen (1994).

Example 4.1 :We have solved the Example 4 with the proposed MILP (6). We have
obtained a cycle time α = 10. Note that the optimal cycle time has decreased even if
the new assignment possibilities introduced in Example 4 came with a higher execution
time. The solution is displayed as Gantt diagram in Figure 6.
4.2 Benders decomposition

The FCJSP formulated as a MILP (6), can be very hard to solve. Using CPLEX,
difficult instances with a large number of tasks or with few robots might exceed any
reasonable time limit. To tackle this issue, we propose a Benders decomposition for
the FCJSP. In the usual Benders decomposition scheme introduce by Benders (1962),
the Master Problem (MP) corresponding to the MILP (6) we proposed for the FCJSP
consists in an integer linear problem composed of the constraints from (6) involving
only the integer variables, and the optimality cuts generated at each iteration of the
Benders algorithm. This master problem can be written as (7).

max z
s.t.

X
mi,r = 1, ∀i ∈ T (7a)
r∈r (i)

Ki,j + Kj,i = 1, ∀(i, j ) ∈ D (7b)

πinr
    X
Y2
X X d d
X d
z+ mi,r P1 πi,j,r + πj,i,r − −πi,r − Ki,j πi,j,r ≤
mi,r
i∈T (i,j )∈D (i,j )∈D r∈R(i,j )
r∈R(i) r∈R(i,j )
X p
X  d d

Hi,j πi,j + 2 P1 πi,j,r + πj,i,r , ∀π ∈ P (7c)
(i,j )∈E (i,j )∈D

mi,r ∈ {0, 1}, ∀i ∈ T , ∀r ∈ R(i) (7d)

z ∈ R, Ki,j ∈ Z, ∀(i, j ) ∈ D. (7e)
Where constraints (7c) are the usual Benders optimality cuts. P is a set of extreme
points, each corresponding to an iteration of the algorithm. The generation of new
elements for P is explained by algorithm 4.2. Constraints (7a) and (7b) reproduce
constraints (6h) and (6g) from the MILP. However, those constraints are not sufficient
to ensure that the solution y provided by the MP is feasible for the MILP as y could
generate negative height cycles (where y = (m, K ) represents a solution of master
problem (7)). In the usual Benders decomposition scheme, this issue is handled with
feasibility cuts. However in our case, the Benders algorithm produces a very large
number of feasibility cuts which greatly slows its convergence. To avoid this issue we
propose cuts (8a) and (8b) to ensure that there exist feasible starting times {wi , i ∈ T }
fulfilling the disjunction constraints and precedence constraints implied by the integer
variables {mi,r , ∀i ∈ T , ∀r ∈ R(i)} and {Ki,j , ∀(i, j ) ∈ D}. Also, we introduce in
constraints (8a) and (8b) a lower bound τLB of the throughput. This lower bound can
easily be obtained as it does not need to be qualitative. For instance, one may set
max pi,r )−1 .
P
τLB = (
i∈T r∈R(i)

P1 (1 − mi,r ) + wj + Hi,j ≥ wi + τLB pi,r , ∀(i, j ) ∈ E (8a)

P1 (2 − mi,r − mj,r ) + wj + Ki,j ≥ wi + τLB pi,r , ∀(i, j ) ∈ D, ∀r ∈ R(i, j ) (8b)
wi ∈ R + , ∀i ∈ T . (8c)
 The remaining constraints of (6), involving only continuous variables or a combi-
nation of continuous and integer variables, compose the primal sub-problem. It can be
written as linear problem (9).
 max τ
s.t.

X mi,r
τ ≤ , ∀i ∈ T (9a)
pi,r
r∈R(i)
X
uj + Hij ≥ ui + yi,r pi,r , ∀(i, j ) ∈ E (9b)
r∈R(i)

P1 (2 − mi,r − mj,r ) + uj + K i,j ≥ ui + yi,r pi,r , ∀(i, j ) ∈ D, ∀r ∈ R(i, j ) (9c)

X
yi,r = τ, ∀i ∈ T (9d)
r∈R(i)

yi,r ≤ mi,r , ∀i ∈ T , ∀r ∈ R(i) (9e)

τ > 0, ui ≥ 0, ∀i ∈ T , yi,r ≥ 0, ∀i ∈ T , ∀r ∈ R(i). (9f)

Hence the dual sub-problem is:

X X mi,r X
min πinr + d
πi,j,r (P1 (2 − mi,r − mj,r ) + K i,j )
pi,r
i∈T r∈R(i) (i,j )∈D
r∈R(i,j )

p y2
X X
+ πi,j Hi,j + πi,r mi,r
(i,j )∈E i∈T
r∈R(i)

s.t.

πinr − πiy1 ≥ 1
X
(10a)
i∈T
p p
X X X d
X d
πi,j − πj,i + πi,j,r − πj,i,r ≥ 0, ∀i ∈ T (10b)
(i,j )∈E (j,i)∈E (i,j )∈D (j,i)∈D
r∈R(i,j ) r∈R(i,j )
p
X X d
πi,j pi,r + πi,j,r pi,r ≥ 0, ∀i ∈ T , ∀r ∈ R(i)
(i,j )∈E (i,j )∈D
(10c)
πinr ≥ 0, ∀i ∈ T (10d)
p
πi,j ≥ 0, ∀(i, j ) ∈ E (10e)
d
πi,j,r ≥ 0, ∀(i, j ) ∈ D, ∀r ∈ R(i, j )
(10f)
πiy1 ∈ R, ∀i ∈ T (10g)
y2
πi,r ≥ 0, ∀i ∈ T , ∀r ∈ R(i).
(10h)

Where πinr , i ∈ T is the dual variable associated to the non-reentrance constraint for
p
task i, πi,j , (i, j ) ∈ E is the dual variable associated to the precedence constraint from
 d
task i to task j, πi,j,r , (i, j ) ∈ D, r ∈ R(i, j ) is the dual variable associated with the
disjunction constraint between tasks i and j for machine r, and π y1 (resp. π y2 ) are the
dual variables associated with the set of constraints (9e) (resp. (9f)).
To further enhance our Benders decomposition algorithm, we use the algorithm
proposed by Magnanti and Wong (1981) to generate Pareto-optimal cuts. To do so, we
need to define the Magnanti-Wong dual sub-problem. Keeping the same notations as
for (10), the Magnanti-Wong dual sub-problem can be written as linear problem (11).
In (11), y = (m, K ) represents a solution of master problem (7), z∗ is the value
of the objective of the dual sub-problem (10), and y 0 = (m0 , K 0 ) is a core point. In
general, generating a core point is not straightforward. However, Papadakos (2008)
showed that given an integer solution y, λy is a core point, for any λ ∈]0, 1[. The
author also showed that any convex combination of core points is a core point. So,
noting yk0 the core point used at iteration k, and y k the integer solution at iteration k,
we propose to use yk0 = 21 yk− 0 1
1 + 2 y k as a core point for stating the Magnanti-Wong
dual sub-problem corresponding to the k-th iteration, k > 0. For the first iteration, we
set y00 = 21 y 0 .
X m0i,r
(P1 (2 − m0i,r − m0j,r ) + Ki,j
0
X X
min πinr + d
πi,j,r )
pi,r
i∈T r∈R(i) (i,j )∈D
r∈R(i,j )

p y2 0
X X
+ πi,j Hi,j + πi,r mi,r
(i,j )∈E i∈T
r∈R(i)
(11)
s.t.

X X mi,r X
πinr + d
πi,j,r (P1 (2 − mi,r − mj,r ) + K i,j )
pi,r
i∈T r∈R(i) (i,j )∈D
r∈R(i,j )
p y2
mi,r = z∗
X X
+ πi,j Hi,j + πi,r (11a)
(i,j )∈E i∈T
r∈R(i)

and
(10a)-(10h).
Having defined the Magnanti-Wong dual sub-problem and an algorithm to generate
core points, we are able to propose the following Magnanti-Wong algorithm for the
FCJSP :
Algorithm 4.2 (Benders algorithm)
P ←− ∅, LB ←− 0
Step 0. Solve the master problem (7).
if infeasible then return infeasible.
Step 1. Solve the dual sub-problem (10). Obtain z∗ .
Step 2. Find a core point yk0 .
Step 3 Solve the Magnanti-Wong problem using yk0 and z∗ .
P ←− P ∪ {u∗ }, U B ←− z, LB ←− max{LB, z∗ }.
if U B − LB > ǫ then go to 0.
return current solution.
Fig. 7 Solution for the FCJSP example solved with the Bender’s algorithm.
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
Time

M1 1 2 1 2 1 2

M2 7 7

M3 5 5 4 5 4

M4 6 3 6 3 6

α = 10

Where z denotes the current master problem objective value, and u∗ denotes the
solution of the Magnanti-Wong dual sub-problem.

Example 4.2 : We have solved Example 4 using our Benders decomposition algorithm.
We have obtained the optimal cycle time α = 10, with a task to machine assignment
different from the one obtained in Example 4.1. The solution is displayed in Fig.7 as a
Gantt diagram.

4.3 Heuristic procedure

The FCJSP is very hard to solve because it is highly combinatorial. For large instances,
the solving time of the MILP presented in Section 5 can be very long. To tackle this
issue, we have developed a heuristic procedure. Our approach consists in reducing the
number of machines able to perform each task, i.e. the number of machines in the
set R(i), ∀i ∈ T . Let us define RH (i) ⊂ R(i) the reduced set of machines on which
task i ∈ T can be assigned in the heuristic procedure. We call this approach "q-Flex",
where q = card(RH (i)). We solve linear program (12a-12d) to build RH (i) such that
the total processing times per machine are equally balanced among all machines.

min Pmax
s.t.

X
Pmax ≥ mi,r pi,r , ∀r ∈ R (12a)
i∈T
X
mi,r = q, ∀i ∈ T (12b)
r∈r (i)

Pmax ∈ R (12c)
mi,r ∈ {0, 1}, ∀i ∈ T , ∀r ∈ R(i). (12d)

For the heuristic to effectively reduce the flexibility of the problem, we must set q
such that q < card(R(i)). We suggest to use q = 2 to guarantee an effective reduction
of the solving time while keeping some flexibility in the problem but notice that this
heuristic is adjustable and a greater value of q could lead to better performance at the
cost of a larger computational time.

Example 4.3 : We have solved Example 4 using this approach. We have obtained a
cycle time α = 10, with a task to machine assignment different from the one obtained
in Example 4.1. The solution is displayed in Fig. 8 as a Gantt diagram.

Fig. 8 Solution given by the "2-Flex" heuristic for the FCJSP example.
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
Time

M1 1 1 7 1 7

M2 5 2 5 2 5 2

M3 3 4 3 4

M4 6 6 6

α = 10

5 Numerical experimentation

The following numerical experiments have been conduced on randomly generated in-
stances with 10 tasks and 3, 4, or 5 machines. In these instances, each tasks can be
assigned to any of the 3 to 5 machines, with an execution time between 10 and 19.
For each kind of instance, we have generated 10 problems. To solve the MILP, we used
the CLEX 12.7 solver. The computer we used is equipped with a dual-core i5-4210H
processor and 8GB RAM and is running Ubuntu 18.04. We fixed the time limit to 3600
i
seconds. Note that the gap is defined as UB−τ τi
, where UB is the best upper bound
found by the solver and τ i is the value of τ in the considered solution.
In the following, we set q = 2 for the number of machines available for each task
in the "q-Flex" heuristic procedure proposed in Section 4.3. Figure 9 displays the
gaps between the solution found by the "2-Flex" heuristic procedure and the optimal
solution found by the MILP and/or the Benders decomposition algorithm. These gaps
are very measured and do not exceed 10% in average for all type of instances.
As we can see in Table 4, the MILP solving is very efficient for the easiest instances
with 10 tasks and 5 machines. For those easy instances, it is much more efficient than
the Benders decomposition, and there is no benefit to use the heuristic procedure since
the execution times of both the MILP and the heuristic are very close and very fast,
but the MILP gives better solutions. For instances of average difficulty with 10 tasks
and 4 machines, the MILP is still more efficient than the Benders decomposition, but
we can remark that the execution time of the MILP is increasing much faster than
the execution time of the Benders decomposition. For these instances, the heuristic
procedure generates solutions whose throughput is close to the optimal throughput
with execution times that are much faster than the MILP’s execution times. In short,
Table 4 Comparison of the solving times in seconds for the different approaches proposed in
the paper. If the MILP times out, we have indicated the gap from the incumbent to CPLEX’s
best bound in parenthesis. Along with the heuristic’s execution time, we displayed the gap
to optima in parenthesis. Instances where the heuristic found the optimal throughput display
"(-)" instead of the gap to optima value.

Instance name MILP Bender’s 2-Flex

decomposition heuristic
inst0_10tasks_5machines 0.76 292.75 0.27(4.57%)
inst1_10tasks_5machines 1.11 459.37 0.48(9.28%)
inst2_10tasks_5machines 0.15 342.91 0.52(12.61%)
inst3_10tasks_5machines 2.98 455.63 0.53(9.01%)
inst4_10tasks_5machines 0.44 336.79 0.17(3.35%)
inst5_10tasks_5machines 0.14 353.07 0.15(1.74%)
inst6_10tasks_5machines 5.78 353.23 0.46(10.21%)
inst7_10tasks_5machines 2.38 451.89 0.10(1.86%)
inst8_10tasks_5machines 0.83 470.23 0.20(10.37%)
inst9_10tasks_5machines 0.91 332.39 0.44(6.55%)
inst0_10tasks_4machines 29.37 505.57 1.78(10.49%)
inst1_10tasks_4machines 461.93 668.82 0.63(-)
inst2_10tasks_4machines 52.68 356.89 0.91(8.25%)
inst3_10tasks_4machines 132.53 703.93 1.04(2.53%)
inst4_10tasks_4machines 93.66 458.89 1.01(1.40%)
inst5_10tasks_4machines 19.78 364.25 0.43(5.44%)
inst6_10tasks_4machines 9.15 514.52 0.66(9.57%)
inst7_10tasks_4machines 49.81 455.74 0.31(2.97%)
inst8_10tasks_4machines 124.83 659.4 0.86(2.46%)
inst9_10tasks_4machines 14.65 317.62 0.87(2.97%)
inst0_10tasks_3machines timeout 819.95 66.29(-)
inst1_10tasks_3machines 946.08 614.28 2.93(-)
inst2_10tasks_3machines 1640.75 516.42 6.74(-)
inst3_10tasks_3machines 823.53 589.63 27.07(-)
inst4_10tasks_3machines 658.47 385.83 34.43(2.58%)
inst5_10tasks_3machines 765.6 424.89 21.01(2.58%)
inst6_10tasks_3machines timeout 954.92 7.62(-)
inst7_10tasks_3machines 2383.02 945.99 34.74(-)
inst8_10tasks_3machines 3215.08 769.91 9.81(-)
inst9_10tasks_3machines 2337.64 473.86 13.17(-)

for this type of instances, the heuristic is useful to quickly generate good feasible
solutions. Finally, for the hard instances with 10 tasks and 3 machines, our Benders
decomposition is always faster to find the optimal solution than the MILP. The heuristic
procedure is also very efficient for this type of instance, often producing an optimal
solution with fast execution times.
From these results, we learn that it is better to use the MILP for easy problems
with numerous machines such as our instances with 10 tasks and 5 machines. For
instances of average difficulty, there is a trade off between getting an optimal solution
relatively slowly using the MILP or getting a close feasible solution very quickly with
the heuristic procedure. However, for hard instances with a considerable number of
disjunctions, such as the instances with 10 tasks and 3 machines, the execution times
of the MILP rocket up and it is much better to use the heuristic procedure to obtain
a feasible solution, or the Benders decomposition to obtain an optimal solution.
Fig. 9 Gap between the optimal solution found with the Benders decomposition algorithm
and the solution generated by the heuristic procedure.
Gap to optima in %
2-Flex max gap
2-Flex mean gap
12 2-Flex min gap

10

5 4 3

Number of machines

6 Conclusion

We have proposed a MILP modelling for the FCJSP where the objective is the min-
imisation of the cycle time. The problem is highly combinatorial, so we also proposed
a Benders decomposition algorithm and a heuristic procedure that are more efficient
for difficult instances. The Benders decomposition includes specific cuts to ensure the
feasibility of the integer solution and uses the Magnanti-Wong algorithm to find Pareto-
optimal optimality cuts. The heuristic reduces the number of machines available for
each elementary task.
Numerical instances have shown that the MILP become inefficient for difficult in-
stances with many disjunctions. The "q-Flex" heuristic procedure is a good way to
tackle this issue since it is much faster than the MILP for these instances while pro-
ducing solutions very close to the optimum. Also, if an optimal solution is required,
our Benders decomposition is more efficient than the MILP for this type of instances.

References

Benders JF (1962) Partitioning procedures for solving mixed-variables programming

problems. Numerische mathematik 4(1):238–252
Bożejko W, Gnatowski A, Klempous R, Affenzeller M, Beham A (2016) Cyclic schedul-
ing of a robotic cell. In: Cognitive Infocommunications (CogInfoCom), 2016 7th IEEE
International Conference on, IEEE, pp 000379–000384
Bożejko W, Pempera J, Wodecki M (2017) A fine-grained parallel algorithm for the
cyclic flexible job shop problem. Archives of Control Sciences 27(2):169–181
Brucker P, Kampmeyer T (2008a) Cyclic job shop scheduling problems with blocking.
Annals of Operations Research 159(1):161–181
Brucker P, Kampmeyer T (2008b) A general model for cyclic machine scheduling prob-
lems. Discrete Applied Mathematics 156(13):2561–2572
Brucker P, Burke EK, Groenemeyer S (2012) A mixed integer programming model
for the cyclic job-shop problem with transportation. Discrete applied mathematics
160(13-14):1924–1935
Błażewicz J, Domschke W, Pesch E (1996) The job shop scheduling problem: Con-
ventional and new solution techniques. European Journal of Operational Research
93(1):1 – 33
Carlier J, Chrétienne P (1988) Problèmes d’ordonnancement: modélisation, complexité,
algorithmes. Masson
Chretienne P, et al. (1991) The basic cyclic scheduling problem with deadlines. Discrete
Applied Mathematics 30(2-3):109–123
Dell’Amico M, Trubian M (1993) Applying tabu search to the job-shop scheduling
problem. Annals of Operations research 41(3):231–252
Draper DL, Jonsson AK, Clements DP, Joslin DE (1999) Cyclic scheduling. In: IJCAI,
Citeseer, pp 1016–1021
Elmi A, Topaloglu S (2017) Cyclic job shop robotic cell scheduling problem: Ant colony
optimization. Computers & Industrial Engineering 111:417–432
Fink M, Rahhou TB, Houssin L (2012) A new procedure for the cyclic job shop problem.
IFAC Proceedings Volumes 45(6):69–74
Gao J, Sun L, Gen M (2008) A hybrid genetic and variable neighborhood descent algo-
rithm for flexible job shop scheduling problems. Computers & Operations Research
35(9):2892–2907
Garey M, Johnson D (1979) Computers and intractability. W II Freeman and Company,
New York
Gomes M, Barbosa-Povoa A, Novais A (2005) Optimal scheduling for flexible job shop
operation. International journal of production research 43(11):2323–2353
Hamaz I, Houssin L, Cafieri S (2018a) A robust basic cyclic scheduling problem. EURO
Journal on Computational Optimization 6(3):291–313
Hamaz I, Houssin L, Cafieri S (2018b) The Cyclic Job Shop Problem with uncertain
processing times. In: 16th International Conference on Project Management and
Scheduling (PMS 2018), Rome, Italy
Hanen C (1994) Study of a np-hard cyclic scheduling problem: The recurrent job-shop.
European journal of operational research 72(1):82–101
Hanen C, Munier A (1995) A study of the cyclic scheduling problem on parallel pro-
cessors. Discrete Applied Mathematics 57(2-3):167–192
Hillion HP, Proth JM (1989) Performance evaluation of job-shop systems using timed
event-graphs. IEEE transactions on automatic control 34(1):3–9
Houssin L (2011) Cyclic jobshop problem and (max, plus) algebra. In: World IFAC
Congress (IFAC 2011), pp 2717–2721
Ioachim I, Soumis F (1995) Schedule efficiency in a robotic production cell. Interna-
tional Journal of Flexible Manufacturing Systems 7(1):5–26
Jalilvand-Nejad A, Fattahi P (2015) A mathematical model and genetic algorithm
to cyclic flexible job shop scheduling problem. Journal of Intelligent Manufacturing
26(6):1085–1098
Jamili A, Shafia MA, Tavakkoli-Moghaddam R (2011) A hybrid algorithm based on par-
ticle swarm optimization and simulated annealing for a periodic job shop scheduling
 problem. The International Journal of Advanced Manufacturing Technology 54(1-
4):309–322
Kampmeyer T (2006) Cyclic scheduling problems
Karp RM, Orlin JB (1981) Parametric shortest path algorithms with an application
to cyclic staffing. Discrete Applied Mathematics 3(1):37–45
Kats V, Levner E (1996) Polynomial algorithms for scheduling of robots. Intelligent
Scheduling of Robots and FMS pp 77–100
Kim HJ, Lee JH (2018) Cyclic robot scheduling for 3d printer-based flexible assembly
systems. Annals of Operations Research pp 1–21
Korbaa O, Camus H, Gentina JC (2002) A new cyclic scheduling algorithm for flexible
manufacturing systems. International Journal of Flexible Manufacturing Systems
14(2):173–187
Levner E, Kats V (1998) A parametric critical path problem and an application for
cyclic scheduling. Discrete Applied Mathematics 87(1-3):149–158
Magnanti TL, Wong RT (1981) Accelerating benders decomposition: Algorithmic en-
hancement and model selection criteria. Operations research 29(3):464–484
Papadakos N (2008) Practical enhancements to the magnanti–wong method. Opera-
tions Research Letters 36(4):444–449
Quinton F, Hamaz I, Houssin L (2018) Algorithms for the flexible cyclic jobshop prob-
lem. In: 14th IEEE International Conference on Automation Science and Engineer-
ing, CASE 2018, Munich, Germany, August 20-24, 2018, pp 945–950
Rossi A, Dini G (2007) Flexible job-shop scheduling with routing flexibility and sep-
arable setup times using ant colony optimisation method. Robotics and Computer-
Integrated Manufacturing 23(5):503–516
Roundy R (1992) Cyclic schedules for job shops with identical jobs. Mathematics of
operations research 17(4):842–865
Saidi-Mehrabad M, Fattahi P (2007) Flexible job shop scheduling with tabu search
algorithms. The International Journal of Advanced Manufacturing Technology 32(5-
6):563–570
Schutten JM (1998) Practical job shop scheduling. Annals of Operations Research
83:161–178
Serafini P, Ukovich W (1989) A mathematical model for periodic scheduling problems.
SIAM Journal on Discrete Mathematics 2(4):550–581
Song JS, Lee TE (1998) Petri net modeling and scheduling for cyclic job shops with
blocking. Computers & Industrial Engineering 34(2):281–295
Thomalla CS (2001) Job shop scheduling with alternative process plans. International
Journal of Production Economics 74(1):125 – 134
Xia W, Wu Z (2005) An effective hybrid optimization approach for multi-objective flex-
ible job-shop scheduling problems. Computers & Industrial Engineering 48(2):409–
425
Zhang H, Collart-Dutilleul S, Mesghouni K (2015) Cyclic scheduling of flexible job-shop
with time window constraints and resource capacity constraints. IFAC-PapersOnLine
48(3):816 – 821