Optimal Scheduling for Multiserver Systems
September 26, 2018 (GHC 8102)

The optimal scheduling policy for minimizing mean response time in a single-server system is the Shortest Remaining Processing Time (SRPT) scheduling policy.

While beautiful results are known for single-server SRPT, much less is known for \emph{multiserver SRPT}.

In particular, stochastic analysis of the \mgk/ under multiserver SRPT is entirely open. Intuition suggests that multiserver SRPT should be optimal or near-optimal for minimizing mean response time. However, the only known analysis of multiserver SRPT is in the worst-case adversarial setting, where SRPT can be far from optimal.

We give the first stochastic analysis bounding mean response time of the \mgk/ under multiserver SRPT. Using our response time bound, we show that multiserver SRPT has asymptotically optimal mean response time in the heavy-traffic limit.