TITLE

MINIMIZING THE SUM OF THE JOB COMPLETION TIMES IN THE TWO-MACHINE FLOW SHOP BY LAGRANGIAN RELAXATION

AUTHOR(S)
van de Velde, S. L.
PUB. DATE
October 1990
SOURCE
Annals of Operations Research;1990, Vol. 26 Issue 1-4, p257
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
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.
ACCESSION #
18649782

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics