Article ID: | iaor20043559 |
Country: | Netherlands |
Volume: | 129 |
Issue: | 1 |
Start Page Number: | 33 |
End Page Number: | 46 |
Publication Date: | Jul 2004 |
Journal: | Annals of Operations Research |
Authors: | Pridy Laurent, Pinson ric, Babu Pascal |
Keywords: | programming: branch and bound |
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 previous 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.