@article{7c755163c43049cfb5d9eb2eada21c2a,
title = "Flow-shop scheduling with exact delays to minimize makespan",
abstract = "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(nlogn) 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(nlogn) under certain conditions.",
keywords = "Coupled task, Exact delays, Flow-shop, Pyramidal property, Scheduling",
author = "Mostafa Khatami and Amir Salehipour and Cheng, {T. C.E.}",
note = "Funding Information: We thank the editors and anonymous referees for their valuable and constructive comments on earlier versions of the paper. Mostafa Khatami is a recipient of UTS International Research Scholarship (IRS) and UTS President's Scholarship (UTSP). Amir Salehipour is a recipient of the Australian Research Council Discovery Early Career Researcher Award (project number DE170100234) funded by the Australian Government. Cheng was also supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration. Funding Information: We thank the editors and anonymous referees for their valuable and constructive comments on earlier versions of the paper. Mostafa Khatami is a recipient of UTS International Research Scholarship (IRS) and UTS President{\textquoteright}s Scholarship (UTSP) . Amir Salehipour is a recipient of the Australian Research Council Discovery Early Career Researcher Award (project number DE170100234) funded by the Australian Government . Cheng was also supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration . Publisher Copyright: {\textcopyright} 2023 The Author(s)",
year = "2023",
month = sep,
doi = "10.1016/j.cie.2023.109456",
language = "English",
volume = "183",
journal = "Computers and Industrial Engineering",
issn = "0360-8352",
publisher = "Elsevier Ltd",
}