Asymptotic Analysis of Queueing Systems under Uncertainty

Queueing theory is a branch of applied probability and operations research that studies waiting lines. The research in this field is well-motivated by real-life applications where resources can be allocated based on predicted waiting times, for example in call centers, health care, and cloud computing. Traditionally, in controlled queueing problems, it is assumed that the parameters of the underlying random models are known. In this project, the investigator will account for uncertainty by assuming the more realistic case where the parameters of the model are unknown. The project will generate policies that are easy to implement and broadly applicable for queueing network models under uncertainty, which will lead to better performance and resource utilization. Moreover, the project aims to develop new mathematical tools and techniques for these problems. The models in this project stem from real-world problems and the results will impact both applied probability and operations research. This research project will support under-represented minority groups and train both graduate and undergraduate students.

This research project is on the asymptotic analysis of controlled queueing systems under heavy traffic with uncertainty about the parameters of the model. Two types of uncertainty are considered: Knightian and Bayesian. In the Knightian case, the decision-maker considers a worst-case criterion to be minimized by taking into account a class of models. The asymptotic analysis is performed using a limiting stochastic game, where the involved players are the decision-maker and an adversary player. In the Bayesian case, the decision-maker has a prior belief on the parameters of the model, which is continuously updated by observing the system. Here, the learning aspect of the optimization problems is of interest. The exploration/exploitation nature suggests a connection to multi-armed bandit problems. The research objectives are: (1) to develop a comprehensive theoretical framework that builds uncertainty about the queueing models into the diffusion scaling heavy traffic regime, balancing between capturing uncertainty and robustness, and attaining easy-to-implement policies; (2) to consider simple policies, which are known to be asymptotic optimal in the case without uncertainty, and to examine their performance under uncertainty; and (3) to combine the following streams of research: queueing theory, diffusion approximations, uncertainty, and learning, and moreover, to develop new mathematical results beyond what is known in each stream considered separately.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.