Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/31286
Title: The complexity of single machine scheduling with two distinct deadlines and identical decreasing rates of processing times
Authors: Cheng, TCE 
Ding, Q
Keywords: Computational complexity
Scheduling
Sequencing
Time-dependence
Issue Date: 1998
Publisher: Pergamon Press
Source: Computers and mathematics with applications, 1998, v. 35, no. 12, p. 95-100 How to cite?
Journal: Computers and mathematics with applications 
Abstract: The makespan problem on a single machine for a set of tasks with two distinct deadlines and identical decreasing rates of processing times is considered in this paper. Ho et al. [1] have proposed a model of a task system in which the processing time of a task decreases with its starting time. When the decreasing rate is identical, the computational complexity of the makespan problem with two distinct deadlines is posed as an open problem. In this paper we show that the problem is NP-complete. It follows that both the corresponding flow time problem and maximum lateness problem are also NP-complete.
URI: http://hdl.handle.net/10397/31286
ISSN: 0898-1221
EISSN: 1873-7668
DOI: 10.1016/S0898-1221(98)00099-6
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

8
Last Week
0
Last month
0
Citations as of Jul 30, 2017

WEB OF SCIENCETM
Citations

9
Last Week
0
Last month
0
Citations as of Aug 13, 2017

Page view(s)

46
Last Week
1
Last month
Checked on Aug 14, 2017

Google ScholarTM

Check

Altmetric



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