On the Average Sojourn Time under M/M/1/SRPT

We consider an M/M/1 queueing system under the Shortest Remaining Processing Time (SRPT) policy. We show that there are constants c1 and c2 such that for any load the average sojourn time under SRPT lies between and where denotes the service rate and denotes the load. Comparing this with the classic result that any scheduling policy that does not use the knowledge of job sizes has average sojourn time implies that SRPT offers a non-constant improvement over such policies. Finally, in the limiting case, as the load approaches 1, we show that the constants c1 and c2 converge to 1.

By: Nikhil Bansal

Published in: Operations Research Letters, volume 33, (no 2), pages 195-200 in 2005

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .