Groupe d’études et de recherche en analyse des décisions


A Note on the Generalized Due Dates Scheduling Problems

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 [4]. We show that this problem is NP-Hard. We also establish NP-Hardness results for the scheduling problems with precedence constraints.

, 16 pages

Ce cahier a été révisé en décembre 1989