Scheduling with step-improving processing times

Edwin Tai Chiu Cheng, Yong He, Han Hoogeveen, Min Ji, Gerhard J. Woeginger

Research output: Journal article publicationJournal articleAcademic researchpeer-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
Number of pages4
JournalOperations Research Letters
Issue number1
Publication statusPublished - 1 Jan 2006


  • Approximation scheme
  • Competitive analysis
  • Knapsack problem
  • Scheduling

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Discrete Mathematics and Combinatorics
  • Modelling and Simulation


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

Cite this