✦ LIBER ✦
Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
✍ Scribed by J.A. Hoogeveen; J.K. Lenstra; B. Veltman
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 352 KB
- Volume
- 89
- Category
- Article
- ISSN
- 0377-2217
No coin nor oath required. For personal study only.
✦ Synopsis
In 1954, Johnson gave an efficient algorithm for minimizing makespan in a two-machine flow shop; there is no advantage to preemption in this case. McNaughton's wrap-around rule of 1959 finds a shortest preemptive schedule on identical parallel machines in linear time. A similarly efficient algorithm is unlikely to exist for the simplest common generalization of these problems. We show that preemptive scheduling in a two-stage flow shop with at least two identical parallel machines in one of the stages so as to minimize makespan is NP-hard in the strong sense.