Georgia Institute of Technology College of Sciences

Large-scale computing systems are massively important, using over 1% of the world's electricity. It is vital that these systems be both fast and resource-efficient, and scheduling theory is a key tool towards that goal. However, prior scheduling theory is not equipped to handle large multiserver systems, with little extant theoretical analysis, and no optimality results.

I focus on two important multiserver scheduling systems: The one-server-per-job (M/G/k) model, and the multiple-servers-per-job (MSJ) model. In the M/G/k, we prove the first optimality result, demonstrating that the Shortest Remaining Processing Time (SRPT) policy yields asymptotically optimal mean response time in the heavy traffic limit. In the MSJ model, we prove the first mean response analysis for any scheduling policy, for a novel policy called ServerFilling. Moreover, we introduce the ServerFilling-SRPT policy, for which we present the first asymptotic optimality result for the MSJ model. Each result progresses by proving novel bounds on relevant work, and using novel methods to convert those bounds to bounds on mean response time. These results push the state of the art of scheduling theory ever closer to applicability to today's large-scale computing systems.