Steady-state $GI/GI/n$ queue in the Halfin-Whitt Regime

Stochastics Seminar
Thursday, September 29, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 006
ISyE, Georgia Tech
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.