Hostname: page-component-74656f9884-54qdv Total loading time: 0 Render date: 2026-11-10T13:25:12.973Z Has data issue: false hasContentIssue false
  • English
  • Français

A unified approach for large queue asymptotics in a heterogeneous multiserver queue

Part of: Special processes Markov processes

Published online by Cambridge University Press:  17 March 2017

Masakiyo Miyazawa
Masakiyo Miyazawa*
Affiliation:
Tokyo University of Science
*
* Postal address: Department of Information Sciences, Tokyo University of Science, 2641 Yamazaki, Noda, Chiba 278-8510, Japan. Email address: miyazawa@rs.tus.ac.jp
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 are interested in a large queue in a GI/G/k queue with heterogeneous servers. For this, we consider tail asymptotics and weak limit approximations for the stationary distribution of its queue length process in continuous time under a stability condition. Here, two weak limit approximations are considered. One is when the variances of the interarrival and/or service times are bounded, and the other is when they become large. Both require a heavy-traffic condition. Tail asymptotics and heavy-traffic approximations have been separately studied in the literature. We develop a unified approach based on a martingale produced by a good test function for a Markov process to answer both problems.

Keywords

Piecewise-deterministic Markov processmartingaleheterogeneous serverqueue length processstationary distributiontail asymptoticslarge varianceheavy-traffic approximation

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60J27: Continuous-time Markov processes on discrete state spaces 60K37: Processes in random environments

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 1 , March 2017 , pp. 182 - 220
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Alsmeyer, G. (1996).The ladder variables of a Markov random walk.Tech. Rep., University of Münster.Google Scholar
[2] Alsmeyer, G. (1997).The Markov renewal theorem and related results.Markov Process. Relat. Fields 3,103–127.Google Scholar
[3] Asmussen, S. (2003).Applied Probability and Queues(Appl. Math. 51),2nd edn.Springer,New York.Google Scholar
[4] Braverman, A.,Dai, J. and Miyazawa, M. (2015).Heavy traffic approximation for the stationary distribution of a generalized Jackson network: the BAR approach.Submitted.Google Scholar
[5] Chen, H. and Ye, H.-Q. (2011).Methods in diffusion approximation for multi-server system: sandwich, uniform attraction and state-space collapse.In Queueing Networks(Internat. Ser. Operat. Res. Manag. Sci. 154),Springer,New York,pp.489–530.Google Scholar
[6] Dai, J. G. (1995).On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models.Ann. Appl. Prob. 5,49–77.CrossRefGoogle Scholar
[7] Davis, M. H. A. (1976).The representation of martingales of jump processes.SIAM J. Control Optimization 14,623–638.CrossRefGoogle Scholar
[8] Davis, M. H. A. (1984).Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models.J. R. Statist. Soc. B 46,353–388.Google Scholar
[9] Davis, M. H. A. (1993).Markov Models and Optimization(Monogr. Statist. Appl. Prob. 49).Chapman and Hall,London.Google Scholar
[10] Dembo, A. and Zeitouni, O. (1998).Large Deviations Techniques and Applications(Appl. Math. 38),2nd edn.Springer,New York.Google Scholar
[11] Ethier, S. N. and Kurtz, T. G. (1986).Markov Processes: Characterization and Convergence.John Wiley,New York.Google Scholar
[12] Foss, S. and Korshunov, D. (2012).On large delays in multi-server queues with heavy tails.Math. Operat. Res. 37,201–218.Google Scholar
[13] Glynn, P. and Whitt, W. (1994).Logarithmic asymptotics for steady-state tail probabilities in a single-server queue.J. Appl. Prob. 31,131–156.Google Scholar
[14] Halfin, S. and Whitt, W. (1981).Heavy-traffic limits for queues with many exponential servers.Operat. Res. 29,567–588.Google Scholar
[15] Jacod, J. and Shiryaev, A. N. (2003).Limit Theorems for Stochastic Processes,2nd edn.Springer,Berlin.Google Scholar
[16] Kingman, J. F. C. (1962).On queues in heavy traffic.J. R. Statist. Soc. B 24,383–392.Google Scholar
[17] Kobayashi, M. and Miyazawa, M. (2012).Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions.In Matrix-Analytic Methods in Stochastic Models,eds G. Latouche et al.,Springer,New York,pp.147–181.Google Scholar
[18] Kobayashi, M. and Miyazawa, M. (2014).Tail asymptotics of the stationary distribution of a two dimensional reflecting random walk with unbounded upward jumps.Adv. Appl. Prob. 46,365–399.Google Scholar
[19] Köllerström, J. (1974).Heavy traffic theory for queues with several servers. I.J. Appl. Prob. 11,544–552.Google Scholar
[20] Miyazawa, M. (2011).Light tail asymptotics in multidimensional reflecting processes for queueing networks.TOP 19,233–299.Google Scholar
[21] Miyazawa, M. (2015).Diffusion approximation for stationary analysis of queues and their networks: a review.J. Operat. Res. Soc. Japan 58,104–148.Google Scholar
[22] Miyazawa, M. (2015).A superharmonic vector for a nonnegative matrix with QBD block structure and its application to a Markov-modulated two-dimensional reflecting process.Queueing Systems 81,1–48.Google Scholar
[23] Miyazawa, M. (2016).A unified approach for large queue asymptotics in a heterogeneous multiserver queue.Preprint. Available at https://arxiv.org/abs/1510.01034v5.Google Scholar
[24] Miyazawa, M. and Zwart, B. (2012).Wiener-Hopf factorizations for a multidimensional Markov additive process and their applications to reflected processes.Stochastic Systems 2,67–114.Google Scholar
[25] Neuts, M. and Takahashi, Y. (1981).Asymptotic behavior of the stationary distributions in the GI/PH/c queue with heterogeneous servers.Z. Wahrscheinlichkeitsth. 57,441–452.Google Scholar
[26] Palmowski, Z. and Rolski, T. (2002).A technique of the exponential change of measure for Markov processes.Bernoulli 8,767–785.Google Scholar
[27] Reed, J. (2009).The G/GI/N queue in the Halfin‒Whitt regime.Ann. Appl. Prob. 19,2211–2269.Google Scholar
[28] Reiman, M. I. (1984).Open queueing networks in heavy traffic.Math. Operat. Res. 9,441–458.Google Scholar
[29] Sadowsky, J. (1995).The probability of large queue lengths and waiting times in a heterogeneous multiserver queue. II. Positive recurrence and logarithmic limits.Adv. Appl. Prob. 27,567–583.Google Scholar
[30] Sadowsky, J. and Szpankowski, W. (1995).The probability of large queue lengths and waiting times in a heterogeneous multiserver queue. I. Tight limits.Adv. Appl. Prob. 27,532–566.Google Scholar
[31] Sakuma, Y. (2011).Asymptotic behavior for MArP/PH/2 queue with join the shortest queue discipline.J. Operat. Res. Soc. Japan 54,46–64.Google Scholar