Minimizing Total Tardiness on One Machine is NP-Hard

Abstract
The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard in the ordinary sense remained open. In this paper the problem is shown to be NP-hard in the ordinary sense.