On-line scheduling on uniform multiprocessors

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s × t) units of execution. The on-line scheduling of hard-real-time systems, in which all jobs must complete by specified deadlines, on uniform multiprocessor machines is considered. It is known that on-line algorithms tend to perform very poorly in scheduling such hard-real-time systems on multiprocessors; resource-augmentation techniques are presented here that permit on-line algorithms to perform better than may be expected given the inherent limitations. Results derived here are applied to the scheduling of periodic task systems on uniform multiprocessor machines.