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 minimizing average
stretch.

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 competitive ratio of SRPT. For
multiprocessors, we show that the competitive ratio of SRPT is at most 14.
Furthermore, we establish constant-factor lower bounds on the competitive
ratio of any on-line algorithm for both uniprocessors and multiprocessors.