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. (International Journal of Production Economics 36 (1994) 213-219). 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 (Operations Research 26 (1978) 444-449), the calculation of the lower bounds and the utilisation of Elmaghraby's (Journal of Industrial Engineering 19 (1968) 105-108) 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. (C) 2000 Elsevier Science B.V. All rights reserved.