An iterated local search for the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times

Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs. (C) 2016 Elsevier B. V. All rights reserved.