Minimizing total tardiness on one machine is NP-hard. (English) Zbl 0714.90052

The NP-hardness (in the ordinary sense) of a well-known one-machine scheduling problem of minimizing total tardiness is established. The problem is to find a schedule S for processing N independent jobs \(J_ i\) with given due dates \(d(J_ i)\) on one machine which minimizes the total tardiness \(\sum^{N}_{i=1}T(J_ i,S)\). Here \(T(J_ i,S)=\max \{0\), \(C(J_ i,S)-d(J_ i)\}\) is the tardiness of a job \(J_ i\) and \(C(J_ i,S)\) is the completion time of a job \(J_ i\) in a schedule S.
This problem has a rich history: it was introduced by R. McNaughton [Manage. Sci. 6, 1-12 (1959/60)] (he considered some more general problem, namely the minimization of total weighted tardiness). The question if the problem is solvable in polynomial time or if it is NP- hard remained open since the middle of the seventies. E. Lawler [Ann. Discrete Math. 1, 331-342 (1977; Zbl 0353.68071)] gave a pseudo- polynomial-time algorithm to find an optimal schedule, so that the problem cannot be NP-hard in the strong sense (unless \(P=NP)\). The NP- hardness (in the strong sense) is proved for some generalizations of the problem: total tardiness with ready times of jobs, but common due date \(d(J_ i)=D\) for all \(J_ i\); total weighted tardiness; total weighted tardiness with precedence constraints (chains) and unit processing times of jobs; total tardiness with precedence constraints (arbitrary) and unite processing times of jobs, and some further generalizations. The NP- hardness is also proved for total tardiness and total weighted tardiness when preemptions are allowed.
Reviewer: Y.M.Shafranskij


90B35 Deterministic scheduling theory in operations research
90C60 Abstract computational complexity for mathematical programming problems


Zbl 0353.68071
Full Text: DOI