A note on the generalized due dates scheduling problems

The paper considers 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. The paper shows that this problem is NP-hard. It also establishes NP-hardness results for the scheduling problems with precedence constraints.