Performance Approximation and Scheduling Control for Large-Scale Queueing Systems

Yu, Lun

doi:https://doi.org/10.21985/n2-frtt-jh19

Work

Performance Approximation and Scheduling Control for Large-Scale Queueing Systems

Public

Download PDF

The thesis is concerned with the design and control of large-scaled queueing systems that are operated under heavy traffic, focusing on the following two research questions: For a given queueing system, how to find a proper heavy-traffic limit that accurately approximates various performance metrics? For multi-class queueing systems, how to dynamically prioritize different classes of customers, so that the system is operated with the highest efficiency? The answer to either question depends on more detailed characterization of the system, and the goal of this thesis is to answer the questions for three specific queueing systems, all motivated by industrial practice. First, motivated by emergency departments, I consider a priority queueing system with two customer classes; the first class (of “high acuity”) requires long service times and receives priority over the second class (“low acuity”), whose average service times are substantially shorter. For a heavy-traffic analysis, I propose a Fluid-Diffusion Hybrid limit to approximate the two queues, and demonstrate how it can be employed to study the benefits of de-pooling (namely, of having a “fast-track”). As a separate future research project, I also consider the optimal scheduling problem in the FDH regime. Second, I consider a finite-horizon scheduling problem for a queueing system with two classes of impatient customers. The queueing system is a clearing system with a large queue at time 0, but also new arrivals that match the system capacity. The goal is to find the optimal scheduling policy that minimizes a linear holding and abandonment cost, up to the time when the queue is cleared. Based on a fluid approximation, I show asymptotic optimality of a static priority policy, where the optimality holds for systems with any number of servers. We also analyze the effect of preemption and generalize the asymptotic optimality to systems with more than two customer classes. Finally, I consider a single-class queueing system staffed according to the square-root rule, such that customers' patience time is perfectly correlated to their service requirements. We prove that the diffusion limit of such a system behaves as if all customers have infinite patience time. Moreover, the system exhibits an asymmetric behavior of its steady-state queue lengths when the traffic intensity is close to its critical value 1: When the traffic intensity approaches 1 from below, the stationary queue length grows in the square-root order; When the traffic intensity approaches 1 from above, the stationary queue length grows in a novel three-fourth order. To capture the convergence to the steady-state, I also develop a novel lower-order fluid limit, which includes both a space scaling and a time scaling.

Creator