×

A simple analysis of system characteristics in the batch service queue with infinite-buffer and Markovian service process using the roots method: \(\mathrm{GI}/\mathrm{C-MSP}^{a,b}/1/\infty\). (English) Zbl 1356.60143

The paper investigates \(\mathrm{GI}/\mathrm{C-MSP}^{(a,b)}/1/\infty \) queues. In such queues, customers are served by a single server in batches of maximum size \(b\) with a minimum threshold size \(a\). From the introduction: “We carry out the analytic analysis through the calculation of roots of the denominator of the underlying generating function for the steady state probabilities of the embedded Markov chain after a particular threshold level for infinite state space. The roots can be easily found using one of the several commercially available packages. The purpose of studying this queueing model using roots is that we obtain computationally simple and analytically closed form solution to the infinite buffer \(\mathrm{GI}/\mathrm{C-MSP}^{(a,b)}/1\) queue. Secondly, we obtain several other quantitative measures such as queue-length distributions, evaluation of expected busy and idle period. Further, we provide a comparison between the computational complexities of the roots method and matrix-geometric method. Also, we have established heavy- and light-traffic approximations as well as approximation for the tail probabilities at the pre-arrival epoch based on the root of the characteristic equation.”

MSC:

60K25 Queueing theory (aspects of probability theory)
60J27 Continuous-time Markov processes on discrete state spaces
60J28 Applications of continuous-time Markov processes on discrete state spaces
90B22 Queues and service in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Software:

QPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] F.J. Albores-Velasco and F.S. Tajonar-Sanabria, Anlysis of the GI/MSP/c/r queueing system. Inf. Processes4 (2004) 46-57.
[2] A.D. Banik, Analyzing state-dependent arrival in GI/BMSP/ 1 / queues. Math. Comput. Model.53 (2011) 1229-1246. · Zbl 1217.90064 · doi:10.1016/j.mcm.2010.12.007
[3] A.D. Banik, Single server queues with a batch Markovian arrival process and bulk renewal or non-renewal service. J. Syst. Sci. Syst. Eng.24 (2015) 337-363. · doi:10.1007/s11518-015-5268-y
[4] A.D. Banik, M.L. Chaudhry and U.C. Gupta, Finite-buffer bulk service queue under Markovian service process: GI/MSP^{(a,b)}/ 1 /N. Stoch. Anal. Appl.27 (2009) 500-522. · Zbl 1171.60020 · doi:10.1080/07362990902844157
[5] P.P. Bocharov, Stationary distribution of a finite queue with recurrent flow and Markovian service. Autom. Remote Control57 (1996) 66-78.
[6] P.P. Bocharov, C. D’Apice, A. Pechinkin and S. Salerno, The Stationary Characteristics of the G/MSP/ 1 /r queueing system. Autom. Remote Control64 (2003) 288-301. · Zbl 1066.60077 · doi:10.1023/A:1022219232282
[7] J.M. Borwein and P.B. Borwein, Pi and the AGM: A study in analytic number theory and computational complexity. Wiley, New York. Stoch. Models3 (1987) 115-148. · Zbl 0611.10001
[8] R.F. Botta, C.M. Harris and W.G. Marchal, Characterizations of generalized hyperexponential distribution functions. Stoch. Models3 (1987) 115-148. · Zbl 0616.62016 · doi:10.1080/15326348708807049
[9] M.S. Cha, P.-H. Koo and J. Joe, Real-time Control Strategies of Batch Processing Machines in Semiconductor Manufacturing. Proc. of the Asia Pacific Industrial Engineering & Management Systems Conference. Patong Beach, Phuket, Thailand (2012).
[10] S. Chakravarthy, A finite capacity GI/PH/ 1 queue with group services. Naval Res. Logist.39 (1992) 345-357. · Zbl 0756.90040 · doi:10.1002/1520-6750(199204)39:3<345::AID-NAV3220390305>3.0.CO;2-V
[11] S. Chakravarthy, Analysis of a finite MAP/G/ 1 queue with group services. Queueing Syst.13 (1993) 385-407. · Zbl 0772.60072 · doi:10.1007/BF01149262
[12] M.L. Chaudhry, On the discrete-time queue length distribution under Markov-dependent phases. Naval Res. Logist. Quart.19 (1972) 369-378. · Zbl 0248.60070 · doi:10.1002/nav.3800190211
[13] M.L. Chaudhry, QPACK Software Package. A&A Publications, 395 Carrie Cresc., Kingston, Ontario, K7M 5X7 Canada (1991).
[14] M.L. Chaudhry and U.C. Gupta, Modelling and analysis of M/G^{(a,b)}/ 1 /N queue - A simple alternative approach. Queueing Syst.31 (1999) 95-100. · Zbl 0955.90015 · doi:10.1023/A:1019197911961
[15] M.L. Chaudhry and J.G.C. Templeton, A First Course in Bulk Queues. John Wiley & Sons, New York (1983). · Zbl 0559.60073
[16] M.L. Chaudhry, C.M. Harris and W.G. Marchal, Robustness of rootfinding in single server queueing models. Informs J. Comput.2 (1990) 273-286. · Zbl 0760.60081 · doi:10.1287/ijoc.2.3.273
[17] M.L. Chaudhry, S.K. Samanta and A. Pacheco, Analytically explicit results for the GI/C-MSP/ 1 / queueing system using roots. Probab. Eng. Inform. Sci.26 (2012) 221-244. · Zbl 1255.60160 · doi:10.1017/S0269964811000349
[18] M.L. Chaudhry, G. Singh and U.C. Gupta, A simple and complete computational analysis of MAP/R/ 1 queue using roots. Methodol. Comput. Appl. Probab.15 (2013) 563-582. · Zbl 1274.60271 · doi:10.1007/s11009-011-9266-3
[19] B.D. Choi, D.H. Han, GI/M^{(a,b)}/ 1 queues with server vacations. J. Oper. Res. Soc. Japan37 (1994) 171-181. · Zbl 0818.60089
[20] E.Çinlar, Introduction to stochastic process. Prentice Hall, New Jersey (1975).
[21] J.H. Dshalalow, Frontiers in Queueing: Models and Applications in Science and Engineering. CRC Press, Boca Raton, FL (1997). · Zbl 0857.00015
[22] W. Feller, An Introduction to Probability Theory and its Applications, 3rd Edition. John Wiley, New York (1968). · Zbl 0155.23101
[23] S. Gagandeep, U.C. Gupta and M.L. Chaudhry, Computational analysis of bulk Service queue with Markovian arrival process: MAP/R^{(a,b)}/ 1 queue. Opsearch50 (2013) 582-603. · Zbl 1353.90044 · doi:10.1007/s12597-013-0128-3
[24] E. Gelenbe and R. Lent, Computer and Information Sciences III: 27th International Symposium on Computer and Information Sciences. Springer, London (2012).
[25] H. Gold and P. Tran-Gia, Performance analysis of a batch service queue arising out of manufacturing and system modelling. Queueing Syst.14 (1993) 413-426. · Zbl 0798.90067 · doi:10.1007/BF01158876
[26] V. Goswami, S.S. Patra and G.B. Mund, Performance analysis of cloud computing centers for bulk services. Int. J. Cloud Appl. Comput.2 (2012) 53-65.
[27] W.K. Grassmann, M.I. Taksar and D.P. Heyman, Regenerative analysis and steady state distributions for Markov chains. Oper. Res.33 (1985) 1107-1116. · Zbl 0576.60083 · doi:10.1287/opre.33.5.1107
[28] U.C. Gupta and A.D. Banik, Complete analysis of finite and infinite buffer GI/MSP/ 1 queue - a computational approach. Oper. Res. Lett.35 (2006) 273-280. · Zbl 1149.90322 · doi:10.1016/j.orl.2006.02.003
[29] U.C. Gupta and P. Vijaya Laxmi, Analysis of MAP/G^{a,b}/ 1 /N queue. Queueing Syst.38 (2001) 109-124. · Zbl 0997.90010 · doi:10.1023/A:1010909913320
[30] G. Hébuterne and C. Rosenberg, Arrival and departure state distributions in the general bulk-service queue. Naval Res. Logist.46 107-118. · Zbl 0922.90068
[31] D.M. Lucantoni, New results on the single server queue with a batch Markovian arrival process. Stoch. Models7 (1991) 1-46. · Zbl 0733.60115 · doi:10.1080/15326349108807174
[32] D.M. Lucantoni and M.F. Neuts, Some steady-state distributions for the MAP/SM/ 1 queue. Commun. Stat. Stoch. Models10 (1994) 575-598. · Zbl 0804.60086 · doi:10.1080/15326349408807311
[33] D.M. Lucantoni, K.S. Meier-Hellstern and M.F. Neuts, A single-server queue with server vacations and a class of non-renewal process. Adv. Appl. Probab.22 (1990) 676-705. · Zbl 0709.60094 · doi:10.2307/1427464
[34] B.R. Madill and M.L. Chaudhry, Probabilities and some measures of efficiency in the queueing system GI/M^{(a,b)}/ 1. Sel. Stat. CanadianaVII (1987) 53-75.
[35] I. Mitrani and R. Chakka, Spectral expansion solution for a class of Markov models: application and comparison with the matrix-geometric method. Perform. Eval.23 (1995) 241-260. · Zbl 0875.68103 · doi:10.1016/0166-5316(94)00025-F
[36] T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices. J. Symb. Comput.35 (2003) 377-401. · Zbl 1028.65038 · doi:10.1016/S0747-7171(02)00139-6
[37] M.F. Neuts, Moment Formulas for the Markov Renewal Branching Process Adv. Appl. Probab.8 (1976) 690-711. · Zbl 0379.60081 · doi:10.2307/1425930
[38] M.F. Neuts, A versatile Markovian point process. J. Appl. Probab.16 (1979) 764-779. · Zbl 0422.60043 · doi:10.2307/3213143
[39] M.F. Neuts, Matrix-Geometric Solutions in Stoch. Models: An Algorithmic Approach. Johns Hopkins University Press, Baltimore, MD (1981). · Zbl 0469.60002
[40] A. Pacheco, L. Tang and N.U. Prabhu, Markov-modulated Processes and Semiregenerative Phenomena. World Scientific, Singapore (2009). · Zbl 1181.60005
[41] J.F. Pérez, Miklós Telek and Benny Van Houdt, A fast Newton’s iteration for M/G/ 1-type and GI/M/ 1-type Markov chains. Stoch. Models28 (2012) 557-583. · Zbl 1259.60083 · doi:10.1080/15326349.2012.726038
[42] V. Ramaswami, Nonlinear matrix equations in applied probability-solution techniques and open problems. SIAM Rev.30 (1988) 256-263. · Zbl 0642.65033 · doi:10.1137/1030046
[43] H.C. Tijms, A First Course in Stoch. Models. John Wiley and Sons (2003). · Zbl 1088.60002
[44] P. Vijaya Laxmi and U.C. Gupta, On the finite buffer bulk-service queue with general independent arrivals: GI/M^{[ b ]}/ 1 /N. Oper. Res. Lett.25 (1999) 241-245. · Zbl 0958.90010 · doi:10.1016/S0167-6377(99)00032-2
[45] M. Yu and A.S. Alfa, Algorithm for computing the queue length distribution at various time epochs in DMAP/G^{(1,a,b)}/ 1 /N queue with batch-size-dependent service time. Eur. J. Oper. Res.244 (2015) 227-239. · Zbl 1347.90026 · doi:10.1016/j.ejor.2015.01.056
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.