We present a simple result in single-machine scheduling theory. Namely, the number of tardy jobs in a sequence which is optimal with respect to total tardiness is no greater than the number of tardy jobs in the earliest due date sequence. This provides a bound for solutions to the total tardiness problem on a single machine found using branch and bound, dynamic programming or the decomposition method.
|Number of pages||9|
|Journal||Australasian Journal of Combinatorics|
|Publication status||Published - 1 Dec 1997|