This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Mandelbaum, A. Articles by Momcilovic, P. Search for Related Content

Queues with Many Servers: The Virtual Waiting-Time Process in the QED Regime

Avishai Mandelbaum, Petar Momilovi

Industrial Engineering and Management, Technion, Haifa 3200, Israel
Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109
avim{at}tx.technion.ac.il
petar{at}eecs.umich.edu

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 (Efficiency-Driven) while waiting time is (Quality-Driven). This is equivalent to having the number of servers N being approximately equal to , where R is the offered load and β is a positive constant.

For the G/D_K/N queue in the QED regime, we analyze the virtual waiting time V_N(t), as N increases indefinitely. Assuming that the service-time distribution has a finite support (hence the D_K in G/D_K/N), it is shown that, in the limit, the scaled virtual waiting time is representable as a supremum over a random weighted tree (S denotes a service time). Informally, it is then argued that, for large N,

here is the averaging of over S, and the process is zero-mean Gaussian that summarizes all relevant information about arrivals and service times ( arises as a limit of an infinite-server (G/D_K/) 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.

Key Words: multiserver queue; heavy-traffic; quality- and efficiency-driven (QED) or Halfin–Whitt regime; economies of scale; telephone call or contact centers
History: Received: August 30, 2005; revision received: August 29, 2007;