# Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time

Authors: Jabrane Belabid; Said Aqil; Karam Allali
Journal: Journal of Applied Mathematics
 (2020)

---

## Abstract

In this paper, we study the resolution of a permutation flow shop problem with sequence-independent setup time. The objective is to minimize the maximum of job completion time, also called the makespan. In this contribution, we propose three methods of resolution, a mixed-integer linear programming (MILP) model; two heuristics, the first based on Johnson’s rule and the second based on the NEH algorithm; and finally two metaheuristics, the iterative local search algorithm and the iterated greedy algorithm. A set of test problems is simulated numerically to validate the effectiveness of our resolution approaches. For relatively small-size problems, it has been revealed that the adapted NEH heuristic has the best performance than that of the Johnson-based heuristic. For the relatively medium and large problems, the comparative study between the two metaheuristics based on the exploration of the neighborhood shows that the iterated greedy algorithm records the best performances.


---

## Body

## 1. Introduction

The problem of scheduling in the manufacturing industry is characterized by the allocation of jobs on machines and establishing the correct sequence of those jobs in order to optimize an imposed criterion. Each job is identified by a set of tasks that form the path to be followed in the production cycle in the workshop. Every task has a running time on each machine when launching jobs in the industrial process. Several classifications are distinguished: one by machine grouping, one by job grouping, and one by mixed group. In this study, we are interested in a family where the set of jobs follows the same path on a set of machines arranged in series. This type of problem is recognized in the scheduling literature as the flow shop problem (see Figure1). In this type of problem, several constraints may be involved, for example, in logistical means, one can find, transferring, assembly, and disassembly of parts between machines, as well as the adjustment of production tools. Solving the scheduling problem is considered as an NP-difficult issue given a certain size of the batch and number of machines. The approaches of resolution are diverse, and we cite exact methods, heuristics, metaheuristics, and other combined methods. In this paper, we propose these three classes for solving the flow shop with permutation problem (PFSP) under the constraint of sequence-independent setup time (SIST). In this case, the SIST constraint depends on the technology nature of the machine, as well as the means used to prepare it for the execution of a new job. This preparation time is considered unproductive, and its introduction into the scheduling is of great use for the control of the process. We note that the PFSPs are widely studied in the last 50 years under various constraints and objectives. Research is currently knowing significant advances by introducing new constraints and new trends of multiobjective optimization. The scheduling problem PFSP is known in the literature as NP-complete optimization problem [1] for more than two machines. In general, since the number of jobs and the number of machines can be high, it is difficult to find the right solution with an exact method. Hence, metaheuristics are usually used to look for the right solution or at least approach it. The mainly used metaheuristics are based on an improvement of an initial solution by research in its neighborhood by one of the disruption procedures of the current solution. In the literature, we find simulated annealing (SA) [2–4], the genetic algorithm (GA) [5–8], and the combined metaheuristics SA and GA [9, 10] that are used to solve flow shop scheduling problem. We find also other resolution methods such as tabu search [11–14] and the greedy randomized adaptive search procedure [15–18].Figure 1
Flow shop problem withn jobs and m machines.Other nature-inspired metaheuristics are applied for solving flow shop scheduling problem, the artificial bee colony algorithm [19–21], ant colony optimization algorithm [22, 23], and water wave optimization algorithm [24, 25]. The efficiency of these metaheuristics is observed during the resolutions of the flow shop scheduling problems with several jobs and machines. Sometimes, a machine has to be prepared in some way before it can process a certain job. It may need retooling, adjusting, and so on. The time required for such preparation is called setup time. The need to consider this new constraint, in simulation models, is pushing researchers to develop new models. Resolving flow shop problems with permutation and setup time is part of this new problem category. This topic has attracted a wide attention and has been subject of recent works for many researchers (see, for example, [26–29]).Several works dealing with scheduling issues are presented in the optimization. Recently, a number of studies have been carried out on permutation flow shop scheduling problem under the constraint of setup time. We distinguish two types of setup time: the first depends on the sequence of the jobs on the same machine, called the sequence-dependent setup time (SDST), and the second is qualified as a setup time independent of the sequence of jobs in the same machine, called the sequence-independent setup time (SIST). For the first category of problem which is designated as the permutation flow shop scheduling problem with sequence-dependent setup time (PFSP-SDST), a large number of works have been carried out. This setup time depends on each job to be processed; for example, a big job requires more time of preparation than a small one. Often additional constraints are added such as no-waiting, blocking, and other new PFSP constraints that concertize industrial cases. The resolution of PFSP-SDST problem is presented in [30] using the migratory bird algorithm as well as a set of heuristics to minimize the makespan. In [31], the authors propose the water wave optimization algorithm to minimize the makespan with a blocking constraint for a PFSP-SDST problem. Similarly, [32] proposes an MILP model for the case of no-wait criterion for the same problem. In the same context, [33] proposes a case study of the PFSP-SDST problem under no-idle constraint to minimize the total flow time. Recently, PFSP-SDST problem is studied by using three metaheuristics with a local search neighborhood [29], and it was revealed that the iterated greedy gives good results comparing with the two other used methods. For the second category of problem, i.e., PFSP-SIST, we note that only few works has been tackled, which may be a way to be explored for future research. This second class of problem is very interesting to study when a given machine requires the same setup time for all jobs. For example, the machine can have an automatic fixed setup time to process every job; such a setup time can be interpreted in same industrial cases as cleaning, parts assembly-disassembly, or maintenance of a certain machine. We note that [34, 35] propose a set of MILP models and lower bounds for specific cases of the PFSP-SIST problem. In the same context, [36] propose an MILP model and a set of constructive heuristics to solve Fmprmu,SISTCmax. We are continuing the investigation in PFSP-SIST issues by solving this problem for larger size of instances and testing two metaheuristics. To this end, we propose a study with three methods: MILP, heuristics, and metaheuristics. The two implemented metaheuristics for resolution are among the most powerful in the neighborhood exploration, the iterative local search (ILS) algorithm, and the iterated greedy (IG) algorithm. We note that our case study is particular because of the presence of the SIST constraint. In fact, this setup time may be the subject of several cases such as assembly and disassembly of parts or tools in the machine, cleaning, evacuation of production means, and so on. These activities can be carried out by robots or manipulators independent of the processed jobs in the machine. In this perspective, we present a study to contribute to the resolution of this problem which forms an essential manufacturing case to be encountered in the new industrial technology. We continue in this line of research and propose a model in MILP and two metaheuristics for solving the PFSP-SIST problem.Our paper is organized as follows. In Section2, a description of the problem is presented; in Section 3, we develop all the proposed approaches to resolution. In Section 4. a comparative study between the different methods of resolution is presented. Section 5 summarizes our resolution approaches.


## 2. Description of the PFSP-SIST Problem

In the PFSP-SIST scheduling problem, a set of jobsJ=J1,J2,…,Jn constituting a production batch is launched in the production process consisting of a set of machines M=M1,M2,…,Mm arranged in series. All jobs have the same path and m operations on all machines, and each job Jj starts with the first machine and ends its cycle with the last machine. We consider that pi,j the processing time of the job Jj on the machine Mi, and each machine has an extra time of preparation si when processing a new job. Denote a sequence π=π1,π2,…,πn constituting a possible permutation when processed by the machines. We note Ci,πj the completion time of the job πj of the sequence on the Mi machine. The goal is to find the right sequence among the n! possible sequence to minimize the production time of the batch of n jobs and determine the start and completion time of each job on each machine. The assumptions used are those of the classic case, that is to say the interruption is not allowed, and each machine processes only one job at time and job can process only once by the same machines. All jobs and machines are available at the initial moment. The aim is to minimize the maximum completion time called makespan Cmax under the selected assumptions as well as the availability constraints of the machines during scheduling in the real time of the entire batch. We give here a set of equations to determine the completion time of each job on each machine:(1)C1,π1=p1,π1+s1,(2)C1,πj=C1,πj−1+p1,πj+s1,j=2,…,n,(3)Ci,π1=maxsi,Ci−1,π1+pi,π1,i=2,…,m,(4)Ci,πj=maxCi,πj−1+si,Ci−1,πj+pi,πj,i=2,…,m;j=2,…,n,(5)Cmax=max1≤j≤nCm,πj.Equations (1) and (2) allow to determine the end date of the first job and the other jobs on the first machine, respectively. Equations (3) and (4) allow to determine, respectively, the end date of the first job and the other jobs on all the other machines. Equation (5) calculates the makespan Cmax. In this model, the objective is to determine an optimal sequence π∗ in the set permutation Π, such as Cmaxπ∗≤Cmaxπ,π∈Π.


### 2.1. Numerical Example

We give here an numerical illustration with small instance represented by three jobs and three machines. The processing time of all jobs and the setup time for all machines of are given in Table1. We represent the Gantt chart for the sequence π=3,1,2, the makespan of this instance is 48 unite of time (see Figure 2). From this numerical example, it can be easily seen that jobs will be processed on the first machine continuously. On the contrary, when scheduling jobs in other machines, some machines remain on hold, which leads to a waste of time. In conclusion, the sequence in the first machine is a determining factor in the search for the right solution.Table 1
The processing time of 3 jobs on 3 machines.
Job
Job 1
Job 2
Job 3
s
i
M
1
9
5
9
3
M
2
8
8
8
2
M
3
7
6
6
3Figure 2
Gantt chart for three jobs in three machines.


## 2.1. Numerical Example

We give here an numerical illustration with small instance represented by three jobs and three machines. The processing time of all jobs and the setup time for all machines of are given in Table1. We represent the Gantt chart for the sequence π=3,1,2, the makespan of this instance is 48 unite of time (see Figure 2). From this numerical example, it can be easily seen that jobs will be processed on the first machine continuously. On the contrary, when scheduling jobs in other machines, some machines remain on hold, which leads to a waste of time. In conclusion, the sequence in the first machine is a determining factor in the search for the right solution.Table 1
The processing time of 3 jobs on 3 machines.
Job
Job 1
Job 2
Job 3
s
i
M
1
9
5
9
3
M
2
8
8
8
2
M
3
7
6
6
3Figure 2
Gantt chart for three jobs in three machines.


## 3. Resolution of PFSP-SIST Problem

The resolution of the scheduling problems during the last decades has undergone a great evolution and a great based on power of the height technology computers. To solve our problemFmprmu,SISTCmax, we propose three approaches, a MILP, two heuristics among the most powerful for the scheduling problem and finally two metaheuristics algorithm ILS and IG. In the last resolution category, we rely on the exploration structures of the neighboring of a sequence π based on the permutation or insertion of a job in the sequence to obtain a new sequence in the space search for solution.


### 3.1. Mixed-Integer Linear Programming

Modeling optimization problems in scheduling and in particular in the PFSP is one of the most important areas of research in operational research. In fact, these models propose a function to optimize under constraints solved by one of the solvers dedicated to this type of model. The models are numerous and diverse, often characterizing a practical case for industrial need or a theoretical case for academic research. Several models in MILP are proposed for different case study models of the PFSP; a comparative study is described in [37], and a new model is presented [38]. Furthermore, more models are presented in [39] for the PFSP-SDST problem. We present here a model in MILP for our problem, and we define a set of parameters and variables necessary for the realization of the proposed model.(6)xk,j=1,if jobjis assigned to the positionkof the sequence,0,otherwise,k,j=1,…,n,Ci,k=completion time of job at positionkon machinei,i=1,…,m,k=1,…,n.The objective is to(7)minimizeCmax=Cm,n,subject to(8)∑j=1nxk,j=1,k=1,…,n,(9)∑k=1nxk,j=1,j=1,…,n,(10)C1,1≥s1+∑j=1nx1,j×p1,π1;j=1,…,n,(11)C1,k≥s1+C1,k−1+∑j=1nxk,j×p1,πj;k=2,…,n,(12)Ci,k≥Ci−1,k+∑j=1nxk,j×pi,πj,i=2,…,m;k=1,…,n,(13)Ci,k≥si+Ci,k−1+∑j=1nxk,j×pi,πj,i=1,…,m,k=1,…,n,(14)Ci,k≥0,i=1,…,m;k=1,…,n,(15)xk,j∈0,1,j,k=1,…,n.Knowing that (7) defines the objective function to minimize. Constraints (8) and (9) make it possible to guarantee that each position in the sequence will be occupied by a single job, and each job can have only one position. Constraint (10) is used to determine the completion time of the job occupying the first position in the first machine. Constraint (11) calculates the completion time of the job at the position k,k≥2 in the first machine. Constraint (12) guarantees that for a job at the k position, the completion time in the machine i is greater than or equal to the completion time in the previous machine i−1 increasing its processing time on the i machine. Constraint (13) ensures that, for two jobs of successive positions, the completion time in the machine of the one in position k is greater than or equal to that of the one in position k−1 increasing in processing and setup times. Constraints (14) and (15) ensure that the completion time is positive and the assignment variables xk,j are binary, respectively. To solve our mixed-integer linear programming model dealing with PFSP-SIST problem, we will use LINGO 17.3 software.


### 3.2. Heuristics

The PFSP scheduling problems under various constraints can be solved through different heuristics. In fact, for the industrialists, the search of the solutions by heuristics constitutes simple and less expensive issue to ensure the production and to satisfy their customers. The heuristics are usually based on priority rules based on job characteristics such as processing time, setup time, and other priorities related to the problem being addressed. In this work, we present two heuristics, the heuristic Johnson’s rule [40] and the one based on the NEH [41] algorithm. These two basic heuristics are among the most promising approaches in finding the right solution for most PFSP scheduling problems.


#### 3.2.1. An Heuristic Based on Johnson’s Rule

The PFSP problem with two machines is the basic problem of any flow shop scheduling problems. The studies that have followed since the first study refer to this problem. The extensions of these problems are numerous, and the cases studied often fall under the particular constraints like the preparation of the machines or the preparation of the jobs to schedule all the jobs in the workshop. The main objective of optimization is to minimize the makespan from which we can deduce many other intrinsic objectives. We were interested in this approach by proposing a heuristic based on Johnson’s rule, which we adopted to solve our case study ofFmprmu,SISTCmax. The following algorithm presents our heuristic of resolution by highlighting the characteristics our problem.In this investigation, the Johnson algorithm is adapted to fit more than two machines flow shop problems. Algorithm1 shows the template of an heuristic based on Johnson’s rule (HBJR) with construction of two virtual machines by assembling the first 1<k<m−1 machines into one virtual machine and the k−m remaining machines into the second virtual one. The processing time of a job πj on a virtual machine pi,πj′ is the sum of the processing times pi,πj of job πj on the machines that compose the virtual machine.Algorithm 1: An heuristic based on Johnson’s rule.
Input: π0=π1,…,πn % The initial sequence
π⟵π0
% Construction ofπ′
p1,πj′⟵p1,πj, j=1,…,n, p2,πj′⟵∑k=2mpk,πj, j=1,…,n
π∗⟵π′ % Sequence π on two virtual machines with new processing time pi,πj′
for i=2 to m−1 do
% Reconstruction of new two machines
p1,πj′⟵∑k=1ipk,πj, j=1,…,n, p2,πj′⟵∑k=i+1mpk,πj, j=1,…,n
π″⟵Johnson’s ruleπ′
if Cmaxπ″<Cmaxπ′ then
π⟵π″
if Cmaxπ<Cmaxπ∗ then
π∗⟵π
end if
end if
end for
makespan⟵Cmaxπ∗
Output: π∗,makespan


#### 3.2.2. NEH Heuristic

The NEH algorithm constitutes a heuristic pillar for solving the PFSP problem withn jobs and m machines. More and more researchers are developing more adopted versions of the case and following the constraints of each problem. We do several research work as in [42, 43] and more recently in [44]. Indeed, Ruiz and Maroto compared NEH with more modern and more complex heuristics, such as those of [45, 46] showing NEH algorithm realized the better performance. Here, we propose a version of the NEH algorithm for the resolution of PFSP-SIST, the Algorithm 2 presents the necessary steps to establish the sequence of NEH.Algorithm 2: NEH algorithm.
Input: processing time pj1,…,pjm and the setup time si in m machines.
Evaluate the total processing time and setup time of each job by:Tj=∑i=1mpji+si
Construct the sequenceπ=π1,…,πn by sorting the jobs in descending order of Tj
Schedule the first two jobsπ1, π2 and choose the best sequence π of the first two jobs
for j=3 to ndo
Insertπj in the all positions of the current sequence built and select the best sequence
with the minimumCmax in the last machine and update πNEH of the optimal sequence.
end for
Output: πNEHIn order to adapt the NEH algorithm to the studied problem, the setup time is added to the sum of processing times of each job in the first step of the algorithmTj=∑i=1mpi,πj+si.


### 3.3. Metaheuristic Algorithms

The resolution of PFSP by metaheuristics has been very successful in recent years. Indeed, the instance size of the problems has become larger and larger, exact methods such as MILP or the branch and bound procedure are limited to a small-size instance. The need to solve the real cases of problems induces researchers to develop metaheuristics to give the right solution in a reasonable time. In this paper, we propose two main metaheuristics, the iterative local search (ILS) algorithm and the iterated greedy (IG) algorithm. The two algorithms are proposed to solve the problemFmprmu,SISTCmax with the diversification of neighborhood exploration that will be given in detail as follows. For our considered instances, the number of machines m∈2,…,30 and the number of jobs n∈5,…,600; the processing times pij are defined in 1,49 and the setup times si are defined in 1,10.


#### 3.3.1. ILS Algorithm

The ILS algorithm is considered one of the powerful optimization algorithms for solving scheduling problems. We find the latest applications of this algorithm in [47–49] for solving the PFSP problem and its extensions under various implementations. In Algorithm 3, we describe the steps of the development of this algorithm. In the first phase, an initial solution is given by one of the initialization heuristics. In the second, while the stopping criterion not satisfied a search procedure in the neighborhood of the current solution is triggered, each time, an update of the best solution is performed. In this implementation model, we choose an adaptation of the simulated annealing criterion to better explore the neighborhood.Algorithm 3: ILS algorithm.
Input: π0=π1,…,πn the initial sequence
πbest⟵π0, π⟵π0
while {the stopping criterion not satisfied} do
Chooseπ′ from the neighborhood of Nkπ
if Cmaxπ′<Cmaxπ then
π⟵π′
if Cmaxπ<Cmaxπbest then
πbest⟵π
end if
else
if random≤exp−Cmaxπ′−Cmaxπ/Temp then
π⟵π′
end if
end if
end while
Output: πbestThe implementation of the ILS algorithm requires a set of parameter settings to better converge to the optimal solution depending on the size of the problem. The first parameter is the stop condition of the algorithm that we consider here in number of iterations, the second parameter is the acceptance condition of the simulated annealing modelTemp, We adopt the following model:(16)Temp=T0×∑j=1n∑i=1mpi,j+si10×m×n.This expression is given according to the characteristic of the PFSP-SIST problem. The parameterT0 makes possible to control the speed of convergence of our algorithm, we choose in this study T0∈0.5,…,0.98. This model of temperature has been adopted in several research works concerning the PFSP problem (see, for example, [50]).The local search metaheuristics requires the definition of the neighborhood structure exploration, we propose four structures (Ni, i = 1, …, 4). Starting from the current sequence of Figure 3 where the jobs in positions 2 and 7, respectively, are used to generate the set of neighborhoods considered. Neighborhood N1 is defined by the permutation of the position of two jobs. Neighborhood N2 adopts the insertion and shift to the right, and Neighborhood N3 considers the insertion and shift on the left. Finally, neighborhood N4 is defined by job blocks inversion between two different positions in the sequence.Figure 3
Neighborhood structure.


#### 3.3.2. IG Algorithm

The second heuristic implemented to solve our problem is the IG algorithm (see Algorithm4). This algorithm is based on three stages of resolution: the step of destruction of the current solution, the step of the reconstruction of the solution and the last step concerns the local search procedure. The first two stages constitute the first main phase of the principle of the algorithm IG, the second main phase is that of the neighborhood exploration. Recent work in applying the IG [51–53] algorithm shows the rising power of this algorithm in solving the optimization problem in the scheduling domain. The implementation of this algorithm requires also a set of setting parameters, the stop condition, the number d of jobs extracted in the sequence to build the new sequence, the parameter of the simulated annealing temperature, and finally the structure of the neighborhood used in the exploration phase. For the stop condition and the temperature parameter Temp, we adopt the same condition as that adopted for the ILS algorithm. As for the neighborhood structure, we consider the same structure as ILS. For the d parameter of extracted jobs, we consider that it also depends on the size of the problem knowing that d∈n/4,n/3, for n∈5,…,50 and d∈n/3,n/2 for n>50.Algorithm 4: Iterated greedy algorithm.
Input:
π the initial sequence.
πbest⟵π
while unsatisfied stopping criterion do
π′⟵π
for u=1 to ddo
Extract a jobπu at random from the sequence π′ and add the job πu to the Φ subset.
end for
for u=1 to ddo
Extract theπu′ job from Φ subset.
Test the job on all positions in the current sequenceπ′ and choose the best position giving the best completion time.
end for
Chooseπ″ from the neighborhood of Nkπ′
if Cmaxπ″<Cmaxπ then
π⟵π″
if Cmaxπ<Cmaxπbest then
πbest⟵π
end if
else
if random≤exp−Cmaxπ″−Cmaxπ/Temp then
π⟵π″
end if
end if
end while
Output: πbestWe present here an illustrative example of the procedure of destruction and reconstruction of the IG algorithm. Knowing that the current solution isπ=7,8,5,4,2,6,1,3, we randomly extract two jobs, for example, 7 and 6, the remaining sequence is πd=8,5,4,2,1,3. Subsequently, we insert the first 7 job in all positions, and we select the best constructed sequence giving the value of Cmax, for example π=8,5,4,7,2,1,3. We repeat the procedure for the new built sequence and insert job 6 in all possible positions, and at the end, we get the best value from the makespan. Figure 4 gives a representation of the procedure of destruction and reconstruction of the IG algorithm.Figure 4
IG procedure.


## 3.1. Mixed-Integer Linear Programming

Modeling optimization problems in scheduling and in particular in the PFSP is one of the most important areas of research in operational research. In fact, these models propose a function to optimize under constraints solved by one of the solvers dedicated to this type of model. The models are numerous and diverse, often characterizing a practical case for industrial need or a theoretical case for academic research. Several models in MILP are proposed for different case study models of the PFSP; a comparative study is described in [37], and a new model is presented [38]. Furthermore, more models are presented in [39] for the PFSP-SDST problem. We present here a model in MILP for our problem, and we define a set of parameters and variables necessary for the realization of the proposed model.(6)xk,j=1,if jobjis assigned to the positionkof the sequence,0,otherwise,k,j=1,…,n,Ci,k=completion time of job at positionkon machinei,i=1,…,m,k=1,…,n.The objective is to(7)minimizeCmax=Cm,n,subject to(8)∑j=1nxk,j=1,k=1,…,n,(9)∑k=1nxk,j=1,j=1,…,n,(10)C1,1≥s1+∑j=1nx1,j×p1,π1;j=1,…,n,(11)C1,k≥s1+C1,k−1+∑j=1nxk,j×p1,πj;k=2,…,n,(12)Ci,k≥Ci−1,k+∑j=1nxk,j×pi,πj,i=2,…,m;k=1,…,n,(13)Ci,k≥si+Ci,k−1+∑j=1nxk,j×pi,πj,i=1,…,m,k=1,…,n,(14)Ci,k≥0,i=1,…,m;k=1,…,n,(15)xk,j∈0,1,j,k=1,…,n.Knowing that (7) defines the objective function to minimize. Constraints (8) and (9) make it possible to guarantee that each position in the sequence will be occupied by a single job, and each job can have only one position. Constraint (10) is used to determine the completion time of the job occupying the first position in the first machine. Constraint (11) calculates the completion time of the job at the position k,k≥2 in the first machine. Constraint (12) guarantees that for a job at the k position, the completion time in the machine i is greater than or equal to the completion time in the previous machine i−1 increasing its processing time on the i machine. Constraint (13) ensures that, for two jobs of successive positions, the completion time in the machine of the one in position k is greater than or equal to that of the one in position k−1 increasing in processing and setup times. Constraints (14) and (15) ensure that the completion time is positive and the assignment variables xk,j are binary, respectively. To solve our mixed-integer linear programming model dealing with PFSP-SIST problem, we will use LINGO 17.3 software.


## 3.2. Heuristics

The PFSP scheduling problems under various constraints can be solved through different heuristics. In fact, for the industrialists, the search of the solutions by heuristics constitutes simple and less expensive issue to ensure the production and to satisfy their customers. The heuristics are usually based on priority rules based on job characteristics such as processing time, setup time, and other priorities related to the problem being addressed. In this work, we present two heuristics, the heuristic Johnson’s rule [40] and the one based on the NEH [41] algorithm. These two basic heuristics are among the most promising approaches in finding the right solution for most PFSP scheduling problems.


### 3.2.1. An Heuristic Based on Johnson’s Rule

The PFSP problem with two machines is the basic problem of any flow shop scheduling problems. The studies that have followed since the first study refer to this problem. The extensions of these problems are numerous, and the cases studied often fall under the particular constraints like the preparation of the machines or the preparation of the jobs to schedule all the jobs in the workshop. The main objective of optimization is to minimize the makespan from which we can deduce many other intrinsic objectives. We were interested in this approach by proposing a heuristic based on Johnson’s rule, which we adopted to solve our case study ofFmprmu,SISTCmax. The following algorithm presents our heuristic of resolution by highlighting the characteristics our problem.In this investigation, the Johnson algorithm is adapted to fit more than two machines flow shop problems. Algorithm1 shows the template of an heuristic based on Johnson’s rule (HBJR) with construction of two virtual machines by assembling the first 1<k<m−1 machines into one virtual machine and the k−m remaining machines into the second virtual one. The processing time of a job πj on a virtual machine pi,πj′ is the sum of the processing times pi,πj of job πj on the machines that compose the virtual machine.Algorithm 1: An heuristic based on Johnson’s rule.
Input: π0=π1,…,πn % The initial sequence
π⟵π0
% Construction ofπ′
p1,πj′⟵p1,πj, j=1,…,n, p2,πj′⟵∑k=2mpk,πj, j=1,…,n
π∗⟵π′ % Sequence π on two virtual machines with new processing time pi,πj′
for i=2 to m−1 do
% Reconstruction of new two machines
p1,πj′⟵∑k=1ipk,πj, j=1,…,n, p2,πj′⟵∑k=i+1mpk,πj, j=1,…,n
π″⟵Johnson’s ruleπ′
if Cmaxπ″<Cmaxπ′ then
π⟵π″
if Cmaxπ<Cmaxπ∗ then
π∗⟵π
end if
end if
end for
makespan⟵Cmaxπ∗
Output: π∗,makespan


### 3.2.2. NEH Heuristic

The NEH algorithm constitutes a heuristic pillar for solving the PFSP problem withn jobs and m machines. More and more researchers are developing more adopted versions of the case and following the constraints of each problem. We do several research work as in [42, 43] and more recently in [44]. Indeed, Ruiz and Maroto compared NEH with more modern and more complex heuristics, such as those of [45, 46] showing NEH algorithm realized the better performance. Here, we propose a version of the NEH algorithm for the resolution of PFSP-SIST, the Algorithm 2 presents the necessary steps to establish the sequence of NEH.Algorithm 2: NEH algorithm.
Input: processing time pj1,…,pjm and the setup time si in m machines.
Evaluate the total processing time and setup time of each job by:Tj=∑i=1mpji+si
Construct the sequenceπ=π1,…,πn by sorting the jobs in descending order of Tj
Schedule the first two jobsπ1, π2 and choose the best sequence π of the first two jobs
for j=3 to ndo
Insertπj in the all positions of the current sequence built and select the best sequence
with the minimumCmax in the last machine and update πNEH of the optimal sequence.
end for
Output: πNEHIn order to adapt the NEH algorithm to the studied problem, the setup time is added to the sum of processing times of each job in the first step of the algorithmTj=∑i=1mpi,πj+si.


## 3.2.1. An Heuristic Based on Johnson’s Rule

The PFSP problem with two machines is the basic problem of any flow shop scheduling problems. The studies that have followed since the first study refer to this problem. The extensions of these problems are numerous, and the cases studied often fall under the particular constraints like the preparation of the machines or the preparation of the jobs to schedule all the jobs in the workshop. The main objective of optimization is to minimize the makespan from which we can deduce many other intrinsic objectives. We were interested in this approach by proposing a heuristic based on Johnson’s rule, which we adopted to solve our case study ofFmprmu,SISTCmax. The following algorithm presents our heuristic of resolution by highlighting the characteristics our problem.In this investigation, the Johnson algorithm is adapted to fit more than two machines flow shop problems. Algorithm1 shows the template of an heuristic based on Johnson’s rule (HBJR) with construction of two virtual machines by assembling the first 1<k<m−1 machines into one virtual machine and the k−m remaining machines into the second virtual one. The processing time of a job πj on a virtual machine pi,πj′ is the sum of the processing times pi,πj of job πj on the machines that compose the virtual machine.Algorithm 1: An heuristic based on Johnson’s rule.
Input: π0=π1,…,πn % The initial sequence
π⟵π0
% Construction ofπ′
p1,πj′⟵p1,πj, j=1,…,n, p2,πj′⟵∑k=2mpk,πj, j=1,…,n
π∗⟵π′ % Sequence π on two virtual machines with new processing time pi,πj′
for i=2 to m−1 do
% Reconstruction of new two machines
p1,πj′⟵∑k=1ipk,πj, j=1,…,n, p2,πj′⟵∑k=i+1mpk,πj, j=1,…,n
π″⟵Johnson’s ruleπ′
if Cmaxπ″<Cmaxπ′ then
π⟵π″
if Cmaxπ<Cmaxπ∗ then
π∗⟵π
end if
end if
end for
makespan⟵Cmaxπ∗
Output: π∗,makespan


## 3.2.2. NEH Heuristic

The NEH algorithm constitutes a heuristic pillar for solving the PFSP problem withn jobs and m machines. More and more researchers are developing more adopted versions of the case and following the constraints of each problem. We do several research work as in [42, 43] and more recently in [44]. Indeed, Ruiz and Maroto compared NEH with more modern and more complex heuristics, such as those of [45, 46] showing NEH algorithm realized the better performance. Here, we propose a version of the NEH algorithm for the resolution of PFSP-SIST, the Algorithm 2 presents the necessary steps to establish the sequence of NEH.Algorithm 2: NEH algorithm.
Input: processing time pj1,…,pjm and the setup time si in m machines.
Evaluate the total processing time and setup time of each job by:Tj=∑i=1mpji+si
Construct the sequenceπ=π1,…,πn by sorting the jobs in descending order of Tj
Schedule the first two jobsπ1, π2 and choose the best sequence π of the first two jobs
for j=3 to ndo
Insertπj in the all positions of the current sequence built and select the best sequence
with the minimumCmax in the last machine and update πNEH of the optimal sequence.
end for
Output: πNEHIn order to adapt the NEH algorithm to the studied problem, the setup time is added to the sum of processing times of each job in the first step of the algorithmTj=∑i=1mpi,πj+si.


## 3.3. Metaheuristic Algorithms

The resolution of PFSP by metaheuristics has been very successful in recent years. Indeed, the instance size of the problems has become larger and larger, exact methods such as MILP or the branch and bound procedure are limited to a small-size instance. The need to solve the real cases of problems induces researchers to develop metaheuristics to give the right solution in a reasonable time. In this paper, we propose two main metaheuristics, the iterative local search (ILS) algorithm and the iterated greedy (IG) algorithm. The two algorithms are proposed to solve the problemFmprmu,SISTCmax with the diversification of neighborhood exploration that will be given in detail as follows. For our considered instances, the number of machines m∈2,…,30 and the number of jobs n∈5,…,600; the processing times pij are defined in 1,49 and the setup times si are defined in 1,10.


### 3.3.1. ILS Algorithm

The ILS algorithm is considered one of the powerful optimization algorithms for solving scheduling problems. We find the latest applications of this algorithm in [47–49] for solving the PFSP problem and its extensions under various implementations. In Algorithm 3, we describe the steps of the development of this algorithm. In the first phase, an initial solution is given by one of the initialization heuristics. In the second, while the stopping criterion not satisfied a search procedure in the neighborhood of the current solution is triggered, each time, an update of the best solution is performed. In this implementation model, we choose an adaptation of the simulated annealing criterion to better explore the neighborhood.Algorithm 3: ILS algorithm.
Input: π0=π1,…,πn the initial sequence
πbest⟵π0, π⟵π0
while {the stopping criterion not satisfied} do
Chooseπ′ from the neighborhood of Nkπ
if Cmaxπ′<Cmaxπ then
π⟵π′
if Cmaxπ<Cmaxπbest then
πbest⟵π
end if
else
if random≤exp−Cmaxπ′−Cmaxπ/Temp then
π⟵π′
end if
end if
end while
Output: πbestThe implementation of the ILS algorithm requires a set of parameter settings to better converge to the optimal solution depending on the size of the problem. The first parameter is the stop condition of the algorithm that we consider here in number of iterations, the second parameter is the acceptance condition of the simulated annealing modelTemp, We adopt the following model:(16)Temp=T0×∑j=1n∑i=1mpi,j+si10×m×n.This expression is given according to the characteristic of the PFSP-SIST problem. The parameterT0 makes possible to control the speed of convergence of our algorithm, we choose in this study T0∈0.5,…,0.98. This model of temperature has been adopted in several research works concerning the PFSP problem (see, for example, [50]).The local search metaheuristics requires the definition of the neighborhood structure exploration, we propose four structures (Ni, i = 1, …, 4). Starting from the current sequence of Figure 3 where the jobs in positions 2 and 7, respectively, are used to generate the set of neighborhoods considered. Neighborhood N1 is defined by the permutation of the position of two jobs. Neighborhood N2 adopts the insertion and shift to the right, and Neighborhood N3 considers the insertion and shift on the left. Finally, neighborhood N4 is defined by job blocks inversion between two different positions in the sequence.Figure 3
Neighborhood structure.


### 3.3.2. IG Algorithm

The second heuristic implemented to solve our problem is the IG algorithm (see Algorithm4). This algorithm is based on three stages of resolution: the step of destruction of the current solution, the step of the reconstruction of the solution and the last step concerns the local search procedure. The first two stages constitute the first main phase of the principle of the algorithm IG, the second main phase is that of the neighborhood exploration. Recent work in applying the IG [51–53] algorithm shows the rising power of this algorithm in solving the optimization problem in the scheduling domain. The implementation of this algorithm requires also a set of setting parameters, the stop condition, the number d of jobs extracted in the sequence to build the new sequence, the parameter of the simulated annealing temperature, and finally the structure of the neighborhood used in the exploration phase. For the stop condition and the temperature parameter Temp, we adopt the same condition as that adopted for the ILS algorithm. As for the neighborhood structure, we consider the same structure as ILS. For the d parameter of extracted jobs, we consider that it also depends on the size of the problem knowing that d∈n/4,n/3, for n∈5,…,50 and d∈n/3,n/2 for n>50.Algorithm 4: Iterated greedy algorithm.
Input:
π the initial sequence.
πbest⟵π
while unsatisfied stopping criterion do
π′⟵π
for u=1 to ddo
Extract a jobπu at random from the sequence π′ and add the job πu to the Φ subset.
end for
for u=1 to ddo
Extract theπu′ job from Φ subset.
Test the job on all positions in the current sequenceπ′ and choose the best position giving the best completion time.
end for
Chooseπ″ from the neighborhood of Nkπ′
if Cmaxπ″<Cmaxπ then
π⟵π″
if Cmaxπ<Cmaxπbest then
πbest⟵π
end if
else
if random≤exp−Cmaxπ″−Cmaxπ/Temp then
π⟵π″
end if
end if
end while
Output: πbestWe present here an illustrative example of the procedure of destruction and reconstruction of the IG algorithm. Knowing that the current solution isπ=7,8,5,4,2,6,1,3, we randomly extract two jobs, for example, 7 and 6, the remaining sequence is πd=8,5,4,2,1,3. Subsequently, we insert the first 7 job in all positions, and we select the best constructed sequence giving the value of Cmax, for example π=8,5,4,7,2,1,3. We repeat the procedure for the new built sequence and insert job 6 in all possible positions, and at the end, we get the best value from the makespan. Figure 4 gives a representation of the procedure of destruction and reconstruction of the IG algorithm.Figure 4
IG procedure.


## 3.3.1. ILS Algorithm

The ILS algorithm is considered one of the powerful optimization algorithms for solving scheduling problems. We find the latest applications of this algorithm in [47–49] for solving the PFSP problem and its extensions under various implementations. In Algorithm 3, we describe the steps of the development of this algorithm. In the first phase, an initial solution is given by one of the initialization heuristics. In the second, while the stopping criterion not satisfied a search procedure in the neighborhood of the current solution is triggered, each time, an update of the best solution is performed. In this implementation model, we choose an adaptation of the simulated annealing criterion to better explore the neighborhood.Algorithm 3: ILS algorithm.
Input: π0=π1,…,πn the initial sequence
πbest⟵π0, π⟵π0
while {the stopping criterion not satisfied} do
Chooseπ′ from the neighborhood of Nkπ
if Cmaxπ′<Cmaxπ then
π⟵π′
if Cmaxπ<Cmaxπbest then
πbest⟵π
end if
else
if random≤exp−Cmaxπ′−Cmaxπ/Temp then
π⟵π′
end if
end if
end while
Output: πbestThe implementation of the ILS algorithm requires a set of parameter settings to better converge to the optimal solution depending on the size of the problem. The first parameter is the stop condition of the algorithm that we consider here in number of iterations, the second parameter is the acceptance condition of the simulated annealing modelTemp, We adopt the following model:(16)Temp=T0×∑j=1n∑i=1mpi,j+si10×m×n.This expression is given according to the characteristic of the PFSP-SIST problem. The parameterT0 makes possible to control the speed of convergence of our algorithm, we choose in this study T0∈0.5,…,0.98. This model of temperature has been adopted in several research works concerning the PFSP problem (see, for example, [50]).The local search metaheuristics requires the definition of the neighborhood structure exploration, we propose four structures (Ni, i = 1, …, 4). Starting from the current sequence of Figure 3 where the jobs in positions 2 and 7, respectively, are used to generate the set of neighborhoods considered. Neighborhood N1 is defined by the permutation of the position of two jobs. Neighborhood N2 adopts the insertion and shift to the right, and Neighborhood N3 considers the insertion and shift on the left. Finally, neighborhood N4 is defined by job blocks inversion between two different positions in the sequence.Figure 3
Neighborhood structure.


## 3.3.2. IG Algorithm

The second heuristic implemented to solve our problem is the IG algorithm (see Algorithm4). This algorithm is based on three stages of resolution: the step of destruction of the current solution, the step of the reconstruction of the solution and the last step concerns the local search procedure. The first two stages constitute the first main phase of the principle of the algorithm IG, the second main phase is that of the neighborhood exploration. Recent work in applying the IG [51–53] algorithm shows the rising power of this algorithm in solving the optimization problem in the scheduling domain. The implementation of this algorithm requires also a set of setting parameters, the stop condition, the number d of jobs extracted in the sequence to build the new sequence, the parameter of the simulated annealing temperature, and finally the structure of the neighborhood used in the exploration phase. For the stop condition and the temperature parameter Temp, we adopt the same condition as that adopted for the ILS algorithm. As for the neighborhood structure, we consider the same structure as ILS. For the d parameter of extracted jobs, we consider that it also depends on the size of the problem knowing that d∈n/4,n/3, for n∈5,…,50 and d∈n/3,n/2 for n>50.Algorithm 4: Iterated greedy algorithm.
Input:
π the initial sequence.
πbest⟵π
while unsatisfied stopping criterion do
π′⟵π
for u=1 to ddo
Extract a jobπu at random from the sequence π′ and add the job πu to the Φ subset.
end for
for u=1 to ddo
Extract theπu′ job from Φ subset.
Test the job on all positions in the current sequenceπ′ and choose the best position giving the best completion time.
end for
Chooseπ″ from the neighborhood of Nkπ′
if Cmaxπ″<Cmaxπ then
π⟵π″
if Cmaxπ<Cmaxπbest then
πbest⟵π
end if
else
if random≤exp−Cmaxπ″−Cmaxπ/Temp then
π⟵π″
end if
end if
end while
Output: πbestWe present here an illustrative example of the procedure of destruction and reconstruction of the IG algorithm. Knowing that the current solution isπ=7,8,5,4,2,6,1,3, we randomly extract two jobs, for example, 7 and 6, the remaining sequence is πd=8,5,4,2,1,3. Subsequently, we insert the first 7 job in all positions, and we select the best constructed sequence giving the value of Cmax, for example π=8,5,4,7,2,1,3. We repeat the procedure for the new built sequence and insert job 6 in all possible positions, and at the end, we get the best value from the makespan. Figure 4 gives a representation of the procedure of destruction and reconstruction of the IG algorithm.Figure 4
IG procedure.


## 4. Computational Results

To validate our approaches of resolution for the studied problem, we propose two comparative studies between the different algorithms. The first comparative study is based on the calculation of the relative percentage deviation (RPD). The second concerns the convergence study of resolution algorithms for medium and large instances. For the first comparative study, we give the expression of RPD by the following formula:(17)RPDHi=CmaxHi−CmaxbestCmaxbest×100;i∈1,2,where H1 stands for HBJR and H2 represents NEH heuristic. In this expression, we measure the deviation of the solution found from the optimal solution given by the MILP, for relatively small instances, where CmaxHi represents the solution found by the heuristic Hi and Cmaxbest represents the value found by the MILP. Table 2 shows the results found for some tested instances. We limit ourselves to such number of problems; our objective is to highlight the effectiveness of resolution heuristics and their relevance to solve this problem. From the results, we find that the heuristic NEH is better compared with the heuristic based on the rule of Johnson.Table 2
Comparison between mixed-integer linear programming and heuristics.
job
×
machine
MILP
HBJR
NEH
RPD
H
1
RPD
H
2
5
×
2
177
177
177
0
0
10
×
2
324
324
324
0
0
15
×
2
495
495
495
0
0
20
×
2
658
658
658
0
0
30
×
2
928
928
928
0
0
5
×
5
316
332
316
5.06
0
10
×
5
449
459
453
2.22
0.89
15
×
5
598
660
602
10.36
0.66
20
×
5
763
826
767
8.25
0.52
5
×
10
460
476
493
3.47
7.17
10
×
10
599
652
616
8.84
2.83
15
×
10
764
841
780
10.07
2.09
5
×
15
599
599
605
0
1.0
10
×
15
727
765
739
5.22
1.65
15
×
15
882
994
919
12.69
4.19
5
×
20
748
757
759
1.2
1.47
10
×
20
900
958
933
6.44
3.66
15
×
20
1069
1166
1101
9.07
2.99Table2 shows the RPDHi obtained for different combinations m×n, where m is the number of machines and n stands for the number of jobs. It is observed that for m=2, the obtained results by the heuristics are the same and equal to those given by the MILP. It is also shown that for a number of jobs n≥10, the NEH heuristic gives better results than those calculated by the heuristic based on Johnson’s rule.For relatively large and medium instances, we measure the deviation from the best solution given by the ILS and IG algorithms. For this last class of problem, we vary the number of jobs and machines to reach high instances. We note that computation is given for an average of five instances for each algorithm. The result in this comparative study is given in Table3; this table shows the clear superiority of the IG algorithm with respect to ILS for all tested instances. We report that the number of machines tested is m∈5,10,20,30, and the number jobs varies in a way to cover different sizes and reaches a maximum of 600 jobs. We have tried to better concertize the real size of the jobs processed in industrial batches.Table 3
Comparison between iterated local search and iterated greedy.
job
×
machine
RPD
ILS
RPD
IG
10
×
5
0.000
0.000
20
×
5
0.864
0.000
30
×
5
0.559
0.000
40
×
5
0.050
0.000
50
×
5
0.086
0.000
60
×
5
0.466
0.000
20
×
10
1.713
0.129
30
×
10
0.440
0.101
40
×
10
0.902
0.043
50
×
10
1.464
0.287
60
×
10
0.272
0.110
10
×
20
0.461
0.000
20
×
20
0.990
0.030
30
×
20
0.427
0.159
40
×
20
0.430
0.187
50
×
20
1.386
0.483
60
×
20
1.937
0.097
70
×
20
1.588
0.010
80
×
20
0.545
0.143
90
×
20
0.645
0.109
100
×
20
0.34
0.120
140
×
20
1.158
0.060
160
×
20
1.370
0.051
200
×
20
1.167
0.000
240
×
20
1.315
0.173
300
×
20
0.466
0.121
340
×
20
0.637
0.007
400
×
20
1.729
0.000
500
×
30
0.816
0.000
600
×
30
0.506
0.016The analysis concerning the numerical results shows the efficiency of our suggested metaheuristics in term of convergence towards their good solutions.In Figure5, we represent the evolution of the values of the objective function as a function of the number of iteration for two instances 40×10 and 40×20; the two algorithms converge to their stable values about after 80th iteration, and IG saves an important gain of units time compared with ILS. For the second instances, the two ILS and IG algorithms converge to their stable bounds at about 280th iterations and that IG is better compared to ILS.Figure 5
Makespan vs. number of iterations forn=40 and m=10 (a) and for n=40 and m=20 (b).
(a)
(b)In Figure6, we represent the evolution of the objective function for the two instances 100×10 and 100×20, respectively. These two instances can be considered relatively larger instances. This type of size is frequently encountered in modern industry, where customers ask for a fairly high batch. For the first instance, we can see that the two algorithms stabilize after the 180th iteration; a significant gain in calendar scheduling time is recorded by IG compared with ILS algorithm. For the second instance, we can conclude that the IG gives best results comparing with the ILS algorithm after 90th iteration.Figure 6
Makespan vs. number of iterations forn=100 and m=10 (a) and for n=100 and m=20 (b).
(a)
(b)The four tested instances, in the convergence comparison study, have been implemented for the NEH initialization heuristic. Indeed, this initialization algorithm gives us better results in terms of RPD for relatively small instances and relatively large and medium instances.


## 5. Conclusion

In this paper, we have studied a flow shop problem with permutation and sequence-independent setup time in order to minimize the makespan. First, we have conducted a comparative study between the exact mixed-integer linear programming method and two heuristics, one is based on Johnson’s rule, and the other is based on NEH algorithm. The two heuristics were compared with the results of the MILP for all instances. Simulations are performed for relatively small instances by varying the number of jobs and machines. It was observed that the NEH heuristic gives better results than those given by the heuristic based on Johnson’s rule. On the contrary, two metaheuristics are used for medium to relatively large instances. We have concluded that IG algorithm gives good results comparing with ILS metaheuristic. In this paper, we have studied PFSP-SIST problem by using MILP model and different metaheuristics. However, adding an other constraint to this problem like unavailability or no-idle machines can be considered as a potential future issue.



---

*Source: 7132469-2020-01-22.xml*