Algorithmic paradoxes of the single-machine total tardiness problem

The paper deals with the single-machine total tardiness problem. It investigates the author's most recent branch and bound algorithm and discovers the following paradoxes. Deleting a lower bound drastically improves the performance of the algorithm, while adding a stronger component, like a better decomposition rule, negatively affects its performance. Guided by those paradoxes it develops a very fast branch algorithm that handles instances with up to 500 jobs. It also shows that the powerful recent result of Chang et al. can be further improved.