Ja. Hoogeveen et al., PREEMPTIVE SCHEDULING IN A 2-STAGE MULTIPROCESSOR FLOW-SHOP IS NP-HARD, European journal of operational research, 89(1), 1996, pp. 172-175
Citations number
9
Categorie Soggetti
Management,"Operatione Research & Management Science
In 1954, Johnson gave an efficient algorithm for minimizing makespan i
n a two-machine flow shop; there is no advantage to preemption in this
case. McNaughton's wrap-around rule of 1959 finds a shortest preempti
ve schedule on identical parallel machines in linear time. A similarly
efficient algorithm is unlikely to exist for the simplest common gene
ralization of these problems. We show that preemptive scheduling in a
two-stage flow shop with at least two identical parallel machines in o
ne of the stages so as to minimize makespan is NP-hard in the strong s
ense.