Insights into two solution procedures for the single machine tardiness problem. (English) Zbl 1130.90330
Summary: This paper explores the well-known modified due date (MDD) rule for minimizing total tardiness on a single machine and shows that it has a decomposition structure. Based on this finding, we propose a decomposition heuristic and draw parallels to the famous optimal decomposition algorithm. We demonstrate that the MDD rule and the decomposition algorithm have striking similarities. We also discuss the key differences between these procedures. Finally, we present a sufficient condition under which the MDD rule is optimal and conclude the paper with some directions for future research.
MSC:
90B35 | Deterministic scheduling theory in operations research |
68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
90C59 | Approximation methods and heuristics in mathematical programming |