Single Machine Scheduling with Deadlines and Increasing Rates of Processing Times
The makespan, flow time and maximum lateness problems of scheduling a set of tasks with deadlines and increasing rates of processing times on a single machine are considered in this paper. We first show that, when the increasing rates of processing time are identical, the makespan problem is equival...
Saved in:
| Main Authors: | , |
|---|---|
| 格式: | text |
| 語言: | English |
| 出版: |
Institutional Knowledge at Singapore Management University
2000
|
| 主題: | |
| 在線閱讀: | https://ink.library.smu.edu.sg/lkcsb_research/873 https://doi.org/10.1007/s002360050170 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Singapore Management University |
| 語言: | English |
| 總結: | The makespan, flow time and maximum lateness problems of scheduling a set of tasks with deadlines and increasing rates of processing times on a single machine are considered in this paper. We first show that, when the increasing rates of processing time are identical, the makespan problem is equivalent to the corresponding flow time problem. Both problems are solvable in O(n[sup 5]) time by a dynamic programming algorithm. As an application of the dynamic programming algorithm, we demonstrate that the corresponding maximum lateness problem can be solved in O(n[sup 6] log r,) time. We then show that the general makespan problem is strongly NP-complete. Thus, both the corresponding flow time problem and maximum lateness problem are also strongly NP-complete. |
|---|