The Complexity of Single Machine Scheduling with Two Distinct Deadlines and Identical Decreasing Rates of Processing Times
Publication Type
Journal Article
Publication Date
1998
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.
Discipline
Business
Research Areas
Finance
Publication
Computers and Mathematics With Applications
Volume
35
Issue
12
First Page
95
Last Page
100
ISSN
0898-1221
Identifier
10.1016/s0898-1221(98)00099-6
Publisher
Elsevier
Citation
Cheng, T. C. E. and DING, Qing.
The Complexity of Single Machine Scheduling with Two Distinct Deadlines and Identical Decreasing Rates of Processing Times. (1998). Computers and Mathematics With Applications. 35, (12), 95-100.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/876