Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T17:12:40.412Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Markov processes Special 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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
Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 1 , March 2017 , pp. 182 - 220
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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