A note on ‘An efficient algorithm for the single-machine tardiness problem.’

The focus of this work is to give some comments on a paper recently published by Kondakci et al. They present a new branch-and-bound algorithm for the famous total tardiness problem. However, some aspects of the algorithm remain vague, namely the application of the labelling scheme of Schrage and Baker, the calculation of the lower bounds and the utilisation of Elmaghraby's dominance theorem. As limiting total enumeration is the most interesting part of a branch-and-bound algorithm we clarify the inaccuracies and propose a fast recursion to calculate the lower bounds. We demonstrate the branch-and-bound algorithm by using an example. [See IAOR abstract 57279]