Flow-shop scheduling with exact delays to minimize makespan

被引：11

作者：

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 [J].