## DIMACS TR: 99-02

## Scheduling to Minimize Average Stretch

### Authors: Johannes E. Gehrke, S. Muthukrishnan, Rajmohan Rajaraman and Anthony Shaheen

**
ABSTRACT
**

We consider the classical problem of online preemptive 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.

We first prove that no on-line algorithm can achieve a competitive ratio that
is smaller than 1.03. The main contribution of this paper is to show that the
shortest remaining processing time algorithm (SRPT) is O(1)-competitive with
respect to average stretch for both uniprocessors as well as multiprocessors.
For uniprocessors, we prove that SRPT is 2-competitive. We also establish
an essentially matching lower bound on the competitve ratio of SRPT on
uniprocessors. For multiprocessors, we show that the competitive ratio of
SRPT is at most 14.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-02.ps.gz

DIMACS Home Page