Keynote Speakers

Mor Harchol-Balter (Carnegie Mellon University, Pittsburgh, USA)

Title: New breakthroughs in scheduling theory

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

This talk is based on a 2018 ACM SIGMETRICS/POMACS paper with Ziv Scully and Alan Scheller-Wolf. The paper was an APS 2018 Best Student Paper Finalist.

Short biography: Mor Harchol-Balter is a Professor of Computer Science at CMU. 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 NSF CAREER award, and several teaching awards, including the Herbert A. Simon Award and Spria 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.

 

Johan van Leeuwaarden (Tilburg University, Tilburg, The Netherlands)

Title: Sharp approximations and sharpest possible bounds for the GI/G/1 queue

Abstract: For the GI/G/1 queue, Kingman (1961) showed that the scaled stationary waiting time W converges in distribution to an exponential random variable as the queue approaches criticality. Kingman showed convergence of transforms, and hence weak convergence of the associated random variables. We apply and extend this transform method to obtain refined approximations for the moments of W. This is Part 1, based on joint work with A.J.E.M. Janssen.

A notorious problem in queueing theory is to identify the worst possible performance of the GI/G/1 queue under mean-dispersion constraints for the interarrival and service time distributions. We address this extremal queue problem by measuring dispersion in terms of Mean Absolute Deviation instead of variance and using Distributionally Robust Optimization. We obtain the extremal interarrival time and service time distributions, and hence the sharpest possible bounds, on all moments of W. This is Part 2, based on joint work with Dick den Hertog.

Short biography: Johan van Leeuwaarden is a Professor of Stochastic Operations Research at Tilburg University. He also holds a professorship at Eindhoven University of Technology (one day a week). He obtained his Ph.D. in mathematics (2005, top honors). He is a recipient of an ERC grant (2010) and the Erlang Prize (2012) for contributions to probability theory and applications. He has been a member of The Young Academy (The Royal Netherlands Academy of Arts and Sciences) since 2015. Johan develops mathematical methods to understand and design large-scale stochastic systems.