  The Shortest Remaining Processing Time (SRPT) scheduling policy and its
variants have been extensively studied in both theoretical and practical
settings. While beautiful results are known for single-server SRPT, much less
is known for multiserver SRPT. In particular, stochastic analysis of the M/G/k
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. In this paper, we give
the first stochastic analysis bounding mean response time of the M/G/k under
multiserver SRPT. Using our response time bound, we show that multiserver SRPT
has asymptotically optimal mean response time in the heavy-traffic limit. The
key to our bounds is a strategic combination of stochastic and worst-case
techniques. Beyond SRPT, we prove similar response time bounds and optimality
results for several other multiserver scheduling policies.
