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 Theta((mu(1-rho)ln(e/(1-rho)))(-1)), where rho is the system load. Thus, SRPT offers a Theta(ln(e/(1-rho))) factor improvement over policies that ignore knowledge of job sizes while scheduling