摘要
In this work, we will study a permutation flow shop scheduling problem under the constraint of sequence independent setup time. In our case, each machine requires a certain setup time to process all the different jobs assigned to it. Hence, this setup time will be independent of sequence of jobs, but will depend only on the nature of machine. The optimization objective is to minimize the maximum tardiness criterion. To solve this optimization problem, an exact method, heuristics and metaheuristics are the three main resolution methods that we have used. The exact method is represented by the mixed integer linear programming (MILP) model. In terms of the second category of resolution methods, we have been focused on two methods, the first is a modified heuristic based on Johnson rule (HBJR) while the second is based on the Nawaz-Enscore-Ham (NEH) algorithm. Finally, three metaheuristics have been used, namely the iterated local search (ILS) method, the iterated greedy (IG) algorithm and the genetic algorithm (GA). Our numerical results indicate that for the problems with small size instances, the NEH heuristic outperforms HBJR approach, while for relatively large size instances, the developed IG algorithm gives best results than both other metaheuristics ILS and GA.
学科与关键词
- Distributed no-wait flow shop problem with sequence dependent setup time: Optimization of makespan and maximum tardinessAllali, Karam*; Aqil, Said; Belabid, JabraneSIMULATION MODELLING PRACTICE AND THEORY, 2022, 116: 102455.被引 28
- Local search metaheuristic for solving hybrid flow shop problem in slabs and beams manufacturingAqil, Said*; Allali, KaramEXPERT SYSTEMS WITH APPLICATIONS, 2020, 162: 113716.被引 20
- A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problemRuiz, Ruben*; Stutzle, ThomasEUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177(3): 2033-2049.被引 812
