NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness

被引:70
|
作者
Fernandez-Viagas, Victor [1 ]
Framinan, Jose M. [1 ]
机构
[1] Univ Seville, Sch Engn, Ind Management, E-41092 Seville, Spain
关键词
Scheduling; Flowshop; Heuristics; NEH; Tie-breaking mechanism; Tardiness; PFSP; SEQUENCING PROBLEM; FLOWTIME MINIMIZATION; M-MACHINE; SHOP; MAKESPAN; ALGORITHM; DATES; JOBS;
D O I
10.1016/j.cor.2015.02.002
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Since Johnson's seminal paper in 1954, scheduling jobs in a permutation flowshop has been receiving the attention of hundreds of practitioners and researchers, being one of the most studied topics in the Operations Research literature. Among the different objectives that can be considered, minimising the total tardiness (i.e. the sum of the surplus of the completion time of each job over its due date) is regarded as a key objective for manufacturing companies, as it entails the fulfilment of the due dates committed to customers. Since this problem is known to be NP-hard, most research has focused on proposing approximate procedures to solve it in reasonable computation times. Particularly, several constructive heuristics have been proposed, with NEHedd being the most efficient one, serving also to provide an initial solution for more elaborate approximate procedures. In this paper, we first analyse in detail the decision problem depending on the generation of the due dates of the jobs, and discuss the similarities with different related decision problems. In addition, for the most characteristic tardiness scenario, the analysis shows that a huge number of ties appear during the construction of the solutions done by the NEHedd heuristic, and that wisely breaking the ties greatly influences the quality of the final solution. Since no tie-breaking mechanism has been designed for this heuristic up to now, we propose several mechanisms that are exhaustively tested. The results show that some of them outperform the original NEHedd by about 25% while keeping the same computational requirements. (C) 2015 Elsevier Ltd. All rights reserved.
引用
收藏
页码:27 / 36
页数:10
相关论文
共 50 条
  • [31] New idle time-based tie-breaking rules in heuristics for the permutation flowshop scheduling problems
    Baskar, A.
    Xavior, M. Anthony
    COMPUTERS & OPERATIONS RESEARCH, 2021, 133
  • [32] MILP-based local search procedures for minimizing total tardiness in the No-idle Permutation Flowshop Problem
    Balogh, Andrea
    Garraffa, Michele
    O'Sullivan, Barry
    Salassa, Fabio
    COMPUTERS & OPERATIONS RESEARCH, 2022, 146
  • [33] Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics
    Vallada, Eva
    Ruiz, Ruben
    Minella, Gerardo
    COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (04) : 1350 - 1373
  • [34] Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem
    Pan, Quan-Ke
    Gao, Liang
    Li Xin-Yu
    Jose, Framinan M.
    APPLIED SOFT COMPUTING, 2019, 81
  • [35] New heuristics for total tardiness minimization in a flexible flowshop
    Guilherme B. Mainieri
    Débora P. Ronconi
    Optimization Letters, 2013, 7 : 665 - 684
  • [36] New heuristics for the 2-stage assembly scheduling problem with total earliness and tardiness minimisation: A computational evaluation
    Talens, Carla
    Valente, Jorge M. S.
    Fernandez-Viagas, Victor
    COMPUTERS & OPERATIONS RESEARCH, 2024, 172
  • [37] A tabu memory based iterated greedy algorithm for the distributed heterogeneous permutation flowshop scheduling problem with the total tardiness criterion
    Feng, Xiaobing
    Zhao, Fei
    Jiang, Gedong
    Tao, Tao
    Mei, Xuesong
    EXPERT SYSTEMS WITH APPLICATIONS, 2024, 238
  • [38] An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem
    Xu, Jianyou
    Yin, Yunqiang
    Cheng, T. C. E.
    Wu, Chin-Chia
    Gu, Shusheng
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (04) : 1188 - 1199
  • [39] Matheuristics for the flowshop scheduling problem with controllable processing times and limited resource consumption to minimize total tardiness
    Prata, Bruno de Athayde
    Fernandez-Viagas, Victor
    Framinan, Jose M.
    Rodrigues, Carlos Diego
    COMPUTERS & OPERATIONS RESEARCH, 2022, 145
  • [40] Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling
    Fernandez-Viagas, Victor
    Molina-Pariente, Jose M.
    Framinan, Jose M.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 282 (03) : 858 - 872