Maximizing job benefits on-line

Baruch Awerbuch, Yossi Azar, Oded Regev

Research output: Contribution to journalArticlepeer-review


We consider a benefit model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and benefit function. The flow time of a job is the time that passes from its release to its completion. The benefit function specifies the benefit gained for any given flow time. A scheduler's goal is to maximize the total benefit gained. We present a constant competitive ratio algorithm for that model in the uniprocessor case for benefit functions that do not decrease too rapidly. We also extend the algorithm to the multiprocessor case while maintaining constant competitiveness. The multiprocessor algorithm does not use migration, i.e. preempted jobs continue their execution on the same processor on which they were originally processed.

Original languageEnglish (US)
Pages (from-to)287-296
Number of pages10
JournalJournal of Scheduling
Issue number6
StatePublished - 2001


  • Benefit
  • Competitive
  • Flow-time
  • On-line
  • Preemptive
  • Scheduling

ASJC Scopus subject areas

  • Software
  • General Engineering
  • Management Science and Operations Research
  • Artificial Intelligence


Dive into the research topics of 'Maximizing job benefits on-line'. Together they form a unique fingerprint.

Cite this