- This event has passed.
YEQT XIII : “Data-Driven Analytics and Optimization for Stochastic Systems”
Oct 16, 2019 - Oct 18, 2019
A very nice conference dinner at the PSV stadium!
Summary
The Young European Queueing Theorists (YEQT) workshops are organized on a yearly basis, and this year the 13th edition of the workshop will take place in October 2019. The aim of these workshops is to bring together young researchers, PhD students or recently appointed lecturers and assistant professors, and world-leading experts in order to share and discuss research related to queueing theory, operations research, applied probability and related areas. This event provides an excellent opportunity for developing researchers to interact and exchange ideas in an informal, friendly, yet research-focused setting. The workshop program will consist of presentations from young researchers and several keynote presentations and tutorials by prominent researchers.
The theme for the YEQT workshop this year is “Data-Driven Analytics and Optimization for Stochastic Systems”. The workshop will focus on combining theoretical stochastic modelling and optimization together with modern statistical techniques in order to tackle important problems that are prevalent today in various domains.
In many applications of queueing theory, such as healthcare, transportation systems, service operations, and communication networks, there is inherent uncertainty in the system behavior which calls for stochastic modelling, and an abundance of data which calls for smart statistical techniques that enable improving the understanding and ultimately the performance optimization of the system. There is often a gap between research focused on the former (i.e. stochastic/statistical modelling) and research focused on the latter (i.e. optimization techniques). However, the increasing availability of real-time data offers new opportunities for not only statistical analysis, and optimization of decision making but especially their integration. In fact, because all modern systems generate their own data, it is now possible to integrate and tailor statistical methods and optimization to individual systems, where before these steps were typically separate, leading to so-called data-driven analytics and optimization.
Sponsors
Organizers
| Mark van der Boor | TU Eindhoven |
| Collin Drent | TU Eindhoven |
| Liron Ravner | University of Amsterdam |
Keynote Speakers
| Mor Armony | New York University |
| Peter Glynn | Stanford University |
| Nathan Kallus | Cornell University |
| Ger Koole | VU Amsterdam |
| Michel Mandjes | University of Amsterdam |
| John Tsitsiklis | Massachusetts Institute of Technology |
Invited Speakers
| Arnoud den Boer | UvA |
| Antonio Castellanos | Technion |
| Johannes Diefenbach | University of Mannheim |
| Prateek Jaiswal | Purdue University |
| Sarah James | Adelaide University |
| Stella Kapodistria | TU Eindhoven |
| Siqiao Li | VU Amsterdam |
| Jaron Sanders | TU Eindhoven |
| Apoorv Saxena | Ghent University |
| Fiona Sloothaak | TU Eindhoven |
| Ran Snitkovsky | Tel Aviv University |
| Heletje van Staden | KU Leuven |
| Rik Timmerman | TU Eindhoven |
| Dongyuan Zhan | UCL |
| Martín Zubeldía | TU Eindhoven |
Programme
Abstracts
Queueing Systems with (MIS)behaving Servers and Customers
Traditional queueing theory has assumed that customer arrival times and service requirements, as well as server service speed, are exogenously determined. This assumption makes sense for systems with non-human customers and servers. In practice, in service systems that involve humans as customers and / or servers, behavioral effects may lead to violation of these assumptions. Specifically, both customers and servers may respond to incentives related to social comparisons, sense of ownership, and fatigue, to name a few. These behaviors can dramatically change the performance and optimal control of queueing systems. We survey recent literature and present opportunities for further research.
Dynamic Pricing with Demand Learning and Reference Effects
We consider a seller’s dynamic pricing problem with reference effects: the phenomenon that sales is not only influenced by the current price, but also by a so-called reference price constructed in the minds of potential customers based on the seller’s price history. There is substantial empirical evidence that customers are loss averse: that means that the demand reduction when the selling price exceeds the reference price is larger than the demand increase when the selling price falls behind the reference price by the same amount. Consequently, the expected demand as a function of price has a time-varying “kink” and is not differentiable everywhere. The seller neither knows the underlying demand function nor observes the time-varying reference prices. In this setting, we show that neglecting the reference effect can be very costly. We design and analyze a policy that (i) changes the selling price very slowly to control the evolution of the reference prices, and (ii) gradually accumulates sales data to balance the trade-off between learning and earning. We prove that, under a variety of reference-price updating mechanisms, our policy is asymptotically optimal; i.e., its T-period revenue loss relative to a clairvoyant who knows the demand function and the reference-price updating mechanism grows at the smallest possible rate in T. We also extend our analysis to the case of gain-seeking customers, and show that, surprisingly, the `difficulty of the learning problem’, measured by the asymptotically optimal growth rate of the regret, is parameter-dependent.
Silent Abandonment in Contact Centers: Estimating Customer Patience with Uncertain Data
In the quest to improve services, companies offer customers the opportunity to interact with servers through contact centers, where the communication is mainly text-based. This has become one of the favorite channels of communication with enterprises in recent years. However, contact centers face operational challenges, since the measurement of common proxies for customer experience such as: knowing if customers abandoned and their willingness to wait (patience), have information uncertainty. We focus this research on the impact of a main source of uncertainty we have identified, that of silent abandonment of customers. These customers leave the system while waiting for a reply to their inquiry, but give no indicator for doing so, such as closing the mobile app of the interaction. As a result, the system is unaware that they left and hence waste server time and capacity until this fact is realized. Therefore, it should not come with surprise that we find that silent abandonment affects system efficiency. We develop methodologies to identify silent-abandonment customers in two types of contact centers for which we have data available: chat and messaging systems. We show how to estimate customer patience accurately in both environments—an important parameter to fitting queuing models to the data—and show how considering silent abandonment improves the estimation of key measures of performance. To conclude, we suggest strategies to cope with the phenomena of silent abandonments.
Data-driven line balancing: bounds and optimization
We analyze the assignment of stochastic tasks to a paced multi-station line. The objective is to minimize the number of stations under a constraint on the reliability of the entire line. We present a data-driven optimization model, based on historic data of task times. We provide a proof that any deterministic lower bound on the number of stations can be transformed to a lower bound for the data-driven optimization model. The data-driven optimization model and lower bounds can be used for any distribution applying a sampling approach. We develop a bidirectional branch and bound algorithm that uses these data-driven lower bounds to solve the stochastic line balancing problem to optimality. We apply the lower bounds and the branch and bound to real data from an automotive supplier to derive the optimal task assignment for a line producing vacuum pumps. A numerical study compares the data-driven bounds to theoretical bounds known from the literature. Furthermore, extensive experiments with sampled task times show that the transformed lower bounds are often sharp and reduce the required solution time significantly.
A Data-centric View of Queueing Theory
In this talk, we will discuss three themes that arise naturally when building queueing models from observed data. First, we will discuss what the data tells us about high intensity arrival process modeling. A dominant feature in such systems is the need to address time-of-day effects explicitly. In view of this, our second theme relates to a set of approximations that are relevant to such systems. Our third and final theme is the development of numerical algorithms appropriate to the analysis of queues with non-stationary arrival processes.
(joint work with Harsha Honnappa, Alex Infanger, and Zeyu Zheng)
Variational Bayesian Methods for Stochastically Constrained System Design Problems
We study system design problems stated as parametrized stochastic programs with a chance constraint set. We adopt a Bayesian approach that requires the computation of a posterior predictive integral which is usually intractable. In addition, for the problem to be a well-defined convex program, we must retain the convexity of the feasible set. Consequently, we propose a variational Bayes-based method to approximately compute the posterior predictive integral that ensures tractability and retains the convexity of the feasible set. We present our analysis and simulations results using an M/M/c queueing model to choose the optimal number of servers c to achieve a given service level agreement.
Modelling intensive care units using quasi-birth-and-death processes
An intensive care unit (ICU) is a crucial and limited resource in a hospital which is affected by uncertainty and variability, and often operates close to capacity. Queueing theory has been used to model the bed occupancy in ICUs for the last 20 years, with a particular focus on using M/M/· and M/PH/· queueing models. These queueing models assume that the arrival process (patient arrivals) is a Poisson process, the service times (length of stay) follow an exponential or Phase-Type distribution, and most crucially that the arrival process and service times are independent of each other. However, Varney et al. showed that there is some dependence structure between the arrival process and the service times in an ICU. Without independence between the arrival process and service times, standard queueing models become invalid. We aim to provide a more principled approach to modelling bed occupancy in ICUs using quasi-birth-and-death processes (QBDs). By allowing the phases of the arrival process and the service times to interact with each other, QBDs provide the flexibility to model a queueing system with dependence between the arrival process and the service times. In this talk, we describe the approaches we have taken to develop model-fitting procedures for QBD models, with a particular focus on fitting suitable QBD models to data from an intensive care unit.
Data-Pooling in Optimization
Managing large-scale systems often involves simultaneously solving thousands of potentially unrelated stochastic optimization problems, each with limited data. Intuition suggests decoupling these unrelated problems and solving them separately. We propose a novel data-pooling algorithm that disproves this intuition and shows that combining data across problems often outperforms decoupling, even when there is no a priori structure linking the problems and data is drawn independently. Our approach does not require strong distributional assumptions and applies to constrained, possibly nonconvex optimization problems such as vehicle-routing, economic lot-sizing, or facility location. We compare and contrast our results to a similar phenomenon in statistics (James-Stein Phenomenon) and show that, unlike the classical statistical setting, the potential benefits of data-pooling, in general, depend strongly on the problem structure, and, in some cases, data-pooling offers no benefit. We prove that as the number of problems grows large, our method learns if pooling is necessary and the optimal amount to pool, even if the expected amount of data per problem is fixed and bounded. We further show that pooling offers significant benefits over decoupling when there are many problems, each of which has a small amount of relevant data. We demonstrate the practical benefits of data-pooling using real data from a chain of retail drug stores in the context of inventory management.
Paper: https://arxiv.org/abs/1906.00255
Data-driven decision making under uncertainty
We consider a class of stochastic dynamic programming (SDP) problems arising in the context of simple decision making (e.g., in the context of preventive maintenance given information on the system’s degradation). In this talk, we focus on the modelling of the heterogeneity of the population due to different exogenous (e.g., environment) and endogenous (e.g., quality) conditions and account for the effect the heterogeneity has on the decision making. To this end, it is paramount to integrate the learning of the individual degradation model (Bayesian learning to infer properties of the component’s degradation process based on its real-time degradation data) with the maintenance optimization, and to strive for cost-optimal tailored maintenance decisions on an individual system level.
From a fundamental perspective, the difficulty of such SDP problems lies in deriving the optimal policy. From a numerical perspective, the difficulty lies in computing the policy (the curse of dimensionality). While, from a practical perspective, the difficulty lies in the stochastic modelling of all the relevant information (big data). In this talk, we present an overview of results covering all three perspectives.
(joint work with Collin Drent (Eindhoven University of Technology), Melvin Drent (University of Luxembourg) and Joachim Arts (University of Luxembourg)).
Data-driven approaches to service operations management
The abundance of data and the development of algorithms capable of using this data have led to an unprecedented shift in scientific focus and funding to these new AI method.
Is our model-based approach still valid or will it soon be replaced by data-driven AI approaches? Is AI a threat to modelling or does it improve our methods and makes it stronger?
After some general thoughts and observations I will give some examples of both, from the field of service operations.
Optimal Contact Center Staffing and Scheduling with Machine Learning
A fundamental challenge in staffing and scheduling of service systems is ensuring certain quality of service (QoS) targets at minimum costs. This challenge is particularly complex when considering modern contact centers that have multi-skill agents and multi-class customers with heterogeneous arrival rates, resulting in the lack of closed-form expressions for QoS measurements and requiring simulations to accurately provide QoS expectations for staffing schedules. Simulations are computationally demanding and reliable optimization procedures cannot meet the time demands of practical use. Therefore, we show how machine learning can be used in combination with simulation to solve the integral staffing and scheduling problem for multi-skill contact centers. This has the potential to provide better solutions for an existing practical problem. In specific, we develop a machine learning framework to approximate QoS expectations by predicting simulation outcomes (offline), allowing us to quickly produce a look-up table of QoS for all candidate schedules. The QoS approximations are highly accurate (online), even when the contact center is considerably large. We then implement a simple deterministic optimization procedure to obtain schedules that can satisfy QoS targets at low costs. Using numerical experiments based on a real-life contact center scenario, we show that under reasonable time constraints our method improves upon the best schedule obtained via the stationary independent period-by-period (SIPP) model by 3.8% for the single-skill scenario, and improves upon the best schedule obtained via simulation optimization by 4.3% for the multi-skill scenario.
Lévy driven queues: the workload correlation function is positive, decreasing and convex
In this talk I will consider Lévy-driven queues, with a focus on structural properties of the workload correlation function. After having introduced the objects studied, I’ll proceed by stating the conjecture that has been around for quite a while, namely that the workload correlation is a positive, decreasing and convex function of time. As a historic account, I’ll briefly discuss the seminal contribution by Ott on the special case of the M/G/1 queue, based on exploiting properties of complete monotone functions. The same methodology has been used in the extension (by Es-Saghouani and me) to queues with spectrally positive Lévy input, whereas later (in a paper by Glynn and me) the spectrally negative case was dealt with. For a long time, there was little hope to prove the conjecture for general Lévy input (and, for that matter, for reflected random walks in discrete-time). In a recent paper (that I wrote with Berkelmans and Cichocka), we provide an elementary proof, only relying on basic properties of Lévy processes and their reflected version. Importantly, the argumentation extends to double reflection, and also covers reflected random walks. By the time of writing this abstract, Kella and I are thinking of ways to extend the results even further (and I’m rather optimistic I can present some interesting new results). I finish by exploring whether the structural properties carry over to the Markov modulated case; there we observe an interesting effect caused by the size of the state space of the modulating process.
Clustering in block Markov chains
In this talk, we will consider cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the $n$ possible states are divided into a finite number of $K$ groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. For BMCs, we have devised a clustering procedure that accurately, efficiently, and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense.
Wireless streaming on VR headsets
Virtual Reality is one of the most popular use case of emerging 5G networks. Their popularity is driven by the immersive experience they provide with the media. However, the varying nature of the radio access network has a big impact on the service quality. We study a model of caching and transmission of degree videos on these headsets and compute the impact of network variations on the Quality of Service.
Complete resource pooling of a load balancing policy for a network of battery swapping stations
In the last decade, there has been an increasing penetration of electric vehicles (EVs), which are perceived as one of the more promising solutions to reduce carbon emission of the transportation sector. Yet, the adoption of this technology remains slow, partly due to issues with long battery charging times. In this talk, we consider the concept of battery swapping stations where EV users can quickly exchange their (almost) depleted batteries by full batteries. We take a queueing perspective by modeling this framework as a closed queueing system operating in a Quality-and-Efficiency-Driven (QED) policy. This policy yields favorable effects: EV user experience low waiting times, while battery swapping stations do not needlessly keep extensively many spare batteries. Moreover, we show state-space collapse when EV users are inclined to swap their batteries at the station that is least loaded (among the stations close to the EV). In other words, all stations are approximately equally busy at all times.
Social and Monopoly Optimization in Observable Queues
Naor’s (1969) celebrated paper studies customer decisions in a canonical (M/M/1) queueing model, where upon arrival, each customer observes the queue length and chooses whether to join or to balk, assuming that joining-customers utility is linearly decreasing with their joining position. Naor shows that under monopoly pricing, the effective (filled) demand of joining customers is less than what is socially optimal, which is less than that of non-regulated equilibrium. Studies show, based on numerical observations and/or ad-hoc proof techniques, that this triangular relation is very robust, in the sense that it holds within various specific setups, where the queueing process need not be M/M/1, and/or when the utility is not linear. In this work we devise a unified approach to studying Naor’s triangular relation for general queueing processes and general utility structures. We point out properties that imply the aforementioned relation in Naor’s model and in its extensions, and suggest model applications for our findings. We further provide a simple example where the result does not hold.
Optimal Maintenance Policies Of Partially Observable Systems With Multi-sensor Observations
We consider a maintenance optimization problem for a system consisting of a partially observable monitored component and a number of unmonitored components, while allowing for economic dependencies. The monitored component is maintained according to its perceived condition, based on sensor data, and the unmonitored ones periodically. We develop optimal maintenance policies, based on real data, and show that these are threshold policies. We further investigate the effect on the optimal policy in the presence of costly multi-sensor data, bringing new insight into the application of Industry 4.0 technologies on maintenance.
A novel data-driven algorithm for the automated detection of unexpectedly high traffic flow in uncongested traffic states
We present an algorithm to identify days that exhibit the seemingly paradoxical behavior of high traffic flow and, simultaneously, a striking absence of traffic jams, such days we name high-performance days. The developed algorithm consists of three steps: step 1, based on the fundamental diagram (i.e. an empirical relation between the traffic flow and traffic density), we estimate the critical speed; step 2, based on a labelling of the data, the breakdown probability can be estimated (i.e. the probability that the average speed drops below the critical speed); step 3, we identify unperturbed moments (i.e. moments when a breakdown is expected, but does not occur) and subsequently identify the high-performance days based on the number of unperturbed moments.
The algorithm relies on a novel approach to estimate the critical speed; we exploit the roughly linear relation between traffic flow and traffic density in case of no congestion using robust regression as a tool for labelling. In addition, we introduce the notion of high-performance days. Identifying high-performance days could be a building block in the quest for traffic jam reduction; using more detailed data one might be able to identify specific characteristics of high-performance days.
The algorithm is applied to a case study featuring the highly congested A15 motorway in the Netherlands.
Excursions of max-weight dynamics
We provide a new perspective into the structural properties of the celebrated max-weight policy, a much studied centerpiece within the field of stochastic network scheduling. We argue that the deterministic max-weight dynamics have a key property: the effects of input (arrival) fluctuations on state trajectories are bounded by a constant multiple of the fluctuations of the cumulative arrival process. This fact, in conjunction with concentration assumptions on the arrival process, provides a new machinery for deriving old and new limiting results, e.g., on fluid limits or state space collapse.
(joint work with A. Sharifnassab and S. J. Golestani)
Harnessing the Double-edged Sword via Routing: Information Provision on Ride-hailing Platforms
We consider a ride-hailing platform that provides free information to taxi drivers. Upon receiving a rider’s request, the platform broadcasts the rider’s origin and destination to idle drivers, who accept or ignore the request depending on the profitability considerations. We show that providing such information may reduce drivers’ equilibrium profit. Hence information provision is a double-edged sword: the drivers may choose to take more profitable riders via “strategic idling”. When multiple drivers compete for the same request, how the platform breaks the tie affects the incentives of the drivers. We propose a routing policy that can align the incentives and achieve the first-best outcome for large systems.
Minimizing delay in distributed service systems with redundancy and random slowdowns
We consider a distributed service system consisting of N servers with infinite capacity FIFO queues, where each server can experience random slowdowns in its processing rate. Incoming jobs consist of K identical tasks that can be executed in parallel, and that can be encoded into any number of at least K “replicas” of the same size (by introducing redundancy) so that a job is considered to be completed when any K replicas associated with it finish their service.
In this setting, our objective is to understand the best possible delay performance of such systems and to propose optimal policies, with emphasis on the asymptotic regime when N is large. In particular, we consider a broad family of control policies, which includes most policies considered in the literature, and work towards characterizing the fundamental structure of optimal policies under two different models for the slowdowns: one where the slowdowns are independent of the job sizes, and a new one where slowdowns depend on the job size.
Registration
We have reached the maximum capacity of participants. The registration is closed. Should you want to be placed on a waiting list, please email Patty Koorn (koorn@eurandom.tue.nl)
Practical Information
Information on travel, location etc. : INFORMATION