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

ABSTRACT

We consider an M/M/1 queueing system under the Shortest Remaining Processing Time (SRPT) policy. We show that there are constants c_l and c₂ such the average sojourn time under SRPT lies between c_l (μ(1 - ρ) log 1/(1 - ρ))^-1 and c₂ (μ(l - ρ) log 1/(1 - ρ))^-1, 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 (μ(1-ρ))^-1, implies that SRPT offers a non-constant improvement over such policies.

REFERENCES

• 1: R. W. Conway, W. L. Maxwell, and L. W. Miller. Theory of Scheduling. Addison-Wesley Publishing Company, 1967.
• 2: L. E. Schrage. A proof of the optimality of the shortest processing remaining time discipline. Operations Research, 16:678--690, 1968.
• 3: L. E. Schrage and L. W. Miller. The queue M/G/1 with the shortest processing remaining time discipline. Operations Research, 14:670--684, 1966.