Queues with many servers: The virtual waiting-time process in the QED regime Academic Article uri icon


  • We consider a first-come first-served multiserver queue in the Quality- and Efficiency-Driven (QED) regime. In this regime, which was first formalized by Halfin and Whitt, the number of servers N is not small, servers' utilization is [Formula: see text] (Efficiency-Driven) while waiting time is [Formula: see text] (Quality-Driven). This is equivalent to having the number of servers N being approximately equal to [Formula: see text], where R is the offered load and is a positive constant. For the G/DK/N queue in the QED regime, we analyze the virtual waiting time VN(t), as N increases indefinitely. Assuming that the service-time distribution has a finite support (hence the DK in G/DK/N), it is shown that, in the limit, the scaled virtual waiting time [Formula: see text] is representable as a supremum over a random weighted tree (S denotes a service time). Informally, it is then argued that, for large N, [Formula: see text]here [Formula: see text] is the averaging of [Formula: see text] over S, and the process [Formula: see text] is zero-mean Gaussian that summarizes all relevant information about arrivals and service times ([Formula: see text] arises as a limit of an infinite-server (G/DK/) process, appropriately scaled). The results are obtained by using both combinatorial and probabilistic arguments. Possible applications of our approximations include fast simulation of queues and estimation/prediction of customer waiting times in the QED regime.

published proceedings


author list (cited authors)

  • Mandelbaum, A., & Momcilovic, P.

citation count

  • 25

complete list of authors

  • Mandelbaum, Avishai||Momcilovic, Petar

publication date

  • January 2008