Abstract
The Gittins scheduling policy minimizes the mean response in the single-server M/G/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service requirements are unknown but drawn from a known distribution. Gittins is also optimal much more generally, adapting to any amount of available information and any preemption restrictions. However, scheduling to minimize mean response time in a multiserver setting, specifically the central-queue M/G/k, is a much more difficult problem.
In this work we give the first general analysis of Gittins in the M/G/k. Specifically, we show that under extremely general conditions, Gittins's mean response time in the M/G/k is at most its mean response time in the M/G/1 plus a term that grows logarithmically in the heavy-traffic limit, namely as the system load approaches capacity. A consequence of this result is that Gittins is optimal in the heavy-traffic M/G/k if the service requirement distribution has finite (2 + ε)th moment for any ε > 0. This is the most general result on minimizing mean response time in the M/G/k to date.
To prove our results, we combine properties of the Gittins policy and Palm calculus in a novel way. Notably, our technique overcomes the limitations of tagged job methods that were used in prior scheduling analyses.
Additional info
Joint work with Isaac Grosof and Mor Harchol-Balter.
Paper link: <https://ziv.codes/publications/#the-gittins-policy-is-nearly-optimal-in-the-mgk-under-extremely-general-conditions>
Speaker bio
Ziv Scully is a graduate student in Computer Science at CMU advised by Mor Harchol-Balter and Guy Blelloch. He graduated from MIT in 2016 with a BS in Mathematics with Computer Science. He is the recipient of an NSF Graduate Fellowship and an ARCS Foundation scholarship. Ziv’s research focus is optimizing and analyzing computer systems and algorithms from a stochastic perspective, including job scheduling, load balancing, combinatorial optimization under uncertainty, and parallel algorithms. Recent publications of his have been recognized with awards from the INFORMS Applied Probability Society (Best Student Paper Prize finalist, 2018), IFIP PERFORMANCE (Best Student Paper Award winner, 2018), and ACM SIGMETRICS (Outstanding Student Paper Award winner, 2019; Best Video Award winner, 2020).
