On the average sojourn time under M/M/1/SRPT

We study an M/M/1 queueing system under the shortest remaining processing time (SRPT) policy. We show that the average sojourn time varies as Θ((μ(1−ρ)ln(e/(1−ρ)))−1), where ρ is the system load. Thus, SRPT offers a Θ(ln(e/(1−ρ))) factor improvement over policies that ignore knowledge of job sizes while scheduling.