Flow-shop scheduling with exact delays to minimize makespan

被引：6
作者：
Khatami, Mostafa [1 ,2 ]
Salehipour, Amir [3 ]
Cheng, T. C. E. [4 ]
机构：
[1] Univ Technol Sydney, Sch Math & Phys Sci, Sydney, NSW 2007, Australia
[2] Queensland Univ Technol, Ctr Data Sci, Brisbane, Qld 4000, Australia
[3] Univ Sydney, Business Sch, Sydney, NSW, Australia
[4] Hong Kong Polytech Univ, PolyU Business Sch, Hong Kong, Peoples R China
来源：
COMPUTERS & INDUSTRIAL ENGINEERING | 2023年 / 183卷
基金：
澳大利亚研究理事会;
关键词：
Scheduling; Flow-shop; Coupled task; Exact delays; Pyramidal property; NO-WAIT FLOWSHOP; SEQUENCING PROBLEM; MACHINE; SHOP;
D O I：
10.1016/j.cie.2023.109456
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
The flow-shop scheduling problem with exact delays is generalization of no-wait flow-shop scheduling in which an exact delay exists between the consecutive tasks of each job. The problem with distinct delays to minimize the makespan is strongly NP-hard even for the two-machine case with unit execution time tasks. Providing polynomial-time solutions for special cases of the problem, we show that the two-machine permutation flow-shop case is solvable in O(n log n) time, while the case with more than two machines is strongly NP-hard. We also show that the multi-machine case with delays following the ordered structure possesses the pyramidal-shaped property and propose an O(n2)-time dynamic program to solve it. We further improve the time complexity of the solution algorithm to O(n log n) under certain conditions.
引用
收藏
页数：8
相关论文
共 34 条
  • [1] Approximation algorithms for UET scheduling problems with exact delays
    Ageev, Alexander A.
    Baburin, Alexei E.
    [J]. OPERATIONS RESEARCH LETTERS, 2007, 35 (04) : 533 - 540
  • [2] The Non-Permutation Flow-Shop scheduling problem: A literature review
    Alejandro Rossit, Daniel
    Tohme, Fernando
    Frutos, Mariano
    [J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2018, 77 : 143 - 153
  • [3] A survey of scheduling problems with no-wait in process
    Allahverdi, Ali
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 255 (03) : 665 - 686
  • [4] SCHEDULING IN A SEMI-ORDERED FLOWSHOP WITHOUT INTERMEDIATE QUEUES
    ARORA, RK
    RANA, SP
    [J]. AIIE TRANSACTIONS, 1980, 12 (03): : 263 - 272
  • [5] Scheduling prioritized patients in emergency department laboratories
    Azadeh, A.
    Farahani, M. Hosseinabadi
    Torabzadeh, S.
    Baghersad, M.
    [J]. COMPUTER METHODS AND PROGRAMS IN BIOMEDICINE, 2014, 117 (02) : 61 - 70
  • [6] Baker K. R., 2013, Principles of sequencing and scheduling
  • [7] Reducing access times for radiation treatment by aligning the doctor's schemes
    Bikker, Ingeborg A.
    Kortbeek, Nikky
    van Os, Rob M.
    Boucherie, Richard J.
    [J]. OPERATIONS RESEARCH FOR HEALTH CARE, 2015, 7 : 111 - 121
  • [8] Scheduling of coupled tasks and one-machine no-wait robotic cells
    Brauner, Nadia
    Finke, Gerd
    Lehoux-Lebacque, Vassilissa
    Potts, Chris
    Whitehead, Jonathan
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) : 301 - 307
  • [9] Well-solvable special cases of the traveling salesman problem: A survey
    Burkard, RE
    Deineko, VG
    Van Dal, R
    Van der Veen, JAA
    Woeginger, GJ
    [J]. SIAM REVIEW, 1998, 40 (03) : 496 - 546
  • [10] Scheduling patient appointments via multilevel template: A case study in chemotherapy
    Condotta, A.
    Shakhlevich, N. V.
    [J]. OPERATIONS RESEARCH FOR HEALTH CARE, 2014, 3 (03) : 129 - 144
1234