×

Waiting time distribution of the \(MAP/D/k\) system in discrete time – a more efficient algorithm. (English) Zbl 1088.90007

Summary: We show that the discrete time \(MAP/D/k\) presented by M. L. Chaudhry, B. K. Yoon and K. C. Chae [Oper. Res. Lett. 30, No. 3, 174–180 (2002; Zbl 1010.90013)] has a special structure which results in a simple and more efficient computational scheme than they have presented. Specifically, we show that the computational efforts for the matrix \(G\) at each iteration can be reduced from \(O(d^3k^3m^3)\) to O\((dk^3m^3)\) by rearranging the state space and then capitalizing on the resulting structure. This saving in computational effort is significant, especially when \(d\) is very large.

MSC:

90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)

Citations:

Zbl 1010.90013
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A.S. Alfa, Discrete time queues and matrix-geometric method: some special features, Lecture Notes, The First Seoul International Workshop on Queueing Theory, July 16-18, 2001, SRCCS.; A.S. Alfa, Discrete time queues and matrix-geometric method: some special features, Lecture Notes, The First Seoul International Workshop on Queueing Theory, July 16-18, 2001, SRCCS.
[2] Alfa, A. S.; Dolhun, L. K.; Chakravarthy, S., A discrete single server queue with Markovian arrivals and phase type group services, J. Appl. Math. Stochastics Anal., 8, 2, 151-176 (1995) · Zbl 0822.60086
[3] Alfa, A. S.; Fitzpatrick, G. J., Waiting time distribution of a FIFO/LIFO Geo/D/1 queue, INFOR, 37, 2, 149-159 (1999) · Zbl 07677586
[4] Chakravarthy, S.; Alfa, A. S., A multiserver queue with Markovian arrivals and group services with thresholds, Naval Res. Logistics, 40, 811-827 (1993) · Zbl 0785.60043
[5] Chaudhry, M. L.; Yoon, B. K.; Chae, K. C., Waiting-time distribution of a discrete multiserver queue with correlated arrivals and deterministic service timesD-MAP/D/k system, Oper. Res. Lett., 30, 3, 174-180 (2002) · Zbl 1010.90013
[6] Crommelin, C. D., Delay probability formulae when the holding times are constant, Post Off. Electr. Eng. J., 25, 41-50 (1932)
[7] Franx, G. J., A simple solution for the M/D/c waiting time distribution, Oper. Res. Lett., 29, 5, 221-229 (2001) · Zbl 0993.90026
[8] Frigui, I.; Alfa, A. S.; Xu, X., Algorithms for computing waiting-time distributions under different disciplines for the D-BMAP/PH/1, Naval Res. Logistics, 44, 559-576 (1997) · Zbl 0893.90066
[9] Latouche, G.; Ramaswami, V., Introduction to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM Series on Statistics and Applied Probability (1999), SIAM: SIAM Philadelphia, PA · Zbl 0922.60001
[10] Neuts, M. F., Matrix-geometric Solutions in Stochastic Models (1981), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0469.60002
[11] Neuts, M. F., Structured Stochastic Matrices of the M/G/1 Type and Their Applications (1989), Marcel Dekker Inc: Marcel Dekker Inc New York · Zbl 0683.60067
[12] Nishimura, A spectral analysis for a MAP/D/N queue, in: G. Latouche, P. Taylor (Eds.), Advances in Algorithmic Methods for Stochastic Models, Notable Publications, Inc., Neshanic Station, NJ, 2000, pp. 279-294.; Nishimura, A spectral analysis for a MAP/D/N queue, in: G. Latouche, P. Taylor (Eds.), Advances in Algorithmic Methods for Stochastic Models, Notable Publications, Inc., Neshanic Station, NJ, 2000, pp. 279-294.
[13] Tijms, H. C., Stochastic Models, an Algorithmic Approach (1994), Wiley: 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.