Bounds on M/G/k Scheduling Under Moderate Load Improving on SRPT-k and Tightening Lower Bounds

A well-designed scheduling policy can significantly improve the performance of a queueing system, without requiring any additional resources. While scheduling is well-understood in the single-server setting, much less is known in the multiserver setting. Results are particularly sparse in moderate load settings, outside of the asymptotic regimes of heavy traffic and light traffic. Multiserver SRPT is known to achieve asymptotically optimal mean response time as in the limit as load approaches capacity, and no better policy is known outside of that asymptotic regime.