Maximizing Job Bene

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