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

被引:850
作者
Ruiz, Ruben
Stutzle, Thomas
机构
[1] Univ Politecn Valencia, Dept Estadist & Invest Operat Aplicadas & Cal, Grp Invest Operat, Valencia 46021, Spain
[2] Univ Libre Bruxelles, B-1050 Brussels, Belgium
关键词
iterated greedy; flowshop scheduling; metaheuristics;
D O I
10.1016/j.ejor.2005.12.009
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:2033 / 2049
页数:17
相关论文
共 38 条
[1]   New heuristics for no-wait flowshops to minimize makespan [J].
Aldowaisan, T ;
Allahverdi, A .
COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (08) :1219-1231
[2]  
[Anonymous], 2000, DESIGN ANAL EXPT
[3]  
[Anonymous], 1998, AIDA9804 TU DARMST F
[4]  
CAMPBELL HG, 1970, MANAGE SCI B-APPL, V16, pB630
[5]   AN APPLICATION OF GENETIC ALGORITHMS FOR FLOW-SHOP PROBLEMS [J].
CHEN, CL ;
VEMPATI, VS ;
ALJABER, N .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 80 (02) :389-396
[6]   EVALUATION OF FLOW SHOP SEQUENCING HEURISTICS [J].
DANNENBRING, DG .
MANAGEMENT SCIENCE, 1977, 23 (11) :1174-1182
[7]   Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem [J].
Framinan, JM ;
Leisten, R ;
Rajendran, C .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2003, 41 (01) :121-148
[8]   A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion [J].
Grabowski, J ;
Wodecki, M .
COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (11) :1891-1909
[9]  
JACOBS LW, 1995, NAV RES LOG, V42, P1129, DOI 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO
[10]  
2-M