Previous: AIDA-98-03 Next: AIDA-99-01 Index 1998

Intellectics Group: Technical Report 98-04

Applying Iterated Local Search to the Permutation Flow Shop Problem

Thomas Stützle

Iterated local search (ILS) is a general and powerful metaheuristic that can significantly improve the performance of local search algorithms. We give a short overview of ILS approaches and widen the range of successful ILS applications to the permutation flow shop problem (FSP). We discuss the effect of specific choices for our ILS algorithm and give an experimental analysis of its performance. Even with our use of a very simple local search, ILS compares very to other metaheuristic approaches proposed for the FSP, and in particular we find new best solutions among Taillard's benchmark problems. Additionally, we show that the so called acceptance criterion has a considerable influence on ILS performance and therefore should receive more attention in future ILS applications.

Full Paper: Compressed postscript BibTeX entry