Geodesic
Group service system with three queues and load balancing
Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 103-119.

Voir la notice de l'article provenant de la source Math-Net.Ru

A group service system for three queues is considered. At each time $t = 1, 2, \ldots$, with some probability, a customer enters the system, selects randomly two queues, and goes to the shorter one. At each moment such that there is at least one customer in each queue, each queue performs instantly the service of one customer. By means of Lyapunov functions, a criterion for the ergodicity of the Markov chain corresponding to this queuing system is established. The limiting joint distribution of queue lengths is found, and the connection with the problem of balanced allocations of particles into cells is described. In the corresponding problem of balanced allocation of particles, the limiting distribution of the range is found, i. e. the difference between the maximal and minimal numbers of particles in cells.
Keywords: queue systems with balanced load, balanced allocations of particles into cells, choosing the shortest queue, range, ergodicity, Markov chain, Lyapunov function. 
@article{DM_2020_32_4_a5,
     author = {M. P. Savelov},
     title = {Group service system with three queues and load balancing},
     journal = {Diskretnaya Matematika},
     pages = {103--119},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_4_a5/}
}
TY  - JOUR
AU  - M. P. Savelov
TI  - Group service system with three queues and load balancing
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 103
EP  - 119
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_4_a5/
LA  - ru
ID  - DM_2020_32_4_a5
ER  - 
%0 Journal Article
%A M. P. Savelov
%T Group service system with three queues and load balancing
%J Diskretnaya Matematika
%D 2020
%P 103-119
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_4_a5/
%G ru
%F DM_2020_32_4_a5
M. P. Savelov. Group service system with three queues and load balancing. Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 103-119. http://geodesic.mathdoc.fr/item/DM_2020_32_4_a5/

[1] Flatto L., McKean H., “Two queues in parallel”, Comm. Pure Appl. Math., 30 (1977), 255–263 | DOI | MR | Zbl

[2] Adan I. J., Wessels J. and Zijm W. H. M., “Analysis of the asymmetric shortest queue problem”, Queueing Systems, 8 (1991), 1–58 | DOI | MR | Zbl

[3] Kurkova I. A., “A load-balanced network with two servers”, Queueing Systems, 37 (2001), 379—389 | DOI | MR | Zbl

[4] Vvedenskaya N. D., Dobrushin R. L., Karpelevich F. I., “Sistema obsluzhivaniya s vyborom naimenshei iz dvukh ocheredei – asimptoticheskii podkhod”, Probl. peredachi inform., 32:1 (1996), 20–34 | MR | Zbl

[5] Eschenfeldt P., Gamarnik D.,, “Join the shortest queue with many servers. The heavy-traffic asymptotics”, Math. Oper. Res., 43:3 (2018), 867—886 | DOI | MR | Zbl

[6] Azar Y., Broder A., Karlin A., Upfal E., “Balanced allocations”, SIAM J. Comput., 29:1 (1999), 180–200 | DOI | MR | Zbl

[7] Czumaj A., Stemann V., “Randomized allocation processes”, Random Struct. Algor., 18 (2001), 297–331 | DOI | MR | Zbl

[8] Mitzenmacher M., Richa A., Sitaraman R., “The power of two random choices: a survey of techniques and results”, Handbook of Randomized Computing, v. 1, Kluwer, 2001, 255–312 | DOI | MR | Zbl

[9] Young D. H., “Two alternatives to the standard $\chi^2$-test of the hypothesis of equal cell frequencies”, Biometrika, 49:1–2 (1962), 107—116 | MR | Zbl

[10] Corrado C. J., “The exact distribution of the maximum, minimum and the range of multinomial/Dirichlet and multivariate hypergeometric frequencies”, Stat. Comput., 21 (2011), 349—359 | DOI | MR | Zbl

[11] Bonetti M., Cirillo P., Ogay A., “Computing the exact distributions of some functions of the ordered multinomial counts: Maximum, minimum, range and sums of order statistics”, Royal Soc. Open Science, 6:10 (2019), 1—32 | DOI

[12] Doshi, B. T., “Queueing systems with vacations. A survey.”, Queueing Systems, 1:1 (1986), 29—66 | DOI | MR | Zbl

[13] Fayolle G., Malyshev V. A., Menshikov M. M., Topics in the Constructive Theory of Countable Markov Chains, Cambridge Univ. Press, Cambridge, 1995, 169 pp. | MR | Zbl

[14] Borovkov A. A., Teoriya veroyatnostei — 3-e izd., Editorial URSS, M., 1999, 472 pp.