Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/7785
Title: Single machine scheduling with step-deteriorating processing times
Authors: Cheng, TCE 
Ding, Q
Keywords: Computational complexity
Scheduling
Sequencing
Step-deterioration
Issue Date: 2001
Publisher: Elsevier
Source: European journal of operational research, 2001, v. 134, no. 3, p. 623-630 How to cite?
Journal: European journal of operational research 
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.
URI: http://hdl.handle.net/10397/7785
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/S0377-2217(00)00284-8
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

54
Last Week
0
Last month
0
Citations as of Aug 14, 2017

WEB OF SCIENCETM
Citations

51
Last Week
0
Last month
0
Citations as of Aug 12, 2017

Page view(s)

43
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.