×

Stationary analysis of the shortest queue problem. (English) Zbl 1377.60085

Summary: A simple analytical solution is proposed for the stationary loss system of two parallel queues with finite capacity \(K\), in which new customers join the shortest queue, or one of the two with equal probability if their lengths are equal. The arrival process is Poisson, service times at each queue have exponential distributions with the same parameter, and both queues have equal capacity. Using standard generating function arguments, a simple expression for the blocking probability is derived, which as far as we know is original. Using coupling arguments and explicit formulas, comparisons with related loss systems are then provided. Bounds are similarly obtained for the average total number of customers, with the stationary distribution explicitly determined on \(\{K,\dots, 2K \}\), and elsewhere upper bounded. Furthermore, from the balance equations, all stationary probabilities are obtained as explicit combinations of their values at states \((0,k)\) for \(0 \leq k \leq K\). These expressions extend to the infinite capacity and asymmetric cases, i.e., when the queues have different service rates. For the initial symmetric finite capacity model, the stationary probabilities of states \((0,k)\) can be obtained recursively from the blocking probability. In the other cases, they are implicitly determined through a functional equation that characterizes their generating function. The whole approach shows that the stationary distribution of the infinite capacity symmetric process is the limit of the corresponding finite capacity distributions. Finally, application of the results for limited capacity to mean-field models for large bike-sharing networks with a local JSQ policy is briefly discussed.

MSC:

60K25 Queueing theory (aspects of probability theory)
60J27 Continuous-time Markov processes on discrete state spaces

References:

[1] Adan, I., van Houtum, G.J., van der Wal, J.: Upper and lower bounds for the waiting time in the symmetric shortest queue system. Ann. Oper. Res. 48(2), 197-217 (1994) · Zbl 0795.60090 · doi:10.1007/BF02024665
[2] Adan, I., Wessels, J., Zijm, W.H.M.: Analysis of the symmetric shortest queue problem. Commun. Stat. Stoch. Models 6(4), 691-713 (1990) · Zbl 0708.60089 · doi:10.1080/15326349908807169
[3] Adan, I., Wessels, J., Zijm, W.H.M.: Analysis of the asymmetric shortest queue problem. Queueing Syst. 8(1), 1-58 (1991) · Zbl 0719.60107 · doi:10.1007/BF02412240
[4] Adan, I., Wessels, J.: Analysis of the asymmetric shortest queue problem with threshold jockeying. Stoch. Models 7(4), 615-627 (1991) · Zbl 0741.60093 · doi:10.1080/15326349108807209
[5] Adan, I., Wessels, J., Zijm, W.H.M.: A compensation approach for two-dimensional Markov processes. Adv. Appl. Probab. 25(04), 783-817 (1993) · Zbl 0798.60081 · doi:10.1017/S0001867800025751
[6] Blanc, J.P.: The power-series algorithm applied to the shortest-queue model. Oper. Res. 40(1), 157-167 (1992) · Zbl 0745.90007 · doi:10.1287/opre.40.1.157
[7] Cohen, J.W.: On the symmetrical shortest queue and the compensation approach. Dep. Oper. Res. Stat. Syst. Theory BS R 9602, 1-21 (1996)
[8] Cohen, JW; Baccelli, F. (ed.); Jean-Marie, A. (ed.); Mitrani, I. (ed.), Two-dimensional nearest-neighbour queueing models, a review and an example, 141-152 (1995), Berlin · Zbl 0845.68011 · doi:10.1007/978-3-642-79917-4_9
[9] Cohen, J.W.: Analysis of the asymmetrical shortest two-server queueing model. Int. J. Stoch. Anal. 11(2), 115-162 (1998) · Zbl 0922.60084 · doi:10.1155/S1048953398000112
[10] Conolly, B.W.: The autostrada queueing problem. J. Appl. Probab. 21(2), 394-403 (1984) · Zbl 0543.60090 · doi:10.1017/S0021900200024761
[11] Dester, P.S., Fricker, C.: Local balancing policies in bike-sharing systems. In preparation (2017)
[12] Dester, P.S., Fricker, C., Tibi, D.: Stationary analysis of the shortest queue problem. arXiv:1704.06442 (2017) · Zbl 1377.60085
[13] Eschenfeldt, P., Gamarnik, D.: Join the shortest queue with many servers. The heavy traffic asymptotics. arXiv preprint arXiv:1502.00999 (2015) · Zbl 1433.60087
[14] Fayolle, G., Iasnogorodski, R.: Two coupled processors: the reduction to a Riemann-Hilbert problem. Z. Wahrscheinlichkeitstheorie verwandte Geb. 47(3), 325-351 (1979) · Zbl 0395.68032 · doi:10.1007/BF00535168
[15] Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random walks in the quarter plane: algebraic methods, boundary value problems, applications to queueing systems and analytic combinatorics, vol. 40. Springer International Publishing AG, Switzerland (2017) · Zbl 1386.60004
[16] Flatto, L.: The longer queue model. Probab. Eng. Inf Sci. 3(04), 537-559 (1989) · Zbl 1134.60395 · doi:10.1017/S0269964800001376
[17] Flatto, L., McKean, H.P.: Two queues in parallel. Commun. Pure Appl. Math. 30(2), 255-263 (1977) · Zbl 0336.60082 · doi:10.1002/cpa.3160300206
[18] Foley, R.D., McDonald, D.R.: Join the shortest queue: Stability and exact asymptotics. Ann. Appl. Probab. 11(3), 569-607 (2001) · Zbl 1016.60078
[19] Fricker, C., Gast, N.: Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity. EURO J. Trans. Logist. 1-31 (2014)
[20] Guillemin, F., Simonian, A.: Stationary analysis of the shortest queue first service policy. Queueing Syst. 77(4), 393-426 (2014) · Zbl 1309.60087 · doi:10.1007/s11134-013-9383-5
[21] Haight, F.: Two queues in parallel. Biometrika 45(3-4), 401-410 (1958) · Zbl 0086.33801 · doi:10.1093/biomet/45.3-4.401
[22] Halfin, S.: The shortest queue problem. J. Appl. Probab. 22(4), 865-878 (1985) · Zbl 0602.60080 · doi:10.1017/S0021900200108101
[23] Hooghiemstra, G., Keane, M., van de Ree, S.: Power series for stationary distributions of coupled processor models. SIAM J. Appl. Math. 48(5), 1159-1166 (1988) · Zbl 0652.60097 · doi:10.1137/0148069
[24] Katehakis, M.N., Smit, L.C.: A successive lumping procedure for a class of Markov chains. Probab. Eng. Inf. Sci. 26(4), 483-508 (2012) · Zbl 1261.60071 · doi:10.1017/S0269964812000150
[25] Katehakis, M.N., Smit, L.C., Spieksma, F.M.: DES and RES processes and their explicit solutions. Probab. Eng. Inf. Sci. 29(2), 191-217 (2015) · Zbl 1370.60172 · doi:10.1017/S0269964814000291
[26] Kingman, J.: Two similar queues in parallel. Ann. Math. Stat. 32(4), 1314-1323 (1961) · Zbl 0104.36901 · doi:10.1214/aoms/1177704869
[27] Knessl, C., Matkowsky, B., Schuss, Z., Tier, C.: Two parallel queues with dynamic routing. IEEE Trans. Commun. 34(12), 1170-1175 (1986) · Zbl 0612.60086 · doi:10.1109/TCOM.1986.1096486
[28] Knessl, C., Yao, H.: On the finite capacity shortest queue problem. Prog. Appl. Math. 2(1), 01-34 (2011) · doi:10.4236/am.2011.21001
[29] Kurkova, I.A., Suhov, Y.M.: Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities. Ann. Appl. Probab. 13(4), 1313-1354 (2003) · Zbl 1039.60082 · doi:10.1214/aoap/1069786501
[30] Latouche, G., Ramaswami, V.: Introduction to Matrix Analytic Methods in Stochastic Modeling, vol. 5. SIAM, Philadelphia (1999) · Zbl 0922.60001 · doi:10.1137/1.9780898719734
[31] Li, H., Miyazawa, M., Zhao, Y.Q.: Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model. Stoch. Models 23(3), 413-438 (2007) · Zbl 1124.60074 · doi:10.1080/15326340701471042
[32] Mitzenmacher, M.: On the analysis of randomized load balancing schemes. In: Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 292-301. ACM (1997) · Zbl 0104.36901
[33] Puhalskii, A.A., Vladimirov, A.A.: A large deviation principle for join the shortest queue. Math. Oper. Res. 32(3), 700-710 (2007) · Zbl 1341.60116 · doi:10.1287/moor.1070.0263
[34] Rao, B.M., Posner, M.J.M.: Algorithmic and approximation analyses of the shorter queue model. Naval Res. Logist. NRL 34(3), 381-398 (1987) · Zbl 0653.60093 · doi:10.1002/1520-6750(198706)34:3<381::AID-NAV3220340306>3.0.CO;2-K
[35] Ridder, A., Schwartz, A.: Large deviations without principle: join the shortest queue. Math. Methods Oper. Res. 62(3), 467-483 (2005) · Zbl 1084.60058 · doi:10.1007/s00186-005-0037-1
[36] Tarabia, A.M.K.: Analysis of two queues in parallel with jockeying and restricted capacities. Appl. Math. Model. 32(5), 802-810 (2008) · Zbl 1165.90409 · doi:10.1016/j.apm.2007.02.014
[37] Turner, S.R.E.: A join the shorter queue model in heavy traffic. J. Appl. Probab. 37(01), 212-223 (2000) · Zbl 0962.60094 · doi:10.1017/S0021900200015357
[38] Turner, S.R.E.: Large deviations for join the shorter queue. Fields Inst. Commun. 28, 95-108 (2000) · Zbl 0974.60082
[39] Van Houtum, G.J., Zijm, W.H.M., Adan, I.J.B.F., Wessels, J.: Bounds for performance characteristics: a systematic approach via cost structures. Stoch. Models 14(1-2), 205-224 (1998) · Zbl 0895.90095 · doi:10.1080/15326349808807467
[40] Van Leeuwaarden, J.S.H., Squillante, M.S., Winands, E.M.M.: Quasi-birth-and-death processes, lattice path counting, and hypergeometric functions. J. Appl. Probab. 46(2), 507-520 (2009) · Zbl 1186.60087 · doi:10.1017/S0021900200005611
[41] Vvedenskaya, N., Dobrushin, R., Karpelevich, F.: Queueing system with selection of the shortest of two queues: an asymptotic approach. Probl. Peredachi Informatsii 32(1), 20-34 (1996) · Zbl 0898.60095
[42] Weber, R.R.: On the optimal assignment of customers to parallel servers. J. Appl. Probab. 15(02), 406-413 (1978) · Zbl 0378.60095 · doi:10.1017/S0021900200045678
[43] Whitt, W.: Deciding which queue to join: some counterexamples. Oper. Res. 34(1), 55-62 (1986) · Zbl 0622.90035 · doi:10.1287/opre.34.1.55
[44] Winston, W.: Optimality of the shortest line discipline. J. Appl. Probab. 14(01), 181-189 (1977) · Zbl 0357.60023 · doi:10.1017/S0021900200104772
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.