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.

Name | Memorandum COSOR |
---|

Volume | 9320 |
---|

ISSN (Print) | 0926-4493 |
---|