Maximizing job benefits on-line

Baruch Awerbuch, Yossi Azar, Oded Regev

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume4
Issue number6
DOIs
StatePublished - 2001

Keywords

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

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

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

Cite this