A Multi-Restart Iterated Local Search Algorithm for the Permutation Flow Shop Problem Minimizing Total Flow Time
Computers & Operations Research
A variety of metaheuristics have been developed to solve the permutation flow shop problem minimizing total flow time. Iterated local search (ILS) is a simple but powerful metaheuristic used to solve this problem. Fundamentally, ILS is a procedure that needs to be restarted from another solution when it is trapped in a local optimum. A new solution is often generated by only slightly perturbing the best known solution, narrowing the search space and leading to a stagnant state. In this paper, a strategy is proposed to allow the restart solution to be generated from a group of solutions drawn from local optima. This allows an extension of the search space, while maintaining the quality of the restart solution. A multi-restart ILS (MRSILS) is proposed, with the performance evaluated on a set of benchmark instances and compared with six state of the art metaheuristics. The results show that the easily implementable MRSILS is significantly better than five of the other metaheuristics and comparable to or slightly better than the remaining one. © 2012 Elsevier Ltd. All rights reserved.
Dong, Xingye; Chen, Ping; Huang, Houkuan; and Nowak, Maciek. A Multi-Restart Iterated Local Search Algorithm for the Permutation Flow Shop Problem Minimizing Total Flow Time. Computers & Operations Research, 40, 2: , 2013. Retrieved from Loyola eCommons, School of Business: Faculty Publications and Other Works, http://dx.doi.org/10.1016/j.cor.2012.08.021
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
© Elsevier, 2013.
Author Posting. © Elsevier, 2013. This is the author's version of the work. It is posted here by permission of Elsevier for personal use, not for redistribution. The definitive version was published in Computers & Operations Research, VOLUME 40, ISSUE 2, FEB, 2013. http://dx.doi.org/10.1016/j.cor.2012.08.021