Article ID: | iaor20061249 |
Country: | South Africa |
Volume: | 17 |
Issue: | 1/2 |
Start Page Number: | 101 |
End Page Number: | 111 |
Publication Date: | Jan 2001 |
Journal: | Orion |
Authors: | Nyirenda J.C. |
Keywords: | heuristics |
In this paper, we consider the problem of scheduling N jobs on a single machine to minimise total tardiness. Both the modified due date (MDD) rule and the heuristic of Wilkerson and Irwin (W-I) are very effective in reducing total tardiness. We show that in fact the MDD rule and the W-I heuristic are strongly related in the sense that both are based on the same local optimality condition for a pair of adjacent jobs, so that a sequence generated by these methods cannot be improved by any further adjacent pair-wise interchange.