Article ID: | iaor19982215 |
Country: | Netherlands |
Volume: | 89 |
Issue: | 1 |
Start Page Number: | 172 |
End Page Number: | 175 |
Publication Date: | Feb 1996 |
Journal: | European Journal of Operational Research |
Authors: | Lenstra J.K., Hoogeveen J.A., Veltman B. |
Keywords: | parallel machines, complexity, flowshop |
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.