The invariability of an optimal schedule for single machine total tardiness problem with due date perturbation

The invariability of an optimal schedule for the single machine total tardiness problem with due dates perturbation is discussed. A conclusion is obtained that the range of the due dates in which a given optimal schedule keeps optimal is an interval (i.e. a convex set) when only one job due date varies, and it is not a convex set when multiple jobs due dates vary. Two methods are given to find the interval of any given job due date in which an optimal schedule keep optimal: the dynamic programming algorithm and trial method