Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/30726
Title: Single machine scheduling with deadlines and increasing rates of processing times
Authors: Cheng, TCE 
Ding, Q
Issue Date: 2000
Source: Acta informatica, 2000, v. 36, no. 9-10, p. 673-692 How to cite?
Journal: Acta Informatica 
Abstract: The makespan, flow time and maximum lateness problems of scheduling a set of tasks with deadlines and increasing rates of processing times on a single machine are considered in this paper. We first show that, when the increasing rates of processing time are identical, the makespan problem is equivalent to the corresponding flow time problem. Both problems are solvable in O(n5) time by a dynamic programming algorithm. As an application of the dynamic programming algorithm, we demonstrate that the corresponding maximum lateness problem can be solved in O(n6 log n) time. We then show that the general makespan problem is strongly NP-complete. Thus, both the corresponding flow time problem and maximum lateness problem are also strongly NP-complete.
URI: http://hdl.handle.net/10397/30726
ISSN: 0001-5903
DOI: 10.1007/s002360050170
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

23
Last Week
0
Last month
0
Citations as of Sep 22, 2017

WEB OF SCIENCETM
Citations

22
Last Week
0
Last month
0
Citations as of Sep 21, 2017

Page view(s)

38
Last Week
1
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



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