Georgia Institute of Technology College of Sciences

In this talk, we resolve several questions related to a certain heavy traffic scaling regime (Halfin-Whitt) for parallel server queues, a family of stochastic models which arise in the analysis of service systems. In particular, we show that the steady-state queue length scales like $O(\sqrt{n})$, and bound the large deviations behavior of the limiting steady-state queue length. We prove that our bounds are tight for the case of Poisson arrivals. We also derive the first non-trivial bounds for the steady-state probability that an arriving customer has to wait for service under this scaling. Our bounds are of a structural nature, hold for all $n$ and all times $t \geq 0$, and have intuitive closed-form representations as the suprema of certain natural processes. Our upper and lower bounds also exhibit a certain duality relationship, and exemplify a general methodology which may be useful for analyzing a variety of stochastic models. The first part of the talk is joint work with David Gamarnik.