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 𝑁𝑃-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 𝑂(𝑛log𝑛) time, while the case with more than two machines is strongly 𝑁𝑃-hard. We also show that the multi-machine case with delays following the ordered structure possesses the pyramidal-shaped property and propose an 𝑂(𝑛2)-time dynamic program to solve it. We further improve the time complexity of the solution algorithm to 𝑂(𝑛log𝑛) under certain conditions.