Constructive heuristics and mathematical formulation for solving the permutation flow shop scheduling problem with setup time

In this work, we will propose a various of constructive heuristics and a mathematical formulation for solving the permutation flow shop scheduling problem. The objective is the minimization of the makespan under constraints of the sequence dependent setup time. The proposed mathematical formulation is represented by a mixed integer linear programming (MILP) model. The constructive solution heuristics are the algorithm developed by Nawaz-Enscore and Ham (NEH) and the greedy randomized adaptive search procedure (GRASP) and the generalized Johnson’s rule method (GJRM). The comparative study is carried out on small sequence size. The objective is to validate our heuristics with respect to the optimal solution given by MILP. The results obtained show that the NEH heuristic has a good results compared to the other two methods.