A simple linear time algorithm for scheduling with step-improving processing times

Min Ji, Yong He, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


We consider the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. For this problem, we present a simple linear time off-line approximation algorithm and prove its worst-case performance guarantee.
Original languageEnglish
Pages (from-to)2396-2402
Number of pages7
JournalComputers and Operations Research
Issue number8
Publication statusPublished - 1 Aug 2007


  • Approximation algorithm
  • Scheduling
  • Worst-case ratio

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this