Johnson  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  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.