Single machine scheduling with release times, deadlines and tardiness objectives

A polynomial time algorithm is developed to minimize maximum tardiness on a single machine in the presence of deadlines. The possibility of extending the total tardiness pseudopolynomial algorithm to the cases where release times or deadlines are in place is also investigated. It is concluded that the aforementioned pseudopolynomial algorithm can be extended only when deadlines and due dates are compatible and all job release times are equal.