| Article ID: | iaor20002063 |
| Country: | United Kingdom |
| Volume: | 26 |
| Issue: | 8 |
| Start Page Number: | 749 |
| End Page Number: | 754 |
| Publication Date: | Jul 1999 |
| Journal: | Computers and Operations Research |
| Authors: | Cheng T.C. Edwin, Ding Q. |
| Keywords: | combinatorial analysis, heuristics |
The computational complexity of the problem of scheduling a set of start-time dependent tasks with deadlines and identical decreasing rates of processing times on a single machine to minimize the makespan is open. In this paper we show that the problem is strongly NP-complete by a reduction from 3-Partition.