Single Machine Scheduling with Step-Deteriorating Processing Times
Publication Type
Journal Article
Publication Date
2001
Abstract
We study in this paper a scheduling model in which each task has a normal processing time which deteriorates as a step function if its starting time is beyond a given deteriorating date. We focus on problems with identical task deteriorating dates. We show that the flow time problem is NP-complete and suggest a pseudo-polynomial algorithm for the makespan problem. We also introduce a general method of solution, which facilitates the identification of solvable cases for some related problems. Finally, we provide a counter-example that invalidates the conjecture of optimality of a switching algorithm reported in the literature. Thus, we solve several unexplored or open problems and obtain a sharp boundary delineating the complexity of the considered problems.
Discipline
Business
Research Areas
Operations Management
Publication
European Journal of Operational Research
Volume
134
Issue
3
First Page
623
Last Page
630
ISSN
0377-2217
Identifier
10.1016/s0377-2217(00)00284-8
Publisher
Elsevier
Citation
Cheng, T. C. E. and DING, Qing.
Single Machine Scheduling with Step-Deteriorating Processing Times. (2001). European Journal of Operational Research. 134, (3), 623-630.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/872
