Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard

Johnson [1954] gave an efficient algorithm for minimizing makespan in a two-rnachine flow shop; there is no advantage to preemption in this case. McNaughton's wrap-around rule [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 prblems. We show that preemptive scheduling in a two-stage flow shop with at least two identical parallel machines in oneofthe stages so as to minimize makespan is NP-hard in the strong sense. Key Words & Phrases: flow shop, parallel machines, complexity, NP-hardness.