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

2 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)37-40
Number of pages4
JournalOperations Research Letters
Volume34
Issue number1
DOIs
Publication statusPublished - 1 Jan 2006

Keywords

  • 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

Cite this