ISL Colloquium: New Breakthroughs in Scheduling Theory

New Breakthroughs in Scheduling Theory
Thursday, October 11, 2018 - 4:15pm
Packard 202
Mor Harchol-Balter (Carnegie Mellon University)
Abstract / Description: 

Scheduling policies are at the heart of computer systems. The right scheduling policy can dramatically reduce response times, ensure fairness, provide class-based priority, etc., without requiring additional resources. While stochastic response time analysis of different scheduling policies has been the focus of thousands of theoretical papers, results are limited to analyzing a relatively small number of "simple" scheduling policies.

In this talk, we introduce the SOAP class of scheduling policies: Schedule Ordered by Age-based Priority. The SOAP policies include almost all scheduling policies in the literature as well as an infinite number of variants which have never been analyzed, or maybe even conceived. SOAP policies include the highly intractable SERPT policy (Shortest-Expected-Remaining-Processing-Time), as well as the famously complex Gittins Index policy. SOAP also includes all sorts of "combination" policies, like a policy that performs Shortest-Job-First on jobs with known size and Foreground-Background scheduling on jobs with unknown size, or a policy that is allowed to preempt jobs only when they hit certain ages. In this talk we present a stochastic response time analysis of all SOAP policies via a single universal framework.

Joint work with: Ziv Scully and Alan Scheller-Wolf

Appeared in ACM SIGMETRICS/POMACS 2018. APS 2018 Best Student Paper Finalist.

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Thursday at 4:15 pm during the academic year.

The Information Theory Forum is organized by graduate students Martin Zhang, Farzan Farnia, and Zhengyuan Zhou. To suggest speakers, please contact any of the students.


Mor Harchol-Balter is a Professor of Computer Science at CMU. She received her Ph.D. from U.C. Berkeley in 1996 under the direction of Manuel Blum. She joined CMU in 1999, and served as the Head of the PhD program from 2008-2011. Mor is a Fellow of the ACM and a Senior Member of IEEE. She is a recipient of the McCandless Junior Chair, the NSF CAREER award, and several teaching awards, including the Herbert A. Simon Award. She has received faculty awards from a dozen companies including Google, Microsoft, IBM, EMC, Facebook, Intel, Yahoo!, and Seagate. Mor's work focuses on designing new resource allocation policies, including load balancing policies, power management policies, and scheduling policies. Mor is heavily involved in the SIGMETRICS/PERFORMANCE research community, where she has received many best paper awards, and where she served as TPC Chair in 2007, as General Chair in 2013, and as the Keynote Speaker for 2016. She is also the author of a popular textbook, "Performance Analysis and Design of Computer Systems," published by Cambridge University Press, which bridges Operations Research and Computer Science.