A Branch and Bound Algorithm for the Total Weighted Tardiness Problem

Chris N. Potts and Luk N. Van Wassenhove
Additional contact information
Chris N. Potts: University of Keele, Staffordshire, United Kingdom
Luk N. Van Wassenhove: Katholieke Universiteit, Leuven, Belgium

Operations Research, 1985, vol. 33, issue 2, 363-377

Abstract: This paper presents a new branch and bound algorithm for the single machine total weighted tardiness problem. It obtains lower bounds using a Lagrangian relaxation approach with subproblems that are total weighted completion time problems. The well-known subgradient optimization technique is replaced by a multiplier adjustment method that leads to an extremely fast bound calculation. The method incorporates various devices for checking dynamic programming dominance in the search tree. Extensive computational results for problems with up to 50 jobs show the superiority of the algorithm over existing methods.

Keywords: 581 single machine total weighted tardiness problem; 627 single machine sequencing (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (52)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.2.363 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:2:p:363-377

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().