ORIE Special Seminar: Ziv Scully (Carnegie Mellon)

Location

https://cornell.zoom.us/j/93548705404?pwd=Y1R3cDhwaWlwNk13cldzazlrTzNxQT09

Description

A New Toolbox for Scheduling Theory

Queueing delays are ubiquitous in many domains, including computer systems, service systems, communication networks, supply chains, and transportation. Queueing and scheduling theory provide a rigorous basis for understanding how to reduce delays with scheduling, including evaluating policy performance and guiding policy design. Unfortunately, state-of-the-art theory fails to address many practical concerns. For example, scheduling theory seldom explicitly models nontrivial preemption limitations, and there is very little theory for scheduling in multiserver queues.

We present two new, broadly applicable tools that greatly expand the reach of scheduling theory, using each to solve multiple open problems. The first tool, called “SOAP”, is a new unifying theory of scheduling in single-server queues, specifically the M/G/1 model. SOAP characterizes the delay distribution of a broad space of policies, most of which have never been analyzed before. Such policies include the Gittins index policy, which minimizes mean delay in low-information settings, and many policies with preemption limitations. The second tool, called “WINE”, is a new queueing identity that complements Little’s law. WINE enables a new method of analyzing complex queueing systems by relating them to simpler systems. This results in the first delay bounds for SRPT (shortest remaining processing time) and the Gittins index policy in multiserver queues, specifically the M/G/k model.

Bio:
Ziv Scully is a graduate student in computer science at Carnegie Mellon University, advised by Mor Harchol-Balter and Guy Blelloch. He graduated from MIT in 2016 with a B.S. in mathematics with computer science. He is the recipient of an NSF Graduate Fellowship and an ARCS Foundation scholarship. Broadly, Ziv researches the theory of decision-making under uncertainty, resource allocation, and performance evaluation. His particular focus has been analyzing and optimizing computer systems and algorithms from a stochastic perspective, studying topics including job scheduling, load balancing, stochastic combinatorial optimization, and parallel algorithms. Recent publications of his have been recognized with awards from ACM SIGMETRICS (Best Paper Award, 2021; Best Video Award, 2020; Outstanding Student Paper Award, 2019), IFIP PERFORMANCE (Best Student Paper Award, 2018), and the INFORMS Applied Probability Society (Best Student Paper Prize finalist, 2018). For part of 2020, he served as an algorithms consultant for the NOVID exposure-notification project.