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

abstract

  • 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. Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company

author list (cited authors)

  • Sriskandarajah, C.

citation count

  • 22

complete list of authors

  • Sriskandarajah, C

publication date

  • August 1990

publisher