Special edition of queueing colloquium in honor of Mor Harchol Balter

*14.10-14:40
Caroline Jagtenberg - VU University
Talk: Learning to dispatch volunteers

For cardiac arrest patients, survival hinges on minutes. To shorten the
time to good-quality cardiopulmonary resuscitation, emergency call
centers may rapidly locate and alert nearby trained volunteers. How many
volunteers to alert, and when, is a sequential decision problem: alert too
few and no one arrives in time; alert too many and volunteer engagement
erodes. We formulate this phased-alerting problem as a Markov decision
process, where the state captures real-time information (volunteer
locations, elapsed triage time). A direct approach using dynamic
programming yields some insights, but is too slow for real-time use. Our
contribution lies in recasting this optimization problem as a multi-class
classification problem and solving it using empirical data from Auckland,
New Zealand’s. Will our algorithm outperform current practice?

*14.40 - 15.10
Sem Borst - Eindhoven University
Talk: Steady-State Approximations for Redundancy Systems in Non-CRP Scenarios \

We consider parallel-processing systems with redundancy policies and arbitrary compatibility constraints between servers and job types.
These systems allow for explicit multi-dimensional state space collapse results in non-Complete-Resource-Pooling (non-CRP) conditions which illuminate the delicate interplay between the various job types and servers.
We leverage these results to construct universal heavy-traffic approximations for the joint steady-state queue length distribution.
The approximations are shown to be asymptotically exact across the entire spectrum of heavy-traffic conditions, even in non-CRP scenarios, while being continuous in the system parameters.
Note: based on joint work with Ellen Cardinaels and Olivier Meiler

*15.30- 16.30
Mor Harchol-Balter - Bruce J. Nelson Professor of Computer
Science, Carnegie Mellon University
Talk: The joys of stochastic scheduling

ABSTRACT:  Scheduling is the primary tool we have for improving system
performance without purchasing additional resources.  By simply changing
the order in which we run jobs, we can dramatically improve response time
(both mean response time and the tail of response time).  Scheduling is
particularly effective in the case of heavy-tailed job size distributions,
which are omnipresent and can result in very high response times.  In this
talk we focus on the heavy-tailed job size setting.

We will start by reviewing optimal scheduling for the single-server queue
(the M/G/1), both for the mean and asymptotic tail of response time.  This
is well understood.

We then turn to multi-server systems (the M/G/n), where almost nothing is
understood on optimal scheduling.  We present our new results on the first
scheduling algorithms for the M/G/n which are asymptotically strongly tail
optimal.

We finish by discussing newer job models, like the multi-server job model,
which is representative of today’s datacenter jobs.  Here we present some
recent algorithms for optimal scheduling under heavy traffic.

Throughout, our emphasis will be on intuition and lessons learned.

BIO:
Mor Harchol-Balter is the Bruce J. Nelson Professor of Computer Science at
Carnegie Mellon. She received her Ph.D. from U.C. Berkeley in 1996, under
the direction of Manuel Blum.  She is the SIG Chair for ACM SIGMETRICS, a
4-year elected position and is a Fellow of both ACM and IEEE.  She has
received several teaching awards, including the Herbert A. Simon Award and
Spira Teaching Award. 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 / INFORMS research community where her papers have
received many awards (ValueTools 24, INFORMS George Nicholson Prize 22,
SIGMETRICS 21, SIGMETRICS 19, PERFORMANCE 18, INFORMS APS 18, EUROSYS 16,
MASCOTS 16, MICRO 10, SIGMETRICS 03, ITC 03, SIGMETRICS 96). She is the
author of two popular textbooks, both published by Cambridge University
Press: Performance Analysis and Design of Computer Systems (2013),
which bridges
queueing theory and computer science, and Introduction to Probability for
Computing (2024).