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
    Ahmadi, S
    Osman, IH
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 162 (01) : 30 - 44
  • [2] A review of scheduling research involving setup considerations
    Allahverdi, A
    Gupta, JND
    Aldowaisan, T
    [J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1999, 27 (02): : 219 - 239
  • [3] SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW
    BAKER, KR
    SCUDDER, GD
    [J]. OPERATIONS RESEARCH, 1990, 38 (01) : 22 - 36
  • [4] Early/tardy scheduling with sequence dependent setups on uniform parallel machines
    Balakrishnan, N
    Kanet, JJ
    Sridharan, V
    [J]. COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (02) : 127 - 141
  • [5] A tabu search algorithm for parallel machine total tardiness problem
    Bilge, Ü
    Kiraç, F
    Kurtulan, M
    Pekgün, P
    [J]. 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
    Bräysy, I
    Gendreau, M
    [J]. TRANSPORTATION SCIENCE, 2005, 39 (01) : 119 - 139
  • [8] A reactive variable neighborhood search for the vehicle-routing problem with time windows
    Bräysy, O
    [J]. 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
    Burke, EK
    Gustafson, S
    Kendall, G
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2004, 8 (01) : 47 - 62
123456