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 条
  • [31] A GREEDY ALGORITHM FOR MULTIOBJECTIVE FUZZY FLOW-SHOP SCHEDULING PROBLEM
    Engin, Orhan
    Yilmaz, M. Kerim
    Akkoyunlu, M. Cabir
    Baysal, M. Emin
    Sarucan, Ahmet
    UNCERTAINTY MODELING IN KNOWLEDGE ENGINEERING AND DECISION MAKING, 2012, 7 : 189 - 194
  • [32] A Modified Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem
    Al Aqel, Ghiath
    Li, Xinyu
    Gao, Liang
    CHINESE JOURNAL OF MECHANICAL ENGINEERING, 2019, 32 (01)
  • [33] A Modi ed Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem
    Ghiath Al Aqel
    Xinyu Li
    Liang Gao
    Chinese Journal of Mechanical Engineering, 2019, 32 (02) : 157 - 167
  • [34] A Hybrid Iterated Greedy Algorithm for a Crane Transportation Flexible Job Shop Problem
    Li, Jun-Qing
    Du, Yu
    Gao, Kai-Zhou
    Duan, Pei-Yong
    Gong, Dun-Wei
    Pan, Quan-Ke
    Suganthan, P. N.
    IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2022, 19 (03) : 2153 - 2170
  • [35] A Modi ed Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem
    Ghiath Al Aqel
    Xinyu Li
    Liang Gao
    Chinese Journal of Mechanical Engineering, 2019, (02) : 157 - 167
  • [36] Performance Analysis of Greedy-based Construction Heuristics on Classical Vehicle Routing Problem
    He, Yandong
    Qi, Mingyao
    Zhou, Fuli
    Li, Huilin
    2020 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEE IEEM), 2020, : 591 - 594
  • [37] The Permutation Flow Shop Scheduling Problem with Human Resources: MILP Models, Decoding Procedures, NEH-Based Heuristics, and an Iterated Greedy Algorithm
    Fernandez-Viagas, Victor
    Sanchez-Mediano, Luis
    Angulo-Cortes, Alvaro
    Gomez-Medina, David
    Molina-Pariente, Jose Manuel
    MATHEMATICS, 2022, 10 (19)
  • [38] Heuristics for an industrial car sequencing problem considering paint and assembly shop objectives
    Joly, Alexandre
    Frein, Yannick
    COMPUTERS & INDUSTRIAL ENGINEERING, 2008, 55 (02) : 295 - 310
  • [39] Quadratic Unconstrained Binary Optimization for the Automotive Paint Shop Problem
    Debevere, Pieter
    Sugimura, Masahiko
    Parizy, Matthieu
    IEEE ACCESS, 2023, 11 : 97769 - 97777
  • [40] Iterated Greedy Algorithm for Solving a Hybrid Flow Shop Scheduling Problem with Reentrant Jobs
    Zhang, Qi
    Tian, Zheng
    Wang, Sen
    Liu, Shixin
    PROCEEDINGS OF THE 32ND 2020 CHINESE CONTROL AND DECISION CONFERENCE (CCDC 2020), 2020, : 5636 - 5641
12345