Contents

On-Line Scheduling to Maximize Task Completions

Sanjoy Baruah1, Jayant Haritsa 2, Nitin Sharma 3
1Department of Computer Science The University of North Carolina at Chapel Hill
2 Supercomputer Education and Research Centre Indian Institute of Science
3Department of Computer Science and Engineering The University of Washington

Abstract

In overloaded task systems, it is by definition not possible to complete all tasks by their deadlines. However, it may still be desirable to maximize the number of in-time task completions. The performance of on-line schedulers with respect to this metric is investigated here. It is shown that in general, an on-line algorithm may perform arbitrarily poorly as compared to clairvoyant (off-line) schedulers. This result holds for general task workloads where there are no constraints on task characteristics. For a variety of constrained workloads that are representative of many practical applications, however, on-line schedulers that do provide a guaranteed level of performance are presented.