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 c₁ and c₂ 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 c₁ and c₂ converge to 1.