Multiclass Queueing Networks with Time-Varying Arrivals: Performance Approximations and Staffing Design

This thesis aims to help improve the capacity planning and operational control for large-scale service systems, such as call centers, healthcare systems, financial services, and manufacturing systems. On the one hand, this thesis will develop effective algorithms to compute useful performance measure estimators, which can be used for forecasting; on the other hand, this thesis will develop appropriate staffing levels for service networks in the face of time-varying demand, so that desired service-level indicators, such as the expected waiting time and tail probability of delay, can be controlled at customary targets.;This thesis considers queueing models with realistic features of real-world service systems, including (i) time-varying demand; (ii) time-varying staffing levels; (iii) abandonment from impatient customers; (iv) nonexponential distributions; and (v) complicated network structure. Despite the immense queueing-theory literature, the model complexity of all five features makes exact analysis far beyond existing methods. Thus it is appropriate to seek effective approximations. Recently developed many-server heavy-traffic limit theorems will be adopted as important building blocks for the main methods of this thesis.;This thesis consists of four pieces of work. In the first one (Chapter 2), analytic formulas are developed to set the time-dependent number of servers in order to stabilize performance for the Gt/GI/s t+GI queueing model, which has a nonstationary non-Poisson arrival process (the Gt), nonexponential service times (the first GI), and allows customer abandonment according to a nonexponential patience distribution (the +GI). Specifically, for any delay target w > 0 and alpha∈ (0; 1), appropriate staffing levels are determined (thestt) so that the time-varying probability that the waiting time exceeds a maximum acceptable value w is stabilized at alpha at all times. In addition, effective approximating formulas are provided for other important performance functions such as the probability of abandonment and the mean queue length. Many-server heavy-traffic limit theorems are developed to show that the proposed staffing function achieves the goal asymptotically as the scale increases. Simulations show that both the staffing functions and the performance approximations are effective, even for smaller systems having around 3 servers.;The second work (Chapter 3) develops deterministic fluid approximations for the multiclass multistation queueing networks with time-varying arrival rates and staffing levels, nonexponential patience and service times, and realistic routing policies. Unlike the traditional Markovian routing (such as in the classical Jackson network), customers are routed according to their own service paths (based on their unique service requirements) inside the network. An efficient algorithm is provided to compute all standard performance functions. The third work (Chapter 4) develops algorithms to set appropriate staffing levels to stabilize the performance for the multiclass multistation network studied in Chapter 3. The goal is to staff the network optimally such that the expected delay can be stabilized at the desired quality-of-service target at each queue, aiming at eliminating the time-varying effect of the arrivals. Simulation experiments verify the effectiveness of both the fluid approximation and the staffing methods.;In the last work (Chapter 5), we continue to develop effective staffing recommendations for nonstationary systems, extending the Poisson arrival assumption to non-Poisson arrivals. We study two staffing methods to achieve time-stable performance in the Gt/GI/st. The first is the generalized square-root staffing formula proposed by Jennings et al. in 1996, which we implement and test for the first time here. The second is a modified offered load approximation, using the diffusion approximation proposed by Whitt in 2004. We show that both methods achieve satisfactory performance by stabilizing the probability of delay at a desired target 0 < alpha < 0.5.