Greedy versus recursive greedy: Uncorrelated heuristics for the binary paint shop problem

被引：1
|
作者：
Andres, Stephan Dominique [1 ]
机构：
[1] Univ Greifswald, Inst Math & Comp Sci, Walther Rathenau Str 47, D-17487 Greifswald, Germany
来源：
DISCRETE APPLIED MATHEMATICS | 2021年 / 303卷
关键词：
Binary paint shop problem; Greedy heuristic; Recursive greedy heuristic; Red first heuristic; Greedy-perfect; Recursive-greedy-perfect; Red-first-perfect; APX-hardness; COLORINGS;
D O I：
10.1016/j.dam.2020.05.028
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
It is well-known that there are instances of the binary paint shop problem for which the recursive greedy heuristic is better than the greedy heuristic. In this note, we give an example of a family of instances where the greedy heuristic is better than the recursive greedy heuristic, thus showing that these heuristics are uncorrelated. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页码：4 / 7
页数：4
相关论文
共 50 条
  • [41] A hybrid iterated greedy algorithm for the distributed no-wait flow shop scheduling problem
    Shao, Weishi
    Pi, Dechang
    Shao, Zhongshi
    2017 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2017, : 9 - 16
  • [42] Improved greedy genetic algorithm for solving the hybrid flow-shop scheduling problem
    Song C.
    Xi Tong Gong Cheng Yu Dian Zi Ji Shu/Systems Engineering and Electronics, 2019, 41 (05): : 1079 - 1086
  • [43] Chemical Reaction Optimization metaheuristic with Greedy algorithm for Flexible Job shop Scheduling Problem
    Marzouki, Bilel
    Driss, Olfa Belkahla
    Ghedira, Khaled
    2017 INTERNATIONAL CONFERENCE ON ENGINEERING & MIS (ICEMIS), 2017,
  • [44] Greedy randomised dispatching heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties
    Jorge M. S. Valente
    Maria R. A. Moreira
    The International Journal of Advanced Manufacturing Technology, 2009, 44 : 995 - 1009
  • [45] Greedy randomised dispatching heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties
    Valente, Jorge M. S.
    Moreira, Maria R. A.
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 44 (9-10): : 995 - 1009
  • [46] NEW GREEDY-LIKE HEURISTICS FOR THE MULTIDIMENSIONAL 0-1 KNAPSACK-PROBLEM
    LOULOU, R
    MICHAELIDES, E
    OPERATIONS RESEARCH, 1979, 27 (06) : 1101 - 1114
  • [47] An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion
    Pan, Quan-Ke
    Wang, Ling
    Zhao, Bao-Hua
    International Journal of Advanced Manufacturing Technology, 2008, 38 (7-8): : 778 - 786
  • [48] An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem
    Ribas, Imma
    Companys, Ramon
    Tort-Martorell, Xavier
    EXPERT SYSTEMS WITH APPLICATIONS, 2019, 121 : 347 - 361
  • [49] Iterated greedy insertion approaches for the flexible job shop scheduling problem with transportation times constraint
    Bekkar A.
    Belalem G.
    Beldjilali B.
    International Journal of Manufacturing Research, 2019, 14 (01) : 43 - 66
  • [50] An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion
    Pan, Quan-Ke
    Wang, Ling
    Zhao, Bao-Hua
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2008, 38 (7-8): : 778 - 786
12345