Algorithmic paradoxes of the single-machine total tardiness problem

The paper deals with the single-machine total tardiness problem. It investi gates the authors' most recent branch and bound algorithm and discovers the following paradoxes. Deleting a lower bound drastically improves the perfo rmance of the algorithm, while adding a stronger component, like a better d ecomposition rule, negatively affects its performance. Guided by those para doxes 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 a l (Operations Research Letters 1995; 17:221-229) can be further improved. C opyright (C) 2001 John Wiley & Sons, Ltd.