We study the basic problem of preemptive scheduling of a stream of jobs on a single processor. Consider an online stream of jobs, and let the $i$th job arrive at time $\rel{i}$ and have processing time $\p{i}$. If $\C{i}$ is the completion time of job $i$, then the flow time of $i$ is $\C{i}-\rel{i}$ and the stretch of $i$ is the ratio of its flow time to its processing time; that is, $\frac{\C{i}-\rel{i}}{\p{i}}$. Flow time measures the time that a job is in the system regardless of the service it requests; the stretch measure relies on the intuition that a job that requires a long service time must be prepared to wait longer than jobs that require small service times.
We present new algorithmic results for the average stretch metric in preemptive uniprocessor scheduling. Our first result is an offline polynomial-time approximation scheme for average stretch scheduling. This result improves on the previous best polynomial-time approximation factor of $2$ achieved by the online algorithm SRPT, that always schedules a job with the shortest remaining processing time. Our second set of results considers the impact of incomplete knowledge of job sizes on the performance of online scheduling algorithms. We show that a constant-factor competitive ratio for average stretch is achievable even if the processing times (or remaining processing times) of jobs are known only to within a constant factor of accuracy.