Solution of the single machine total tardiness problem

The paper deals with the solution of the single machine total tardiness model. It improves and generalizes an important rule to decompose the model into two subproblems. It also provides a O(n²) procedure to implement this rule and its generalization. Those two rules, along with some known results, are incorporated in a branch and bound algorithm that efficiently handles instances with up to 300 jobs and uses the original and maximally increased due dates to solve the original problem. Several properties that justify the modified due date version of our algorithm and produce an easy-to-implement new lower bound are established. The paper also provides an explanation why using the increased due dates may improve the efficiency of certain algorithms.