A note on the complexity of flow-shop scheduling with deteriorating jobs

Authors :: Thörnblad, Karin
Patriksson, Michael
Source :: Discrete Applied Mathematics. Feb2011, Vol. 159 Issue 4, p251-253. 3p.
Publication Year :: 2011
Abstract: Abstract: 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. [ABSTRACT FROM AUTHOR]