Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard

Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard

0.00 Avg rating0 Votes
Article ID: iaor2008186
Country: United Kingdom
Volume: 7
Issue: 5
Start Page Number: 333
End Page Number: 348
Publication Date: Sep 2004
Journal: Journal of Scheduling
Authors: , ,
Keywords: computational analysis
Abstract:

One of the first problems to be studied in scheduling theory was the problem of minimizing the makespan in a two-machine flow shop. Johnson showed that this problem can be solved in O(n log n) time. A crucial assumption here is that the time needed to move a job from the first to the second machine is negligible. If this is not the case and if this ‘delay’ is not equal for all jobs, then the problem becomes NP-hard in the strong sense. We show that this is even the case if all processing times are equal to one. As a consequence, we show strong NP-hardness of a number of similar problems, including a severely restricted version of the Numerical 3-Dimensional Matching problem.

Reviews

Required fields are marked *. Your email address will not be published.