TITLE

A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor

AUTHOR(S)
Babu, Pascal; Peridy, Laurent; Pinson, Eric
PUB. DATE
July 2004
SOURCE
Annals of Operations Research;Jul2004, Vol. 129 Issue 1-4, p33
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
In this paper, we consider the problem of minimizing the total weighted tardiness of a set of jobs processed on a single processor. First, a lower bound based on a Lagrangian decomposition is presented. The particularity of this decomposition, based on a 0–1 time indexed formulation, is to be sensitive to the domain reduction of jobs which are proposed. A branch and bound strategy including these different components is proposed. The results obtained on problems from the literature can be favourably compared to previously works and seem to prove that a trade-off between a tight lower bound and time consuming in the enumeration process can be a good strategy.
ACCESSION #
18724133

 

Share

Read the Article

Courtesy of NEW JERSEY STATE LIBRARY

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

Try another library?
Sign out of this library

Other Topics