Maximizing job benefits on-line

✍ Scribed by Baruch Awerbuch; Yossi Azar; Oded Regev

• Book ID: 102397842
• Publisher: Springer US
• Year: 2001
• Tongue: English
• Weight: 81 KB
• Volume: 4
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/jos.84

✦ Synopsis

We consider a beneÿt 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 beneÿt function. The ow time of a job is the time that passes from its release to its completion. The beneÿt function speciÿes the beneÿt gained for any given ow time. A scheduler's goal is to maximize the total beneÿt gained. We present a constant competitive ratio algorithm for that model in the uniprocessor case for beneÿt 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.