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

Times Cited: 2 Article English Ruiz, R Univ Politecn Valencia, Dept Estadist {&} Invest Operat Aplicadas {&} Calidad, Grp Invest Operat, Camino Vera S-N, Valencia 46021, Spain Cited References Count: 37 253ZS ELSEVIER SCIENCE BV PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS AMSTERDAM

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