Iterated Local Search Algorithms for the Sequence-Dependent Setup Times Flow Shop Scheduling Problem Minimizing Makespan

Iterated Local Search (ILS) algorithm is a simple and effective metaheuristic for permutation flow shop scheduling problem (PFSP) minimizing the total flow time. In this work, the ILS algorithms are studied to deal with the PFSP with sequence-dependent setup times (SDST-PFSP) minimizing makespan. The first two methods, originally proposed for the PFSP minimizing total flow time, are adapted for the discussed problem. Four other ILS versions are also designed using different perturbation methods. Experimental results on a benchmark set show that the proposed ILSs can solve the discussed problem more effectively, and much better than the iterated greedy algorithm, one of the existing state-of-the-art algorithms. This work shows that the ILS is a promising method for extended types of scheduling problems.