A note on the generalized due dates scheduling problems Academic Article

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

authors

• Sriskandarajah, Chelliah

published proceedings

• Naval Research Logistics

author list (cited authors)

• Sriskandarajah, C.

citation count

• 34

complete list of authors

• Sriskandarajah, C

publication date

• August 1990

publisher

• Wiley  Publisher

published in

• Naval Research Logistics  Journal

keywords

• 49 Mathematical Sciences
• 4901 Applied Mathematics
• 4904 Pure Mathematics

Digital Object Identifier (DOI)

• 10.1002/1520-6750(199008)37:4<587::aid-nav3220370411>3.0.co;2-o

start page

• 587

end page

• 597

volume

• 37

issue

• 4

URL

• http://dx.doi.org/10.1002/1520-6750(199008)37:4%3C587::aid-nav3220370411%3E3.0.co;2-o