×

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
Full Text: DOI