http://www.umiacs.umd.edu/users/liberato/cats/

Rajmohan Rajaraman

Northeastern University

Friday, November 5, 1999, 2 p.m.

AVW 2120

We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, which is defined as the ratio of the amount of time that the job spends in the system to the processing time of the job. For a given sequence of jobs, we measure the performance of an algorithm by the average stretch achieved by the algorithm over all the jobs in the sequence. The average stretch metric has been used to evaluate the performance of scheduling algorithms in many applications arising in databases, networks and systems; however, no formal analysis of scheduling algorithms is known for the average stretch metric.

The main contribution of this work is to show that the shortest remaining processing time algorithm (SRPT) is O(1)-competitive with respect to average stretch for both uniprocessors and multiprocessors. For uniprocessors, we prove that SRPT is 2-competitive; we also establish an essentially matching lower bound on the competitive ratio of SRPT. For multiprocessors, we show that the competitive ratio of SRPT is at most 14. Furthermore, we establish non-trivial constant-factor lower bounds on the competitive ratio of any uniprocessor or multiprocessor scheduling algorithm.

In conjunction with earlier work on the average response time measure, our results imply that SRPT achieves asymptotically optimal competitive ratios for average response time and average stretch simultaneously, for both uniprocessors and multiprocessors.

(Joint work with S. Muthukrishnan, Anthony Shaheen, and Johannes E. Gehrke.)

Rajmohan Rajaraman is an assistant professor in the College of Computer Science at Northeastern University. Prior to joining Northeastern in September 1998, he was a postdoctoral fellow at DIMACS, the NSF Center for Discrete Mathematics and Theoretical Computer Science. He obtained his Ph.D. at the University of Texas at Austin in December 1997.

The Capital Area Theory Symposia is an NSF sponsored series of symposia in theoretical computer science bringing computer scientists from around the world to the Capital area. The Symposia are given at the University of Maryland in cooperation with the Computer Science Department and UMIACS. NSF support under grant CCR-9732907 is gratefully acknowledged.