A Branch and Bound Algorithm for the Total Weighted Tardiness Problem

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.