Maximizing job benefits on-line

We consider a benefit model for on-line preemptive scheduling. In this mode l jobs arrive at the on-line scheduler at their release time. Each job arri ves with its own execution time and benefit function. The flow time of a jo b is the time that passes from its release to its completion. The benefit f unction specifies the benefit gained for any given flow time. A scheduler's goal is to maximize the total benefit gained. We present a constant compet itive ratio algorithm for that model in the uniprocessor case for benefit f unctions that do not decrease too rapidly. We also extend the algorithm to the multiprocessor case while maintaining constant competitiveness: The mul tiprocessor algorithm does not use migration, i.e. preempted jobs continue their execution on the same processor on which they were originally process ed. Copyright (C) 2001 John Wiley & Sons, Ltd.