Back to Search Start Over

Minimizing the maximum tardiness for a permutation flow shop problem under the constraint of sequence independent setup time.

Authors :
Elissaouy, Oualid
Allali, Karam
Source :
RAIRO: Operations Research (2804-7303); 2024, Vol. 58 Issue 1, p373-395, 23p
Publication Year :
2024

Abstract

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
28047303
Volume :
58
Issue :
1
Database :
Complementary Index
Journal :
RAIRO: Operations Research (2804-7303)
Publication Type :
Academic Journal
Accession number :
175985361
Full Text :
https://doi.org/10.1051/ro/2024001