Journal
DISCRETE APPLIED MATHEMATICS
Volume 159, Issue 4, Pages 251-253Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2010.11.006
Keywords
Deteriorating jobs; Flow shop; Makespan; NP-hardness
Categories
Funding
- Swedish Research Council [621-2007-4716]
Ask authors/readers for more resources
This paper is a note on Complexity analysis of job-shop scheduling with deteriorating jobs [G. Mosheiov, Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics 117 (2002) 195-209]. A proportional deterioration rate is assumed and the objective is the minimization of the makespan. Mosheiov presents NP-hardness results for flow-shops and open-shops with three or more machines and for job-shops with two or more machines. The proof of NP-hardness for the flow-shop case is however not correct. This paper provides a correct proof. (C) 2010 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
