Victor Araman
American University of Beirut
Scheduled Traffic with Application to Queues
Abstract: The queueing literature, for the most part, has considered renewal-like input processes (typically, characterized by an i.i.d. sequence of interarrivals, or some variant of that). In this work, we discuss a new model for input traffic, known as scheduled arrivals. These processes differ markedly from renewal-like input, and find their roots in a number of real-world applications, ranging from manufacturing to appointment-based service systems. A “scheduled” arrival process is one in which the nth arrival is scheduled for time n, but instead occurs at n + x_n , where the x_j ‘s are i.i.d. In this talk, I will discuss a number of interesting properties of this process and characterize among other things its correlation structure. I will then analyze the impact of such input traffic on a single server queue with deterministic processing times. I will first argue that under some conditions on the perturbation x, the queue is stable even when the utilization is equal to one. I will then fully characterize the performance of this system under a heavy traffic regime for Pareto-like perturbations (with finite and infinite mean) and compare these results to standard G/D/1 and a D/D/1 queues. In a nutshell, our work shows that, despite the random perturbations, scheduled traffic exhibits many of the good properties associated with deterministic arrival streams.
Marko Boon
Eindhoven University of Technology
Adaptive and dynamic appointment scheduling
Abstract: In this talk, we consider appointment scheduling in a setting where the schedule of all future clients can be adapted at specific time points. The classical paradigm in appointment scheduling is to rely on `a priori schedules’, determined by minimizing a given cost function; the corresponding arrival times are then announced to the clients, and not adjusted while serving them. The idea of this talk is to reduce the cost by periodically updating the schedule (and notifying the clients about this), based on the current state of the system. Evaluation of the objective function is done highly efficiently and accurately by approximating the service times by their phase-type counterparts. The resulting method is computationally inexpensive, thus facilitating frequent evaluation and adaptation of schedules `on the fly’.
We compare two strategies: dynamic and adaptive updating of the schedule. The first approach relies on dynamic programming, with the state information being the number of clients waiting, the elapsed service time of the client in service, and the number of clients still to be scheduled. Numerical evaluation of the dynamic programming procedure poses computational challenges; we point out how we have succeeded in overcoming these. The second approach, adaptive scheduling, also allows for regularly updating the schedule, but does not rely on dynamic programming to find the optimal schedule. The crucial difference is that the dynamic programming approach `exploits’ the fact that when rescheduling, one knows that there will be more future rescheduling moments. While using this knowledge yields truly optimal results, the enormous state space makes real-time computations of schedules computationally challenging. In numerical experiments we quantify the difference between both algorithms. Other numerical experiments show (i) the effect of wrongly assuming exponentially distributed service times, and (ii) the gains (over static schedules, that is) achieved by rescheduling.
The most prominent conclusion is that typically, even with relatively few updates, costs can be reduced drastically. Our experiments, however, also reveal that one can construct instances for which increasing the rescheduling frequency does not guarantee a cost reduction; we provide an in-depth analysis of the remarkable phenomenon. The work has broad application potential, e.g. in healthcare and for delivery companies.
Joint work with Roshan Mahes, Michel Mandjes, and Peter Taylor
Xinyun Chen
The Chinese University of Hong Kong, Shenzhen
Online Learning and Optimization for Queues with Unknown Demand Curve and Service Distribution
Abstract: We investigate an online learning and optimization problem in a queueing system having unknown arrival rates and service-time distribution. The service provider’s objective is to seek the optimal service fee $p$ and service capacity $\mu$ so as to maximize the cumulative expected profit (the service revenue minus the capacity cost and delay penalty). We develop an online learning algorithm is able to effectively evolves the service provider’s decisions utilizing real-time data including customers’ arrival and service times, without needing the information of the arrival rate or service-time distribution. Effectiveness of the online learning algorithm is substantiated by (i) theoretical results including the algorithm convergence and analysis of the regret, i.e. the cost to pay over time for the algorithm to learn the optimal policy, and (ii) engineering confirmation via simulation experiments of a variety of representative examples. This is joint work with Yunan Liu from NCSU and Guiyu Hong from CUHK-Shenzhen.
Nicolas Gast
INRIA Grenoble
Restless bandits, weakly coupled MDPs and LP relaxations
Abstract: Many resource allocation problems can be modeled as « weakly coupled MDPs ». In such a problem, an operator is faced with a set of resources whose state evolves over time. The evolution of resources are coupled through the actions of the controller. These problems are in general computationally hard. Yet, there exists different LP-based relaxations (including the famous Whittle index) that generally provide a near-optimal solution. The goal of this talk is to introduce these policies, and to present recent results on when they become asymptotically optimal and the rate at which they become optimal.
Harsha Honnappa
Purdue University
The Sample Complexity of Offline Reinforcement Learning
Abstract: Offline reinforcement learning (RL) is a paradigm wherein an agent learns from static datasets collected from prior interactions with a random environment. The offline RL paradigm can be seen to be very natural in the context of critical service systems, where the online nature of standard RL may not be appropriate to use. The datasets are collected under a fixed, albeit unknown, ‘behavior’ control policy. The agent, then, first estimates the Markov decision process (MDP) model, and then, in a separate step, uses the learnt model to further identify an optimal policy. The estimation or system identification first step is therefore crucial to the efficacy of offline RL, and statistical inference for this problem is remarkably important and hard to achieve.
In this talk, I will present recent results establishing sample complexity results for nonparametric estimators of the MDP, under very general mixing assumptions on the control sequence generated by the behavior policy. Our first result exploits an Azuma-Hoeffding-type concentration inequality established by Kontorovich and Ramanan (2008) for dependent sequences. However, the mixing conditions are weak, and consequently the sample complexity bound is not sharp, in the sense that we cannot show that the nonparametric estimator is minimax optimal. By further strengthening the mixing assumptions, we also show that it is possible to exploit a tighter, Bernstein-type inequality proved by Merlevede, Peligrad and Rio (2009) for strong mixing sequences. In fact, it turns out that under these conditions, the sample complexity bound is indeed sharp. To the best of our knowledge, this is the first result establishing the minimax optimality of a nonparametric estimator for offline RL/system identification of MDPs.
This is joint work with Imon Banerjee and Vinayak A. Rao of the Department of Statistics at Purdue University. This research is supported by the National Science Foundation (NSF) under grant CMMI/2143752 and DMS/2153915.
Rouba Ibrahim
University College London
Size-based scheduling in service systems
Abstract: Size-based scheduling policies, such as shortest-remaining-processing-time (SRPT) and shortest-job-first (SJF), have been extensively studied, for decades, yet almost exclusively in single-server queues with infinitely patient jobs and under exact job-size information. Motivated by applications to service systems, such as call centers or healthcare facilities, we analyze the performance of size-based scheduling in multiserver queues with abandonment and inexact job-size information. In particular, we demonstrate that system performance under size-based scheduling with noisy service times is asymptotically equivalent, in the many-server heavy-traffic limit, to performance under a two-class priority queue where customers with short service times (below a threshold) are served without wait, and customers with long service times (above a threshold) eventually abandon without service. This is joint work with Jing Dong, from Columbia Business School.
Caroline Jagtenberg
Vrije Universiteit Amsterdam
Modeling Emergency Medical Service Volunteer Response
Abstract: Survival for cardiac arrest patients can be improved by alerting CPR-trained volunteers via an app. To answer the question how many volunteers are needed, and how this depends on their location distribution, we model the presence of volunteers throughout a region as a Poisson point process. We compute the response-time distribution and, using known survival functions from literature, infer survival rates. We evaluate the impact of volunteer alert systems under both plausible volunteer location distributions and develop an optimization model to compute the volunteer location distribution that maximizes survival rates. We introduce several variants of this optimization problem, all of which are highly tractable, and include a case study for Auckland, New Zealand. Our results provide the required density of volunteers to meet a given response-time target, which can be used to justify the introduction of a volunteer alert app in new cities. Moreover, our methods quantify the number of volunteers needed to substantially increase survival rates, depending on the spread of cardiac arrests as well as volunteers throughout the city. This may guide the recruitment of additional volunteers in existing systems, indicating the city locations where additional recruitment would be most beneficial. Effective targets for additional recruitment are not always obvious, since volunteers recruited from one area may spend time in various areas across the city; our optimization explicitly captures this issue.
Petar Momcilovic
Texas A&M University
A Probabilistic Approach to Growth Networks
Abstract: Closed product-form networks, consisting of single-server and infinite-server queues, have emerged as relevant models for several applications. Although such models admit a seemingly tractable product-form solution, explicit analytical characterization of its partition function is difficult in the case of large-scale networks. To this end, we develop a novel methodology, based on a probabilistic representation of product-form solutions and large-deviations concentration inequalities, which identifies distinct operating regimes and yields explicit expressions for the marginal distributions of queue lengths. The parameters of the derived distributions can be computed from equations involving large-deviations rate functions, often admitting closed-form algebraic expressions. From a methodological perspective, a fundamental feature of our approach is that it provides exact results for order-one probabilities, even though our analysis involves large-deviations rate functions, which characterize only vanishing probabilities on a logarithmic scale.
Tava Olsen
The University of Auckland
Time Is Money: Leadtime Quotation and Pricing in Make-to-order Environments
Abstract: This talk is based on a series of my papers (with a variety of co-authors) considering leadtime quotation and pricing. All papers consider a make-to-order (monopolistic) firm (i.e., a queueing system) where customers are quoted leadtimes and prices. Canonical applications for this work include make-to-order furniture or custom-services such as DNA sequencing. The first half of the talk will consider my recent work where we allow the act of quotation to affect customers’ perceptions of delay. I will briefly review a controlled behavioral experiment we ran that confirms that quotes act as reference points for customers. Based on this evidence, we built static and dynamic models in which customers’ utility explicitly captures the interaction between quotes and waiting times, which the provider then considers when supplying quotes to customers. We use these models to derive optimal static and dynamic quotation policies for a single-server queue. The experiment, which mimics a situation where accuracy in quotation is valued, also demonstrates a negative linear relationship between quote inaccuracy and the participants’ overall satisfaction. Unlike previous work in this area, we find that shorter waits can induce dissatisfaction if service concludes earlier than the lead-time quotation. Based on this empirical finding, we examine a customers’ cost function with a piecewise linear component. We find that is not always optimal to supply quotes higher than the expected waiting times, contrary to the conventional wisdom of “under-promise and over-deliver”. The remainder of the talk will review published work where customers have general (non-linear) disutility for delay (unaffected by the quote). We assume that quoted leadtimes must be met either through overtime or expediting. We use approximations in the large-capacity asymptotic regime to make the problem tractable. We provide recommended policies for convex, concave, and convex-concave leadtime cost functions for firms with either one (homogenous) or multiple (heterogeneous) classes of customer. We consider both the full information case and the (more realistic) case where the firm, being unaware of customer type, must offer incentive-compatible menus. We propose readily-implementable policies and test them numerically against a number of natural benchmarks. The policies are both highly intuitive and provide delay guarantees for all served customers
Michael O’Sullivan
The University of Auckland
Modern Tools for the Management of Healthcare Systems: modelling and AI in a digital future
Abstract – Modelling and artificial intelligence (AI) have been explored as tools for healthcare management for over a decade. However, the more recent focus on digital technology and, in particular, digital transformation means that these tools can now easily be used in day-to-day management of healthcare services. We will present case studies on research into the use of modelling and AI in healthcare management and suggest how these tools could be used in the digital future of healthcare.
Chung Piaw Teo
National University of Singapore
Online Flow Control: Theory and Application
Abstract: In this talk, I will provide an overview of a series of work on online resource allocation problem, and discuss a recent application in Crowd management during peak commuting hours in oversaturated metro systems. We develop real-time passenger flow control policies to manage the inflow of crowds at each station, to optimize the total load carried or revenue earned (efficiency), and to ensure that adequate service is provided to passengers on each o-d pair (fairness), as much as possible. For given train capacity, we use Blackwell’s approachability theorem and Fenchel duality to characterize the attainable service level of each o-d pair. We use these insights to develop online policies for crowd control problems. Numerical experiments on a set of transit data from Beijing show that our approach performs well compared to existing benchmarks in the literature. Joint work with Jinpeng Liang, Guodong Lyu and Ziyou Gao.
Melanie Reuter-Oppermann
Technical University of Darmstadt
Recent topics in EMS logistics
Abstract: Many countries have well-established and well-equipped emergency medical service (EMS) systems that send trained paramedics or emergency medical assistants to the scene of events. Emergency services in countries such as Germany are defined by a complex service network and a multitude of planning problems and necessary decisions. However, almost all EMS systems worldwide face an increasing cost pressure often accompanied with a shortage of staff and other necessary resources as well as the issue of long distances to sparsely populated areas. This means that adequate response times for all patients, 24/7, and throughout all regions are difficult or even impossible to ensure. To overcome these issues and potentially reduce the consequences of daily emergencies (i.e., frequent events with low magnitude of consequences), several countries, including Sweden, Germany, the UK, and the Netherlands have started initiatives in which new types of resources, human resources as well as equipment, are employed in response to daily (medical) emergencies. In this talk, we want to address recent topics in EMS logistics from a practical and a research perspective and present and discuss ideas and approaches for as well as service aspects of different planning problems including the location of ambulances and the scheduling of patient transports.
Rhonda Righter
University of California, Berkeley
Robustness in Markov Matching Models
Abstract: We consider one- and two-sided matching models and give sufficient conditions for insensitivity and policy-space collapse. By insensitivity, we mean that the stationary behavior depends only on the means of some of the distributions. By policy-space collapse, we mean that the model behavioris the same for any queue-position-based matching order, such as first-come-first-matched and last come-first-matched. Many existing results are corollaries of our results, and we show new results for variants of redundancy(d) models, both under cancel-on-complete and cancel-on-start protocols. Joint work with Runhan Xie and Kristy Gardner
Amy Ward
The University of Chicago
Learning the Scheduling Policy in Time-Varying Multiclass Many Server Queues with Abandonment
Abstract: We consider a learning variant of a canonical scheduling problem in a multiclass many server queue with abandonment (specifically, the M_t/M/N+M and the GI/GI/N+GI queues). The objective is to minimize the long-run average class-dependent expected linear holding and abandonment costs when the class-dependent model parameters (arrival rates, service rates and abandonment rates) are a priori unknown. The difficulty is that even when parameters are known, characterizing an optimal scheduling policy appears intractable. Fortunately, the simple cμ/θ rule, that prioritizes classes in accordance with a static ranking that depends on the costs, the service rates, and the abandonment rates, is asymptotically optimal as the arrival rates and number of servers become large under certain conditions. Then, our task is to learn the service and abandonment rates well enough to determine an optimal static priority ranking for the classes, and we can benchmark our performance by defining the regret relative to the cμ/θ rule. We propose a Learn-Then-Schedule algorithm, which is composed of a learning phase during which point estimates of the mean service and patience times are formed, and an exploitation phase during which the cμ/θ rule with empirical mean estimates as a surrogate for actual parameters is followed. It is shown that the smallest achievable regret for static priority scheduling policies in T periods is Ω(logT), and we prove that our proposed algorithm achieves a regret upper bound of O(logT), which matches the lower bound.
Adam Wierman
California Institute of Technology
Learning & Control in Safety-Critical Systems
Abstract: Making use of modern black-box AI tools such as deep reinforcement learning is potentially transformational for safety-critical systems such as data centers, the electricity grid, transportation, and beyond. However, such machine-learned algorithms typically do not have formal guarantees on their worst-case performance, stability, or safety and are typically difficult to make use of in distributed, networked settings. So, while their performance may improve upon traditional approaches in “typical” cases, they may perform arbitrarily worse in scenarios where the training examples are not representative due to, e.g., distribution shift or unrepresentative training data, or in situations where global information is unavailable to local controllers. These represent significant drawbacks when considering the use of AI tools in safety-critical networked systems. Thus, a challenging open question emerges: Is it possible to provide guarantees that allow black-box AI tools to be used in safety-critical applications? In this talk, I will provide an overview of a variety of projects from my lab at Caltech that seek to develop robust and localizable tools combining model-free and model-based approaches to yield AI tools with formal guarantees on performance, stability, safety, and sample complexity.
Kuang Xu
Stanford University
Information design for load balancing
Abstract: Information has long played a crucial, if somewhat understated, role in dynamic resource allocation and control for queueing networks. I will discuss some recent results, as well as open questions, in understanding how to perform efficient inference and information exchange in load balancing systems. In the first part of the talk, we will examine the problem of using empirical operational data to perform statistical inference. We ask what types of observables provide the most information and how dynamic control polices may impact the inferential power of the data produced. In the second part, we will look at the problem of load balancing under a limited communication budget by using approximations of the system state. Our goal is to obtain conditions under which quality approximation leads to strong performance guarantees, and to generate desirable state approximations using the least amount of communication possible. Based on joint work with Gal Mendelson (Stanford).
See also:
Christos Zacharias
University of Miami
Dynamic Interday and Intraday Scheduling
Abstract: The simultaneous consideration of appointment day (interday scheduling) and time of day (intraday scheduling) in dynamic scheduling decisions is a theoretical and practical problem that has remained open. We introduce a novel dynamic programming framework that incorporates jointly these scheduling decisions in two timescales. Our model is designed with the intention of bridging the two streams of literature on interday and intraday scheduling and to leverage their latest theoretical developments in tackling the joint problem. We establish theoretical connections between two recent studies by proving novel theoretical results in discrete convex analysis regarding constrained multimodular function minimization. Grounded on our theory, we develop a practically implementable and computationally tractable scheduling paradigm with performance guarantees. Numerical experiments demonstrate that the optimality gap is less than 1% for practical instances of the problem.