| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143454 | Operations Research Letters | 2006 | 4 Pages |
Abstract
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, an FPTAS, and an on-line algorithm with best possible competitive ratio.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
T.C. Edwin Cheng, Yong He, Han Hoogeveen, Min Ji, Gerhard J. Woeginger,