Abstract
A branch-and-bound algorithm is presented for the two-machine flow shop problem with the objective of minimizing the sum of the job completion times. Lower bounds and precedence constraints result from a Lagrangian relaxation of this problem. The Lagrangian subproblem turns out to be a linear ordering problem that is polynomially solvable for appropriate choices of the Lagrangian multipliers. The best choice within this class yields a lower bound that dominates previous bounds. In fact, the existing bounds correspond to particular choices of the multipliers. Several dominance criteria are given to restrict the search tree. Computational experiments show that the proposed algorithm outperforms the previously best method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. Adiri and N. Amit, Openshop and flowshop scheduling to minimize sum of completion times, Comput. Oper. Res. 11(1984)275–284.
S.P. Bansal, Minimizing the sum of completion times of n jobs over m machines in a flowshop - a branch and bound approach, AIIE Trans. 9(1977)306–311.
P.P. Bergmans, Minimizing expected travel time on geometrical patterns by optimal probability rearrangements, Information and Control 20(1972)331–350.
R.W. Conway, W.L. Maxwell and L.W. Miller, Theory of Scheduling (Addison-Wesley, Reading, MA, 1967).
M.L. Fisher, The Lagrangian relaxation method for solving integer programming problems, Manag. Sci. 27(1981)1–18.
M.L. Fisher, B.J. Lageweg, J.K. Lenstra and A.H.G. Rinnooy Kan, Surrogate duality relaxation for job shop scheduling, Discr. Appl. Math. 5(1983)65–75.
M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res. (1976)117–129.
R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discr. Math. 5(1979)287–326.
J.N.D. Gupta and R.A. Dudek, Optimality criteria for flowshop schedules, AIIE Trans. 3(1971) 199–205.
A.M.A. Hariri and C.N. Potts, Algorithms for two-machine flow-shop sequencing with precedence constraints, Eur. J. Oper. Res. 17(1984)238–248.
E. Ignall and L. Schrage, Application of the branch and bound technique for some flowshop scheduling problems, Oper. Res. 13(1965)400–412.
S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Logist. Quart. 1(1954)61–68.
W.H. Kohler and K. Steiglitz, Exact, approximate and guaranteed accuracy algorithms for the flowshop problem n/2/F/F, J. Assoc. Comput. Mach. 22(1975)106–114.
M.J. Krone and K. Steiglitz, Heuristic programming solution of a flowshop-scheduling problem, Oper. Res. 22(1974)629–638.
C.L. Monma and J.B. Sidney, Sequencing with series-parallel precedence constraints, Math. Oper. Res. 3(1979)215–224.
J.-C. Picard and M. Queyranne, On the one-dimensional space allocation problem, Oper. Res. 29(1982)371–391.
V.R. Pratt, An O(n log n) algorithm to distribute n records in a sequential access file, in: Complexity of Computer and Computations, ed. R.E. Miller and J.W. Thatcher (Plenum, New York, 1972), pp. 111–118.
W.E. Smith, Various optimizers for single-stage production, Naval Res. Logists. Quart. 3(1956)59–66.
W. Szwarc, The flow-shop problem with mean completion time criterion, AIIE Trans. 15(1983) 172–176.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
van de Velde, S. Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation. Ann Oper Res 26, 257–268 (1990). https://doi.org/10.1007/BF03500931
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF03500931