## 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

### MSC:

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

### Keywords:

one-machine scheduling; total tardiness; due dates

Zbl 0353.68071
Full Text: