A note on the generalized due dates scheduling problems
Academic Article
Overview
Research
Identity
Additional Document Info
View All
Overview
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 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