Minimizing Total Tardiness on a Single Machine with Precedence Constraints

The problem of minimizing the total tardiness for a set of unit-processing-time jobs on a single machine is considered. J. K. Lenstra and A. H. G. Rinnooy Kan have shown that the problem is NP-hard if the jobs have arbitrary precedence constraints. They asked whether the problem remains NP-hard for tree-structured precedence constraints. In this paper we show that the problem is NP-hard even for a set of chains. Our result gives a sharp boundary for the complexity of this problem, since there is a simple, polynomial-time algorithm for a set of independent jobs.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.