Branch and bound algorithm for the flow shop with multiple processors. (English) Zbl 0732.90040

Summary: The sequencing of a flow shop with multiple processors at each stage is a general case of the flow shop problem. It involves sequencing n jobs in a flow shop where, for at least one stage, the facility has one or more identical machines. The purpose of this paper is to present a branch and bound algorithm to solve scheduling problems of such facilities for optimizing the maximum completion time. The lower bounds and elimination rules developed in this reseach are based upon the generalization of the flow shop problem. Furthermore, a computational algorithm, along with results, is also presented. The branch and bound algorithm can also be used to optimize other measures of performance in a flow shop with multiple processors.


90B35 Deterministic scheduling theory in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] Ashour, S., A branch and bound algorithm for flow shop scheduling problems, AIIE transactions, 2, 2, 172-176, (1970)
[2] Baker, K.R., A comparative study of flow shop algorithms, Operations research, 23, 1, 62-73, (1975) · Zbl 0307.90037
[3] Bansal, S.P., Minimizing the sum of completion times of n jobs over m machines in a flow shop - A branch and bound approach, AIIE transactions, 9, 3, 306-311, (1977)
[4] Bansal, S.P., On lower bounds in permutation flow shop problems, International journal of production research, 17, 4, 411-418, (1979)
[5] Brah, S.A., Scheduling in a flow shop with multiple processors, (), 30-33, Unpublished Ph.D. Dissertation
[6] Brah, S.A.; Hunsucker, J.L., Optimal scheduling in a flow shop with multiple processors, ()
[7] Bratley, P.; Florian, M.; Robillard, P., Scheduling with earliest start and due date constraints on multiple machines, Naval research logistics quarterly, 22, 1, 165-173, (1975) · Zbl 0306.90032
[8] Cho, Y.; Sahni, S., Preemptive scheduling of independent jobs with release and due times on open, flow and job shops, Operations research, 29, 3, 511-522, (1981) · Zbl 0455.90043
[9] French, S., Sequencing and scheduling: an introduction to the mathematics of job-shop, (1982), Wiley · Zbl 0479.90037
[10] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman Press San Francisco, CA · Zbl 0411.68039
[11] Garey, M.R.; Johnson, D.S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Management science, 1, 2, 117-129, (1976) · Zbl 0396.90041
[12] Gonzalez, T.; Sahni, S., Flowshop and jobshop schedules: complexity and approximation, Operations research, 26, 1, 36-52, (1978) · Zbl 0371.90061
[13] Gupta, J.N.D., M-stage flowshop scheduling by branch and bound, Opsearch, 7, 1, 37-43, (1970)
[14] Ignall, E.; Schrage, L.E., Application of the branch and bound technique to some flow-shop problems, Operations research, 13, 4, 400-412, (1965)
[15] King, J.R., Scheduling and the problem of computational complexity, Omega, the international journal of management science, 7, 3, 233-240, (1979)
[16] Kochhar, S.; Morris, R.J.T., Heuristic methods for flexible flow line scheduling, Journal of manufacturing systems, 6, 4, 299-314, (1987)
[17] Köhler, W.H.; Steiglitz, K., Enumerative and iterative computational approaches, ()
[18] Lageweg, B.J.; Lenstra, J.K.; Rinnooy Kan, A.H.G., A general building scheme for the permutation flow-shop problem, Operations research, 26, 1, 53-67, (1978) · Zbl 0371.90059
[19] Lomnicki, Z., A branch and bound algorithm for the exact solution of the three-machine scheduling problem, Operations research quarterly, 16, 1, 89-100, (1965)
[20] McMahon, G.B.; Burton, P.G., Flow-shop scheduling with the branch and bound method, Operations research, 15, 3, 473-481, (1967)
[21] Salvador, M.S., A solution to a special case of flow shop scheduling problems, ()
[22] Wittrock, R.J., Scheduling algorithms for flexible flow lines, IBM journal of research and development, 29, 4, 401-412, (1985)
[23] Wittrock, R.J., An adaptable scheduling algorithms for flexible flow lines, Operations research, 33, 4, 445-453, (1988) · Zbl 0646.90039
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.