We consider the problem of scheduling jobs on a single machine with generalized due dates. The due dates are given according to the position in which a job is completed, rather than the identity of that job. The computational complexity question of whether the total weighted tardiness problem can be solved in polynomial time or NP-Hard is posed as an open problem in . We show that this problem is NP-Hard. We also establish NP-Hardness results for the scheduling problems with precedence constraints.
Paru en octobre 1988 , 16 pages
Ce cahier a été révisé en décembre 1989