Essays on Heavy-Traffic Approximations for Many-Server Queueing Systems

Heavy-traffic limit theorems have proven to be very useful in approximating the dynamics of queueing systems. They allow one to derive simple formulas for queueing performance measures for queueing systems that are not amenable to exact analysis. This thesis consists of three pieces of work on heavy-traffic approximations for large-scale queueing systems. In the first two we establish heavy-traffic stochastic-process limit theorems for infinite server (G/GI/infinity) queues and many-server queues with abandonment. In the third we approximate more complicated, multi-class many-server queueing systems by deterministic fluid models without formally proving supporting limit theorems. We first study the G/GI/infinity queue from two different perspectives in the same heavy-traffic regime. We focus separately on one measure-valued process that keeps track of the age of each customer in the system and another that keeps track of the residual service time of each customers in the system. In both cases, we find that our diffusion limits may be characterized as distribution-valued Ornstein-Uhlenbeck processes. Further, we show how these diffusion limits can be analyzed using standard results from the theory of Markov processes. In our second study, we establish heavy-traffic limits for waiting times in many-server queues with customer abandonment. If the system is asymptotically critically loaded, as in the quality-and-efficiency-driven (QED) regime, then a bounding argument shows that the abandonment does not affect waiting-time processes. If system is overloaded, as in the efficiency-driven (ED) regime, we treat customer abandonment by studying the limiting behavior of the queueing models with arrivals turned off at some time t. Then, the waiting time of an infinitely patient customer arriving at time t is the additional time it takes for the queue to empty. To prove stochastic-process limits for virtual waiting times, we establish a two-parameter version of Puhalskii's invariance principle for first passage times. In our third study, which was motivated by tenant assignment in public housing, we analyze approximating deterministic fluid models for overloaded queueing systems having multiple customer classes (classes of tenants) and multiple service pools (housing authorities), each with many servers (housing units). Customer abandonment acts to keep the system stable, yielding a proper steady-state description. In order to treat customers as fairly as possible, we assume that customers are selected for service by newly available servers on a first-come first-served (FCFS) basis from all classes the corresponding service pools are allowed to serve. It is then challenging to determine stationary routing flow rates between customer classes and service pools. Given those routing flow rates, each single fluid queue can be analyzed separately using previously established methods. Our ability to determine the routing flow rates depends on the structure of the network routing graph. We obtain the desired routing flow rates in three cases: when the routing graph is (i) a tree, (ii) complete bipartite, and (iii) an appropriate combination of the previous two cases.