Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T02:30:50.370Z Has data issue: false hasContentIssue false
  • English
  • Français

Heavy-Traffic Limits for Nearly Deterministic Queues

Part of: Operations research and management science Special processes Limit theorems

Published online by Cambridge University Press:  14 July 2016

Karl Sigman  and
Ward Whitt
Karl Sigman*
Affiliation:
Columbia University
Ward Whitt*
Affiliation:
Columbia University
*
∗ Postal address: Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027-6699, USA.
∗ Postal address: Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027-6699, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We establish heavy-traffic limits for nearly deterministic queues, such as the G/D/n many-server queue. Since waiting times before starting service in the G/D/n queue are equivalent to waiting times in an associated Gn /D/1 model, where the Gn interarrival times are the sum of n consecutive interarrival times in the original model, we focus on the Gn /D/1 model and the generalization to Gn /Gn /1, where ‘cyclic thinning’ is applied to both the arrival and service processes. We establish different limits in two cases: (i) when (1 − ρn )√n → β as n → ∞ and (ii) when (1 − ρn )n → β as n → ∞, where ρn is the traffic intensity in model n. The nearly deterministic feature leads to interesting nonstandard scaling.

Keywords

Heavy trafficnearly deterministic queueErlang queuemany-server queuedeterministic service timeGaussian random walkcyclic thinningfunctional central limit theoreminvariance principle

MSC classification

Secondary: 60K25: Queueing theory 60F17: Functional limit theorems; invariance principles 90B22: Queues and service
Type
Research Papers
Information
Journal of Applied Probability , Volume 48 , Issue 3 , September 2011 , pp. 657 - 678
Copyright
Copyright © Applied Probability Trust 2011 

References

[1] Abate, J., Choudhury, G. L. and Whitt, W. (1993). Calculation of the GI/G/1 steady-state waiting-time distribution and its cumulants from Pollaczek's formula. Internat. J. Electronics Commun. 47, 311–321.Google Scholar
[2] Asmussen, S. (2003). Applied Probability and Queues, 2nd edn. Springer, New York.Google Scholar
[3] Billingsley, P. (1999). Convergence of Probability Measures, 2nd edn. John Wiley, New York.Google Scholar
[4] Borovkov, A. A. (1984). Asymptotic Methods in Queuing Theory. John Wiley, Chichester.Google Scholar
[5] Glynn, P. W. and Whitt, W. (1991). A new view of the heavy-traffic limit theorem for the infinite-server queue. Adv. Appl. Prob. 23, 188–209.Google Scholar
[6] Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Operat. Res. 29, 567–588.Google Scholar
[7] Jelenkovic, P., Mandelbaum, A. and Momcilović, P. (2004). Heavy traffic limits for queues with many deterministic servers. Queueing Systems 47, 53–69.Google Scholar
[8] Kingman, J. F. C. (1961). The single-server queue in heavy traffic. Proc. Camb. Phil. Soc. 57, 902–904.Google Scholar
[9] Liu, Y. and Whitt, W. (2011). Nearly periodic behavior in the overloaded G/D/S+GI queue. Stoch. Systems 1, 71pp.Google Scholar
[10] Pang, G., Talreja, R. and Whitt, W. (2007). Martingale proofs of many-server heavy-traffic limits for Markovian queues. Prob. Surveys 4, 193–267.Google Scholar
[11] Sigman, K. and Whitt, W. (2011). Heavy-traffic limits for nearly deterministic queues: stationary distributions. To appear in Queueing Systems.Google Scholar
[12] Song, J.-S. and Zipkin, P. H. (1996). The Joint effect of leadtime variance and lot size in a parallel processing environment. Manag. Sci. 42, 1352–1363.Google Scholar
[13] Tijms, H. C. (1994). Stochastic Models. John Wiley, Chichester.Google Scholar
[14] Whitt, W. (2002). Stochastic-Process Limits. Springer, New York.Google Scholar