Coupled queues whose interior stationary joint content distribution is a finite sum of bivariate geometric terms

• Herwig Bruneel ^[1] ; Arnaud Devos ^[1]
  1. [1] Ghent University

     Ghent University

     Arrondissement Gent, Bélgica

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 34, Nº. 2, 2026, págs. 245-304
• Idioma: inglés
• DOI: 10.1007/s11750-025-00710-5
• Enlaces
  • Texto completo
• Resumen

  • Triggered by earlier work on random walks in the quarter-plane, we study the issue of two-queue systems whereby, at least for states (m, n) in some interior part of the state space, the stationary joint system-content distribution u(m, n) can be expressed as a finite linear combination of bivariate geometric terms of type γ mδn. Using a transform-based approach, we prove that this is certainly the case if the steady-state joint probability generating function U(z1,z2) of the two system contents can be expressed as a bivariate rational function of its two arguments, with mutually prime numerator and denominator, whereby the denominator is the product of two univariate polynomials in z1 and z2, respectively, whose zeroes zˆ1 and zˆ2 all have multiplicity one. We show that the decay rates γ and δ appearing in u(m, n) are the inverse values of (some of) the zeroes zˆ1 and zˆ2, but, in general, there may be zero-pairs (zˆ1,zˆ2) that do not contribute a bivariate geometric term in u(m, n). For two specific classes of discrete-time two-queue systems, we prove that, when U(z1,z2) has the prescribed form, only the zero-pairs that are zero-tuples of the kernel of the system contribute a term in u(m, n). In an extended series of examples, we then demonstrate that, within the two classes, specific instances (corresponding with specific arrival processes) that comply with the condition on U(z1,z2) indeed exist. In some examples, we can use existing solutions, but in other cases, we also construct entirely new solutions, thereby identifying several new solvable two-queue models. We observe that, in most cases, the zero-pairs that do contribute terms in u(m, n) are mutually connected, in the sense that each of them has its first or second component in common with at least one other pair that contributes, but we also construct a remarkable example where this is not the case.

• Referencias bibliográficas
  • Adan I, van Houtum G, Wessels J, Zijm W (1993) A compensation procedure for multiprogramming queues. OR Spektrum 15(2):95–106
  • Adan I, Wessels J, Zijm W (1993) A compensation approach for two-dimensional Markov processes. Adv Appl Probab 25(4):783–817
  • Adan I, Boxma O, Resing J (2001) Queueing models with multiple waiting lines. Queueing Systems 37(1):65–98
  • Adan I, Boxma O, Kapodistria S, Kulkarni V (2016) The shorter queue polling model. Ann Oper Res 241(1):167–200
  • Adan I, Dimitriou I (2023) A finite compensation procedure for a class of two-dimensional random walks. Indagationes Mathematicae
  • Al Hanbali A, de Haan R, Boucherie R, van Ommeren J (2012) Time-limited polling systems with batch arrivals and phase-type service times....
  • Alfa A (2002) Discrete time queues and matrix-analytic methods. TOP 10(2):147–185
  • Borst S, Boxma O (2018) Polling: past, present, and perspective. TOP 26(3):335–369
  • Boxma O, van Houtum G (1993) The compensation approach applied to a 2x2 switch. Probab Eng Inf Sci 7(4):471–493
  • Boxma O, Resing J (1994) Tandem queues with deterministic service times. Ann Oper Res 49(1):221–239
  • Bruneel H (2022) Some thoughts on the analysis of coupled queues. Queueing Systems 100(3):185–187
  • Bruneel H, Devos A (2023) Asymptotic behavior of a system of two coupled queues when the content of one queue is very high. Queueing Systems...
  • Bruneel H, Devos A (2024) Explicit solutions for coupled parallel queues. Mathematics 12(15):2345
  • Bruneel H, Devos A (2025) Coupled queues with server interruptions: some solutions. Perform Eval 167:102466
  • Bruneel H, Kim B (1993) Discrete-time models for communication systems including ATM. Kluwer Academic Publisher, Boston
  • Bruneel H, Fiems D, Walraevens J, Wittevrongel S (2014) Queueing models for the analysis of communication systems. TOP 22(2):421–448
  • Bruneel H, Fiems D, Walraevens J, Wittevrongel S (2014) Rejoinder on: Queueing models for the analysis of communication systems. TOP 22(2):460–468
  • Bruneel H, Devos A, Walraevens J (2025) A generalized result for the discrete-time two-queue randomly alternating service system. Perform...
  • Chen Y, Boucherie R, Goseling J (2015) The invariant measure of random walks in the quarter-plane: representation in geometric terms. Probab...
  • Cohen J (1997) On the determination of the stationary distribution of a symmetric clocked buffered switch. In V. Ramaswami and P. Wirth, editors,...
  • Devos A (2022) Analysis of a two-class queueing model with randomly alternating service. PhD thesis, Ghent University
  • Devos A, Walraevens J, Fiems D, Bruneel H (2020) Analysis of a discrete-time two-class randomly alternating service model with Bernoulli arrivals....
  • Devos A, Walraevens J, Fiems D, Bruneel H (2022) Approximations for the performance evaluation of a discrete-time two-class queue with an...
  • Devos A, De Muynck M, Bruneel H, Walraevens J (2022) A product-form solution for a two-class Geo/Geo/D/1 queue with random routing and randomly...
  • Hunter J (2014) Mathematical techniques of applied probability: Discrete time models: Basic theory, volume 1. Academic Press
  • Jacobi C, Furmans K (2022) Point and interval estimation of decomposition error in discrete-time open tandem queues. Oper Res Lett 50(5):529–535
  • Jaffe S (1992) The equilibrium distribution for a clocked buffered switch. Probab Eng Inf Sci 6(4):425–438
  • Resing J, Ormeci L (2003) A tandem queueing model with coupled processors. Oper Res Lett 31(5):383–389
  • Takagi H (1991) Queueing analysis: Discrete-time systems, volume 3. North-Holland
  • Vanlerberghe J, Maertens T, Walraevens J, De Vuyst S, Bruneel H (2016) On the optimization of two-class work-conserving parameterized scheduling...
  • Vanlerberghe J, Walraevens J, Maertens T, Bruneel H (2018) Calculation of the performance region of an easy-to-optimize alternative for generalized...