Relationship between the modified due date rule and the heuristic of Wilkerson and Irwin

Abstract

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.