An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives

Iterated Greedy (IG) algorithms are based on a very simple principle, are easy to implement and can show excellent performance. In this paper, we propose two new IG algorithms for a complex flowshop problem that results from the consideration of sequence dependent setup times on machines, a characteristic that is often found in industrial settings. The first IG algorithm is a straightforward adaption of the IG principle, while the second incorporates a simple descent local search. Furthermore, we consider two different optimization objectives, the minimization of the maximum completion time or makespan and the minimization of the total weighted tardiness. Extensive experiments and statistical analyses demonstrate that, despite their simplicity, the IG algorithms are new state-of-the-art methods for both objectives. (C) 2006 Elsevier B.V. All rights reserved.