Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation

Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation

0.00 Avg rating0 Votes
Article ID: iaor19911579
Country: Switzerland
Volume: 26
Start Page Number: 257
End Page Number: 268
Publication Date: Dec 1990
Journal: Annals of Operations Research
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.