Scheduling with step-improving processing times

T.C.E. Cheng, Yong He, J.A. Hoogeveen, Min Ji, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)37-40
JournalOperations Research Letters
Issue number1
Publication statusPublished - 2006


Dive into the research topics of 'Scheduling with step-improving processing times'. Together they form a unique fingerprint.

Cite this