@inproceedings{b818906983834f618b45149d60e391a5,
title = "Maximizing job benefits on-line",
abstract = "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{\textquoteright}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.",
author = "Baruch Awerbuch and Yossi Azar and Oded Regev",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000 ; Conference date: 05-09-2000 Through 08-09-2000",
year = "2000",
doi = "10.1007/3-540-44436-x_6",
language = "English (US)",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "42--50",
editor = "Klaus Jansen and Samir Khuller",
booktitle = "Approximation Algorithms for Combinatorial Optimization - 3rd International Workshop, APPROX 2000, Proceedings",
}