×

Discrete-time queue with batch renewal input and random serving capacity rule: \(GI^X/ Geo^Y/1\). (English) Zbl 1466.60186

Summary: In this paper, we provide a complete analysis of a discrete-time infinite buffer queue in which customers arrive in batches of random size such that the inter-arrival times are arbitrarily distributed. The customers are served in batches by a single server according to the random serving capacity rule, and the service times are geometrically distributed. We model the system via the supplementary variable technique and further use the displacement operator method to solve the non-homogeneous difference equation. The analysis done using these methods results in an explicit expression for the steady-state queue-length distribution at pre-arrival and arbitrary epochs simultaneously, in terms of roots of the underlying characteristic equation. Our approach enables one to estimate the asymptotic distribution at a pre-arrival epoch by a unique largest root of the characteristic equation lying inside the unit circle. With the help of few numerical results, we demonstrate that the methodology developed throughout the work is computationally tractable and is suitable for light-tailed inter-arrival distributions and can also be extended to heavy-tailed inter-arrival distributions. The model considered in this paper generalizes the previous work done in the literature in many ways.

MSC:

60K25 Queueing theory (aspects of probability theory)
Full Text: DOI

References:

[1] Abolnikov, L., Dukhovny, A.: Markov chains with transition delta-matrix: ergodicity conditions, invariant probability measures and applications. Int. J. Stoch. Anal. 4(4), 333-355 (1991) · Zbl 0745.60069
[2] Akar, N., Arikan, E.: A numerically efficient method for the \[MAP/D/1/K\] MAP/D/1/K queue via rational approximations. Queueing Syst. 22(1), 97-120 (1996) · Zbl 0851.90036 · doi:10.1007/BF01159395
[3] Artalejo, J.R., Hernández-Lerma, Onésimo: Performance analysis and optimal control of the \[Geo/Geo/c\] Geo/Geo/c queue. Perform. Eval. 52(1), 15-39 (2003) · doi:10.1016/S0166-5316(02)00161-X
[4] Bruneel, H., Kim, B.G.: Discrete-Time Models for Communication Systems Including \[{ATM}\] ATM. Kluwer Acadmic, Boston (1993) · doi:10.1007/978-1-4615-3130-2
[5] Cardellini, V., Colajanni, M., Yu, P.S.: Dynamic load balancing on web-server systems. IEEE Internet Comput. 3(3), 28-39 (1999) · doi:10.1109/4236.769420
[6] Chang, S Ho, Choi, D .W.: 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\] MX/GY/1/K+B queue with setup times. INFORMS J. Comput. 18(2), 218-228 (2006) · Zbl 1241.90030 · doi:10.1287/ijoc.1040.0098
[7] Chaudhry, M.L., Gupta, U.C.: Queue-length and waiting-time distributions of discrete-time \[GI^X/Geom/1\] GIX/Geom/1 queueing systems with early and late arrivals. Queueing Syst. 25(1-4), 307-324 (1997) · Zbl 0894.60089 · doi:10.1023/A:1019144116136
[8] Chaudhry, M.L., Kim, J.J.: Analytically simple and computationally efficient solution to \[GI^X/Geom/1\] GIX/Geom/1 queues involving heavy-tailed distributions. Oper. Res. Lett. 44(5), 655-657 (2016) · Zbl 1408.90060 · doi:10.1016/j.orl.2016.07.012
[9] Chaudhry, M.L., Gupta, U.C., Templeton, James GC: On the relations among the distributions at different epochs for discrete-time \[GI/Geom/1\] GI/Geom/1 queues. Oper. Res. Lett. 18(5), 247-255 (1996) · Zbl 0855.90057 · doi:10.1016/0167-6377(95)00051-8
[10] Claeys, D., Steyaert, B., Walraevens, J., Laevens, K., Bruneel, H.: Analysis of a versatile batch-service queueing model with correlation in the arrival process. Perform. Eval. 70(4), 300-316 (2013) · doi:10.1016/j.peva.2012.12.004
[11] Claeys, D., Steyaert, B., Walraevens, J., Laevens, K., Bruneel, H.: Tail probabilities of the delay in a batch-service queueing model with batch-size dependent service times and a timer mechanism. Comput. Oper. Res. 40(5), 1497-1505 (2013) · Zbl 1352.90025 · doi:10.1016/j.cor.2012.10.009
[12] Cordeau, J.L., Chaudhry, M.L.: A simple and complete solution to the stationary queue-length probabilities of a bulk-arrival bulk-service queue. Infor. 47, 283-288 (2009) · Zbl 07683552
[13] Economou, A., Fakinos, D.: On the stationary distribution of the \[GI^X/M^Y/1\] GIX/MY/1 queueing system. Stoch. Anal. Appl. 21, 559-565 (2003) · Zbl 1044.60088 · doi:10.1081/SAP-120020426
[14] Feller, W.: An Introduction to Probability Theory and its Applications, vol. 1. Wiley, New York (1968) · Zbl 0155.23101
[15] Gravey, A., Hebuterne, G.: Simultaneity in discrete-time single server queues with bernoulli inputs. Perform. Eval. 14(2), 123-131 (1992) · Zbl 0752.60079 · doi:10.1016/0166-5316(92)90014-8
[16] Harris, C.M., Brill, P.H., Fischer, M.J.: Internet-type queues with power-tailed interarrival times and computational methods for their analysis. INFORMS J. Comput. 12(4), 261-271 (2000) · Zbl 1238.68035 · doi:10.1287/ijoc.12.4.261.11882
[17] Hochbaum, D.S., Landy, D.: Scheduling semiconductor burn-in operations to minimize total flowtime. Oper. Res. 45(6), 874-885 (1997) · Zbl 0895.90116 · doi:10.1287/opre.45.6.874
[18] Hunter, J .J.: Mathematical Techniques of Applied Probability: Discrete Time Models, Techniques and Applications. Academic Press, Cambridge (1983) · Zbl 0539.60065
[19] Kim, B., Choi, B.D.: Asymptotic analysis and simple approximation of the loss probability of the \[GI^X/M/c/K\] GIX/M/c/K queue. Perform. Eval. 54(4), 331-356 (2003) · doi:10.1016/S0166-5316(03)00095-6
[20] Li, L., Li, S., Zhao, S., Indus: QoS-aware scheduling of services-oriented internet of things. IEEE Trans. Ind. Inform. 10(2), 1497-1505 (2014) · doi:10.1109/TII.2014.2306782
[21] Pacheco, A., Samanta, S.K., Chaudhry, M.L.: A short note on the \[GI/Geo/1\] GI/Geo/1 queueing system. Stat. Probab. Lett. 82(2), 268-273 (2012) · Zbl 1239.60087 · doi:10.1016/j.spl.2011.09.022
[22] Singh, G., Gupta, U.C., Chaudhry, M.L.: Analysis of queueing-time distributions for \[MAP/D_N/1\] MAP/DN/1 queue. Int. J. Comput. Math. 91, 1911-1930 (2014) · Zbl 1306.60147 · doi:10.1080/00207160.2013.867021
[23] Takagi, H.: Queuing Analysis: A Foundation of Performance Evaluation. Discrete Time Systems, vol. 3. North-Holland, Amsterdam (1993)
[24] Vinck, B., Bruneel, H.: Analyzing the discrete-time \[G^{(G)}/Geo/1\] G(G)/Geo/1 queue using complex contour integration. Queueing Syst. 18(1-2), 47-67 (1994) · Zbl 0806.60088 · doi:10.1007/BF01158774
[25] Woodward, M.E.: Communication and Computer Networks: Modelling with Discrete-Time Queues. Wiley-IEEE Computer Society Pr, Hoboken (1994)
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.