Scheduling Start Time Dependent Tasks with Deadlines and Identical Initial Processing Times on a Single Machine
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.
Sequencing, Time dependence scheduling, Computational complexity
Computers and Operations Research
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. Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/871