Maximizing job benefits on-line

Baruch Awerbuch, Yossi Azar, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider a benefit model for on-line preemptive scheduling. In this model jobs arrive to the on-line scheduler at their release time. Each job arrives with its own execution time and its 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 gained benefit. We present a constant competitive ratio algorithm for that model in the uniprocessor case for benefit functions that do not decrease too fast. 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)
Title of host publicationApproximation Algorithms for Combinatorial Optimization - 3rd International Workshop, APPROX 2000, Proceedings
EditorsKlaus Jansen, Samir Khuller
PublisherSpringer Verlag
Number of pages9
ISBN (Electronic)9783540679967
StatePublished - 2000
Event3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000 - Saarbrucken, Germany
Duration: Sep 5 2000Sep 8 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this