A note on the generalized due dates scheduling problems Academic Article uri icon


  • 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 NPhard is posed as an open problem in [4]. We show that this problem is NPhard. We also establish NPhardness results for the scheduling problems with precedence constraints. Copyright 1990 Wiley Periodicals, Inc., A Wiley Company

published proceedings

  • Naval Research Logistics

author list (cited authors)

  • Sriskandarajah, C.

citation count

  • 34

complete list of authors

  • Sriskandarajah, C

publication date

  • August 1990