Minimizing total tardiness for single machine sequencing

The authors consider the single machine sequencing problem in which each job has a processing time and a due date. The objective is to find a sequence of n jobs which minimizes the sum of the tardiness of each job. The authors present an MDD (Modified Due Date) rule which satisfies local optimality and show that the MDD rule has a worst-case performance ratio of . The MDD rule is superior to other known heuristics in the sense of worst-case performance.