ORIE Colloquium: Mor Harchol-Balter (Carnegie Mellon) - New Breakthroughs in Scheduling Theory

Location

Frank H. T. Rhodes Hall 253

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. If time permits, we will also discuss some open problems in scheduling of current interest.

Joint work with Ziv Scully and Alan Scheller-Wolf.

Bio:
Mor Harchol-Balter is a professor of computer science at Carnegie Mellon University. She received her Ph.D. from U.C. Berkeley in 1996. She joined CMU in 1999, and served as the head of the Ph.D. program from 2008-2011. Mor is a Fellow of the ACM and a Fellow 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.