| Article ID: | iaor20061705 |
| Country: | Netherlands |
| Volume: | 34 |
| Issue: | 1 |
| Start Page Number: | 37 |
| End Page Number: | 40 |
| Publication Date: | Jan 2006 |
| Journal: | Operations Research Letters |
| Authors: | Woeginger Gerhard J., Cheng T.C. Edwin, Hoogeveen Han, He Yong, Ji Min |
| Keywords: | combinatorial analysis |
We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, a fully polynomial time approximation scheme, and an on-line algorithm with best possible competitive ratio.