Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T14:46:13.026Z Has data issue: false hasContentIssue false
  • English
  • Français

A comparative analysis of the successive lumping and the lattice path counting algorithms

Published online by Cambridge University Press:  24 March 2016

Michael N. Katehakis ,
Laurens C. Smit  and
Floske M. Spieksma
Laurens C. Smit
Affiliation:
Mathematisch Instituut, Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands. Email address: lsmit@math.leidenuniv.nl
Floske M. Spieksma
Affiliation:
Mathematisch Instituut, Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands. Email address: spieksma@math.leidenuniv.nl
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper provides a comparison of the successive lumping (SL) methodology developed in Katehakis et al. (2015) with the popular lattice path counting (Mohanty (1979)) in obtaining rate matrices for queueing models, satisfying the specific quasi birth and death structure as in Van Leeuwaarden et al. (2009) and Van Leeuwaarden and Winands (2006). The two methodologies are compared both in terms of applicability requirements and numerical complexity by analyzing their performance for the same classical queueing models considered in Van Leeuwaarden et al. (2009). The main findings are threefold. First, when both methods are applicable, the SL-based algorithms outperform the lattice path counting algorithm (LPCA). Second, there are important classes of problems (for example, models with (level) nonhomogenous rates or with finite state spaces) for which the SL methodology is applicable and for which the LPCA cannot be used. Third, another main advantage of SL algorithms over lattice path counting is that the former includes a method to compute the steady state distribution using this rate matrix.

Keywords

Steady state analysisqueueingsuccessive lumping
Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 1 , March 2016 , pp. 106 - 120
Copyright
Copyright © Applied Probability Trust 2016 

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]Adan, I., Economou, A. and Kapodistria, S. (2009). Synchronized reneging in queueing systems with vacations. Queueing Systems 62, 1–33. Google Scholar
[2]Adan, I. J. B. F., Kapodistria, S. and van Leeuwaarden, J. S. H. (2013). Erlang arrivals joining the shorter queue. Queueing Systems 74, 273–302. Google Scholar
[3]Adan, I. J. B. F., Boxma, O. J., Kapodistria, S. and Kulkarni, V. G. (2015). The shorter queue polling model. To appear in Ann. Operat. Res.Google Scholar
[4]Bini, D. A., Meini, B., Steffé, S. and Van Houdt, B. (2006). Structured Markov chains solver: software tools. In SMCTOOLS (Pisa, Italy, October 2006), ACM, New York, 10pp. Google Scholar
[5]Böhm, W., Krinik, A. and Mohanty, S. G. (1997). The combinatorics of birth–death processes and applications to queues. Queueing Systems Theory Appl. 26, 255–267. Google Scholar
[6]Bright, L. and Taylor, P. G. (1995). Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Commun. Statist. Stoch. Models 11, 497–525. Google Scholar
[7]Eisenblätter, A.et al. (2003). Modelling feasible network configurations for UMTS. In Telecommunications Network Design and Management, Springer, New York, pp. 1–23. Google Scholar
[8]Ertiningsih, D., Katehakis, M., Smit, L. and Spieksma, F. (2015). QSF processes with level product form stationary distributions. Submitted. Google Scholar
[9]Etessami, K., Wojtczak, D. and Yannakakis, M. (2010). Quasi-birth–death processes, tree-like QBDs, probabilistic 1-counter automata, and pushdown systems. Performance Evaluation 67, 837–857. Google Scholar
[10]Flajolet, P. and Guillemin, F. (2000). The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions. Adv. Appl. Prob. 32, 750–778. Google Scholar
[11]Gillent, F. and Latouche, G. (1983). Semi-explicit solutions for M/PH/1-like queuing systems. Europ. J. Operat. Res. 13, 151–160. Google Scholar
[12]Hager, W. W. (1989). Updating the inverse of a matrix. SIAM Rev. 31, 221–239. Google Scholar
[13]Heinig, G. and Rost, K. (1984). Algebraic Methods for Toeplitz-Like Matrices and Operators. Birkhäuser, Basel. Google Scholar
[14]Katehakis, M. N. and Derman, C. (1989). On the maintenance of systems composed of highly reliable components. Manag. Sci. 35, 551–560. CrossRefGoogle Scholar
[15]Katehakis, M. N. and Melolidakis, C. (1988). Dynamic repair allocation for a k-out-of-n system maintained by distinguishable repairmen. Prob. Eng. Inf. Sci. 2, 51–62. Google Scholar
[16]Katehakis, M. N. and Smit, L. C. (2012). A successive lumping procedure for a class of Markov chains. Prob. Eng. Inf. Sci. 26, 483–508. CrossRefGoogle Scholar
[17]Katehakis, M. N. and Smit, L. C. (2012). On computing optimal (Q, r) replenishment policies under quantity discounts. Ann. Operat. Res. 200, 279–298. CrossRefGoogle Scholar
[18]Katehakis, M., Smit, L. and Spieksma, F. (2014). A solution to a countable system of equations arising in stochastic processes. Submitted. Google Scholar
[19]Katehakis, M. N., Smit, L. C. and Spieksma, F. M. (2015). DES and RES processes and their explicit solutions. Prob. Eng. Inf. Sci. 29, 191–217. Google Scholar
[20]Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM, Philadelphia, PA. Google Scholar
[21]Liu, D. and Zhao, Y. Q. (1997). Determination of explicit solutions for a general class of Markov processes. In Matrix-Analytic Methods in Stochastic Models (Lecture Notes Pure Appl. Math. 183), Dekker, New York, pp. 343–358. Google Scholar
[22]Mohanty, S. G. (1979). Lattice Path Counting and Applications. Academic Press, New York. Google Scholar
[23]Mohanty, S. G. and Panny, W. (1990). A discrete-time analogue of the M/M/1 queue and the transient solution: a geometric approach. Sankhyā A 52, 364–370. Google Scholar
[24]Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD. Google Scholar
[25]Perros, H. G. (1994). Queueing Networks with Blocking. Oxford University Press, Google Scholar
[26]Spitzer, F. (2001). Principles of Random Walk (Graduate Texts Math. 34), 2nd edn. Springer, New York. Google Scholar
[27]Ulukus, M. Y., Güllü, R. and Örmeci, L. (2011). Admission and termination control of a two class loss system. Stoch. Models 27, 2–25. CrossRefGoogle Scholar
[28]Van Houdt, B. and van Leeuwaarden, J. S. H. (2011). Triangular M/G/1-type and tree-like quasi-birth–death Markov chains. INFORMS J. Comput. 23, 165–171. CrossRefGoogle Scholar
[29]Van Leeuwaarden, J. S. H. and Winands, E. M. M. (2006). Quasi-birth-and-death processes with an explicit rate matrix. Stoch. Models 22, 77–98. Google Scholar
[30]Van Leeuwaarden, J. S. H., Squillante, M. S. and Winands, E. M. M. (2009). Quasi-birth-and-death processes, lattice path counting, and hypergeometric functions. J. Appl. Prob. 46, 507–520. CrossRefGoogle Scholar
[31]Vlasiou, M., Zhang, J. and Zwart, B. (2014). Insensitivity of proportional fairness in critically loaded bandwidth sharing networks. Preprint. Available at http://arxiv.org/abs/1411.4841. Google Scholar
[32]Williams, V. V. (2012). Multiplying matrices faster than Coppersmith–Winograd. In STOC '12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, pp. 887–898. Google Scholar
[33]Woodbury, M. A. (1950). Inverting modified matrices. Memo. Rep. 42, Statistical Research Group, Princeton University. Google Scholar
[34]Zhao, Y. Q. and Grassmann, W. K. (1995). Queueing analysis of a jockeying model. Operat. Res. 43, 520–529. Google Scholar
[35]Zheng, Y.-S. and Zipkin, P. (1990). A queueing model to analyze the value of centralized inventory information. Operat. Res. 38, 296–307. Google Scholar