Outperforming Multiserver SRPT at All Loads

A well-designed scheduling policy can unlock significant performance improvements with no additional resources. Multiserver SRPT (SRPT-k) is known to achieve asymptotically optimal mean response time in the heavy traffic limit, as load approaches capacity. No better policy is known for the M/G/k queue in any regime. We introduce a new policy, SRPT-Except-k+1 & Modified SRPT (SEK-SMOD), which is the first policy to provably achieve lower mean response time than SRPT-k. SEK-SMOD outperforms SRPT-k across all loads and all job size distributions. The key idea behind SEK-SMOD is to prioritize large jobs over small jobs in specific scenarios to improve server utilization, and thereby improve the response time of subsequent jobs in expectation. Our proof is a novel application of hybrid worst-case and stochastic techniques to relative analysis, where we analyze the deviations of our proposed SEK-SMOD policy away from the SRPT-k baseline policy. Furthermore, we empirically verify the improvement of SEK (a simplified variant of SEK-SMOD) over SRPT-k via simulation.