Article ID: | iaor20031402 |
Country: | United Kingdom |
Volume: | 30 |
Issue: | 1 |
Start Page Number: | 51 |
End Page Number: | 62 |
Publication Date: | Jan 2003 |
Journal: | Computers and Operations Research |
Authors: | Cheng T.C.E., Ding Q. |
Keywords: | combinatorial analysis |
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.