Minimizing total tardiness in parallel machine scheduling with setup times:: An adaptive memory-based GRASP approach

被引：39
作者：
Armentano, Vinicius Amaral
de Franca Filho, Moacir Felizardo
机构：
[1] Univ Estadual Campinas, Fac Engn Eletr & Computacao, BR-13083852 Campinas, SP, Brazil
[2] Ctr Fed Educacao Tecnol Minas Gerais, Dept Acad Engn Mec, BR-30510000 Belo Horizonte, MG, Brazil
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2007年 / 183卷 / 01期
基金：
巴西圣保罗研究基金会;
关键词：
scheduling; parallel machines; setup times; adaptive memory; greedy randomized adaptive search procedures;
D O I：
10.1016/j.ejor.2006.09.077
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
This paper deals with the problem of scheduling jobs in uniform parallel machines with sequence-dependent setup times in order to minimize the total tardiness relative to job due dates. We propose GRASP versions that incorporate adaptive memory principles for solving this problem. Long-term memory is used in the construction of an initial solution and in a post-optimization procedure which connects high quality local optima by means of path relinking. Computational tests are carried out on a set of benchmark instances and the proposed GRASP versions are compared with heuristic methods from the literature. (c) 2006 Published by Elsevier B.V.
引用
收藏
页码：100 / 114
页数：15
相关论文
共 53 条
[1]   Greedy random adaptive memory programming search for the capacitated clustering problem [J].
Ahmadi, S ;
Osman, IH .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 162 (01) :30-44
[2]   A review of scheduling research involving setup considerations [J].
Allahverdi, A ;
Gupta, JND ;
Aldowaisan, T .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1999, 27 (02) :219-239
[3]   SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].
BAKER, KR ;
SCUDDER, GD .
OPERATIONS RESEARCH, 1990, 38 (01) :22-36
[4]   Early/tardy scheduling with sequence dependent setups on uniform parallel machines [J].
Balakrishnan, N ;
Kanet, JJ ;
Sridharan, V .
COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (02) :127-141
[5]   A tabu search algorithm for parallel machine total tardiness problem [J].
Bilge, Ü ;
Kiraç, F ;
Kurtulan, M ;
Pekgün, P .
COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (03) :397-414
[6]  
Binato S, 2002, OPER RES COMPUT SCI, V15, P59
[7]   Vehicle routing problem with time windows, part II:: Metaheuristics [J].
Bräysy, I ;
Gendreau, M .
TRANSPORTATION SCIENCE, 2005, 39 (01) :119-139
[8]   A reactive variable neighborhood search for the vehicle-routing problem with time windows [J].
Bräysy, O .
INFORMS JOURNAL ON COMPUTING, 2003, 15 (04) :347-368
[9]  
Bresina JL, 1996, PROCEEDINGS OF THE THIRTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE EIGHTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE, VOLS 1 AND 2, P271
[10]   Diversity in genetic programming: An analysis of measures and correlation with fitness [J].
Burke, EK ;
Gustafson, S ;
Kendall, G .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2004, 8 (01) :47-62
123456