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. © 2004 Elsevier B.V. All rights reserved.