Title: Shortest Processing Time Approximates Total Flow Time

Abstract:

We discuss the problem of scheduling jobs on a single processor. The flow
time of a job is its completion time minus its release time, i.e. the
total time that job was in the system.  In the preemptive setting, where
jobs can be interrupted and restarted, it is well know that the minimum
total flow time is achieved by the algorithm Shortest Remaining Processing
Time (SRPT), which always runs the job with least remaining processing
time. The non-preemptive analog of SRPT is Shortest Processing Time (SPT),
which selects the shortest job whenever the processor becomes idle.  We
show that SPT is a Delta approximation for total flow time, where Delta is
the ratio between the longest and shortest jobs.  This is best possible.

Thanks,

David Bunde (UIUC Department of Computer Science)