New Breakthroughs in Scheduling Theory

Speaker: Mor Harchol-Balter, Professor of Computer Science, CMU

Abstract:  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.  

Bio: 

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.