Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. (English) Zbl 0908.90164

Summary: 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.


90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems
Full Text: DOI


[1] Arthanari, T.S., On some problems of sequencing and grouping, () · Zbl 1103.90078
[2] Blazewicz, J.; Dror, M.; Pawlak, G.; Stecke, K.E., Scheduling parts through a two-stage tandem flexible flow shop, (1992), unpublished manuscript
[3] Brah, S.A.; Hunsucker, J.L., Branch and bound algorithm for the flow shop with multiple processors, European journal of operational research, 51, 88-99, (1991) · Zbl 0732.90040
[4] Buten, R.E.; Shen, V.Y., A scheduling model for computer systems with two classes of processors, (), 130-138
[5] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[6] Johnson, S.M., Optimal two- and three-stage production schedules with set-up times included, Naval research logistics quarterly, 1, 61-68, (1954) · Zbl 1349.90359
[7] McNaughton, R., Scheduling with deadlines and loss functions, Management science, 6, 1-12, (1959) · Zbl 1047.90504
[8] Sriskandarajah, C.; Sethi, S.P., Scheduling algorithms for flexible flowshops: worst and average case performance, European journal of operational research, 43, 143-160, (1989) · Zbl 0691.90038
[9] Vandevelde, A.M.G.; Hoogeveen, J.A.; Hurkens, C.A.T.; Lenstra, J.K., Lower bounds for the multiprocessor flow shop, (1995), submitted for publication
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.