Journal
APPLIED MATHEMATICS AND COMPUTATION
Volume 218, Issue 11, Pages 6498-6510Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.amc.2011.12.020
Keywords
Scheduling; Deteriorating; Aging effect; Computational complexity
Categories
Ask authors/readers for more resources
In this paper, we analyse the single machine maximum lateness minimization scheduling problem with the processing time based aging effect, where the processing time of each job is described by a non-decreasing function dependent on the sum of the normal processing times of preceded jobs. The computational complexity of this problem was not determined. However, we show it is strongly NP-hard by proving the strong NP-hardness of the single machine maximum completion time minimization problem with this aging model and job deadlines. Furthermore, we determine the boundary between polynomially solvable and NP-hard cases. (C) 2011 Elsevier Inc. All rights
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