Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 155-163 |
| Number of pages | 9 |
| Journal | Australasian Journal of Combinatorics |
| Volume | 16 |
| Publication status | Published - 1 Dec 1997 |
| Externally published | Yes |