A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem

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

Over the last decade, many metaheuristics have been applied to the flowshop scheduling problem, ranging from Simulated Annealing or Tabu Search to complex hybrid techniques. Some of these methods provide excellent effectiveness and efficiency at the expense of being utterly complicated. In fact, several published methods require substantial implementation efforts, exploit problem specific speed-up techniques that cannot be applied to slight variations of the original problem, and often re-implementations of these methods by other researchers produce results that are quite different from the original ones. In this work we present a new iterated greedy algorithm that applies two phases iteratively, named destruction, were some jobs are eliminated from the incumbent solution, and construction, where the eliminated jobs are reinserted into the sequence using the well known NEH construction heuristic. Optionally, a local search can be applied after the construction phase. Our iterated greedy algorithm is both very simple to implement and, as shown by experimental results. highly effective when compared to state-of-the-art methods. (c) 2005 Elsevier B.V. All rights reserved