Scheduling Start Time Dependent Tasks with Deadlines and Identical Initial Processing Times on a Single Machine
Publication Type
Journal Article
Publication Date
2003
Abstract
In this paper, we study the feasibility problem of scheduling a set of start time dependent tasks on a single machine with deadlines, processing rates and identical initial processing times. First, we show that the cases with arbitrary deadlines are strongly NP-complete. Second, we show that the cases with two distinct deadlines are NP-complete in the ordinary sense. Finally, we give an optimal polynomial algorithm for the makespan problem with two distinct processing rates. We solve a series of open problems in the literature and give a sharp boundary delineating the complexity of the problems.
Keywords
Sequencing, Time dependence scheduling, Computational complexity
Discipline
Business
Research Areas
Operations Management
Publication
Computers and Operations Research
Volume
30
Issue
1
First Page
51
Last Page
62
ISSN
0305-0548
Identifier
10.1016/s0305-0548(01)00077-6
Publisher
Elsevier
Citation
Cheng, T. C. E. and DING, Qing.
Scheduling Start Time Dependent Tasks with Deadlines and Identical Initial Processing Times on a Single Machine. (2003). Computers and Operations Research. 30, (1), 51-62.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/871