A branch and bound algorithm to minimize total weighted tardiness on a single processor

A branch and bound algorithm to minimize total weighted tardiness on a single processor

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: branch and bound
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 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.

Reviews

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