Stability and renormalization of Jackson networks
endowed with a finite pool of greedy mobile servers

Guy Fayolle * Christine Fricker †

December 2025

**Abstract**

A tandem of two queues sharing a pool of servers, where users take the time to switch to the second queue, is used to model a typical pathway through an emergency department (ED), where patients undergo two consultations separated by diagnostic tests. In this article, explicit conditions for ergodicity and transience are given and proven via Foster's criterion, using a linear Lyapunov function. This result is extended to a Jackson network, with the key difference that the nodes share a pool of servers, with a non-idling service policy. Further, the delay times for customers to move from one node to another must be taken into account. This covers some of the main features of models for emergency departments, namely priorities (triage) between patients. In the case of the tandem queue, by scaling the arrival rate and the number of servers by N, we obtain a renormalized process that converges to the solution of an ordinary differential equation (ODE) with boundary conditions. In the case of stability, we discuss the nature of this ODE as $t \to \infty$.

**Keywords:** Markov Process, Jackson Queueing Networks, Renormalization, ODE with Bound-
aries.

# 1 Introduction

The initial motivation for this article is the study of emergency departments (EDs). These are complex stochastic systems in which patients follow typical pathways within the ED and where various human resources intervene at each stage. See [1, section 2] for more details. We focus on the role of emergency physicians who examine patients at different stages, usually during the initial consultation and the final consultation before discharge, the latter taking place after certain diagnostic tests or nursing care have been provided to patients. The crucial question is the arrival rate that the ED can handle, based on what is known as the *emergency physician policy*, i.e., how physicians decide to schedule patients at different stages.

The basic underlying model is a tandem of two queues served by a pool of servers (the emergency physicians). Customers (patients) arrive at queue 1, are served (first consultation), then proceed to queue 2 for service (final consultation before discharge) and leave the system. The diagnostic tests, acting as set-up times (or delays) before the second queue, are taken into account by adding a $M/M/\infty$ queue between the two original ones.

Stability conditions, which are crucial issues, are obtained in Sections 2.1 and 2.2, for the two-queue tandem and for the version with intermediate delay. Although the transition rates of the Markov process are quite complex, the stability proof, in particular the choice of the Lyapunov function to apply Foster's criterion, seems quite natural.

<footnote>*INRIA Paris, 48 rue Barrault, 75013 Paris, France. Email: Guy.Fayolle@inria.fr</footnote>

<footnote>†INRIA Paris, 48 rue Barrault, 75013 Paris, France. E.mail: Christine.Fricker@inria.fr</footnote>
This idea is extended in Section 4 in order to construct a Lyapunov function allowing to derive the stability conditions for an open *Jackson network*, in which a pool of greedy servers move between queues.

The model considers a set of *N* queues where customers arrive in each queue, wait for being served and then move from one queue to another until they leave the system, as in a classic Jackson network. The crucial difference with such a network is that the queues are served by a pool of *M* servers serving one customer at a queue then moving instantaneously to another one according to a Markovian routing, as in a polling system, where the service policy would be called one-limited. Note that the switches are immediate, and one main feature of the service policy is that all servers not idle if there is a customer waiting somewhere, they are called *greedy*.

The main result is Theorem 4.3, saying that, in this inhomogeneous setting, the stability condition writes

$$ \sum_{i=1}^{N} \bar{\rho}_i < M, $$

with *M* the number of servers and, for $1 \le i \le N$, $\bar{\rho}_i = \bar{\lambda}_i/\mu_i$ where the $\bar{\lambda}_i$'s are the solution of the traffic equations of the associated Jackson network with arrival rate $\lambda_i$ and service rate $\mu_i$ at queue *i*. The proof is based on Foster's criterion with a linear Lyapunov function. This result is then extended in Section 5 to the case where customers are subject to a set-up time before joining a queue. Note that these set-up times can be simply modeled by adding to the previous *N* queues a set of $N^2$ queues with an infinite number of dedicated servers.

Section 2 is devoted to the stability condition of the tandem of queues. In Section 3, we turn our attention to the scaling limit of the state process. In Section 4, the study of stability is extended to open Jackson networks with greedy mobile servers. Next, Section 5 considers a generalization where customers experience delays (represented by additional $M/M/\infty$ queues) between network nodes.

## 2 The two-queue network in tandem

Two queues in tandem with infinite capacity are served by a poll of *M* servers. Customer arrivals take place at the first queue and form a Poisson process with intensity $\lambda$. A customer either waits in his queue or is served immediately if a server is available on arrival. The main assumption is that all servers must work whenever there are customers waiting. At each service completion time at queue $i \in \{1, 2\}$, the server who has finished serving decides either to stay at queue *i* with probability $q_i$, or to serve the other queue with probability $1 - q_i$. If there is no customer waiting in the chosen queue, the server immediately switches to the other queue if customers are waiting there, otherwise becomes available. Service times in queue *i* are independent and exponentially distributed with rates $\mu_i, i = 1, 2$.

### 2.1 Markovian evolution and stability conditions

The system evolves as a 3-dimensional Markov process $U = \{(X(t), Y(t), V(t)), t \ge 0\}$, letting, at time *t*, denote by

* $X(t)$ the number of customers in queue 1;

* $Y(t)$ the number of customers in queue 2;

* $V(t)$ the number of servers in queue 1.

According to the previous description, the state space belongs to a subset of $\mathbb{N}^3$, with specific constraints on the three coordinates, the most significant one being that, for $(i, j, k) \in \mathbb{N}^3$, necessarily $k \le M \wedge i$.

$U$ is endowed with the state space

$$ S = \{(i, j, k) \in \mathbb{N}^3, i + j \ge M, M - j \le k \le M \wedge i\} \cup \{(i, j, i) \in \mathbb{N}^2, i + j < M\}, $$
and, from $(i, j, k) \in S$, the following transitions can take place.

• For $i + j \ge M$, $M - j \le k \le M \land i$,

$$ (i, j, k) \rightarrow \begin{cases} (i+1, j, k) & \text{with rate } \lambda, \\ (i-1, j+1, k) & \text{with rate } q_1 k \mu_1 \mathbb{1}_{\{k<i\}}, \\ (i-1, j+1, k-1) & \text{with rate } k \mu_1 [(1-q_1)\mathbb{1}_{\{k<i\}} + \mathbb{1}_{\{k=i\}}], \\ (i, j-1, k+1) & \text{with rate } (M-k)\mu_2 [(1-q_2)\mathbb{1}_{\{M-k<j\}} + \mathbb{1}_{\{M-k=j\}}]\mathbb{1}_{\{k<i\}}, \\ (i, j-1, k) & \text{with rate } (M-k)\mu_2 [q_2 \mathbb{1}_{\{M-k<j, k<i\}} + \mathbb{1}_{\{k=i\}}]. \end{cases} \quad (2.1) $$

It is worth noting that these transitions contain simultaneous actions. For instance, the second and third transitions of (2.1) say that a customer is served at queue 1 and joins queue 2. This is the part $(i, j) \rightarrow (i-1, j+1)$ of the transitions. Then one of the $k$ servers at queue 1 has two possibilities:

(1) If $k < i$, he can remain in queue 1 with probability $q_1$, or join queue 2 with probability $1 - q_1$, since there are customers waiting in both queues.

(2) If $k = i$, he must be directed to queue 2 because there are enough servers attached to queue 1.

• For $i + j < M$,

$$ (i, j, i) \rightarrow \begin{cases} (i+1, j, i+1) & \text{with rate } \lambda, \\ (i-1, j+1, i-1) & \text{with rate } i\mu_1, \\ (i, j-1, i) & \text{with rate } j\mu_2. \end{cases} \quad (2.2) $$

Letting $A$ denote the generator of the process $U$, we have, for $u = (i, j, k)$ and $w = (i, j, i) \in S$,

$$ \begin{aligned} Af(u) = \mathbb{1}_{\{i+j>M\}} & [\lambda(f(u+e_1) - f(u)) + q_1 k \mu_1 \mathbb{1}_{\{k<i\}}(f(u-e_1+e_2) - f(u)) \\ & + k \mu_1 [(1-q_1)\mathbb{1}_{\{k<i\}} + \mathbb{1}_{\{k=i\}}](f(u-e_1+e_2-e_3) - f(u)) \\ & + (M-k)\mu_2 [(1-q_2)\mathbb{1}_{\{M-k<j\}} + \mathbb{1}_{\{M-k=j\}}]\mathbb{1}_{\{k<i\}}(f(u-e_2+e_3) - f(u)) \\ & + (M-k)\mu_2 (q_2 \mathbb{1}_{\{M-k<j, k<i\}} + \mathbb{1}_{\{k=i\}})(f(u-e_2) - f(u))] \\ & + \mathbb{1}_{\{i+j=M\}} [\lambda(f(w+e_1) - f(w)) + i\mu_1(f(w-e_1+e_2-e_3) - f(w)) \\ & + j\mu_2(f(w-e_2) - f(w))] \\ & + \mathbb{1}_{\{i+j<M\}} [\lambda(f(w+e_1+e_3) - f(w)) + i\mu_1(f(w-e_1+e_2-e_3) - f(w)) \\ & + j\mu_2(f(w-e_2) - f(w))]. \end{aligned} \quad (2.3) $$

The service policy is clearly of Stakhanovite type (!). The forward Kolmogorov's equations satisfied by the stationary probabilities $p(i, j, k)$ are written in Appendix B.

The forthcoming theorem establishes the conditions for system stability.

**Theorem 2.1.** Let $\rho_i = \lambda_i/\mu_i$, for $i = 1, 2$. Then the Markov process $U$ is

(i) ergodic if $\rho_1 + \rho_2 < M$,

(ii) transient if $\rho_1 + \rho_2 > M$.

*Proof.* The idea is to construct an ad hoc linear Lyapunov function for the discrete-time embedded Markov chain $\xi^{\text{def}} = \{\xi_m, m \ge 0\}$, which represents $U$ at jump instants. Then we will be in a position to apply Foster's criteria (for the ergodicity part) and other general theorems (for the transience part), see e.g. [5].

The Markov chain $\xi$ satisfies a recursive relationship of the form

$$ \xi_{m+1} = [\xi_m + \theta_{m+1}]^+, \quad (2.4) $$
where the distribution of $\theta_{n+1}$ depends only of the position of $\xi_m$ in the state space $S$.

We consider the linear function $L(u) = ax + by, u = (x, y, k) \in S$, where $a$ and $b$ are real constants. Then, in the region $x + y \ge M$, we can write

$$ \begin{aligned} \mathbb{E}[L(\xi_{m+1}) - L(\xi_m)/\xi_m = u] &= \frac{\lambda a + k\mu_1(-a+b) - (M-k)\mu_2 b}{\lambda + k\mu_1 + (M-k)\mu_2} \\ &= \frac{\lambda a - M\mu_2 b + k(b(\mu_1 + \mu_2) - \mu_1 a)}{\lambda + k\mu_1 + (M-k)\mu_2}. \end{aligned} \quad (2.5) $$

Choosing now $a = \mu_1 + \mu_2$ and $b = \mu_1$, (2.5) reduces to

$$ \mathbb{E}[L(\xi_{m+1}) - L(\xi_m)/\xi_m = u] = \frac{\mu_1 \mu_2 (\rho_1 + \rho_2 - M)}{\lambda + k\mu_1 + (M-k)\mu_2}. \quad (2.6) $$

Hence, outside the compact (finite) set $\{x + y \le M, k \le M\}$, $L(\xi_m)$ is

* either a positive supermartingale if $\rho_1 + \rho_2 < M$, in which case (by Foster's criterion quoted in the Appendix) the Markov chain $\{\xi_m\}$ is positive recurrent;

* or a positive submartingale if $\rho_1 + \rho_2 > M$ and, by Theorem A.1 quoted in the Appendix, $\xi$ is transient.

The proof of the Theorem is concluded. ■

## 2.2 Stability of the two-queue tandem network with intermediate delay

In fact, in a medical context, patients, after having been examined in the first station, must undergo an additional check before being admitted to the second station. This control procedure will be modeled by a $M/M/\infty$ queue (infinite number of exponential servers of rate $\mu$, corresponding to a pure delay) placed between the two queues of the preceding model.

Thus, we have now 3 queues in tandem, and the system can be viewed as a 4-dimensional Markov process denoted by $Z \stackrel{\text{def}}{=} \{X(t), W(t), Y(t), V(t), t \ge 0\}$, endowed with the state space

$$ \mathcal{D} = \{(x, w, y, k) \in \mathbb{N}^4, x + y \ge M, M - y \le k \le M \wedge x\} \cup \{(x, w, y, x) \in \mathbb{N}^4, x + y < M\}. $$

At time $t$,

* $X(t)$ the number of customers in the first $M/M/1$ queue,

* $W(t)$ the number of customers in the second $M/M/\infty$ queue,

* $Y(t)$ the number of customers in the third $M/M/1$ queue;

* $V(t)$ the number of servers in the first queue.

The expression for transitions is straightforward from (2.1)-(2.2) and is therefore omitted.

**Theorem 2.2.** The Markov process $Z$ is

(i) ergodic if $\rho_1 + \rho_2 < M$,

(ii) transient if $\rho_1 + \rho_2 > M$.

*Proof.* The arguments are identical to those used in Theorem 2.1, and it will be convenient to use the same notation as in (2.4), where $\xi_m$ stands now for the embedded Markov chain at jump times of the process $Z$.

For $u = (x, w, y, k) \in \mathcal{D}$, consider the linear function $G(u) = ax + cw + by$, where $a, b, c$ are real constants.
• For $x + y \ge M$,

$$ 
\begin{aligned}
\mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] &= \frac{\lambda a + k\mu_1(-a+c) + (b-c)\mu w - (M-k)\mu_2 b}{\lambda + k\mu_1 + \mu w + (M-k)\mu_2} \\
&= \frac{\lambda a - M\mu_2 b + k(\mu_1(c-a) + \mu_2 b) + (b-c)\mu w}{\lambda + k\mu_1 + \mu w + (M-k)\mu_2} \stackrel{\text{def}}{=} \frac{N_1(u)}{D_1(u)}. 
\end{aligned}
\quad (2.7) $$

• For $x + y < M$ (proceeding in this case as in (2.2),

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] = \frac{\lambda a + x\mu_1(-a+c) + (b-c)\mu w - \mu_2 y b}{\lambda + x\mu_1 + \mu w + y\mu_2} \stackrel{\text{def}}{=} \frac{N_2(u)}{D_2(u)}. \quad (2.8) $$

**Proof of (i) when** $\rho_1 + \rho_2 - M = -\delta < 0$.

Noting $u = (x, w, y, k)$ an arbitrary element of $\mathcal{D}$, we introduce the sets $E \stackrel{\text{def}}{=} \{u : x + y < M\}$, $F \stackrel{\text{def}}{=} \{u : w < w_0\}$. Since $k$ (the 4-th coordinate of $u$) is bounded by $M$, the set $H \stackrel{\text{def}}{=} E \cap F$ is finite, its complementary being $H^c = E^c \cup F^c = \{x + y \ge M\} \cup \{w \ge w_0\}$.

Fix now $a = \mu_1 + \mu_2$, $b = \mu_1$, $c = \mu_1 + \varepsilon$, where $\varepsilon$ is a positive real number. Then the respective numerators of (2.7) and (2.8) rewrite as

$$ 
\left\{ 
\begin{aligned}
N_1(u) &= -\delta\mu_1\mu_2 + \varepsilon(k\mu_1 - \mu w), \\
N_2(u) &= \lambda(\mu_1 + \mu_2) - \mu_1\mu_2(x + y) + \varepsilon(x\mu_1 - \mu w).
\end{aligned}
\right. 
\quad (2.9) $$

It is not difficult to check that, for $\varepsilon < \frac{\delta\mu_2}{M}$, $N_1(u)$ given in (2.9) is strictly negative, for all $w \ge 0$, $0 \le k \le M$. Noting in addition

$$ \lim_{w \to \infty} \frac{N_1(u)}{D_1(u)} = -\varepsilon, $$

we have shown that, for $u \in E^c$, there exists a real number $\theta_1 > 0$ satisfying

$$ \max_{w \ge 0} \frac{N_1(u)}{D_1(u)} \le -\theta_1 < 0. $$

The next step is to choose $u \in F^c$ and $w_0$ large enough to ensure the existence of a number $\theta_2 > 0$ such that, $\varepsilon$ being fixed,

$$ \max_{w \ge w_0} \frac{N_1(u)}{D_1(u)} \le -\theta_2 \quad \text{and} \quad \max_{w \ge w_0} \frac{N_2(u)}{D_2(u)} \le -\theta_2, $$

But this is immediate, since the above ratios are simple homographic functions in $w$.

Hence, we get, for $u \in H^c$,

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] < -\min(\theta_1, \theta_2) < 0, $$

and $\{\xi_m\}$ is ergodic by Foster's Theorem A.1.

**Proof of (ii) when** $\rho_1 + \rho_2 - M = \delta > 0$. Here we choose $a = \mu_1 + \mu_2$, $b = \mu_1$, $c = \mu_1 - \theta$, where $\theta < \mu_1$ is a positive real number to be fixed later. Then

$$ 
\left\{ 
\begin{aligned}
N_1(u) &= \delta\mu_1\mu_2 + \theta(\mu w - k\mu_1), \\
N_2(u) &= \lambda(\mu_1 + \mu_2) - \mu_1\mu_2(x + y) + \theta(\mu w - x\mu_1).
\end{aligned}
\right. 
\quad (2.10) $$

Proceeding as above, one checks that, when $\theta < \frac{\delta\mu_2}{M}$, the quantities $N_1(u)$, $N_2(u)$ are positive. Hence, for $u \in H^c$, there exists $\eta$

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] > \eta > 0, $$

and $G(\xi_m)$ is a submartingale outside the finite set $H$, which implies the transience of $\{\xi_m\}$ by Theorem 2.2.7 in [5]. The proof of the theorem is concluded. ■
### 3 Renormalization of the two-queue system

It seems hopeless to derive a tractable analytic solution of the Kolmogorov's equations stated in Section B. For this reason, and in order to identify some salient features of the system, we propose to analyze a renormalized rescaled version of the process U defined in Section 2.1.

For each $n \ge 1$, let $U_n$ be the process obtained from U after replacing $\lambda$ by $n\lambda$ and $M$ by $nM$, and consider the process

$$Z_n(t) \stackrel{\text{def}}{=} \frac{U_n(t)}{n}, \quad t \ge 0. \qquad (3.1)$$

It is worth noting that the processes $Z_n(t)$, $n \ge 1$, have all the same ergodicity condition $\rho_1 + rho_2 < M$. We intend to show that $Z_n$ converges in distribution to a Markov process Z to be characterized later. Let $\mathcal{E}_n \stackrel{\text{def}}{=} \{s/n : s = (i, j, k) \in \mathcal{S}\}$, and $C_c^k(\mathbb{E})$ denote the class of k-times continuously differentiable functions with compact support on some metric space $\mathbb{E}$. Then, for any $z = (x, y, v) \in \mathcal{E}_n$,

$$T_n(t)f(z) = \mathbb{E}[f(Z_n(t))|Z_n(0) = z]$$

defines a semigroup $T_n(t)$ on $C^1(\mathcal{E}_n)$ with generator $G_n$ of the form (immediate from (2.3))

$$\begin{aligned} G_n f(z) = {}& \mathbb{1}_{\{x+y \ge M\}} \left[ \begin{aligned}[t] & n\lambda(f(z + e_1/n) - f(z)) + nq_1v\mu_1 \mathbb{1}_{\{v<x\}}(f(z - e_1/n + e_2/n) - f(z)) \\ & + nv\mu_1[(1 - q_1)\mathbb{1}_{\{v<x\}} + \mathbb{1}_{\{v=x\}}](f(z - e_1/n + e_2/n - e_3/n) - f(z)) \\ & + n(M - v)\mu_2[(1 - q_2)\mathbb{1}_{\{M-v<y\}} + \mathbb{1}_{\{M-v=y\}}]\mathbb{1}_{\{v<x\}}(f(z - e_2/n + e_3/n) - f(z)) \\ & + n(M - v)\mu_2(q_2\mathbb{1}_{\{M-v<y, v<x\}} + \mathbb{1}_{\{v=x\}})(f(z - e_2/n) - f(z)) \end{aligned} \right] \\ & + \mathbb{1}_{\{x+y<M, v=x\}} \left[ \begin{aligned}[t] & n\lambda(f(z + e_1/n + e_3/n) - f(z)) \\ & + nx\mu_1(f(z - e_1/n + e_2/n - e_3/n) - f(z)) + ny\mu_2(f(z - e_2/n) - f(z)) \end{aligned} \right]. \end{aligned} \qquad (3.2)$$

Letting now $n \to \infty$ in (3.2), for all $f \in C_c^1(\mathbb{E}^3)$, the set of real valued functions with bounded derivatives, a Taylor expansion yields directly

$$\lim_{n \to \infty} \sup_{z \in \mathcal{E}_n} |G_n f(z) - Gf(z)| = 0, \qquad (3.3)$$

where

$$\begin{aligned} Gf(z) = {}& \mathbb{1}_{\{x+y \ge M\}} \left[ \begin{aligned}[t] & \lambda f_x'(z) + q_1\mu_1 v \mathbb{1}_{\{v<x\}}(-f_x'(z) + f_y'(z)) \\ & + \mu_1 v \left( (1 - q_1) \mathbb{1}_{\{v<x\}} + \mathbb{1}_{\{v=x\}} \right) (-f_x'(z) + f_y'(z) - f_v'(z)) \\ & + \mu_2(M - v) \left( (1 - q_2) \mathbb{1}_{\{M-v<y\}} + \mathbb{1}_{\{M-v=y\}} \right) \mathbb{1}_{\{v<x\}}(-f_y'(z) + f_v'(z)) \\ & - \mu_2(M - v) \left( q_2 \mathbb{1}_{\{M-v<y, v<x\}} + \mathbb{1}_{\{v=x\}} \right) f_y'(z) \end{aligned} \right] \\ & + \mathbb{1}_{\{x+y < M, v=x\}} \left[ \begin{aligned}[t] & \lambda(f_x'(z) + f_v'(z)) + \mu_1 x(-f_x'(z) + f_y'(z) - f_v'(z)) - \mu_2 y f_y'(z) \end{aligned} \right], \end{aligned}$$

which can be rewritten as

$$\begin{aligned} Gf(z) = {}& \mathbb{1}_{\{x+y \ge M\}} \left[ \begin{aligned}[t] & (\lambda - \mu_1 v) f_x'(z) + (\mu_1 v - \mu_2(M - v)) f_y'(z) \\ & + \left( \mathbb{1}_{\{v<x, M-v<y\}} \left( (q_1 - 1)\mu_1 v + (1 - q_2)\mu_2(M - v) \right) \right. \end{aligned} \right. \\ & \left. - \mathbb{1}_{\{v=x\}}\mu_1 v + \mathbb{1}_{\{v<x, M-v=y\}} \left( (q_1 - 1)\mu_1 v + \mu_2(M - v) \right) \right) f_v'(z) \right] \\ & + \mathbb{1}_{\{x+y < M, v=x\}} \left[ \begin{aligned}[t] & (\lambda - \mu_1 x) f_x'(z) + (\mu_1 x - \mu_2 y) f_y'(z) + (\lambda - \mu_1 x) f_v'(z) \end{aligned} \right]. \end{aligned} \qquad (3.4)$$

Clearly $e^{tG_n}$ is a Feller semigroup on $C(\mathbb{R}^3)$ and

$$\lim_{n \to \infty} e^{tG_n} = \lim_{n \to \infty} T_n(t)f = T(t)f = e^{tG}, \qquad (3.5)$$

where $T(t)$ is a strongly continuous positive contraction semigroup. This is a direct consequence of Theorem A.4, since it is enough to show (3.3) for each $f$ belonging to a core $\mathcal{D}$ of $G$, here the set of functions $f \in C_c^1(\mathbb{R}^3)$.
Let $D_S[0, \infty]$ denote the space of right continuous $S$-valued functions with left limits endowed with the Skorohod topology. Then, assuming that $Z_n(0)$ has a limit distribution, there exists a Markov process $Z$ with sample paths in $D_S[0, \infty]$ and generator $G$, such that $Z_n \Rightarrow Z$ (weak convergence).

Consider the following differential system satisfied by $z(t) = (x(t), y(t), v(t))$ (ad libitum we shall often omit the argument $t$), subject to a given initial condition $z(0)$:

(a) If $x + y \ge M$, then

$$ \left\{ \begin{aligned} \dot{x} &= \lambda - \mu_1 v, \\ \dot{y} &= \mu_1 v - \mu_2 (M - v), \end{aligned} \right. \qquad \left\{ \begin{aligned} (q_1 - 1)\mu_1 v + (1 - q_2)\mu_2 (M - v) &\quad \text{if } v < x, M - v < y, \\ -\mu_1 v &\quad \text{if } v = x, \\ (q_1 - 1)\mu_1 v + \mu_2 (M - v) &\quad \text{if } v < x, M - v = y. \end{aligned} \right. \qquad (3.6) $$

(b) If $x + y < M$, then

$$ \left\{ \begin{aligned} \dot{x} &= \dot{v} = \lambda - \mu_1 x, \\ \dot{y} &= \mu_1 x - \mu_2 y. \end{aligned} \right. \qquad (3.7) $$

It is immediate to check (we omit some classical arguments) that the one-parameter family $\{S(t), t \ge 0\}$ of operators piecewise $C^1(\mathbb{R}^3)$, defined by

$$ S(t)f(z(0)) = f(z(t)) $$

is a strongly continuous positive contraction semigroup, which coincides with $T(t)$ and is generated by $G$. Rewriting the system (3.6)-(3.7) in the form

$$ \dot{z}(t) = F(z(t)), $$

the chief difficulty here lies in the fact that the function $F(\cdot)$ does not satisfy a global Lipschitz condition in its domain of definition (see e.g. [6]).

In the following theorem, the stability condition is supposed to be satisfied.

**Theorem 3.1.** Let $\rho_1 + \rho_2 < M$, $z(0) = (x(0), y(0), v(0)) \in \mathbb{R}_+^3$ and assume that the distribution of $Z_n(0)$ converges weakly to $\delta_{z(0)}$, where $\delta_{z(t)}$ denotes the Dirac measure. Then $\delta_{z(t)}$, the limiting distribution of $Z_n(t)$, has the following properties up to a null set with respect to the Lebesgue measure.

Assume $x(0) + y(0) < M$, $v(0) = x(0)$, and either of the three following conditions holds:

$$ (x(0) \ge \rho_1, y(0) \ge \rho_2), \quad (x(0) \le \rho_1, y(0) \ge \rho_2), \quad (x(0) \le \rho_1, y(0) \le \rho_2). $$

Then $0 < x(t) + y(t) < M, \forall t \ge 0$, with

$$ \left\{ \begin{aligned} x(t) &= \rho_1 + (x(0) - \rho_1)e^{-\mu_1 t}, \\ y(t) &= \left\{ \begin{aligned} &\frac{(x(0) - \rho_1)\mu_1 e^{-\mu_1 t}}{\mu_2 - \mu_1} + \left(y(0) - \rho_2 - \frac{(x(0) - \rho_1)\mu_1}{\mu_2 - \mu_1}\right)e^{-\mu_2 t} + \rho_2, & \quad \text{if } \mu_1 \neq \mu_2 \\ &\left(x(0) - \rho_1)\mu_1 t e^{-\mu_1 t} + (y(0) - \rho_2)e^{-\mu_2 t} + \rho_2, & \quad \text{if } \mu_1 = \mu_2 \end{aligned} \right. \\ v(t) &= x(t), \end{aligned} \right. \qquad (3.8) $$

and

$$ \lim_{t \to \infty} z(t) = (\rho_1, \rho_2, \rho_1). \qquad (3.9) $$

*Proof.* The solution (3.8) follows directly from (3.7) and yields in turn

$$ x(t) + y(t) = \rho_1 + \rho_2 + (x(0) - \rho_1) \left( \frac{\mu_2 e^{-\mu_1 t} - \mu_1 e^{-\mu_2 t}}{\mu_2 - \mu_1} \right) + (y(0) - \rho_2) e^{-\mu_2 t}. \qquad (3.10) $$
**Fact 1:** When $(x(0) \ge \rho_1, y(0) \ge \rho_2)$, (3.10) immediately implies that $x(t) + y(t)$ is a decreasing function of $t$, whence

$$ \rho_1 + \rho_2 \le x(t) + y(t) \le x(0) + y(0) < M, \forall t \ge 0. $$

**Fact 2:** Conversely, if $(x(0) \le \rho_1, y(0) \le \rho_2)$, then

$$ M > \rho_1 + \rho_2 \ge x(t) + y(t) \ge x(0) + y(0), \forall t \ge 0. $$

**Fact 3:** If $(x(0) \le \rho_1, y(0) \ge \rho_2)$, the same conclusion holds, just remarking by (3.7) that $\dot{x}(t) + \dot{y}(t)$ is negative at $t = 0$ and has at most one zero on $[0, \infty]$.

Since (3.9) is immediate by letting $t \to \infty$ in (3.8), the proof of the theorem is concluded. ■

In the previous theorem, we did not take into account the other two possibilities described below.

**Lemma 3.2.** Assume $x(0) + y(0) < M$ and $(x(0) \ge \rho_1, y(0) \le \rho_2)$.

(1.1) If

$$ \mu_2 > \mu_1 \text{ or } \left( \mu_2 < \mu_1 \text{ and } \frac{(\mu_2 - \mu_1)(y(0) - \rho_2)}{\mu_1(x(0) - \rho_1)} < 1 \right), \quad (3.11) $$

and

$$ (x(0) - \rho_1) \left( 1 + \frac{(\mu_2 - \mu_1)(\rho_2 - y(0))}{\mu_1(x(0) - \rho_1)} \right)^{-\frac{\mu_1}{\mu_2 - \mu_1}} \ge M - \rho_1 - \rho_2, \quad (3.12) $$

then there exists an exit time $t_e$, function of $z(0)$, such that $x(t_e) + y(t_e) = M$.

(1.2) Otherwise, $0 < x(t) + y(t) < M, \forall t \ge 0$.

*Proof.* When $(x(0) \ge \rho_1, y(0) \le \rho_2)$, the situation is slightly more complex and requires careful analysis. Here, the quantity $\dot{x}(t) + \dot{y}(t)$ is positive at $t = 0$ and, from a direct integration of (3.7), may eventually cancel out at a single instant $t_0$, the unique real root of the equation

$$ 1 - e^{(\mu_2 - \mu_1)t_0} = \frac{(\mu_2 - \mu_1)(y(0) - \rho_2)}{\mu_1(x(0) - \rho_1)}, \quad (3.13) $$

which exists when condition (3.11) holds.

Adding the two equations of system (3.7) together, we immediately obtain $y(t_0) = \rho_2$. Hence, the inequality $x(t) + y(t) \ge M$ will eventually hold at some instant $t$ if, and only if, the inequality (3.12)), rewritten in the form

$$ \rho_1 + \rho_2 + (x(0) - \rho_1)e^{-\mu_1 t_0} \ge M, $$

is satisfied, as well as condition (3.11).

**Conjecture 3.3.** When $x(0) + y(0) \ge M$, there exists a time $t_0$, function of $z(0)$, such that $x(t) + y(t) < M$ for $t \ge t_0$ and that the assumptions of Theorem 3.1 are satisfied, thus guaranteeing in particular the limit (3.9).

To illuminate the conjecture, we suppose now $x(0) + y(0) \ge M$, so that $z(t)$ starts being governed by system (3.6). The following straightforward assertions hold.

* If $v(0) = x(0)$, then the system $\{v = x, \dot{x} = \lambda - \mu_1 v, \dot{v} = -\mu_1 v\}$ cannot hold on a set of positive Lebesgue measure. Immediate, since this would imply $\lambda = 0$.
• If $v(0) < x(0), y(0) + v(0) = M$, then the system

$$ \begin{cases} M = y + v, \\ \dot{y} = \mu_1 v - \mu_2(M - v), \\ \dot{v} = (q_1 - 1)\mu_1 v + \mu_2(M - v), \end{cases} \qquad (3.14) $$

obtained by instantiating $M = v + y$ in (3.6) cannot hold on a set of positive Lebesgue measure, except in the particular case $q_1 = 0$. Indeed, summing the last two equations of (3.14) gives

$$ \dot{y} + \dot{v} = 0 = q_1 \mu_1 v. $$

Thus, assuming $q_1 = 0$ and combining the first equation of (3.6) with (3.14), we get immediately

$$ x(t) + y(t) = At + B(e^{-(\mu_1+\mu_2)t} - 1) + x(0) + y(0), \qquad (3.15) $$

where $A = \lambda - \frac{\mu_1 \mu_2 M}{\mu_1 + \mu_2}$ and $B = \left(v(0) - \frac{\mu_2 M}{\mu_1 + \mu_2}\right) \frac{\mu_2}{\mu_1 + \mu_2}$.

Since the condition $\rho_1 + \rho_2 < M$ is exactly equivalent to $A < 0$, equation (3.15) shows the existence of a time $t_1$ for which $x(t_1) + y(t_1) < M$, letting $z(t)$ enter the region $\{x + y < M\}$ in which it stays for ever.

The final step is to consider the region $v < x, M - v < y$, comprising the initial condition $z(0)$ and corresponding to the evolution of the first three equations of (3.6), rewritten as

$$ \begin{cases} \dot{x} = \lambda - \mu_1 v, \\ \dot{y} = \mu_1 v - \mu_2 (M - v), \\ \dot{v} = ((q_1 - 1)\mu_1 + (q_2 - 1)\mu_2)v + \mu_2(1 - q_2)M. \end{cases} \qquad (3.16) $$

In particular, setting $a = (1 - q_1)\mu_1 + (1 - q_2)\mu_2$, $b = (1 - q_2)\mu_2 M$, we get

$$ v(t) = \frac{b}{a} + \left(v(0) - \frac{b}{a}\right) e^{-at}, \quad t \ge 0, $$

highlighting the boundedness of $v$. Furthermore, a linear combination of the first two equations of system (3.16) yields

$$ (\mu_1 + \mu_2)\dot{x} + \mu_1 \dot{y} = \mu_1 \mu_2 (\rho_1 + \rho_2 - M), \qquad (3.17) $$

together with

$$ \begin{cases} x(t) = Kt + \frac{\mu_1}{a} \left(v(0) - \frac{b}{a}\right) (e^{-at} - 1) + x(0), \\ x(t) + y(t) = Lt + \frac{\mu_2}{a} \left(\frac{b}{a} - v(0)\right) (e^{-at} - 1) + x(0) + y(0), \end{cases} \qquad (3.18) $$

where

$$ K = \lambda - \frac{\mu_1 \mu_2 M (1 - q_2)}{(1 - q_1) \mu_1 + (1 - q_2) \mu_2}, \quad L = \lambda - \frac{\mu_1 \mu_2 M (1 - q_1)}{(1 - q_1) \mu_1 + (1 - q_2) \mu_2}. $$

Concerning the constants $K$ and $L$, a simple algebra shows that there are only three possible scenarios when the system is ergodic:

(i) $(K < 0, L > 0)$, implying $q_1 > q_2$;

(ii) $(K > 0, L < 0)$, implying $q_1 < q_2$;

(iii) $(K < 0, L < 0)$.

Since the right-hand side of (3.17) is negative, the sum $(\mu_1 + \mu_2)x(t) + \mu_1 y(t)$ is a decreasing function. Hence, upon combining with (3.18), there exists a time $t_0$ after which
* either $x$ decreases sharply, until it reaches the boundary $x = v$ ($K < 0, L > 0$);

* or $y$ decreases sharply, until it reaches the boundary $y = M - v$ ($K > 0, L < 0$).

To go further, in particular to obtain (3.9), two avenues can be explored.

* A probabilistic approach, based on the following argument. Indeed, as previously remarked, the processes $Z_n, n \ge 1$, have the same ergodicity conditions, independent of $n$. Hence, with probability one, $Z_n$ will visit any compact set with states of the form

$$z_n = (i_n/n = x, j_n/n = y, v_n/n = v),$$

where $z = (x, y, v)$ is a vector of positive rational numbers. In particular, $z$ could be chosen to satisfy the conditions of Theorem 3.1.

* A purely analytic method, possibly using the concept of differential inclusion for system (3.6), see e.g. [6];

## 4 Ergodicity conditions for open Jackson networks with greedy servers

The model considered in this section can be viewed as a modified stochastic network of Jackson type with $N$ queues, where a fixed pool of servers moves to find work. As in a standard open Jackson networks, customers arrive and require a service time independently in each queue. In the following, arrival and service rates in queue $i$ are denoted by $\lambda_i$ and $\mu_i$, respectively. $1 \le i \le N$. After completing service at some queue, a customer may either move to another queue according to a routing matrix $P = (p_{ij})$, or leave the system. More precisely, a customer at queue $i$ goes to queue $j$ with probability $p_{ij}$ or leaves the system with probability $1 - p_{i1} - \dots - p_{iN}$. It will be convenient to denote this last quantity by $p_{i0}$ ($p_{00} = 1$) and $\lambda_i / \sum_{j=1}^N \lambda_j$ by $p_{0i}$.

Thus, $P$ is a stochastic matrix and in the following we assume that the Markov chain on $\{0, \dots, N\}$ associated with $P$ is transient, with a single absorbing state 0. This condition relies on classical results and will be called **Condition J**, as in [5, p. 63].

The difference in terms of service policy compared to a classical Jackson network is that there is a pool of $M$ servers moving among the queues according to a non-idling policy. This is why servers are called greedy. The switch is immediate and several servers can handle the same queue. The following non-idling routing policy is important.

**Definition 4.1. The q-policy.** Let the matrix $q = (q_{ij})$ be irreducible. From queue $i$, a server joins queue $j$ with probability $q_{ij}$ at infinite speed, and continues until a queue with a waiting customer is found; and if there are no more customers waiting in the system at service completion time, the corresponding server becomes idle.

For $i = 1, \dots, N$ and $t \ge 0$, let $X(t) = (X_1(t), \dots, X_N(t))$ where $X_i(t)$ is the number of customers present in queue $i$ at time $t$, and $V(t) = (V_1(t), \dots, V_N(t))$ where $V_i(t)$ is the number of servers serving queue $i$ at time $t$. The process

$$U = \{(X(t), V(t)), t \ge 0\}$$

is a Markov process with state space

$$S = \left\{ \begin{array}{l} u = (x, v) \in \mathbb{N}^{2N}, \forall i, v_i \le x_i, \sum_{i=1}^{N} v_i = M, \sum_{i=1}^{N} x_i \ge M \\ \cup \left\{ (x, x) \in \mathbb{N}^{2N}, \sum_{i=1}^{N} x_i < M \right\} \end{array} \right\}$$

where $x = (x_1, \dots, x_N)$ and $v = (v_1, \dots, v_N)$. For $u = (x, v) \in S$, let us define

$$A(u) = \{l : v_l < x_l, 1 \le l \le N\}$$
which stands for the set of queues where customers are waiting for service.

To write the transitions, we have to formalize the moving policy of the greedy servers. For that, let us give the following additional definition.

**Definition 4.2.** When the system is in state $u$, let $r_{ijk}(u)$ denote the probability for a server after serving queue $i$ to move to queue $j$, when the customer who has just been served joined queue $k$. Similarly, $r_{ij0}(u)$ stands for the same probability when the customer leaves the system.

Note that in the first case $r_{ijk}(u)$ is the probability of entering $A(u - e_i - f_i + e_k)$ at $j$, and $A(u - e_i - f_i + e_k) \neq \emptyset$ since a customer just served is waiting for service at queue $k$. This gives

$$ \sum_{j \in A(u - e_i - f_i + e_k)} r_{ijk}(u) = 1. \qquad (4.1) $$

and

$$ \sum_{j \in A(u - e_i - f_i)} r_{ij0}(u) = \mathbb{1}_{\{A(u - e_i - f_i) \neq \emptyset\}}. \qquad (4.2) $$

Let $e = (e_1, \dots, e_N)$, $f = (f_1, \dots, f_N)$ and $(e, f)$ the canonical basis of $\mathbb{R}^{2N}$. The transitions from an arbitrary state $u = (x, v) \in S$ are as follows.

* For $\sum_{i=1}^N x_i \geq M$,

$$ u = (x, v) \rightarrow \begin{cases} u + e_i & \text{with rate } \lambda_i, \\ u - e_i + e_k - f_i + f_j & \text{with rate } \mu_i v_i r_{ijk}(u) p_{ik}, \quad k \geq 1, \\ u - e_i - f_i + f_j & \text{with rate } \mu_i v_i r_{ij0}(u) p_{i0} \text{ if } A(u - e_i - f_i) \neq \emptyset, \\ u - e_i - f_i & \text{with rate } \mu_i v_i p_{i0} \text{ otherwise.} \end{cases} $$

* For $\sum_{i=1}^N x_i < M$,

$$ (x, x) \rightarrow \begin{cases} (x, x) + e_i + f_i & \text{with rate } \lambda_i, \\ (x, x) - e_i - f_i + e_k + f_k & \text{with rate } \mu_i x_i p_{ik}, \\ (x, x) - e_i - f_i & \text{with rate } \mu_i x_i p_{i0}. \end{cases} $$

Under **Condition J** mentioned above, the system

$$ \bar{\lambda}_i = \lambda_i + \sum_{j=1}^{N} \bar{\lambda}_j p_{ji}, \quad 1 \leq i \leq N, \qquad (4.3) $$

usually referred to as the system of traffic equations, has a unique solution which is strictly positive. To prove this, it suffices to remark that the equations are equivalent to (see e.g. [5, p. 63]),

$$ \bar{\lambda}_i = \sum_{j=1}^{N} \lambda_j m_{ji}, \quad 1 \leq i \leq N, $$

where $m_{ji}$ stands for the mean number of visits to $i$ starting from $j$, which is finite from **Condition J**.

Letting $\bar{\rho}_i$ denote the ratio $\bar{\lambda}_i/\mu_i$, the following theorem holds.

**Theorem 4.3.** *The Markov process U is*

(i) ergodic if $\sum_{i=1}^{N} \bar{\rho}_i < M,$
(ii) transient if $\sum_{i=1}^{N} \bar{\rho}_i > M$.

*Proof.* As in Theorem 2.1, $\xi_m$ stands for the embedded Markov chain at the jump times of the process $U$.

For $u \in S$, consider the linear function $L(u) \stackrel{\text{def}}{=} \sum_{i=1}^{N} a_i x_i$, where the $a_i$'s are real numbers. For $\sum_{i=1}^{N} x_i \ge M$, we have

$$ \mathbb{E}[L(\xi_{m+1}) - L(\xi_m)/\xi_m = u] = \frac{\sum_{i=1}^{N} \left( \lambda_i a_i + \sum_{k=1}^{N} \mu_i v_i (-a_i + a_k) p_{ik} - \mu_i v_i a_i p_{i0} \right)}{\sum_{i=1}^{N} \lambda_i + \sum_{i=1}^{N} \mu_i v_i} \stackrel{\text{def}}{=} \frac{A(u)}{B(u)}. $$

Now, using the fact that if $\sum_{i=1}^{N} x_i \ge M$ then all servers are busy (i.e. $\sum_{i=1}^{N} v_i = M$), the numerator $A(u)$ can be rewritten as

$$ \begin{aligned} A(u) &= \sum_{i=1}^{N} \lambda_i a_i + \sum_{i=1}^{N} \mu_i v_i \left( -a_i + \sum_{k=1}^{N} a_k p_{ik} \right) \\ &= \sum_{i=1}^{N} \lambda_i a_i + \sum_{i=1}^{N-1} \mu_i v_i \left( -a_i + \sum_{k=1}^{N} a_k p_{ik} \right) + \mu_N \left( M - \sum_{i=1}^{N-1} v_i \right) \left( -a_N + \sum_{k=1}^{N} a_k p_{Nk} \right) \\ &= \sum_{i=1}^{N} \lambda_i a_i + \mu_N M \left( -a_N + \sum_{k=1}^{N} a_k p_{Nk} \right) + \sum_{i=1}^{N-1} v_i \left[ \mu_i \left( -a_i + \sum_{k=1}^{N} a_k p_{ik} \right) - \mu_N \left( -a_N + \sum_{k=1}^{N} a_k p_{Nk} \right) \right]. \end{aligned} \quad (4.4) $$

Canceling the factor of $v_i$ in $A(u)$, for $1 \le i \le N$, amounts to finding quantities ($a_i$) satisfying

$$ \frac{1}{\mu_i} = a_i - \sum_{k=1}^{N} a_k p_{ik}, \quad 1 \le i \le N. \quad (4.5) $$

The system (4.5) admits a unique solution ($a_i$), since the matrix $I - P$ is invertible. Moreover, for all $1 \le i \le N$, $a_i > 0$, this choice for the $a_i$'s cancels out of the last sum on the right-hand side of (4.4). Plugging the traffic equations (4.3) and (4.5) repeatedly in (4.4), $A(u)$ becomes

$$ \begin{aligned} A(u) &= \sum_{i=1}^{N} \lambda_i a_i + \mu_N M \left( -a_N + \sum_{k=1}^{N} p_{Nk} a_k \right) \\ &= \sum_{i=1}^{N} \left( \bar{\lambda}_i - \sum_{j=1}^{N} \bar{\lambda}_j p_{ji} \right) a_i + \mu_N M \left( -a_N + \sum_{k=1}^{N} p_{Nk} a_k \right) \\ &= \sum_{j=1}^{N} \bar{\lambda}_j \left( a_j - \sum_{i=1}^{N} p_{ji} a_i \right) + \mu_N \left( -a_N + \sum_{k=1}^{N} p_{Nk} a_k \right) M \\ &= \sum_{j=1}^{N} \bar{\lambda}_j \frac{\mu_N}{\mu_j} \left( a_N - \sum_{k=1}^{N} p_{Nk} a_k \right) + \mu_N \left( -a_N + \sum_{k=1}^{N} p_{Nk} a_k \right) M \\ &= \sum_{j=1}^{N} \bar{\rho}_j - M. \end{aligned} \quad (4.6) $$

Finally, for all $u$ outside the finite set $\{\sum_{i=1}^{N} x_i < M, \sum_{i=1}^{N} v_i \le M\}$, we have

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] = \frac{\sum_{j=1}^{N} \bar{\rho}_j - M}{\sum_{i=1}^{N} \lambda_i + \sum_{i=1}^{N} \mu_i v_i}, $$
and the end of the proof is in every respect analogous to that of Theorem 2.1.

**An example of a greedy server policy.** For the q-policy previously described, for fixed $u$, $r_{ij}(u)$ is the probability that the Markov chain in $\{1, \dots, N\}$, with transition matrix $q$, starting from $i$ enters the set $A(u)$ at $j$. If $q_{ij} > 0$ for all $i, j$, then

$$r_{ij}(u) = \frac{q_{ij} \mathbb{1}_{\{j \in A(u)\}}}{\sum_{l \in A(u)} q_{il}},$$

with the convention that $r_{ij}(u) = 0$ if $A(u) = \emptyset$. The basic model of Section 2 fits into this framework driven by the q-policy with

$$P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, \quad Q = \begin{pmatrix} q_1 & 1-q_1 \\ 1-q_2 & q_2 \end{pmatrix},$$

with an explicit expression,

$$r_{ij}(u) = \left( q_{ij} + \frac{1}{|A(u)|} \sum_{l \in A(u)} q_{il} \mathbb{1}_{\{l \notin A(u)\}} \right) \mathbb{1}_{\{j \in A(u)\}}, \quad (4.7)$$

since $|A(u)| \le 1$ ($N = 2$). Note that $r(u)$ is defined even when $q$ is neither positive nor irreducible. This definition means that after completing its service at queue $i$, the server moves to some queue $j$ chosen uniformly among the queues with waiting customers, if there is one, otherwise the server becomes idle. For $u$ with $A(u) \ne \emptyset$, using (4.7), $r$ satisfies

$$\sum_{j \in A(u)} r_{ij}(u) = \sum_{j \in A(u)} q_{ij} + \sum_{l \notin A(u)} q_{il} = 1,$$

which is consistent with equations (4.1) and (4.2). By performing a careful calculation, we can verify that the transitions of the first model given in Section 2.1 are a special case of the above transitions.

# 5 Ergodicity conditions for open Jackson networks with greedy servers and intermediate delays for customers

In this section, to simplify the notation, all indices range from 1, ..., N, unless otherwise specified. The model differs from the previous one only in that, to move from node $i$ to node $j$, the customer needs an amount of time exponentially distributed with parameter denoted by $\mu_{[ij]}$.

The model is still a Jackson network with $N^2 + N$ nodes:

* $N$ nodes with $M$ servers moving among the $N$ nodes according to the greedy policy,

* $N^2$ nodes which are infinite-server queues with service rate $\mu_{[ij]}$ for nodes $[ij]$.

Let now $U$ denote the process

$$U = \left\{ \left( (X_i(t))_i, (V_i(t))_i, (W_{[ij]}(t))_{i,j}, t \ge 0 \right) \right\}$$

where, at time $t$,

* $X_i(t)$ is the number of customers in queue $i$,

* $V_i(t)$ is the number of active servers in queue $i$,

* $W_{[ij]}(t)$ is the number of customers transitioning from queue $i$ to queue $j$.
The process U is a Markov process with state space

$$ \mathcal{S} = \left\{ \begin{array}{l} u = ((x_i)_i, (v_i)_i, (w_{[ij]})_{i,j}) \in \mathbb{N}^{2N+N^2}, \forall i, v_i \le x_i, \sum_i v_i = M, \sum_i x_i \ge M \\ \cup \left\{ (x, x, w) = ((x_i)_i, (x_i)_i, (w_{[ij]})_{i,j}) \in \mathbb{N}^{2N+N^2}, \sum_i x_i < M \right\} \end{array} \right\} $$

and, denoting by $\{(e_i)_i, (f_i)_i, (e_{[ij]})_{i,j}\}$ the canonical basis of $\mathbb{R}^{2N}$, the transitions from an arbitrary state $u = (x, v, w) \in \mathcal{S}$ are as follows.

* For $\sum_i x_i > M$,

$$ u \to u + \begin{cases} e_i & \text{with rate } \lambda_i, \\ -e_i - f_i + e_{[ik]} + f_j & \text{with rate } \mu_i v_i r_{ij0}(u) p_{ik}, \\ -e_i - f_i + f_j & \text{with rate } \mu_i v_i r_{ij0}(u) p_{i0}, \\ -e_{[ik]} + e_k & \text{with rate } w_{[ik]} \mu_{[ik]}. \end{cases} $$

* For $\sum_i x_i = M$,

$$ (x, x, w) \to (x, x, w) + \begin{cases} e_i & \text{with rate } \lambda_i, \\ -e_i - f_i + e_{[ik]} & \text{with rate } \mu_i x_i p_{ik}, \\ -e_i - f_i & \text{with rate } \mu_i x_i p_{i0}, \\ -e_{[ik]} + e_k + f_k & \text{with rate } w_{[ik]} \mu_{[ik]}. \end{cases} $$

* For $\sum_i x_i < M$,

$$ (x, x, w) \to (x, x, w) + \begin{cases} e_i + f_i & \text{with rate } \lambda_i, \\ -e_i - f_i + e_{[ik]} & \text{with rate } \mu_i x_i p_{ik}, \\ -e_i - f_i & \text{with rate } \mu_i x_i p_{i0}, \\ -e_{[ik]} + e_k + f_k & \text{with rate } w_{[ik]} \mu_{[ik]}. \end{cases} $$

The model described in Section 2.2 is an example of this model with $N = 2$,

$$ P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, \quad Q = \begin{pmatrix} q_1 & 1 - q_1 \\ 1 - q_2 & q_2 \end{pmatrix} $$

and the $r_{ij0}$'s are defined in (4.2).

With $\bar{\rho}_i = \bar{\lambda}_i / \mu_i$ as in Theorem 4.3, we have the following.

**Theorem 5.1.** The Markov process U is

(i) ergodic if $\sum_{i=1}^N \bar{\rho}_i < M$,

(ii) transient if $\sum_{i=1}^N \bar{\rho}_i > M$.

where the $\bar{\rho}_i$'s are as in Theorem 4.3.

*Proof.* The arguments are identical to those used in Theorem 4.3, and it will be convenient to use the same notation as in (2.4), where $\xi_m$ stands for the embedded Markov chain at jump times of the process U.
For $u \in S$, consider the linear function $G(u) \stackrel{\text{def}}{=} \sum_{i} a_{i}x_{i} + \sum_{i,j} b_{ij}w_{[ij]}$, where $a_i$ and $b_{ij}$ are real numbers.

* For $\sum_{i=1}^{N} x_i \ge M$,

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] = \frac{\sum_i \left( \lambda_i a_i + \sum_k \mu_i v_i (-a_i + b_{ik}) p_{ik} - \mu_i v_i a_i p_{i0} + \sum_l \mu_{[li]} w_{[li]} (-b_{li} + a_i) \right)}{\sum_i \lambda_i + \sum_i \mu_i v_i + \sum_{i,l} \mu_{[li]} w_{[li]}} \stackrel{\text{def}}{=} \frac{A_1(u)}{B_1(u)}. $$

* For $\sum_{i=1}^{N} x_i < M$,

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] = \frac{\sum_i \left( \lambda_i a_i + \sum_k \mu_i x_i (-a_i + b_{ik}) p_{ik} - \mu_i x_i a_i p_{i0} + \sum_l \mu_{[li]} w_{[li]} (-b_{li} + a_i) \right)}{\sum_i \lambda_i + \sum_i \mu_i x_i + \sum_{i,l} \mu_{[li]} w_{[li]}} \stackrel{\text{def}}{=} \frac{A_2(u)}{B_2(u)}. $$

**Proof of (i) when** $\sum_i \bar{\rho}_i - M = -\delta < 0$.

Taking $u = (x, v, w)$ as an arbitrary element of $S$, we introduce the sets $E \stackrel{\text{def}}{=} \{u \in S, \sum_i x_i < M\}$ and $F \stackrel{\text{def}}{=} \{u \in S, w < w_0\}$. Since $v$ is always bounded by $M$, the set $H \stackrel{\text{def}}{=} E \cap F$ is finite, and its complementary is $H^c = E^c \cup F^c = \{\sum_i x_i \ge M\} \cup \{w \ge w_0\}$.

Fixing $\varepsilon$, we choose, for all $(i, k)$, $b_{ik} = a_k + \varepsilon$. The numerator $A_1(u)$ is then rewritten as

$$ A_1(u) = \sum_i \lambda_i a_i + \sum_i \mu_i v_i \left( -a_i + \sum_k (a_k + \varepsilon) p_{ik} \right) - \sum_{i,l} \mu_{[li]} w_{[li]} \varepsilon. \quad (5.1) $$

Following the same lines as in (4.4),

$$ A_1(u) = \sum_i \lambda_i a_i + \mu_N M \left( \varepsilon - a_N + \sum_k a_k p_{Nk} \right) + \sum_{i=1}^{N-1} v_i \left[ \mu_i \left( \varepsilon - a_i + \sum_k a_k p_{ik} \right) - \mu_N \left( \varepsilon - a_N + \sum_k a_k p_{Nk} \right) \right] - \sum_{i,l} \mu_{[li]} w_{[li]} \varepsilon. \quad (5.2) $$

Similarly,

$$ \begin{aligned} A_2(u) &= \sum_i \lambda_i a_i + \sum_i \mu_i x_i \left( -a_i + \sum_k (a_k + \varepsilon) p_{ik} \right) - \varepsilon \sum_{i,l} \mu_{[li]} w_{[li]} \\ &= \sum_i \lambda_i a_i + \sum_i \mu_i x_i \left( -a_i + \sum_k a_k p_{ik} \right) + \varepsilon \sum_i \mu_i x_i (1 - p_{i0}) - \varepsilon \sum_{i,l} \mu_{[li]} w_{[li]}. \end{aligned} \quad (5.3) $$

Then, cancelling for each $i$ the factor of $v_i$ in $A_1(u)$ shows, as in the proof of Theorem 4.3, that the $a_i$'s are the unique solution of (4.5). For these $a_i$'s, using repeatedly the traffic equations as in (4.6), the numerators $A_1(u)$ and $A_2(u)$ become

$$ \left\{ \begin{aligned} A_1(u) &= \sum_j \bar{\rho}_j - M + \varepsilon \mu_N M - \sum_{i,l} \mu_{[li]} w_{[li]} \varepsilon, \\ A_2(u) &= \sum_i \lambda_i a_i - \sum_i x_i + \varepsilon \left( \sum_i \mu_i x_i (1 - p_{i0}) - \sum_l \mu_{[li]} w_{[li]} \right). \end{aligned} \right. \quad (5.4) $$
Now it is not difficult to check that, for $\varepsilon < \frac{\delta}{\mu_N M}$, $A_1(u)$ given in (5.4) is strictly negative for all $w \ge 0$. Noting in addition

$$ \lim_{|w| \to \infty} \frac{A_1(u)}{B_1(u)} = -\varepsilon, $$

we have shown that, the existence of $\theta_1 > 0$ satisfying, for $u \in E^c$ (thus for $w \ge 0$),

$$ \frac{A_1(u)}{B_1(u)} \le -\theta_1 < 0. $$

The next step is to choose $w_0$ large enough to ensure the existence of a number $\theta_2 > 0$ such that, $\varepsilon$ being fixed, for $u \in S$,

$$ \max_{w \ge w_0} \frac{A_1(u)}{B_1(u)} \le -\theta_2 \quad \text{and} \quad \max_{w \ge w_0} \frac{A_2(u)}{B_2(u)} \le -\theta_2. $$

But this is immediate, since the above ratios are simple homographic functions in $w$. This completes the case where $u \in F^c$.

In conclusion, we get, for $u \in H^c$,

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] < -\min(\theta_1, \theta_2) < 0, $$

and $\{\xi_m\}$ is ergodic by Foster's Theorem A.1.

**Proof of (ii) when** $\sum_i \bar{\rho}_i - M = \delta > 0$. Here we choose the $a_i$'s solution of (4.5) and $b_{ik} = a_k - \theta$, where $\theta < \min_k a_k$ is a positive real number to be properly fixed later. Then, exactly as in (5.4) we obtain

$$ \left\{ \begin{aligned} A_1(u) &= \sum_{j=1}^{N} \bar{\rho}_j - M - \theta \mu_N M + \sum_{i,l} \mu_{[li]} w_{[li]} \theta, \\ A_2(u) &= \sum_i \lambda_i a_i - \sum_i x_i - \theta \left( \sum_i \mu_i x_i (1 - p_{i0}) - \sum_l \mu_{[li]} w_{[li]} \right). \end{aligned} \right. \quad (5.5) $$

Straightforwardly from (5.5), when $\theta < \frac{\delta}{\mu_N M}$, $A_1(u)$ is positive. Moreover, we can choose $w_0$ large enough such that $A_2(u)$ is positive for $u \in F^c$. Hence, for $u \in H^c$, there exists $\eta$

$$ \mathbb{E}[G(\xi_{m+1}) - G(\xi_m)/\xi_m = u] > \eta > 0, $$

and $G(\xi_m)$ is a submartingale outside the finite set $H$, which implies the transience of $\{\xi_m\}$ by Theorem 2.2.7 in [5]. The proof of the theorem is concluded. ■

**Remark 5.2.** It is interesting to note that the current model does indeed include different priority classes between customers. This covers one of the main features of models relating to emergency departments.

# 6 Conclusion

This study could be considered within the framework of polling systems, where a set of independent queues are served by one or more servers. Numerous works, particularly in the 1990s, are devoted to these systems, with stability conditions being one of the main issues for one server systems ([8, 7, 2] and others), and being solved thanks to fluid limits for multiple servers ([3]).

Additional work is related to optimization or computational issues, even for network with moving servers, from the same period ([9]) (see [1] and references therein). However, to our knowledge, no stability results have been obtained for a Jackson network with a shared pool of servers. According to polling terminology, the service policy in our model is said to be “one-limited” with zero switching times, recalling that switching concerns servers. For this limited service policy, non-zero switching times should appear in the stability condition. This question is the object of a future work.
## A Some general criteria for convergence

Let $\mathcal{L}$ denote an irreducible Markov chain $\{\xi_m, m \ge 0\}$ with countable state space $\mathcal{A}$. The following criterion known as Foster criterion can be found in [5, Theorem 2.2.3].

**Theorem A.1. (Foster)** $\mathcal{L}$ is ergodic if and only if there exist a positive function $f(\alpha), \alpha \in \mathcal{A}$, a number $\epsilon > 0$ and a finite set $A \in \mathcal{A}$ such that

$$E[f(\xi_{m+1}) - f(\xi_m)/\xi_m = \alpha_j] \le -\epsilon, \alpha_j \notin A, \quad (A.1)$$

$$E[f(\xi_{m+1})/\xi_m = \alpha_i] < \infty, \alpha_i \in A.$$

With regard to transience, the following criterion can be found in [5, Theorem 2.2.7].

**Theorem A.2. (Transience)** For $\mathcal{L}$ to be transient, it suffices that there exist a positive function $f(\alpha), \alpha \in \mathcal{A}$, a bounded integer-valued positive function $k(\alpha), \alpha \in \mathcal{A}$, and numbers $\epsilon, C > 0$, such that, setting $A_c = \{\alpha : f(\alpha) > C\} \ne \emptyset$, the following conditions hold:

(i) $\sup_{\alpha \in A} k(\alpha) = k < \infty$;

(ii) $E(f(\xi_{m+k}) - f(\xi_m)/\xi_m = \alpha_i) \ge \epsilon, \forall m, \text{ for all } \alpha_i \in A_c$;

(iii) for some $d > 0$, the inequality $|f(\alpha_i) - f(\alpha_j)| > d$ implies $p_{ij} = 0$.

**Definition A.3.** ([4], p. 17) Let $\mathcal{O}$ be a closed linear operator with domain $\mathcal{D}(\mathcal{O})$. A subspace $S$ of $\mathcal{D}(\mathcal{O})$ is said to be a core for $\mathcal{O}$ if the closure of the restriction of $\mathcal{O}$ to $S$ is equal to $\mathcal{O}$, i.e., if $\overline{O|_S} = \mathcal{O}$.

**Theorem A.4.** ([4], Theorem 6.1 p. 28) In addition to $\mathcal{L}$, let $\mathcal{L}_k, k \ge 1$, be a sequence of Banach spaces, $\Pi_k : \mathcal{L} \to \mathcal{L}_k$ be a bounded linear transformation, subject to the constraint $\sup_k \|\Pi_k\| < \infty$. Let also $\{T_k(t)\}$ and $\{T(t)\}$ be strongly continuous contraction semigroups on $\mathcal{L}_k$ and $\mathcal{L}$ with generators $\mathcal{O}_k$ and $\mathcal{O}$. We write $f_k \to f$ to mean exactly

$$f \in \mathcal{L}, f_k \in \mathcal{L}_k \text{ for } k \ge 1, \text{ and } \lim_{k \to \infty} \|f_k - \Pi_k f\| = 0.$$

Then, if $\mathcal{D}$ is a core for $\mathcal{O}$ the following are equivalent:

(a) For each $f \in \mathcal{L}$, $T_k(t)\Pi_k f \to T(t)f$ for all $t \ge 0$, uniformly on bounded intervals.

(b) For each $f \in \mathcal{L}$, $T_k(t)\Pi_k f \to T(t)f$ for all $t \ge 0$.

(c) For each $f \in \mathcal{D}$, there exists $f_k \in \mathcal{D}(\mathcal{O}_k)$ for each $k \ge 1$, such that $f_k \to f$ and $\mathcal{O}_k f_k \to \mathcal{O}f$.

■

## B Forward Kolmogorov's equations for the discrete two-queue model

(1) For all $(i, j, k)$ with $i + j \ge M, M - j \le k \le M \land i,$

$$p(i, j, k)(\lambda + k\mu_1 + (M-k)\mu_2) = \lambda p(i-1, j, k) \mathbb{1}_{\{i+j>M\}} + \lambda \tilde{p}(i-1, j) \mathbb{1}_{\{i+j=M\}} \\ + q_1 k \mu_1 \mathbb{1}_{\{k<i+1\}} p(i+1, j-1, k) + (k+1) \mu_1 [(1-q_1) \mathbb{1}_{\{k<i\}} + \mathbb{1}_{\{k=i\}}] p(i+1, j-1, k+1) \\ + (M-k+1) \mu_2 [(1-q_2) \mathbb{1}_{\{M-k<j\}} + \mathbb{1}_{\{M-k=j\}}] \mathbb{1}_{\{k<i+1\}} p(i, j+1, k-1) \\ + (M-k) \mu_2 [q_2 \mathbb{1}_{\{M-k<j+1, k<i\}} + \mathbb{1}_{\{k=i\}}] p(i, j+1, k).$$

(2) For all $(i, j)$ with $i + j < M,$

$$p(i, j, i)(\lambda + i\mu_1 + j\mu_2) = \lambda p(i-1, j, i-1) + (i+1)\mu_1 p(i+1, j-1, i+1) + (j+1)\mu_2 p(i, j+1, i).$$

Trying to solve this system by using generating functions

$$F_k(x, y) = \sum_{i \ge 0, j \ge 0} p(i, j, k) x^i y^j, k \le i,$$

would be intricate and not necessarily very enlightening!
References

[1] AHN, H.-S., AND RIGHTER, R. Dynamic load balancing with flexible workers. *Advances in Applied Probability* 38, 3 (2006), 621–642.

[2] CHERNOVA, N., FOSS, S., AND KIM, B. On the stability of a polling system with an adaptive service mechanism. *Annals of Operations Research* 198, 1 (2012), 125–144.

[3] DOWN, D. On the stability of polling models with multiple servers. *Journal of Applied Probability* 35, 4 (1998), 925–935.

[4] ETHIER, S. N., AND KURTZ, T. G. *Markov Processes. Characterization and Convergence*. John Wiley & Sons, 1986.

[5] FAYOLLE, G., MALYSHEV, V., AND MENSHIKOV, M. *Topics in the Constructive Theory of Countable Markov Chains*, 1st ed. Cambridge University Press, 1995.

[6] FILIPPOV, A. F. *Differential Equations with Discontinuous Righthand Sides*. Springer Netherlands, 1988.

[7] FOSS, S., AND LAST, G. Stability of polling systems with exhaustive service policies and state-dependent routing. *The Annals of Applied Probability* 6, 1 (1996), 116–137.

[8] FRICKER, C., AND JAIBI, M. R. Monotonicity and stability of periodic polling models. *Queueing systems* 15, 1 (1994), 211–238.

[9] SIDI, M., LEVY, H., AND FUHRMANN, S. W. A queueing network with a single cyclically roving server. *Queueing Systems* 11, 1 (1992), 121–144.