Scalable analysis and design of service systems

Abstract

In this dissertation, we develop analytical and computational tools for performance analysis and design of large-scale service systems. The dissertation consists of three main chapters.

The first chapter is devoted to devising efficient task assignment policies for large-scale service system models from a rare event analysis standpoint. Specifically, we study the steady-state behavior of multi-server queues with general job size distributions under size-interval task assignment (SITA) policies. Assuming Poisson arrivals and the existence of the alpha-th moment of the job size distribution for some alpha> 1, we show that if the job arrival rate and the number of servers increase to infinity with the traffic intensity held fixed, a SITA policy parameterized by alpha minimizes in a large deviation sense the steady-state probability that the total number of jobs in the system is greater than or equal to the number of servers. The optimal large deviation decay rate can be arbitrarily close to the one for the corresponding probability in an infinite-server queue, which only depends on the system traffic intensity but not on any higher moments of the job size distribution. This supports in a many-server asymptotic framework the common wisdom that separating large jobs from small jobs protects system performance against job size variability.

In the second chapter, we study constraint satisfaction problems for a Markovian parallel-server queueing model with impatient customers, motivated by large telephone call centers. To minimize the staffing level subject to different service-level constraints, we propose refined square-root staffing (SRS) rules, which preserve the insightfulness and computational scalability of the celebrated SRS principle and yet achieve a stronger form of optimality. In particular, using asymptotic series expansion techniques, we first develop refinements to a set of asymptotic performance approximations recently used in analyzing large call centers, namely, the Quality and Efficiency Driven (QED) diffusion approximations. We then use the improved performance approximations to explicitly characterize the error of conventional SRS and further obtain the refined SRS rules. Finally, we demonstrate how the explicit form of the staffing refinements enables an analytical assessment of the accuracy of conventional SRS and its underlying QED approximation.

In the third chapter, we study a fluid model for many-server Markovian queues in changing environments, which can be used to model large-scale service systems with customer abandonments and time-varying arrivals. We obtain the stationary distribution of the fluid model, which refines and is shown to converge, as the environment changing rate vanishes in a proper way, to a simple discrete bimodal approximation. We also prove that the fluid model arises as a law of large number limit in a many-server asymptotic regime.