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

Chaudhry, M. L.; Banik, A. D.; Pacheco, A.; Ghosh, Souvik

doi:10.1051/ro/2015035

A simple analysis of system characteristics in the batch service queue with infinite-buffer and Markovian service process using the roots method:

G I / C

M S P^{(a, b)} / 1 / \infty

Chaudhry, M. L.¹ ; Banik, A. D.^2,³ ; Pacheco, A.³ ; Ghosh, Souvik ²

¹ Department of Mathematics and Computer Science, Royal Military College of Canada, P.O. Box 17000, STN Forces, Kingston Ont., Canada K7K 7B4.
² School of Basic Sciences, Indian Institute of Technology, Samantapuri, Nandan Kanan Road, 751 013 Bhubaneswar, India.
³ CEMAT and Department of Mathematics, Instituto Superior Técnico, Universidade de Lisboa, Av. Rovisco Pais 1, 1049-001 Lisbon, Portugal.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 3, pp. 519-551.

Résumé

We consider an infinite-buffer single-server queue with renewal input and Markovian service process where customers are served in batches according to a general bulk service rule. Queue-length distributions at epochs of pre-arrival, arbitrary and post-departure have been obtained along with some important performance measures such as mean queue lengths and mean waiting times in both the system as well as the queue. We also obtain the steady-state service batch size distributions as well as system-length distributions. The proposed analysis is based on roots of the associated characteristic equation of the vector-generating function of queue-length distribution at a pre-arrival epoch. Also, we provide analytical and numerical comparison between the roots method used in this paper and the matrix geometric method in terms of computational complexities and required computation time to evaluate pre-arrival epoch probabilities for both the methods. Later, we have established heavy- and light-traffic approximations as well as an approximation for the tail probabilities at pre-arrival epoch based on one root of the characteristic equation. Numerical results for some cases have been presented to show the effect of model parameters on the performance measures.

Reçu le : 2014-09-09
Accepté le : 2015-09-17

MR Zbl

DOI : 10.1051/ro/2015035

Classification : 60K25, 60J27, 68M20, 90B22
Mots-clés : Continuous-time Markovian service process (C-MSP), general independent arrival, infinite-buffer, general bulk service rule((a, b)-rule), queue- and system-length distributions, service batch size distributions, roots, light- and heavy-traffic approximations, Weibull inter-arrival distribution, comparison with matrix-geometric method

Affiliations des auteurs :

Chaudhry, M. L. ¹ ; Banik, A. D. ^{2, 3} ; Pacheco, A. ³ ; Ghosh, Souvik ²

@article{RO_2016__50_3_519_0,
     author = {Chaudhry, M. L. and Banik, A. D. and Pacheco, A. and Ghosh, Souvik},
     title = {A simple analysis of system characteristics in the batch service queue with infinite-buffer and {Markovian} service process using the roots method: $GI/C$-$MSP^{(a,b)}/ 1 / \infty{}$},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {519--551},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {3},
     year = {2016},
     doi = {10.1051/ro/2015035},
     mrnumber = {3519331},
     zbl = {1356.60143},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2015035/}
}

TY  - JOUR
AU  - Chaudhry, M. L.
AU  - Banik, A. D.
AU  - Pacheco, A.
AU  - Ghosh, Souvik
TI  - A simple analysis of system characteristics in the batch service queue with infinite-buffer and Markovian service process using the roots method: $GI/C$-$MSP^{(a,b)}/ 1 / \infty{}$
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 519
EP  - 551
VL  - 50
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2015035/
DO  - 10.1051/ro/2015035
LA  - en
ID  - RO_2016__50_3_519_0
ER  -

%0 Journal Article
%A Chaudhry, M. L.
%A Banik, A. D.
%A Pacheco, A.
%A Ghosh, Souvik
%T A simple analysis of system characteristics in the batch service queue with infinite-buffer and Markovian service process using the roots method: $GI/C$-$MSP^{(a,b)}/ 1 / \infty{}$
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 519-551
%V 50
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2015035/
%R 10.1051/ro/2015035
%G en
%F RO_2016__50_3_519_0

Chaudhry, M. L.; Banik, A. D.; Pacheco, A.; Ghosh, Souvik. A simple analysis of system characteristics in the batch service queue with infinite-buffer and Markovian service process using the roots method: $GI/C$-$MSP^{(a,b)}/ 1 / \infty{}$. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 3, pp. 519-551. doi : 10.1051/ro/2015035. http://www.numdam.org/articles/10.1051/ro/2015035/

Bibliographie
Cité par

F.J. Albores-Velasco and F.S. Tajonar-Sanabria, Anlysis of the $G I / M S P / c / r$ queueing system. Inf. Processes 4 (2004) 46–57.

A.D. Banik, Analyzing state-dependent arrival in $G I / B M S P / 1 / \infty$ queues. Math. Comput. Model. 53 (2011) 1229–1246. | DOI | MR | Zbl

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

A.D. Banik, M.L. Chaudhry and U.C. Gupta, Finite-buffer bulk service queue under Markovian service process: $G I / M S P^{(a, b)} / 1 / N$ . Stoch. Anal. Appl. 27 (2009) 500–522. | DOI | MR | Zbl

P.P. Bocharov, Stationary distribution of a finite queue with recurrent flow and Markovian service. Autom. Remote Control 57 (1996) 66–78. | MR | Zbl

P.P. Bocharov, C. D’Apice, A. Pechinkin and S. Salerno, The Stationary Characteristics of the $G / M S P / 1 / r$ queueing system. Autom. Remote Control 64 (2003) 288–301. | DOI | MR | Zbl

J.M. Borwein and P.B. Borwein, Pi and the AGM: A study in analytic number theory and computational complexity. Wiley, New York. Stoch. Models 3 (1987) 115–148. | MR | Zbl

R.F. Botta, C.M. Harris and W.G. Marchal, Characterizations of generalized hyperexponential distribution functions. Stoch. Models 3 (1987) 115–148. | DOI | MR | Zbl

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).

S. Chakravarthy, A finite capacity $G I / P H / 1$ queue with group services. Naval Res. Logist. 39 (1992) 345–357. | DOI | MR | Zbl

S. Chakravarthy, Analysis of a finite $M A P / G / 1$ queue with group services. Queueing Syst. 13 (1993) 385–407. | DOI | MR | Zbl

M.L. Chaudhry, On the discrete-time queue length distribution under Markov-dependent phases. Naval Res. Logist. Quart. 19 (1972) 369–378. | DOI | MR | Zbl

M.L. Chaudhry, QPACK Software Package. A&A Publications, 395 Carrie Cresc., Kingston, Ontario, K7M 5X7 Canada (1991).

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. | DOI | MR | Zbl

M.L. Chaudhry and J.G.C. Templeton, A First Course in Bulk Queues. John Wiley & Sons, New York (1983). | MR | Zbl

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. | DOI | Zbl

M.L. Chaudhry, S.K. Samanta and A. Pacheco, Analytically explicit results for the $G I / C$ - $M S P / 1 / \infty$ queueing system using roots. Probab. Eng. Inform. Sci. 26 (2012) 221–244. | DOI | MR | Zbl

M.L. Chaudhry, G. Singh and U.C. Gupta, A simple and complete computational analysis of $M A P / R / 1$ queue using roots. Methodol. Comput. Appl. Probab. 15 (2013) 563–582. | DOI | MR | Zbl

B.D. Choi, D.H. Han, $G I / M^{(a, b)} / 1$ queues with server vacations. J. Oper. Res. Soc. Japan 37 (1994) 171–181. | MR | Zbl

E.Çinlar, Introduction to stochastic process. Prentice Hall, New Jersey (1975). | MR | Zbl

J.H. Dshalalow, Frontiers in Queueing: Models and Applications in Science and Engineering. CRC Press, Boca Raton, FL (1997). | MR | Zbl

W. Feller, An Introduction to Probability Theory and its Applications, 3rd Edition. John Wiley, New York (1968). | MR

S. Gagandeep, U.C. Gupta and M.L. Chaudhry, Computational analysis of bulk Service queue with Markovian arrival process: $M A P / R^{(a, b)} / 1$ queue. Opsearch 50 (2013) 582–603. | DOI | MR | Zbl

E. Gelenbe and R. Lent, Computer and Information Sciences III: 27th International Symposium on Computer and Information Sciences. Springer, London (2012). | Zbl

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. | DOI | Zbl

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.

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. | DOI | MR | Zbl

U.C. Gupta and A.D. Banik, Complete analysis of finite and infinite buffer $G I / M S P / 1$ queue – a computational approach. Oper. Res. Lett. 35 (2006) 273–280. | DOI | MR | Zbl

U.C. Gupta and P. Vijaya Laxmi, Analysis of MAP/G^a,b/ 1 /N queue. Queueing Syst. 38 (2001) 109–124. | DOI | MR | Zbl

G. Hébuterne and C. Rosenberg, Arrival and departure state distributions in the general bulk-service queue. Naval Res. Logist. 46 107–118. | DOI | MR | Zbl

D.M. Lucantoni, New results on the single server queue with a batch Markovian arrival process. Stoch. Models 7 (1991) 1–46. | DOI | MR | Zbl

D.M. Lucantoni and M.F. Neuts, Some steady-state distributions for the $M A P / S M / 1$ queue. Commun. Stat. Stoch. Models 10 (1994) 575–598. | DOI | MR | Zbl

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. | DOI | MR | Zbl

B.R. Madill and M.L. Chaudhry, Probabilities and some measures of efficiency in the queueing system $G I / M^{(a, b)} / 1$ . Sel. Stat. Canadiana VII (1987) 53–75. | MR

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. | DOI | Zbl

T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices. J. Symb. Comput. 35 (2003) 377–401. | DOI | MR | Zbl

M.F. Neuts, Moment Formulas for the Markov Renewal Branching Process Adv. Appl. Probab. 8 (1976) 690–711. | DOI | MR | Zbl

M.F. Neuts, A versatile Markovian point process. J. Appl. Probab. 16 (1979) 764–779. | DOI | MR | Zbl

M.F. Neuts, Matrix-Geometric Solutions in Stoch. Models: An Algorithmic Approach. Johns Hopkins University Press, Baltimore, MD (1981). | MR | Zbl

A. Pacheco, L. Tang and N.U. Prabhu, Markov-modulated Processes and Semiregenerative Phenomena. World Scientific, Singapore (2009). | MR | Zbl

J.F. Pérez, Miklós Telek and Benny Van Houdt, A fast Newton’s iteration for $M / G / 1$ -type and $G I / M / 1$ -type Markov chains. Stoch. Models 28 (2012) 557–583. | DOI | MR | Zbl

V. Ramaswami, Nonlinear matrix equations in applied probability-solution techniques and open problems. SIAM Rev. 30 (1988) 256–263. | DOI | MR | Zbl

H.C. Tijms, A First Course in Stoch. Models. John Wiley and Sons (2003). | MR

P. Vijaya Laxmi and U.C. Gupta, On the finite buffer bulk-service queue with general independent arrivals: $G I / M^{[b]} / 1 / N$ . Oper. Res. Lett. 25 (1999) 241–245. | DOI | MR | Zbl

M. Yu and A.S. Alfa, Algorithm for computing the queue length distribution at various time epochs in $D M A P / G^{(1, a, b)} / 1 / N$ queue with batch-size-dependent service time. Eur. J. Oper. Res. 244 (2015) 227–239. | DOI | MR | Zbl

Cité par Sources :