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

74
Last Week
0
Last month
0
Citations as of Feb 7, 2019

WEB OF SCIENCETM
Citations

67
Last Week
0
Last month
0
Citations as of Feb 16, 2019

Page view(s)

102
Last Week
0
Last month
Citations as of Feb 18, 2019

Google ScholarTM

Check

Altmetric


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