Stationary analysis of the shortest queue problem

Plinio S. Dester (), Christine Fricker () and Danielle Tibi ()
Additional contact information
Plinio S. Dester: INRIA Paris
Christine Fricker: INRIA Paris
Danielle Tibi: LPMA - Université Paris Diderot, bâtiment Sophie Germain

Queueing Systems: Theory and Applications, 2017, vol. 87, issue 3, No 2, 243 pages

Abstract: Abstract 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, \ldots , 2K \}$$ { K , … , 2 K } , 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 \le k \le K$$ 0 ≤ k ≤ 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.

Keywords: Shortest queue; Finite capacity; Stationary probabilities; Bivariate generating function; 60J27; 60K25 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-017-9556-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:87:y:2017:i:3:d:10.1007_s11134-017-9556-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-017-9556-8

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().