Obtaining the Due Dates Range that Keeps an Optimal Schedule the Same for Single Machine Total Tardiness Problem

摘要

The single machine total tardiness problem with due dates disturbance is discussed in this paper. A method by which the due dates range that keeps the optimal schedule no change can be obtained is presented. This method is based on the result of the analysis of the two-job case, the optimality principle of dynamic programming and the fact that any arrangement of n elements can be obtained from the natural arrangement by repeatedly exchanging the position of adjacent jobs. The defect of this method is the whole due dates range that keeps the optimal schedule no change can not be work out generally.