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.
| Original language | English |
|---|---|
| Pages (from-to) | 333-348 |
| Number of pages | 16 |
| Journal | Journal of Scheduling |
| Volume | 7 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - Sept 2004 |
Bibliographical note
Funding Information:This research was conducted when the first author visited the Technische Universiteit Eindhoven. The visit was made possible by a grant from EIDMA, the Euler Institute of Discrete Mathematics and its Applications.
Keywords
- Computational complexity
- Flow shop scheduling
- Intermediate delays
- Makespan
- Strong NP-hardness