Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/24295
Title: The complexity of scheduling starting time dependent tasks with release times
Authors: Cheng, TCE 
Ding, Q
Keywords: Computational complexity
Release time
Scheduling
Sequencing
Time dependence
Issue Date: 1998
Source: Information processing letters, 1998, v. 65, no. 2, p. 75-79 How to cite?
Journal: Information Processing Letters 
Abstract: We consider a family of problems of scheduling a set of starting time dependent tasks with release times and linearly increasing/decreasing processing rates on a single machine to minimize the makespan. We first present an equivalence relationship between several pairs of problems. Based on this relationship, we show that the makespan problem with arbitrary release times and identical increasing processing rates is strongly NP-complete and the corresponding case with only one non-zero release time is at least NP-complete in the ordinary sense. On the other hand, the makespan problem with arbitrary release times and identical decreasing processing rates is solvable in O(n6 log n) time by a dynamic programming algorithm. Using a different approach, we also show that, when the normal processing times are identical, the makespan problem with arbitrary release times and increasing/decreasing processing rates is strongly NP-complete and the corresponding case with only one non-zero release time is at least NP-complete in the ordinary sense.
URI: http://hdl.handle.net/10397/24295
ISSN: 0020-0190
DOI: 10.1016/S0020-0190(97)00195-6
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

72
Last Week
0
Last month
0
Citations as of Sep 11, 2017

WEB OF SCIENCETM
Citations

66
Last Week
1
Last month
0
Citations as of Sep 12, 2017

Page view(s)

50
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.