Abstract
This paper considers a non-preemptive two-stage hybrid flow shop problem in which the first stage contains several identical machines, and the second stage contains a single machine. Each job is to be processed on one of the first-stage machines, and then on the second-stage machine. The objective is to find a schedule which minimizes the maximum completion time or makespan. The problem is NP-hard in the strong sense, even when there are two machines at the first stage. Several lower bounds are derived and are tested in a branch and bound algorithm. Also, constructive heuristics are presented, and a descent algorithm is proposed. Extensive computational tests with up to 250 jobs, and up to 10 machines in the first stage, indicate that some of the heuristics consistently generate optimal or near-optimal solutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S.A. Brah and J.L. Hunsucker, Branch and bound algorithm for a flowshop with multiple processors, European Journal of Operational Research 51(1991)88–99.
R.E. Buten and V.Y. Shen, A scheduling model for computer systems with two classes of processors, Proceedings of the Sagamore Computer Conference on Parallel Processing, 1973, pp. 130–138.
B. Chen, Scheduling multiprocessor flow shops, in: New Advances in Optimization and Approximation, D.Z. Du and J. Sun, eds., Kluwer, Boston, 1994, pp. 1–8.
B. Chen, Analysis of classes of heuristics for scheduling two-stage flow shops with parallel machines at one stage, Journal of the Operational Research Society 46(1995)234–244.
D.E. Deal and J.L. Hunsucker, The two-stage flowshop scheduling problem with M machines at each stage, Journal of Information and Optimization Sciences 12(1991)407–417.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
J.N.D. Gupta, Two-stage, hybrid flowshop scheduling problem, Journal of the Operational Research Society 39(1988)359–364.
J.N.D. Gupta and E.A. Tunc, Schedules for a two-stage hybrid flowshop with parallel machines at the second stage, International Journal of Production Research 29(1991)1489–1502.
J.A. Hoogeveen, J.K. Lenstra and B. Veltman, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European Journal of Operational Research 89(1996)172–175.
J.L. Hunsucker and J.R. Shah, Performance of priority rules in a due date flowshop, OMEGA 20 (1992)73–89.
S.M. Johnson, Optimal two-and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1(1954)61–68.
R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, eds., Plenum Press, New York, 1972, pp. 85–103.
M.A. Langston, Interstage transportation planning in the deterministic flowshop environment, Operations Research 35(1987)556–564.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Sequencing and scheduling: algorithms and complexity, in: Handbooks in Operations Research and Management Science. Vol. 4: Logistics of Production and Inventory, S.C. Graves, A.H.G. Rinnooy Kan and P.H. Zipkin, eds., North-Holland, Amsterdam, 1993, pp. 445–522.
C.-Y. Lee and G.L. Vairaktarakis, Design for schedulability: Flexible look-behind and look-ahead flowshops, Research Report 93–23, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 1993.
C.-Y. Lee and G.L. Vairaktarakis, Minimizing makespan in hybrid flowshops, Operations Research Letters 16(1994)149–158.
C. Rajendran and D. Chaudhari, Scheduling in n-job, m-stage flowshop with parallel processors to minimize makespan, International Journal of Production Economics 27(1992)137–143.
A.H.G. Rinnooy Kan, Machine Scheduling Problems, Martinus Nijhoff, The Hague, 1976.
M.S. Salvador, A solution to a special class of flow shop scheduling problems, in: Symposium of the Theory of Scheduling and Applications, S.E. Elmaghraby, ed., Springer, New York, 1973, pp. 83–91.
T.J. Sawik, Scheduling flowshops with parallel machines and finite in-process buffers by multilevel programming, in: System Modelling and Optimization, W.M. Iri and K. Yajima, eds., Springer, Berlin, 1988, pp. 691–700.
C. Sriskandarajah and S. Sethi, Scheduling algorithms for flexible flowshops: worst and average case performance, European Journal of Operational Research 43(1989)143–160.
W.H.M. Zijm and E.H.L.B. Nelissen, Scheduling a flexible machining centre, Engineering Costs and Production Economics 19(1990)249–258.
Rights and permissions
About this article
Cite this article
Gupta, J., Hariri, A. & Potts, C. Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Annals of Operations Research 69, 171–191 (1997). https://doi.org/10.1023/A:1018976827443
Issue Date:
DOI: https://doi.org/10.1023/A:1018976827443