Academic Commons


Heavy-traffic extreme-value limits for queues

Glynn, Peter W.; Whitt, Ward

We consider the maximum waiting time among the first n customers in the GI/G/1 queue. We use strong approximations to prove, under regularity conditions, convergence of the normalized maximum wait to the Gumbel extreme-value distribution when the traffic intensity ρ approaches 1 from below and n approaches infinity at a suitable rate. The normalization depends on the interarrival-time and service-time distributions only through their first two moments, corresponding to the iterated limit in which first ρ approaches 1 and then n approaches infinity. We need n to approach infinity sufficiently fast so that n ( 1 − ρ )2 → ∞. We also need n to approach infinity sufficiently slowly: If the service time has a pth moment for ρ > 2, then it suffices for ( 1 − ρ ) n 1 / p to remain bounded; if the service time has a finite moment generating function, then it suffices to have ( 1 − ρ ) log n → 0. This limit can hold even when the normalized maximum waiting time fails to converge to the Gumbel distribution as n → ∞ for each fixed ρ. Similar limits hold for the queue length process.


Also Published In

Operations Research Letters

More About This Work

Academic Units
Industrial Engineering and Operations Research
Published Here
September 19, 2017
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.