Alternative approach based on roots for computing the stationary queue-length distributions in G I X / M ( 1 , b ) / 1 single working vacation queue
RAIRO. Operations Research, Tome 55 (2021), pp. S2259-S2290

The purpose of this paper is to present an alternative algorithm for computing the stationary queue-length and system-length distributions of a single working vacation queue with renewal input batch arrival and exponential holding times. Here we assume that a group of customers arrives into the system, and they are served in batches not exceeding a specific number b. Because of batch arrival, the transition probability matrix of the corresponding embedded Markov chain for the working vacation queue has no skip-free-to-the-right property. Without considering whether the transition probability matrix has a special block structure, through the calculation of roots of the associated characteristic equation of the generating function of queue-length distribution immediately before batch arrival, we suggest a procedure to obtain the steady-state distributions of the number of customers in the queue at different epochs. Furthermore, we present the analytic results for the sojourn time of an arbitrary customer in a batch by utilizing the queue-length distribution at the pre-arrival epoch. Finally, various examples are provided to show the applicability of the numerical algorithm.

DOI : 10.1051/ro/2020083
Classification : 60K25, 90B22
Keywords: Working vacation queue, renewal input, batch arrival bulk service, roots, Rouché’s theorem 
@article{RO_2021__55_S1_S2259_0,
     author = {Yu, Miaomiao},
     title = {Alternative approach based on roots for computing the stationary queue-length distributions in $GI^{X} /M^{(1 , b)}  / 1$ single working vacation queue},
     journal = {RAIRO. Operations Research},
     pages = {S2259--S2290},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020083},
     mrnumber = {4223173},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020083/}
}
TY  - JOUR
AU  - Yu, Miaomiao
TI  - Alternative approach based on roots for computing the stationary queue-length distributions in $GI^{X} /M^{(1 , b)}  / 1$ single working vacation queue
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S2259
EP  - S2290
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020083/
DO  - 10.1051/ro/2020083
LA  - en
ID  - RO_2021__55_S1_S2259_0
ER  - 
%0 Journal Article
%A Yu, Miaomiao
%T Alternative approach based on roots for computing the stationary queue-length distributions in $GI^{X} /M^{(1 , b)}  / 1$ single working vacation queue
%J RAIRO. Operations Research
%D 2021
%P S2259-S2290
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020083/
%R 10.1051/ro/2020083
%G en
%F RO_2021__55_S1_S2259_0
Yu, Miaomiao. Alternative approach based on roots for computing the stationary queue-length distributions in $GI^{X} /M^{(1 , b)}  / 1$ single working vacation queue. RAIRO. Operations Research, Tome 55 (2021), pp. S2259-S2290. doi: 10.1051/ro/2020083

[1] A. S. Alfa, Markov chain representations of discrete distributions applied to queueing models. Comput. Oper. Res. 31 (2004) 2365–2385. | MR | Zbl | DOI

[2] A. S. Alfa, Applied Discrete-Time Queues. Springer, New York, NY (2016). | MR

[3] R. Arumuganathan and S. Jeyakumar, Steady state analysis of a bulk queue with multiple vacations, setup times with N policy and closedown times. Appl. Math. Modell. 29 (2005) 972–986. | Zbl | DOI

[4] R. Arumuganathan and K. S. Ramaswami, Analysis of a bulk queue with fast and slow service rates and multiple vacations. Asia-Pac. J. Oper. Res. 22 (2005) 239–260. | MR | Zbl | DOI

[5] F. P. Barbhuiya and U. C. Gupta, A difference equation approach for analysing a batch service queue with the batch renewal arrival process. J. Differ. Equ. App. 25 (2019) 233–242. | MR | DOI

[6] F. P. Barbhuiya and U. C. Gupta, Discrete-time queue with batch renewal input and random serving capacity rule: G I X / G e o Y / 1 . Queueing Syst. 91 (2019) 347–365. | MR | DOI

[7] F. P. Barbhuiya and U. C. Gupta, A discrete-time G I X / G e o / 1 queue with multiple working vacation under late and early arrival system. Methodol. Comput. Appl. Probab. 22 (2020) 599–624. | MR | DOI

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

[9] P. J. Burke, Delays in single-server queues with batch input. Oper. Res. 23 (1975) 830–832. | MR | Zbl | DOI

[10] K. C. Chae, D. E. Lim and W. S. Yang, The G I / M / 1 queue and the G I / G e o / 1 queue both with single working vacation. Perform. Eval. 66 (2009) 356–367. | DOI

[11] S. H. Chang and D. W. Choi, Performance analysis of a finite-buffer discrete-time queue with bulk arrival, bulk service and vacations. Comput. Oper. Res. 32 (2005) 2213–2234. | Zbl | DOI

[12] S. H. Chang and D. W. Choi, Modeling and performance analysis of a finite buffer queue with batch arrivals, batch services and setup times: The M X / G Y / 1 / K + B queue with setup times queue with setup times. INFORMS J. Comput. 18 (2006) 218–228. | MR | Zbl | DOI

[13] M. L. Chaudhry and J. J. Kim, Analytically elegant and computationally efficient results in terms of roots for the G I X / M / c queueing system. Queueing Syst. 82 (2016) 237–257. | MR | DOI

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

[15] 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 | DOI

[16] M. L. Chaudhry, A. D. Banik, A. Pacheco and S. Ghosh, 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 / ∞ . RAIRO:OR 50 (2016) 519–551. | MR | Numdam | Zbl | DOI

[17] M. L. Chaudhry, A. D. Banik and A. Pacheco, A simple analysis of the batch arrival queue with infinite-buffer and Markovian service process using roots method: G I [ X ] / C - M S P / 1 / ∞ . Ann. Oper. Res. 252 (2017) 135–173. | MR | DOI

[18] D. Claeys, B. Steyaert, J. Walraevens, K. Laevens and H. Bruneel, Analysis of a versatile batch-service queueing model with correlation in the arrival process. Perform. Eval. 70 (2013) 300–316. | DOI

[19] B. T. Doshi, Queueing systems with vacations-a survey. Queueing Syst. 1 (1986) 29–66. | MR | Zbl | DOI

[20] D. Gross and C. M. Harris, Fundamentals of Queueing Theory, 2nd edition. John Wiley & Sons, New York, NY (1985). | MR | Zbl

[21] D. Guha and A. D. Banik, On the renewal input batch-arrival queue under single and multiple working vacation policy with application to EPON. INFOR: Inf. Syst. Oper. Res. 51 (2013) 175–191. | MR

[22] D. Guha, V. Goswami and A. D. Banik, Equilibrium balking strategies in renewal input batch arrival queues with multiple and single working vacation. Perform. Eval. 94 (2015) 1–24. | DOI

[23] M. Haridass and R. Arumuganathan, Analysis of a M X / G ( a , b ) / 1 queueing system with vacation interruption . RAIRO:OR 46 (2012) 305–334. | MR | Zbl | Numdam | DOI

[24] V. Klimenok, On the modification of Rouches theorem for the queueing theory problems. Queueing Syst. 38 (2001) 431–434. | MR | Zbl | DOI

[25] G. V. Krishna Reddy, R. Nadarajan and R. Arumuganathan, Analysis of a bulk queue with N -policy multiple vacations and setup times. Comput. Oper. Res. 25 (1998) 957–967. | MR | Zbl | DOI

[26] J. H. Li and N. S. Tian, The discrete-time G I / G e o / 1 queue with working vacations and vacation interruption. Appl. Math. Comput. 185 (2007) 1–10. | MR | Zbl

[27] J. H. Li and N. S. Tian, Performance analysis of a G I / M / 1 queue with single working vacation. Appl. Math. Comput. 217 (2011) 4960–4971. | MR | Zbl

[28] A. Maity and U. C. Gupta, Analysis and optimal control of a queue with infinite buffer under batch-size dependent versatile bulk-service rule. OPSEARCH 52 (2015) 472–489. | MR | DOI

[29] M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD (1981). | MR | Zbl

[30] G. Panda, A. D. Banik and D. Guha, Stationary analysis and optimal control under multiple working vacation policy in a G I / M ( a , b ) / 1 queue. J. Syst. Sci. Complexity 31 (2018) 1003–1023. | MR | DOI

[31] S. Pradhan and U. C. Gupta, Modeling and analysis of an infinite-buffer batch-arrival queue with batch-size-dependent service: M X / G n ( a , b ) / 1 . Perform. Eval. 108 (2017) 16–31. | DOI

[32] S. Pradhan and U. C. Gupta, Analysis of an infinite-buffer batch-size-dependent service queue with Markovian arrival process. Ann. Oper. Res. 277 (2019) 161–196. | MR | DOI

[33] S. K. Samanta, M. L. Chaudhry and U. C. Gupta, Discrete-time G e o X / G ( a , b ) / 1 / N queues with single and multiple vacations queues with single and multiple vacations. Math. Comput. Modell. 45 (2007) 93–108. | MR | Zbl | DOI

[34] S. K. Samanta, M. L. Chaudhry, A. Pacheco and U. C. Gupta, Analytic and computational analysis of the discrete-time G I / D - M S P / 1 queue using roots. Comput. Oper. Res. 56 (2015) 33–40. | MR | DOI

[35] L. D. Servi and S. G. Finn, M / M / 1 queues with working vacations ( M / M / 1 / W V ) . Perform. Eval. 50 (2002) 41–52. | DOI

[36] G. Singh, U. C. Gupta and M. L. Chaudhry, Analysis of queueing-time distributions for M A P / D N / 1 queue. Int. J. Comput. Math. 91 (2014) 1911–1930. | Zbl | DOI

[37] H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation. North-Holland, Amsterdam 3 (1993). | MR

[38] N. S. Tian and Z. G. Zhang, Vacation Queueing Models-Theory and Applications. Springer, New York, NY (2006). | MR | Zbl

[39] H. C. Tijms, A First Course in Stochastic Models. John Wiley & Sons, Chichester (2003). | MR | Zbl

[40] M. M. Yu, Y. H. Tang and Y. H. Fu, Steady state analysis and computation of the G I [ x ] / M b / 1 / L queue with multiple working vacations and partial batch rejection. Comput. Ind. Eng. 56 (2009) 1243–1253. | DOI

Cité par Sources :