Preemptive scheduling in overloaded systems.

Abstrakt

We are given a set of tasks with release times, deadlines, and profit rates. We present an efficient offline algorithm and improve both the lower and upper bounds on the competitive ratio of online algorithms.