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

@article{citeulike:5013323, abstract = {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.}, author = {Ruiz, R. and Stutzle, T.}, citeulike-article-id = {5013323}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.ejor.2005.12.009}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0377221705008507}, day = {16}, doi = {10.1016/j.ejor.2005.12.009}, issn = {03772217}, journal = {European Journal of Operational Research}, keywords = {heuristics, phd, scheduling}, month = {March}, number = {3}, pages = {2033--2049}, posted-at = {2009-06-29 16:04:24}, priority = {2}, title = {A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem}, url = {http://dx.doi.org/10.1016/j.ejor.2005.12.009}, volume = {177}, year = {2007} }

TY - JOUR ID - citeulike:5013323 L3 - citeulike-article-id:5013323 N2 - 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. IS - 3 JF - European Journal of Operational Research SN - 03772217 EP - 2049 TI - A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem VL - 177 SP - 2033 KW - heuristics KW - phd KW - scheduling AU - Ruiz, R AU - Stutzle, T PY - 2007/03/16/ UR - http://dx.doi.org/10.1016/j.ejor.2005.12.009 ER -