A Branch and Bound Algorithm for the Total Weighted Tardiness Problem

TLDR

The authors propose a branch‑and‑bound algorithm for the single‑machine total weighted tardiness problem. The algorithm derives lower bounds via Lagrangian relaxation of total weighted completion time subproblems, replaces subgradient optimization with a multiplier‑adjustment scheme for rapid bound computation, and employs dynamic‑programming dominance checks within the search tree. Experiments on instances with up to 50 jobs demonstrate that the algorithm outperforms existing approaches.

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.