Algorithmic analysis of the BMAP/D/\(k\) system in discrete time. (English) Zbl 1044.60087

The paper considers a queueing system in discrete time which consists of \(k\) identical servers that serve in parallel. The service times are constant of duration \(d\) units, \(d\geq 1\). The input flow is given by a batch Markovian arrival process. The author gives algorithms for computing waiting-time, busy period, and queue-length distributions.


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI


[1] Alfa, A. S. (2001). Discrete time queues and matrix-geometric method: some special features. In Lecture Notes First Seoul Internat. Workshop Queueing Theory (Seoul 16–18 July 2001), SRCCS.
[2] Alfa, A. S. (2003). Waiting time distribution of the MAP/D/\(k\) system in discrete time—a more efficient algorithm. Operat. Res. Lett. 31, 263–267. · Zbl 1088.90007
[3] Alfa, A. S. and Fitzpatrick, G. J. (1999). Waiting time distribution of a FIFO/LIFO Geo/D/1 queue. INFOR 37, 149–159.
[4] Alfa, A. S., Dolhun, L. K. and Chakravarthy, S. (1995). A discrete single server queue with Markovian arrivals and phase type group services. J. Appl. Math. Stoch. Anal. 8, 151–176. · Zbl 0822.60086
[5] Bini, D. and Meini, B. (1995). On cyclic reduction applied to a class of Toeplitz-like matrices arising in queueing problems. In Computations with Markov Chains , ed. W. J. Stewart, Kluwer, Boston, MA, pp. 21–38. · Zbl 0862.60085
[6] Bini, D. and Meini, B. (1998). Using displacement structure for solving non-skip-free M/G/1 type Markov chains. In Advances in Matrix-Analytic Methods for Stochastic Models , eds A. S. Alfa and S. Chakravarthy, Notable Publications, Neshanic Station, NJ, pp. 17–37. · Zbl 0894.65008
[7] Blondia, C. (1993). A discrete-time batch Markovian arrival process as B-ISDN traffic model. Belg. J. Operat. Res. Statist. Comput. Sci. 32, 3–23. · Zbl 0781.60097
[8] Bruneel, H. and Kim, B. G. (1993). Discrete-Time Models for Communications Systems Including ATM . Kluwer, Boston, MA. · Zbl 0771.60074
[9] Bruneel, H. and Wuyts, I. (1994). Analysis of discrete-time multiserver queueing models with constant service time. Operat. Res. Lett. 15, 231–236. · Zbl 0814.90030
[10] Chakravarthy, S. and Alfa, A. S. (1993). A multiserver queue with Markovian arrivals and group services with thresholds. Naval Res. Logistics 40, 811–827. · Zbl 0785.60043
[11] Chaudhry, M. L., Yoon, B. K. and Chae, K. C. (2002). Waiting-time distribution of a discrete multiserver queue with correlated arrivals and deterministic service times: D-MAP/D/\(k\) system. Operat. Res. Lett. 30, 174–180. · Zbl 1010.90013
[12] Crommelin, C. D. (1932). Delay probability formulae when the holding times are constant. Post Office Electrical Eng. J. 25, 41–50.
[13] Franx, G. J. (2001). A simple solution for the M/D/\(c\) waiting time distribution. Operat. Res. Lett. 29, 221–229. · Zbl 0993.90026
[14] Frigui, I., Alfa, A. S. and Xu, X. (1997). Algorithms for computing waiting-time distributions under different disciplines for the D-BMAP/PH/1. Naval Res. Logistics 44, 559–576. · Zbl 0893.90066
[15] Gail, H. R., Hantler, S. L. and Taylor, B. A. (1997). Non-skip-free M/G/1 and GI/M/1 type Markov chains. Adv. Appl. Prob. 29, 733–758. · Zbl 0892.60091
[16] Iversen, V. B. (1983). Decomposition of an M/D/\(rk\) queue with FIFO into \(k\)E\(_k\)/D/\(r\) queues with FIFO. Operat. Res. Lett. 2, 20–21. · Zbl 0507.60090
[17] Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling . SIAM, Philadelphia, PA. · Zbl 0922.60001
[18] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models . Johns Hopkins University Press, Baltimore, MD. · Zbl 0469.60002
[19] Neuts, M. F. (1989). Structured Stochastic Matrices of the M/G/\(1\) Type and Their Applications . Marcel Dekker, New York. · Zbl 0695.60088
[20] Nishimura, S. (2000). A spectral analysis for a MAP/D/\(N\) queue. In Advances in Algorithmic Methods for Stochastic Models , eds G. Latouche and P. Taylor, Notable Publications, Neshanic Station, NJ, pp. 279–294.
[21] Ramaswami, V. (1988). A stable recursion for the steady state vector in Markov chains of M/G/1 type. Stoch. Models 4, 183–188. · Zbl 0646.60098
[22] Takine, T. (2000). A simple approach to the MAP/D/\(s\) queue. Stoch. Models 16, 543–556. · Zbl 0964.60087
[23] Tijms, H. C. (1994). Stochastic Models, an Algorithmic Approach . John Wiley, New York. · Zbl 0838.60075
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.