Single machine scheduling with maximum allowable tardiness in ET model

This paper addresses the problem of scheduling a set of jobs with a common due date on a single machine. The objective is to minimize the sum of the earliness and tardiness of jobs subject to Tmax≤ Δ for Δ ≥0. Properties for the MAD/Tmax problem are found and the problem is shown to be NP-complete in the ordinary sense. According to the range of Δ, the problem can be solved in polynomial time. Also, some special cases where an optimal schedule is found in polynomial time are discussed.