2. Model and notation

Consider a polling system with cyclic routeing of the server and with M queues, $M \geq 1$ . Each queue has Poisson arrivals, and independent and identically distributed service times. The model extension with batch Poisson arrivals or Markovian polling of the server is deferred to Section 5. In this paper we consider two service disciplines, that is,

• • pure exponential time-limited discipline (P-TL),

• • exhaustive exponential time-limited discipline (E-TL).

According to both disciplines, the server will visit a queue for at most an amount of time $Y_i$ , which is exponentially distributed with rate $\xi_i$ and independent of other visit times and of the service times. Under the E-TL discipline the server will move to the next queue as soon as the (currently visited) queue becomes empty or when the timer $Y_i$ expires, whichever occurs first. Under the P-TL discipline the server remains at the queue until the timer expires. Under both disciplines, the customer receiving service will be preempted at the expiration of the timer and in such a case a new service time will be drawn from the original distribution at the start of the next visit; that is, we assume the preemptive-repeat with resampling strategy.

Customers who have completed their service at $Q_i$ , $ i=1,\ldots,M$ , will join $Q_j$ , $ j=1,\ldots,M$ , with probability $r_{ij}\geq 0$ , and with probability $r_{i0} \geq 0$ they will leave the system. Clearly, these routeing probabilities $r_{ij}$ must satisfy $\sum_{j=0}^M r_{ij} = 1$ , $ i=1,\ldots,M$ . We assume henceforth that $r_{ii} = 0$ and let $r^i({\textbf{z}})$ denote the p.g.f. of the number of arrivals to all queues generated by a single departing customer at $Q_i$ , i.e. $r^i({\textbf{z}}) = r_{i0} + \sum_j r_{ij}z_j$ . Note that $r_{ii}\neq0$ may be incorporated if we redefine the service time at $Q_i$ as the sum of a geometric number (with expectation $1/(1-r_{ii})$ ) of independent original service times, and adjust the routeing probabilities as follows: $r^{\prime}_{ij}=r_{ij}/(1-r_{ii})$ and $r^{\prime}_{ii}=0$ .

The random variables $I_{i}$ and $X_{i}$ , $i=1,\ldots,M$ , refer to the interarrival time of new customers and the service time of customers at $Q_i$ . The three families of interarrival times, service times, and visit times are assumed to be independent.

The switch-over times are not considered in this paper. The only exceptions are in Lemmas 1 and 2, and in Section 5.2. This is because we focus purely on the key relation, equation (1). We refer to [Reference Al Hanbali, de Haan, Boucherie and van Ommeren2] and [Reference de Haan, Boucherie and van Ommeren9] for the incorporation of this relation into the framework for the computation of the joint queue-length probabilities. Namely, in [Reference Al Hanbali, de Haan, Boucherie and van Ommeren2 Section 5–7] an iterative algorithm was proposed. In this latter paper the performance of this algorithm was evaluated from a computational point of view, and compared with an existing algorithm.

It is assumed that the queues of the polling system are stable. In the following lemmas we shall state the stability condition for both the pure time-limited and the exhaustive time-limited systems. The proofs of these lemmas are straightforward extensions of those of Theorems 3.1 and 3.2 in [Reference de Haan8]. Note that the stability proof in [Reference de Haan8] relied largely on the stability proof of Fricker and Jaibi [Reference Fricker and Jaibi13] for a class of polling systems with non-preemptive and work-conserving service disciplines.

Lemma 1. (Stability of the pure time-limited discipline.) Let $c_t$ denote the total expected switch-over time during a polling cycle. The stability of the pure time-limited discipline is as follows:

\begin{equation*}\mbox{\it System is stable} \Longleftrightarrow \rho_i < \kappa_i, \quad i=1,\ldots,M,\end{equation*}

where

\[\rho_i=\lambda_i^* \cdot \dfrac{1-\tilde{X}_i(\xi_i)}{c_t+\xi_i\tilde{X}_i(\xi_i)}, \quad \kappa_i = \dfrac{1/\xi_i}{c_t+\sum_{j=1}^{M}1/\xi_j}, \quad \lambda_i^* = \lambda_i + \sum_{j=1}^M \lambda_j^* r_{ji}.\]

Note that $\tilde{X}_i(s)$ is the LST of the service time and $(1-\tilde{X}_i(\xi_i))/(\xi_i\tilde{X}_i(\xi_i))$ is the expected value of the effective service time of a job in $Q_i$ which includes the work lost due to service preemptions; $\kappa_i$ is the availability fraction of the server at $Q_i$ .

Lemma 2. (Stability of the exhaustive time-limited discipline.) Let $c_t$ denote the total expected switch-over time during a polling cycle. The stability of the exhaustive time-limited discipline is as follows:

\begin{equation*}\mbox{\it System is stable} \Longleftrightarrow \rho + \max_{i=1,\ldots,M}\bigg(\lambda_i^*\dfrac{1- \tilde{X}_i(\xi_i)}{\tilde{X}_i(\xi_i)}\bigg)\cdot c_t <1,\end{equation*}

where

\[\rho=\sum_{j=1}^{M} \dfrac{\lambda_i^* (1-\tilde{X}_i(\xi_i))}{\xi_i\tilde{X}_i(\xi_i)}, \quad \lambda_i^* = \lambda_i + \sum_{j=1}^M \lambda_j^* r_{ji}.\]

Observe that $\rho$ represents the total offered load to the system and $\tilde{X}_i(\xi_i)/(1- \tilde{X}_i(\xi_i))$ is the mean number of served jobs at $Q_i$ during a cycle when $Q_i$ is saturated, that is, $Q_i$ has infinitely many jobs waiting for service.

Here we introduce the notation that will be used below.

• • Q: an arbitrary queue in the system.

• • $x_t$ : number of customers at time t at Q.

• • $z_{(n)}$ : number of customers left behind by the nth departing customer from Q.

• • $r^{\prime}_n$ : time of the nth departure from Q.

• • D(t): number of departures from Q in [0, t).

• • A(t): number of arrivals to Q in [0, t).

• • I: exponentially distributed random variable with parameter $\lambda$ denoting the interarrival time to Q.

• • X: generally distributed random variable denoting the service time at Q.

• • ${\textbf{1}}_{A}$ : indicator function of event A.

• • $\tilde{X}(\cdot)$ : LST of random variable X.

• • $\hat{\mu}(s,y)$ : root x with the smallest absolute value less than one of $x = y \cdot\tilde{X}(s+\lambda(1-x))$ .

• • $\textbf{N}_i^s$ : number of customers at all queues at the start of a server visit to $Q_i$ .

• • $\textbf{N}_i^e$ : number of customers at all queues at the end of a server visit to $Q_i$ .

• • $N_{i,j}(t)$ : number of customers at $Q_j$ at time t during a server visit to $Q_i$ .

• • $\alpha^i({\textbf{z}})$ : p.g.f. of $\textbf{N}_i^s$ .

• • $\beta^i({\textbf{z}})$ : p.g.f. of $\textbf{N}_i^e$ .

• • $r^i({\textbf{z}})$ : p.g.f. of the number of arrivals to all queues generated by a single departing customer at $Q_i$ .

3. Analysis of the pure time-limited service discipline

In this section we analyze the P-TL discipline. Under this discipline, the server will only depart from the queue when the time limit is reached. It should be stressed that the server will not leave the queue when it becomes empty. We will derive an expression for $\beta^i({\textbf{z}})$ , the p.g.f. of the number of customers at all queues at the instant that the server leaves $Q_i$ , in terms of the number of customers present at the start of the visit, $\alpha^i({\textbf{z}})$ . Here, we present only the essential analytical steps and the main result. The detailed proofs are given in Appendix B.

Consider a visit of the server to an arbitrary queue Q. During this visit, the queue-length process at Q is a birth-and-death process, while the queue-length process at the other queues is a pure birth process. Note also that arrivals to these other queues may be both exogenous and endogenous (from Q). Our interest is in the number of customers at time t given an initial number of customers at the queues at the start of the server visit to Q. Moreover, to include customer routeing in the analysis, we need to keep track of the number of departures during a visit. To record this number of departures, it is not sufficient to know the number of customers at Q at the beginning and end of a visit. To keep track of the number of departures, we will focus on the transient probabilities $p_{hk}^{(n)}(t)$ , which are defined as follows:

\[p_{hk}^{(n)}(t) \,{:\!=}\,\begin{cases}\mathbb{P}(x_t = k,\, D(t)=n \mid x_0 = h) & h,k,n=0,1,\ldots, \\[3pt] 0 & \mbox{otherwise} ,\end{cases}\]

where $x_t$ refers to the number of customers at Q at time t and D(t) refers to the number of departures from Q until time t. We relate these probabilities to the transient probabilities for the standard M/G/1 queue, which we denote by $P_{hj}^{(n)}(t)$ . These time-dependent conditional probabilities, which also incorporate the number of departures until time t, are defined for $n=1,2,\ldots, h,j=0,1,\ldots,$ and $t\gt0$ as [Reference Cohen7, page 239]

\begin{equation*}P_{hj}^{(n)}(t) \,{:\!=}\, \mathbb{P}( z_{(n)}=j, \, r^{\prime}_n \leq t \mid z_{(0)} = h) ,\end{equation*}

where $z_{(n)}$ refers to the number of customers left behind by the nth departure, and $r^{\prime}_n$ refers to the epoch of the nth departure. Further, it is assumed that at time $t=0$ the 0th customer left the queue. We consider the function $\pi_h(r,s,y)$ , which is defined in terms of $P_{hj}^{(n)}(t)$ as follows:

\begin{equation*}\pi_h(r,s,y) \,{:\!=}\, \sum_{n=1}^{\infty} y^n \sum_{j=0}^\infty r^j \int_0^{\infty} \,{\textrm{e}}^{-s t} \,{\textrm{d}} P_{hj}^{(n)}(t),\quad h=0,1,\ldots ,\end{equation*}

and which is explicitly provided in [Reference Cohen7, page 240] for $h=0,1,\ldots,$ as

(2) \begin{equation}\pi_{h}(r,s,y) = \dfrac{y \cdot \tilde{X}(s + \lambda(1-r))}{r - y \cdot \tilde{X}(s + \lambda(1-r))} \cdot\bigg\{ r^h - \dfrac{\lambda(1-r) + s}{\lambda(1-\hat{\mu}(s,y)) + s} \cdot \hat{\mu}^h(s,y) \bigg\},\end{equation}

where $\hat{\mu}(s,y)$ is the root x with the smallest absolute value less than one of $x = y \cdot \tilde{X}(s+\lambda(1\,{-}\,x))$ . Note that $\hat{\mu}(s,y)$ is the joint generating function of the busy period and the number of customers served during this period; see e.g. [Reference Cohen7, page 250].

To take advantage of this explicit result, we will first present an explicit expression for the transient probabilities $p_{hk}^{(n)}(t)$ in terms of $P_{hj}^{(n)}(t)$ . For convenience, we define

\begin{align*}F^{(0)}_k(t) &= {\textbf{1}}_{\{k=0\}}\mathbb{P}(A(t)=0,\, I \gt t)+ {\textbf{1}}_{\{k \geq 1\}}\mathbb{P}(A(t)=k,\, I + X \gt t),\quad k=0,1,\ldots ,\\[4pt] F_k(t) &= \mathbb{P}(A(t)=k,\, X \gt t),\quad k=0,1,\ldots .\end{align*}

That is, $F_k(t)$ refers to k exogenous arrivals to Q during period [0, t] which is shorter than the service time X of the job that started service at time $t=0$ , that is, assuming a non-empty queue at $t=0$ and the job under service is not yet finished. In the special case of an empty queue at $t=0$ (see $F^{(0)}_k(t)$ ), we need to account for the fact that first an arrival should occur before any service may start. Then, we can relate $p_{hk}^{(n)}(t)$ to $P_{hj}^{(n)}(t)$ for $n=1,2,\ldots, h,k=0,1,\ldots,$ and $t\gt0$ as follows.

Lemma 3. We have

\begin{equation*}p_{hk}^{(n)}(t) = \int_{u=0}^t F^{(0)}_k(t-u) \,{\textrm{d}} P_{h0}^{(n)}(u) + \sum_{j=1}^k \int_{u=0}^t F_{k-j}(t-u) \,{\textrm{d}} P_{hj}^{(n)}(u) .\end{equation*}

To retrieve the terms $\pi_h(r,s,y)$ , we first take the LST of $p_{hk}^{(n)}(t)$ (see Remark 2 below). Next, we take the generating function of this expression with respect to the number of customers at the end of a server visit. Note that our interest here is specifically in this number rather than in the number at the time of the nth departure, since the server only leaves upon expiration of the timer. In a final step, we take the generating function with respect to the number of departures until time t to obtain an expression for $p_{hk}^{(n)}(t)$ in terms of $\pi_h(r,s,y)$ . These consecutive steps provide us with the following result for $h=0,1,\ldots.$

Lemma 4. We have

(3) \begin{align}& \sum_{n=1}^\infty y^n \sum_{k=0}^\infty r^k \int_{t=0}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} p_{hk}^{(n)}(t) \notag \\[3pt] &\quad = \dfrac{s}{\lambda(1-r) + s} \cdot \dfrac{\lambda(1- r \cdot \tilde{X}(\lambda(1-r)+s)) + s}{\lambda + s} \cdot \pi_{h0}(s,y) \notag \\[3pt] &\quad\quad\, + \dfrac{s}{\lambda(1-r) + s} \cdot (1 - \tilde{X}(\lambda(1-r)+s)) \cdot (\pi_h(r,s,y) - \pi_{h0}(s,y) ),\end{align}

where the terms $\pi_{h0}(s,y)$ are given by (see [Reference Cohen7, page 240])

(4) \begin{align}\hspace*{-25pt}\pi_{00}(s,y) &= \dfrac{\lambda}{\lambda(1-\hat{\mu}(s,y)) + s}\cdot \hat{\mu}(s,y) ,\kern45pt \end{align}

(5) \begin{align}\pi_{h0}(s,y) &= \dfrac{\lambda + s}{\lambda(1-\hat{\mu}(s,y)) + s} \cdot \hat{\mu}^h(s,y),\quad h=1,2,\ldots. \\[-40pt] \nonumber\end{align}

The right-hand side of (3) can be interpreted as follows. The first part refers to the case that upon the nth departure zero customers are left behind, while the second part refers to a strictly positive number left behind by the nth departing customer. Moreover, the second part can be decomposed into two independent components: $\pi_h(r,s,y) - \pi_{h0}(s,y)$ accounts for the queue-length evolution until the nth departure and the other component accounts for the queue-length evolution during the final, interrupted service. A similar reasoning holds for the first part.

Thus, we have related the transient probabilities of our interest to known results for the M/G/1 queue. To incorporate these results into the polling model, we refer to a specific queue $Q_i$ by adding an index i to the generic variables. Next, by unconditioning on the system state at the start of a visit and incorporating the expressions above into the definition of $\beta^i({\textbf{z}})$ , we obtain the main result of this section for the p.g.f. of the joint queue length at the end of a server visit under the P-TL discipline.

Theorem 1. (Pure exponential time-limited discipline.) We have

(6) \begin{equation*}\beta^i({\textbf{z}}) = d^{P}_1({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*)) + d^{P}_2({\textbf{z}}) \cdot \alpha^i({\textbf{z}}_i^*) ,\end{equation*}

where

\begin{align}d^{P}_1({\textbf{z}}) &=\dfrac{\xi_i}{z_i - r^i({\textbf{z}}) \cdot \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i)} \cdot \dfrac{z_i \cdot (1 - \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i))}{\lambda_i(1-z_i) + \xi^*_i} ,\notag \\[3pt] d^{P}_2({\textbf{z}}) &=d^{P}_1({\textbf{z}}) + \dfrac{\xi_i}{z_i - r^i({\textbf{z}}) \cdot \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i)}\cdot\dfrac{(z_i - r^i({\textbf{z}})) \cdot \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i)}{\lambda_i(1-\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))) + \xi^*_i},\notag \\[3pt] \xi^*_i &= \xi_i + \sum_{j \not= i} \lambda_j(1-z_j) , \notag \\*\alpha^i({\textbf{z}}_i^*) &\,{:\!=}\, \alpha^i(z_1,\ldots,z_{i-1},\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}})),z_{i+1},\ldots,z_M).\end{align}

We refer to Section 6 for a detailed interpretation of the results shown in Theorem 1.

4. Analysis of the exhaustive time-limited service discipline

Let us next consider the E-TL discipline. Under this discipline the server will depart from a queue not only when the time limit is reached but also when the queue becomes empty. Again, we will derive an expression for $\beta^i({\textbf{z}})$ , the p.g.f. of the number of customers at all queues at the instant that the server leaves $Q_i$ . This will be done in terms of the number of customers present at the start of the visit, $\alpha^i({\textbf{z}})$ . As in the previous section, we present here only the main analytical steps and the final result. The proofs are given in Appendix C.

Under the E-TL discipline, the server may leave a queue for two reasons, namely, the server departs due to the queue being empty or due to the timer expiring. Let $\{ \text{empty} \}$ and $\{ \text{timer} \}$ denote the corresponding server events. Recall that $\textbf{N}_i^s$ and $\textbf{N}_i^e$ denote the multi-dimensional random variable of the number of customers at all queues at the start and the end of a server visit to $Q_i$ , respectively. The p.g.f. of $\textbf{N}_i^e$ , $\beta^i({\textbf{z}})$ , can be decomposed into two parts depending on the reason for a server departure, as the server departs only if the queue is empty or if the timer expires. Moreover, these events are readily seen to be mutually exclusive (the service-time distribution and timer distribution are both continuous distributions, so that the probability of the given events occurring simultaneously is zero). Hence, the p.g.f. of the number of customers at the end of a server visit period to $Q_i$ satisfies

\begin{equation*}\beta^i({\textbf{z}}) = \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}] = \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{empty}\}}] + \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{timer}\}}] .\end{equation*}

Next, in Sections 4.1 and 4.2, we will derive the conditional p.g.f.s

\[\mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{empty}\}} \mid \textbf{N}_i^s = \textbf{n}],\quad\mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{empty}\}} \mid \textbf{N}_i^s = \textbf{n} ],\]

where $\textbf{n}$ denotes the vector $(n_1,\ldots,n_M)$ . Finally, we will uncondition these expressions to get our main result in Section 4.3.

4.1 $\mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{empty}\}} \mid \textbf{N}_i^s = \textbf{n}]$

If the ${\{\text{empty}\}}$ event occurs, the queue may be empty upon arrival of the server or become empty upon departure of a customer. If the server finds an empty queue upon arrival, then clearly $\textbf{N}_i^e = \textbf{N}_i^s$ . Else, if the queue is non-empty upon server arrival, then the evolution of queue-length process during the visit is closely related to the length of a busy period in a standard M/G/1 queue. This is formalized in the following lemma.

Lemma 5. The joint conditional p.g.f. of the number of customers at the end of a visit period to $Q_i$ and the server departure due to the queue being empty satisfies

(7) \begin{equation}\mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{empty}\}} \mid \textbf{N}_i^s = \textbf{n}] = \hat{\mu}^{n_i}_i(\xi^*_i,r^i({\textbf{z}})) \cdot \prod_{j \not= i} z_j^{n_j} ,\end{equation}

where

\begin{equation*}\xi^*_i = \xi_i + \sum_{j \not= i} \lambda_j(1-z_j) .\end{equation*}

For the case when the server departs due to an empty $Q_i$ , Lemma 5 shows that every customer waiting in $Q_i$ at the beginning of server visit is replaced in an independent and identically distributed manner. These replacement jobs do not only concern $Q_i$ but all other queues as well. This latter is captured via the term $r^i({\textbf{z}})$ , which is defined as the p.g.f. of the number of arrivals to all queues generated by a single departing customer at $Q_i$ .

4.2 $\mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{timer}\}} \mid \textbf{N}_i^s = \textbf{n}]$

If the ${\{\text{timer}\}}$ event occurs, the queue must be non-empty upon arrival of the server, and it remains non-empty during the course of the visit and is still non-empty at the expiration of the timer. The analysis of this case builds on the work of Cohen for the transient analysis of the M/G/1 queue. However, contrary to the analysis for the P-TL discipline, we cannot directly apply the formulae derived in [Reference Cohen7]. This is due to the fact that we need specifically to account for not entering the state with zero customers at $Q_i$ during the course of a server visit. Below, we state the transient probabilities of interest and several related expressions. Next, using these expressions, we will derive $\mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{timer}\}} \mid \textbf{N}_i^s = \textbf{n}]$ .

We first consider the conditional joint queue-length distribution at time $t\gt0$ given an initial number of customers at time $t=0$ and given that the server is at an arbitrary queue Q. It is good to note that during a server visit to Q the queue-length process at the other queues is simply a pure-birth process. Hence, we neglect the other queues for the moment and concentrate on the marginal queue-length probabilities for Q, denoted by $q_{hk}^{(n)}(t)$ , which we define as

\[q_{hk}^{(n)}(t) \,{:\!=}\,\begin{cases}\mathbb{P}(x_t = k,\, D(t) = n,\, x_v>0,\, 0 \lt v \lt t \mid x_0 = h)& n=0,1,\ldots, h,k=1,2,\ldots, \\[4pt] 0 & \text{otherwise.}\end{cases}\]

For convenience, let us recall the definition of the probabilities $P_{hj}^{(n)}(t)$ , for $n=1,2,\ldots, h,j\,{=}\,0,1,\ldots$ and $t \gt 0$ ,

\begin{equation*}P_{hj}^{(n)}(t) \,{:\!=}\, \mathbb{P}(z_{(n)}=j,\quad r^{\prime}_n \le t \mid z_{(0)} = h) .\end{equation*}

Analogously, we define $R_{hj}^{(n)}(t)$ , for $h,j,n=1,2,\ldots,$ and $t \gt 0$ ,

\begin{equation*}R_{hj}^{(n)}(t) \,{:\!=}\, \mathbb{P}(z_{(n)}=j,\, r^{\prime}_n \le t,\, z_{(k)} \gt 0,\, 0 \lt k < n \mid z_{(0)} = h) ,\end{equation*}

where it is assumed that at time $t=0$ a new service starts. We note that $R_{hj}^{(n)}(t)$ is only defined for $h,j=1,2,\ldots.$ This is due to the fact that the event of a server arriving at an empty queue (i.e. $h=0$ ) and the event of the nth customer leaving an empty queue behind (i.e. $j=0$ ) are not considered as $\{ \text{timer} \}$ events, but always as $\{ \text{empty} \}$ events.

We consider the function $\gamma_h(r,s,y)$ , which is defined in terms of $R_{hj}^{(n)}(t)$ as

\begin{equation*}\gamma_h(r,s,y) \,{:\!=}\, \sum_{n=1}^\infty y^n \sum_{j=1}^\infty r^j \int_0^\infty \,{\textrm{e}}^{-s t} \,{\textrm{d}} R_{hj}^{(n)}(t),\quad h=1,2,\ldots ,\end{equation*}

and which is explicitly given (see Appendix A for the derivation) for $h=1,2,\ldots,$ as

\begin{equation*}\gamma_{h}(r,s,y) = \dfrac{r ( -\hat{\mu}^h(s,y) + y \cdot \tilde{X}(\lambda (1-r) + s ) \cdot r^{h-1} )}{r - y \cdot \tilde{X}(\lambda(1-r) + s )} .\end{equation*}

Analogous to the approach in the previous section, we intend to utilize the explicit expressions for $\gamma_h(r,s,y)$ . To this end, we will start by relating the transient probabilities $q_{hk}^{(n)}(t)$ to the time-dependent probabilities $R_{hj}^{(n)}(t)$ at embedded epochs of service completion. For convenience, we recall that

\begin{equation*}F_k(t) = \mathbb{P}(A(t)=k,\, X>t),\quad k=0,1,\ldots ,\end{equation*}

that is, $F_k(t)$ refers to the number of arrivals to Q during a period which is shorter than a service time X. The specific relation between $q_{hk}^{(n)}(t)$ and $R_{hj}^{(n)}(t)$ is then given in the following lemma.

Lemma 6. We have

\begin{equation*}q_{hk}^{(n)}(t) = \int_{u=0}^t \sum_{j=1}^k F_{k-j}(t-u) \,{\textrm{d}} R_{hj}^{(n)}(u), \quad n=1,2,\ldots, h,k=1,2,\ldots .\end{equation*}

Again, to obtain the terms $\gamma_h(r,s,y)$ , we take the LST of $q_{hk}^{(n)}(t)$ (see Remark 2). Next, we take the generating function with respect to the number of customers at the end of the server visit of the resulting expression, and finally we take the generating function with respect to the number of departures. Hence, we obtain the following result.

Lemma 7. We have

(8) \begin{align}& \sum_{n=1}^\infty y^n \sum_{k=1}^\infty r^k \int_{t=0}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} q_{hk}^{(n)}(t) \notag \\* &\quad = \gamma_{h}(r, s, y) \cdot \dfrac{s}{\lambda(1-r) + s} \cdot (1 - \tilde{X}(\lambda(1-r) + s)) , \quad h=1,2,\ldots .\end{align}

The right-hand side of (8) can be recognized as a convolution of two independent parts. The first part, $\gamma_{h}(r, s, y)$ , refers to the queue length at the instant of the final (successful) service completion during the visit, while the other part refers to the number of arrivals during an interrupted service.

Next, we present the explicit expression for the joint conditional p.g.f. of the number of customers at all queues at the end of a visit to a specific queue $Q_i$ when the server departure is due to the timer expiration. The condition is on the number of customers present at the start of the visit.

Lemma 8. We have

(9) \begin{equation} \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{timer}\}} \mid \textbf{N}_i^s = \textbf{n}] = \dfrac{\xi_i \cdot z_i \cdot (1 - \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i)) ( z_i^{n_i} - \hat{\mu}_i^{n_i}(\xi^*_i, r^i({\textbf{z}})) )}{[ \lambda_i(1-z_i) + \xi^*_i ] \cdot [z_i - r^i({\textbf{z}}) \cdot \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i) ]}\cdot \prod_{j \not=i} z_j^{n_j} ,\end{equation}

where

\begin{equation*}\xi^*_i = \xi_i + \sum_{j \not= i} \lambda_j(1-z_j) .\end{equation*}

Compared to Lemma 5, expression (9) is much more complex, which is due to the fact that when the timer expires the remaining jobs at $Q_i$ are not replaced in an independent and identical manner.

4-3 $\mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}]$

Combining the two conditional results of (7) and (9), we obtain our main result of this section for the E-TL service discipline.

Theorem 2. (Exhaustive exponential time-limited discipline). We have

(10) \begin{equation}\beta^i({\textbf{z}}) = d^{E}_1({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*)) + d^{E}_2({\textbf{z}}) \cdot \alpha^i({\textbf{z}}_i^*) ,\end{equation}

where

\begin{align*}d^{E}_1({\textbf{z}}) \notag &= d^{P}_1({\textbf{z}})\notag, \\[3pt] d^{E}_2({\textbf{z}}) \notag &= 1, \\[3pt] \alpha^i({\textbf{z}}_i^*) &=\alpha^i(z_1,\ldots,z_{i-1},\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}})),z_{i+1},\ldots,z_M), \\[3pt] \xi^*_i &= \xi_i + \sum_{j \not= i} \lambda_j(1-z_j).\end{align*}

Observe that (10) generalizes the result for the special case $r^i({\textbf{z}})=1$ (i.e. no customer routeing) given in [Reference Eliazar and Yechiali11]. We refer to Section 6 for a detailed interpretation of the results shown in Theorem 2. To find the p.g.f.s of joint queue-length distribution based on results in Theorem 2, we refer to Remark 3.

Remark 4. (Phase-type service times.) Theorem 2 generalizes the result for the special case $r^i({\textbf{z}})=1$ (i.e. no customer routeing) given in [Reference Al Hanbali, de Haan, Boucherie and van Ommeren2] for the case of phase-type service times and in [Reference Al Hanbali, de Haan, Boucherie and van Ommeren1] for the exponential service times.

Remark 5. (Exhaustive service discipline.) In the limit case of $\xi_i \downarrow 0$ the time limit is of infinite length. Hence, in this case (assuming a stable queue), the server will always depart due to $Q_i$ being empty. It can readily be found that for $ \xi_i \downarrow 0$ and $r^i({\textbf{z}})=1$ the following expression for $\beta^i({\textbf{z}})$ is obtained:

\begin{equation*} \beta^i({\textbf{z}}) = \alpha^i({\textbf{z}}_i^*) ,\end{equation*}

where

\[\alpha^i({\textbf{z}}_i^*) \,{:\!=}\, \alpha^i\bigg(z_1,\ldots,z_{i-1},\hat{\mu}_i\bigg(\sum_{j \not= i} \lambda_j(1-z_j),1\bigg),z_{i+1},\ldots,z_M\bigg).\]

This result matches the well-known result for the exhaustive service discipline [Reference Fuhrmann14,Reference Resing18].

5. Model extensions

The analysis of the basic polling model may be extended in various directions. Extending the basic model increases the range of applications that can be modeled. Moreover, such extensions are also interesting from a theoretical point of view. The specific extensions that we discuss here are the following: batch Poisson arrivals of customers and Markovian polling of the server.

5.1 Batch Poisson arrivals

In this subsection we concentrate on the time-limited polling systems with batch Poisson arrivals. The analysis of these batch arrival systems closely follows the analysis of single arrival systems. Therefore we will only present the main steps and the final results.

The analysis of the time-limited polling system is based on the transient analysis of the M/G/1 queue, for which closed-form expressions for the joint LST for the queue length and number of departures at time t is available; see e.g. [Reference Cohen7, pages 239–240]. In the case of batch arrivals, we need the transient analysis for the M $^X$ /G/1 queue, that is a single server queue with compound Poisson arrivals. The transient analysis was partially done in [Reference Cohen7, pages 239–240]. Below, we shall derive the required expressions for our analysis.

The batch sizes are assumed to be mutually independent and independent of the arrival and service processes. Let $\lambda$ denote the arrival rate of batches and ${\hat \psi(\cdot)}$ the generating function of the batch size. Recall that the generating function of the service time of an individual customer is denoted by ${\tilde X(\cdot)}$

Let ${z_{(n)}}$ denote the number of customers left behind by the nth departing customer after time 0 and let ${r^{\prime}_{n}}$ be its departure time. We assume that at time $t=0$ customer 0 departs. Let $R_{hj}^{(n)}(t)$ denote the following probability:

\[R_{hj}^{(n)}(t) \,{:\!=}\, {{\mathbb P}}({z_{(n)}}=j, {r^{\prime}_{n}}\le t, {z_{(k)}}>0, 0<k<n \mid {z_{(0)}}=h)\,\,\,\,\text{for $h=1,2,\ldots, j=\max(0,h-n)$.}\]

Lemma 9. The generating function of $R_{hj}^{(n)}(t)$ is

\[\gamma_h(r,s,y)= \dfrac{r(-\hat\mu^h(s,y)+y{\tilde X({s+\lambda(1-{\hat \psi(r)})})}\cdot r^{h-1})}{r-y{\tilde X({s+\lambda(1-{\hat \psi(r)})})}},\]

for $h=1,2,\ldots.$

The result in Lemma 9 can be seen as an extension of Theorem 5 in Appendix A for the M/G/1 queue. Now we have the ingredients to relate $\beta^i({\textbf{z}})$ and $\alpha^i({\textbf{z}})$ for batch Poisson arrivals. For the system with a P-TL service discipline with batch arrivals, after a similar analysis to Section 3 and Appendix B, we obtain the following result (cf. Theorem 1).

Theorem 3. (Pure exponential time-limited discipline with batch arrivals.) We have

\begin{equation*}\beta^i({\textbf{z}}) = d^{P}_{B1}({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*)) + d^{P}_{B2}({\textbf{z}}) \cdot \alpha^i({\textbf{z}}_i^*) ,\end{equation*}

where

\begin{align*}d^{P}_{B1}({\textbf{z}}) &=\dfrac{\xi_i}{z_i - r^i({\textbf{z}}) \cdot \tilde{X}_i(\lambda_i(1-{\hat \psi}_i(z_i)) + \xi^*_i)} \cdot\dfrac{z_i \cdot (1 - \tilde{X}_i(\lambda_i(1-{\hat \psi}_i(z_i)) + \xi^*_i))}{\lambda_i(1-{\hat \psi}_i(z_i)) + \xi^*_i} , \\[3pt] d^{P}_{B2}({\textbf{z}}) &=d^{P}_{B1}({\textbf{z}}) + \dfrac{\xi_i}{z_i - r^i({\textbf{z}}) \cdot \tilde{X}_i(\lambda_i(1-{\hat \psi}_i(z_i)) + \xi^*_i)} \cdot\dfrac{(z_i - r^i({\textbf{z}})) \cdot \tilde{X}_i(\lambda_i(1-{\hat \psi}_i(z_i)) + \xi^*_i)}{\lambda_i(1-\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))) + \xi^*_i}, \\[3pt] \alpha^i({\textbf{z}}_i^*) &=\alpha^i(z_1,\ldots,z_{i-1},\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}})),z_{i+1},\ldots,z_M), \\[3pt] \xi^*_i &= \xi_i + \sum_{j \not= i} \lambda_j(1-{\hat \psi}_j(z_j)).\end{align*}

For the system with an E-TL service discipline with batch Poisson arrivals, after a similar analysis to Section 4 and Appendix C, we obtain the following result (cf. Theorem 2).

Theorem 4. (Exhaustive exponential time-limited discipline with batch arrivals.) We have

\begin{equation*}\beta^i({\textbf{z}}) = d^{P}_{B1}({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*)) + \alpha^i({\textbf{z}}_i^*),\end{equation*}

where $d^{P}_{B1}({\textbf{z}})$ is given in Theorem 3.

5.2 Markovian polling of the server

We have assumed until now that the server polls the queues according to a fixed cyclic schedule. To allow for more general polling schedules, the routeing (or polling) of the server is taken to follow a Markovian pattern (see [Reference Boxma and Weststrate5] and [Reference Levy and Sidi17]). Let $s_{i,j} \geq 0$ , $ j=1,\ldots,M,$ denote the probability upon departure from queue i that the next queue that will be visited is j. This next queue could also be i again. This feature is particularly meaningful in the case of non-zero switch-over times, whereas in the case of zero switch-over times we may simply set $s_{i,i}=0$ , $ i=1,\ldots,M$ .

Let us describe the embedded process of visits to the queues (thus neglecting switch-over times for the moment) by a discrete-time Markov chain $X_n \in \{1,\ldots,M\}$ , $n \geq 0,$ driven by the transition probability matrix $S=\{ s_{i,j}\}_{i,j=1,\ldots,M}$ . We assume that this Markov chain has an equilibrium distribution which we denote by $\tau_i$ , $ i=1,\ldots,M$ . Our interest is in the fraction of time that the Markov chain is in a state i (denoted by $\kappa_i$ ) and also in the fraction of times that the process is switching from state i to state j (denoted by $\Delta_{i,j}$ ). To enrich the analysis here we include the switch-over time from $Q_i$ to $Q_j$ and assume it is independent of all other variables, for example arrival times, service times, and server visit times. Let us define the cycle time of $Q_i$ by $C_i$ as the time between two consecutive polling instants of the server at $Q_i$ . This means that a cycle $C_i$ comprises exactly one visit time to $Q_i$ . The mean cycle time can then be expressed as a weighted sum of mean visit and mean switch-over times as follows:

\begin{equation*}\mathbb{E}[C_i] = \sum_k \dfrac{\tau_k}{\tau_i} \bigg(\mathbb{E}[Y_k] + \sum_j s_{k,j} \cdot c_{k,j}\bigg), \quad i=1,\ldots,M ,\end{equation*}

where $\mathbb{E}[Y_k]$ denotes the mean visit time to queue k and $c_{k,j}$ the mean switch-over time from $Q_k$ to $Q_j$ . Note that the ratio $\tau_k / \tau_i$ equals the mean number of visits to queue k per visit to i. There exists a simple relation between the mean cycle times of the different queues in the sense that the product $\mathbb{E}[C_i] \cdot \tau_i$ is constant for all queues. This relation immediately explains why, under Markovian polling, in contrast to the cyclic polling case (for which $\tau_i = 1/M$ , $i=1,\ldots,M$ ), the mean cycle times per queue are not necessarily equal for all queues.

It readily follows for $\kappa_i$ , $ i=1,\ldots,M$ , which is in fact the long-term fraction of time the server is available at $Q_i$ , that

(11) \begin{equation}\kappa_i= \dfrac{\mathbb{E}[Y_i]}{\mathbb{E}[C_i]} = \dfrac{\mathbb{E}[Y_i]}{\sum_k {({\tau_k}/{\tau_i})}(\mathbb{E}[Y_k] + \sum_j s_{k,j} \cdot c_{k,j})}= \dfrac{\tau_i \mathbb{E}[Y_i]}{\sum_k \tau_k (\mathbb{E}[Y_k] + \sum_j s_{k,j} \cdot c_{k,j})} ,\end{equation}

where it should be noted that the denominator in the last part of (11) does not depend on i. Similarly, for $\Delta_{i,j}$ we find that

\begin{equation*}\Delta_{i,j}= \dfrac{\tau_i \cdot s_{i,j} \cdot c_{i,j} }{\sum_k \tau_k (\mathbb{E}[Y_k] + \sum_j s_{k,j} \cdot c_{k,j})} .\end{equation*}

Again, the adjustments in our modeling framework for the joint queue-length probabilities are relatively simple. We note that routeing of the server solely plays a role in the relation between the queue length at a visit start instant and the queue length at the preceding visit completion instant. Since the preceding queue that was served is now random, the expression for $\alpha^i({\textbf{z}})$ becomes

\begin{equation*}\alpha^i({\textbf{z}}) = \sum_j q_{j,i} \hat{C}_{j,i}({\textbf{z}}) \beta^j({\textbf{z}}) ,\end{equation*}

where $ \hat{C}_{j,i}({\textbf{z}})$ is the joint generating function of the total number of Poisson arrivals to all the queues during $C_{j,i}$ , the switch-over time from $Q_j$ to $Q_i$ . Here $q_{j,i}$ is the probability that the preceding queue was $Q_j$ , given that the server is at $Q_i$ , and is given by the transition probability of the time reversed Markov chain (see e.g. [Reference Kelly15])

\begin{equation*}q_{j,i} = \dfrac{\tau_j \cdot s_{j,i}}{\tau_i} {.}\end{equation*}

Finally, we conclude that for the P-TL discipline the p.g.f. of the steady-state joint queue-length probabilities is

\begin{equation*}P({\textbf{z}})= \sum_{i=1}^M \bigg( \beta^i({\textbf{z}}) \cdot \kappa_i + \sum_{j=1}^M \hat{C}^R_{i,j}({\textbf{z}}) \cdot \Delta_{i,j} \bigg) ,\end{equation*}\vskip-\lastskip{\pagebreak}

where

\begin{equation*}\hat{C}^R_{i,j}({\textbf{z}}) = \beta^i({\textbf{z}}) \cdot \dfrac{1 - \tilde{C}_{i,j}(\sum_k \lambda_k(1-z_k))}{c_{i,j} \cdot \sum_k \lambda_k(1-z_k)} .\end{equation*}

Note that for the E-TL discipline we can just derive the expressions of the p.g.f. of the steady-state joint queue-length process at polling instances. Based on these results, it is possible to find the p.g.f. of the marginal queue-length distribution in $Q_i$ at an arbitrary time; see e.g. [Reference Eliazar and Yechiali11].

6. Concluding remarks

The final results for the P-TL discipline and the E-TL discipline have a similar form. More specifically, these results can be written as follows:

(12) \begin{align}& \mbox{P-TL: } \beta^i({\textbf{z}}) = d^{P}_1({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*)) + d^{P}_2({\textbf{z}}) \cdot \alpha^i({\textbf{z}}_i^*) {,} \end{align}

(13) \begin{align}\mbox{E-TL: } \beta^i({\textbf{z}}) = d^{E}_1({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*)) + d^{E}_2({\textbf{z}}) \cdot \alpha^i({\textbf{z}}_i^*), \end{align}

where $d^{E}_1({\textbf{z}})=d^{P}_1({\textbf{z}})$ is given in (6), $d^{E}_2({\textbf{z}}) = 1$ and $d^{P}_2({\textbf{z}})$ is given in (6).

Equations (12) and (13) may be interpreted as follows. Consider a visit of the server to $Q_i$ . Regarding the timer, it may occur that (i) the timer expires before $Q_i$ becomes empty for the first time, or (ii) the timer expires only after $Q_i$ becomes empty for the first time. It is readily seen that the queue-length process is identical for both service disciplines in the case (i). This is reflected in the similarity of the terms $d^{P}_1({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*))$ and $d^{E}_1({\textbf{z}}) \cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*))$ . However, in case (ii), the queue-length process is different for the disciplines. Under the exhaustive time-limited discipline, the server immediately leaves upon the queue becoming empty; say this occurs at time $t_0$ . Under the pure time-limited discipline, at time $t_0$ the server will remain at the queue and a sequence of idle and busy periods will follow until eventually the timer expires. This latter contribution (after $t_0$ ) to the queue-length process is represented in the term $d^{P}_2({\textbf{z}})$ .

The function $d^{P}_2({\textbf{z}})$ reflects the p.g.f. of the number of customers at all queues at the end of a server visit process, which runs for an exponential amount of time and which starts from an empty queue. This function can be analyzed as follows. First, observe that the timer will interrupt the visit process during either an idle or a busy period. Second, observe that this process is regenerative in the sense that if the timer does not expire before the end of the first busy period, then the process starts like new at that specific time instant. Recall that $I_i$ denotes the length of an idle period at $Q_i$ and $Y_i$ denotes the exponential visit time of the server to $Q_i$ . Further, let $U_i$ denote the length of a busy period at $Q_i$ starting with a single customer. Then we may write the following relation for $d^{P}_2({\textbf{z}})$ :

\begin{align*}d^{P}_2({\textbf{z}}) &=\mathbb{E}[{\textbf{z}}^{\textbf{N}_i(Y_i)}{\textbf{1}}_{\{I_i \gt Y_i\}} \mid \textbf{N}_i(0) = \textbf{n},\, N_{i,i}(0)=0 ] \\[3pt] &\quad\, + \mathbb{E}[{\textbf{z}}^{\textbf{N}_i(Y_i)}{\textbf{1}}_{\{I_i \le Y_i, I_i + U_i \gt Y_i\}} \mid \textbf{N}_i(0) = \textbf{n},\, N_{i,i}(0)=0 ] \\[3pt] &\quad\, + \mathbb{E}[{\textbf{z}}^{\textbf{N}_i(I_i + U_i)}{\textbf{1}}_{\{I_i + U_i \le Y_i\}} \mid \textbf{N}_i(0) = \textbf{n},\, N_{i,i}(0)=0 ] \cdot d^{P}_2({\textbf{z}}) \\[3pt] &= \dfrac{\xi_i}{\lambda_i + \xi^*_i} + \dfrac{\lambda_i}{\lambda_i + \xi^*_i} \\[3pt] &\quad\, \times \mathbb{E}[{\textbf{z}}^{\textbf{N}_i(Y_i)}{\textbf{1}}_{\{\text{timer}\}} \mid \textbf{N}_i(0) = (n_1,\ldots,n_{i-1},1,n_{i+1},\ldots,n_M)] \\[3pt] &\quad\, + \dfrac{\lambda_i}{\lambda_i + \xi^*_i} \cdot \hat{\mu}_i(\xi^*_i,r^i({\textbf{z}})) \cdot d^{P}_2({\textbf{z}}) ,\end{align*}

where $\mathbb{E}[{\textbf{z}}^{\textbf{N}_i(Y_i)}{\textbf{1}}_{\{\text{timer}\}} \mid \textbf{N}_i(0) = \textbf{n}]$ is provided in the analysis of the exhaustive time-limited discipline (see Lemma 8). Then, inserting this result of Lemma 8 and reorganizing the terms appropriately, we obtain $d^{P}_2({\textbf{z}})$ as in (6).

This result indeed confirms the interpretation given above. We remarked that for the common exhaustive discipline (E), i.e. the time-limited version with the time limit set to infinity, the term $d^{E}_1({\textbf{z}})$ vanishes, that is,

\begin{equation*} \mbox{E: } \beta^i({\textbf{z}}) = \alpha^i({\textbf{z}}_i^*) ,\end{equation*}

In this paper we have studied two time-limited service disciplines for polling systems, namely, the pure and the exhaustive exponential time-limited discipline with preemptive service. Specifically, we have obtained relations between the p.g.f.s of the joint queue-length distribution at visit beginning and visit completion epochs. To this end, we have used both known (see Section 3) and novel results (see Section 4) for the transient behavior of the M/G/1 queue. Our final expressions for the key relation, (1), extend earlier results for the pure limited [Reference Al Hanbali, de Haan, Boucherie and van Ommeren2] and the exhaustive time-limited discipline [Reference Eliazar and Yechiali11] by incorporating new model features such as customers routeing among queues; see Section 5 for the other model features. These relations can be used to obtain the joint queue-length distribution at these embedded epochs, for example using the framework presented in [Reference Al Hanbali, de Haan, Boucherie and van Ommeren2]. These key relations not only provide us with a more elegant result but have also been shown to significantly alleviate the computational efforts required to compute the joint queue-length distribution of the polling system along the framework of [Reference de Haan, Boucherie and van Ommeren9]. Finally, we have been able to give a clear interpretation of the final expressions for the key relations, the discussion after (12) and (13).

Appendix A: Transient analysis of the M/G/1 queue during a busy period

In this section we analyze the transient behavior of the M/G/1 queue during a busy period. We follow an approach similar to that used by Cohen [Reference Cohen7] to study the transient behavior of the full queue-length process of the M/G/1 queue. To this end, we consider a single queue served by a single server. Customers arrive at the queue according to a Poisson process with rate $\lambda$ . The service requirement X of a customer is generally distributed.

Our interest is in the queue-length process during a busy period with some initial number of customers. Moreover, we keep track of the number of departures until time t. Therefore, as in the transient transition probabilities $P_{hj}^{(n)}(t)$ that were defined in [Reference Cohen7, page 239], we define the transient probabilities $R_{hj}^{(n)}(t)$ which specifically account for the fact that the system is non-empty from time 0 up to time t. More precisely, the transient probabilities $R_{hj}^{(n)}(t)$ are defined for $h,j,n=1,2,\ldots,$ and $t \gt 0$ as

\begin{equation*}R_{hj}^{(n)}(t) \,{:\!=}\, \mathbb{P}(z_{(n)}=j,\, r^{\prime}_n \le t,\, z_{(k)} \gt 0,\, 0 \lt k < n \mid z_{(0)} = h) ,\end{equation*}

where it is assumed that at time $t=0$ a new service starts. Note that $R_{hj}^{(n)}(t)$ is only defined for $h,j \geq 1$ . Our objective is to find an explicit expression for $\gamma_h(r,s,y)$ which is defined as

\begin{align*}\gamma_h(r,s,y) & \,{:\!=}\, \sum_{n=1}^\infty y^n\mathbb{E}(r^{{z_{(n)}}}\,{\textrm{e}}^{-s{r^{\prime}_{n}}}\textbf{1}({z_{(k)}}\gt0, 0\lt\k\lt\n)), \\[3pt] &= \sum_{n=1}^\infty y^n \sum_{j=1}^\infty r^j \int_0^\infty \,{\textrm{e}}^{-s t} \,{\textrm{d}} R_{hj}^{(n)}(t),\quad h=1,2,\ldots .\end{align*}

From the definition of $R_{hj}^{(n)}(t)$ it follows immediately that

\begin{align*}R_{1j}^{(1)}(t) &= \int_{\tau=0}^t \,{\textrm{e}}^{-\lambda \tau} \dfrac{(\lambda \tau)^j}{j!} \,{\textrm{d}} X(\tau),\quad j=1,2,\ldots, \\[4pt] R_{hj}^{(1)}(t) &= \int_{\tau=0}^t \,{\textrm{e}}^{-\lambda \tau} \dfrac{(\lambda \tau)^{j+1-h}}{(j+1-h)!} \,{\textrm{d}} X(\tau),\quad j=h-1,h,\ldots, h=2,3,\ldots , \\[4pt] R_{hj}^{(1)}(t) &= 0,\quad \mbox{otherwise} .\end{align*}

Also, analogously to (4.20) of [Reference Cohen7, page 239], we have the following recursive relation for $R_{hj}^{(n)}(t)$ for $t\gt0$ , $h,j=1,2,\ldots, n=2,3,\ldots$ :

(14) \begin{equation} R_{hj}^{(n)}(t) = \sum_{l=1}^{\infty} \int_{u=0}^t R_{hl}^ {(n-1)}(t-u)d_u R_{lj}^{(1)}(u) .\end{equation}

The following definitions will be used below:

\begin{align*}\gamma_{hj}^{(n)}(s) &\,{:\!=}\, \int_0^\infty \,{\textrm{e}}^{-s t} \,{\textrm{d}} R_{hj}^{(n)}(t), \quad h,j,n=1,2,\ldots , \\[4pt] \gamma_h^{(n)}(r,s) &\,{:\!=}\, \sum_{j=1}^\infty r^j \gamma_{hj}^{(n)}(s),\quad h,n=1,2,\ldots , \\[4pt] \gamma_{hj}(s,y) &\,{:\!=}\, \sum_{n=1}^\infty y^n \gamma_{hj}^{(n)}(s),\quad h,j=1,2,\ldots , \\[4pt] \gamma_h(r,s,y) &\,{:\!=}\, \sum_{n=1}^\infty y^n \gamma_h^{(n)}(r,s),\quad h=1,2,\ldots .\end{align*}

As an immediate consequence of (14), we obtain the following result.

Lemma 10. We have

(15) \begin{equation}\gamma_h^{(n)}(r,s) = \sum_{l=1}^\infty \gamma_{hl}^{(n-1)}(s) \cdot \gamma_l^{(1)}(r,s), \quad h=1,2,\ldots, n=2,3,\ldots .\end{equation}

The final term of the right-hand side of (15), $\gamma_l^{(1)}(r,s)$ , refers to the number of arrivals during a service time starting with l customers. We have to distinguish between starting with one or with two or more customers, since in the former case the queue might be empty upon service completion and this situation should be excluded as we restrict the analysis to the evolution within a busy period. A closed-form expression for this term is then given in the following lemma.

Lemma 11. We have

\begin{equation*}\gamma_1^{(1)}(r,s) = \tilde{X} (\lambda(1-r) + s ) - \tilde{X} (\lambda + s ),\end{equation*}

and for $h \geq 2$ ,

\begin{equation*} \gamma_h^{(1)}(r,s) = r^{h-1} \cdot \tilde{X} (\lambda(1-r) + s ) .\end{equation*}

Proof.Let us first consider the case $h \geq 2$ :

\begin{align*} \gamma_h^{(1)}(r,s) &= \sum_{j=1}^\infty r^j \gamma_{hj}^{(1)}(s)\\[3pt] & = \sum_{j=h-1}^\infty r^j \gamma_{hj}^{(1)}(s) \\[3pt] &= \sum_{j=h-1}^\infty r^j \int_{t=0}^\infty \,{\textrm{e}}^{-s t} \,{\textrm{d}} R_{hj}^{(1)}(t) \\[3pt] & = \int_{t=0}^\infty s \,{\textrm{e}}^{-s t} \sum_{j=h-1}^\infty r^j R_{hj}^{(1)}(t) \,{\textrm{d}} t \\[3pt] &= \int_{t=0}^\infty s \,{\textrm{e}}^{-s t} \int_{\tau=0}^t \,{\textrm{e}}^{-\lambda \tau} \sum_{j=h-1}^\infty r^{h-1} \cdot \dfrac{(r \lambda \tau)^{j+1-h}}{(j+1-h)!}\, {\textrm{d}} X(\tau) \,{\textrm{d}} t \\[3pt] &= r^{h-1} \int_{\tau=0}^\infty \,{\textrm{e}}^{-\lambda \tau(1-r)} \int_{t=\tau}^\infty s \cdot \,{\textrm{e}}^{-s t} \,{\textrm{d}} t \, {\textrm{d}} X(\tau) \\[3pt] &= r^{h-1} \cdot \tilde{X} (\lambda(1-r)+s ) .\end{align*}

For $h = 1$ , we should have at least one arrival before the first departure, otherwise the queue would become empty. Hence, in the derivation of $\gamma_1^{(1)}(r,s)$ , we do not encounter the complete power series representation of the exponential function, so that the final expression will consist of two parts. More precisely,

\begin{align*} \hspace*{76pt}\gamma_1^{(1)}(r,s) &= \sum_{j=1}^\infty r^j \gamma_{hj}^{(n)}(s) \\[3pt] &= \int_{t=0}^\infty s \,{\textrm{e}}^{-s t} \int_{\tau=0}^t \,{\textrm{e}}^{-\lambda \tau} \sum_{j=1}^\infty \dfrac{(r \lambda \tau)^{j}}{j!} \,{\textrm{d}} X(\tau)\,{\textrm{d}} t \\[3pt] &= \int_{\tau=0}^\infty \,{\textrm{e}}^{-\lambda \tau} \cdot ({\textrm{e}}^{-\lambda \tau r} - 1) \int_{t=\tau}^\infty s \,{\textrm{e}}^{-s t} \,{\textrm{d}} t\, {\textrm{d}} X(\tau) \\[3pt] &= \tilde{X} (\lambda (1-r) + s ) - \tilde{X} (\lambda + s ).\hspace*{134pt}\qed\\[-20pt]\end{align*}

Next, we are ready to present our main result of this section, i.e. a closed-form expression for $\gamma_h(r,s,y)$ .

Theorem 5. We have

\begin{equation*}\gamma_h(r,s,y) = \dfrac{r}{r - y \cdot \tilde{X} (\lambda(1-r) + s )} ( -\hat{\mu}^h(s,y) + y \cdot \tilde{X} (\lambda (1-r) + s ) \cdot r^{h-1} ),\end{equation*}

where $h=1,2,\ldots,$ and $\hat{\mu}(s,y)$ is the smallest root in x with absolute value smaller than one of the function $x = y \cdot \tilde{X} (\lambda(1-x) + s )$ .

Proof.Starting from the definition of $\gamma_h(r,s,y)$ and applying Lemmas 10 and 11, we obtain the following relations after some manipulations:

(16) \begin{align}& \gamma_1(r,s,y) \cdot \bigg(1 - \dfrac{y}{r} \cdot \tilde{X} (\lambda(1-r) + s )\bigg) = y \cdot ( \tilde{X} ( \lambda (1-r) + s ) - \tilde{X} (\lambda + s ) \cdot (1 + \gamma_{11}(s,y)) ) ,\end{align}

and for $h=2,3,\ldots,$

(17) \begin{align}& \gamma_h(r,s,y) \cdot \bigg(1 - \dfrac{y}{r} \cdot \tilde{X} (\lambda(1-r) + s )\bigg) = y \cdot ( \tilde{X} (\lambda(1-r) + s ) \cdot r^{h-1} - \tilde{X} (\lambda + s ) \cdot \gamma_{h1}(s,y)) ) .\end{align}

Let $\hat{\mu}(s,y)$ denote the smallest root of the function $x= y \cdot \tilde{X} (\lambda(1-x) + s )$ in x with absolute value smaller than one. Since the functions $\gamma_h(r,s,y)$ should be analytic for $|r|\leq1$ , it follows that $\hat{\mu}(s,y)$ is a zero of the right-hand side of the expressions above. Thus, we immediately obtain for $\gamma_{h1}(s,y)$

\begin{equation*}\gamma_{11}(s,y) = \dfrac{\hat{\mu}(s,y) - y \cdot \tilde{X} (\lambda + s )}{y \cdot \tilde{X} (\lambda + s )} ,\quad\gamma_{h1}(s,y) = \dfrac{\hat{\mu}^h(s,y)}{y \cdot \tilde{X} (\lambda + s )},\quad h=2,3,\ldots .\end{equation*}

Note that inserting $h=1$ in the latter expression, which we denote by $(\gamma_{h1}(s,y))|_{h=1}$ , shows that $\gamma_{11}(s,y) + 1 = (\gamma_{h1}(s,y))|_{h=1}$ . Finally, inserting these expressions into (16) and (17) completes the proof.

Appendix B: Proofs of results in Section 3

For convenience, let us recall the following definitions for $t\gt0$ :

\begin{align*}p_{hk}^{(n)}(t) &\,{:\!=}\,\begin{cases}\mathbb{P}(x_t = k,\, D(t)=n \mid x_0 = h) & h,k,n=0,1,\ldots, \\[4pt] 0 & \mbox{otherwise} ,\end{cases} \\[3pt] P_{hj}^{(n)}(t) &\,{:\!=}\, \mathbb{P}(z_{(n)}=j,\, r^{\prime}_n \le t \mid z_{(0)} = h), \quad n=1,2,\ldots, h,j=0,1,\ldots , \\[3pt] F^{(0)}_k(t) &\,{:\!=}\, {\textbf{1}}_{\{k=0\}}\mathbb{P}(A(t)=0,\, I \gt t) + {\textbf{1}}_{\{k \geq 1\}}\mathbb{P}(A(t)=k,\, I + X \gt t),\quad k=0,1,\ldots , \\[3pt] F_k(t) &\,{:\!=}\, \mathbb{P}(A(t)=k,\, X \gt t),\quad k=0,1,\ldots .\end{align*}

Proof of Lemma 3 Proof.The proof of Lemma 3 is carried out as follows:

(18) \begin{align}\hspace*{-40pt}p_{hk}^{(n)}(t) &\,{:\!=}\, \mathbb{P}(x_t = k, D(t)=n \mid x_0 = h) \notag \\[3pt]&= \mathbb{P}(x_t = k, r^{\prime}_n \leq t, r^{\prime}_{n+1} \gt\t\mid z_{(0)} = h) \hspace*{65pt}\\[-35pt] \nonumber\end{align}

(19) \begin{align}\hspace*{13pt} &= \int_{u=0}^t \sum_{j=0}^k \mathbb{P}(x_t = k,\, r^{\prime}_{n+1} \gt\t \mid r^{\prime}_n = u,\, z_{(0)} = h,\, z_{(n)}=j)\nonumber\\ & \quad \times d_u \mathbb{P}( r^{\prime}_n \leq u,\, z_{(n)}=j \mid z_{(0)} = h) \\[-35pt] \nonumber \end{align}

(20) \begin{align} \hspace*{25pt} = \int_{u=0}^t F^{(0)}_k(t-u) \,{\textrm{d}} P_{h0}^{(n)}(u) + \sum_{j=1}^k \int_{u=0}^t F_{k-j}(t-u) \,{\textrm{d}} P_{hj}^{(n)}(u). \end{align}

That is, first we rewrite the event $D(t)=n$ and use the assumption that at time 0 the 0th customer departed from the queue, so that we obtain (18). Next, we condition on the number of customers present at the nth departure, $z_{(n)}$ , and on the time this departure occurs, $r^{\prime}_n$ , which leads to (19). Finally, observing that $r_{n+1}$ , $ n=0,1,\ldots,$ depends in fact only on $r_{n}$ and $z_{(n)}$ , using that the arrival process is stationaryand applying the definitions of $F^{(0)}_k(t)$ , $ F_k(t)$ , and $P_{hj}^{(n)}(t)$ provides us with (20).

Let us define the following LSTs:

\begin{align*}\tilde{F}^{(0)}_k(s) &\,{:\!=}\, \int_{0-}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} F^{(0)}_{k}(t),\quad k=0,1,\ldots , \\[3pt] \tilde{F}_k(s) &\,{:\!=}\, \int_{0-}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} F_{k}(t),\quad k=0,1,\ldots , \\[3pt] \pi_{hj}^{(n)}(s) &\,{:\!=}\, \int_{0-}^\infty \,{\textrm{e}}^{-s t} \,{\textrm{d}} P_{hj}^{(n)}(t), \quad n=1,2,\ldots, h,j=0,1,\ldots .\end{align*}

Then, we may present the following result as an immediate consequence of Lemma 3.

Corollary 1. We have

\begin{equation*}\hspace*{73pt}\int_{t=0-}^\infty \,{\textrm{e}}^{-st} {\textrm{d}} p_{hk}^{(n)}(t)= \tilde{F}^{(0)}_k(s) \pi_{h0}^{(n)}(s) + \sum_{j=1}^k \tilde{F}_{k-j}(s) \pi_{hj}^{(n)}(s).\hspace*{72pt}\qed \end{equation*}

Proof of Lemma 4 Before we get to the actual proof of Lemma 4, we present another lemma. Let us introduce the auxiliary functions $G^{(0)}(r,s)$ and G(r, s). These functions refer to the number of customers that arrive in the system during a period which starts at a service completion instant at an arbitrary queue Q and ends at a timer expiration which occurs before the next service is completed. More specifically, the function $G^{(0)}(r,s)$ refers to the case with zero customers present after a service completion, while G(r, s) refers to the case with a strictly positive number of customers present at a service completion instant.

Lemma 12. We have

\begin{align*}G^{(0)}(r,s)&\,{:\!=}\, \sum_{k=0}^\infty r^k \tilde{F}_k^{(0)}(s) = \dfrac{s}{\lambda(1-r) + s} \cdot \dfrac{\lambda(1- r \cdot \tilde{X}(\lambda(1-r)+s)) + s}{\lambda + s} , \\[3pt] G(r,s) &\,{:\!=}\, \sum_{k=0}^\infty r^{k} \tilde{F}_k(s) = \dfrac{s}{\lambda(1-r)+s} \cdot ( 1 - \tilde{X}(\lambda(1-r)+s) ) .\end{align*}

Proof.First we will prove the expression for $G^{(0)}(r,s)$ as follows:

(21) \begin{align} G^{(0)}(r,s) &\,{:\!=}\, \sum_{k=0}^\infty r^k \tilde{F}_k^{(0)}(s) \notag \\[3pt] &= s \cdot \int_{t=0}^\infty \,{\textrm{e}}^{-st} \mathbb{P}(A(t)=0) \,{\textrm{d}} t + r \cdot \sum_{k=1}^\infty r^{k-1} \cdot s \cdot \int_{t=0}^\infty \,{\textrm{e}}^{-st} \mathbb{P}(A(t)=k,\quad I + X \gt t) \,{\textrm{d}} t \end{align}

(22) \begin{align} \hspace*{-104pt}= \dfrac{s}{\lambda(1-r) + s} \cdot \dfrac{\lambda(1- r \cdot \tilde{X}(\lambda(1-r)+s)) + s}{\lambda + s} .\end{align}

That is, we separate the terms for $k=0$ and $k \geq 1$ , insert the expression for $\tilde{F}_k^{(0)}(s)$ and perform some simple calculations, yielding (21). Next, we condition on the interarrival time (for the case $k \geq 1$ ) and use the fact that for a given time t the events $\{ A(t)=k \}$ and $\{ X\gt\t \}$ are independent. The final expression, (22), then readily follows from the Poisson arrival assumption and some simple manipulations. Analogously, we find for G(r, s) that

\begin{align*} G(r,s) &\,{:\!=}\, \sum_{k=0}^\infty r^{k} \tilde{F}_{k}(s) = \sum_{k=0}^\infty r^{k} \cdot s \int_{t=0}^\infty \,{\textrm{e}}^{-st} \mathbb{P}(A(t)=k,\, X \gt t) \,{\textrm{d}} t \notag \\* &= \dfrac{s}{\lambda(1-r)+s} \cdot ( 1 - \tilde{X}(\lambda(1-r)+s) ).\\[-40pt] \end{align*} \hfill\qed

Let us give several definitions which will be used in the proof of Lemma 4:

\begin{align*}\pi_h^{(n)}(r,s) &\,{:\!=}\, \sum_{j=0}^\infty r^j \pi_{hj}^{(n)}(s),\quad h=0,1,\ldots, n=1,2,\ldots , \\*\pi_{h0}(s,y) &\,{:\!=}\, \sum_{n=1}^\infty y^n \pi_{h0}^{(n)}(s),\quad h=0,1,\ldots , \\*\pi_h(r,s,y) &\,{:\!=}\, \sum_{n=1}^\infty y^n \pi_h^{(n)}(r,s),\quad h=0,1,\ldots .\end{align*}

Proof of Lemma 4. The proof of Lemma 4 in fact consists of the following three main steps:

(23) \begin{align}& \hspace*{-115pt}\sum_{n=1}^\infty y^n \sum_{k=0}^\infty r^k \int_{t=0}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} p_{hk}^{(n)}(t)\hspace*{40pt} \end{align}

(24) \begin{align} \hspace*{-43pt} = \sum_{n=1}^\infty y^n \sum_{k=0}^\infty r^k \bigg( \tilde{F}^{(0)}_k(s) \pi_{h0}^{(n)}(s) + \sum_{j=1}^k \tilde{F}_{k-j}(s) \pi_{hj}^{(n)}(s) \bigg) \end{align}

(25) \begin{align} &\quad = \sum_{n=1}^\infty y^n ( G^{(0)}(r,s) \cdot \pi_{h0}^{(n)}(s) + G(r,s) ( \pi_h^{(n)}(r,s) - \pi_{h0}^{(n)}(s) ) ) \\[3pt] &\quad = \dfrac{s}{\lambda(1-r) + s} \cdot \dfrac{\lambda(1- r \cdot \tilde{X}(\lambda(1-r)+s)) + s}{\lambda + s} \cdot \pi_{h0}(s,y) \notag \\[3pt] &\quad\quad\, + \dfrac{s}{\lambda(1-r) + s} \cdot (1 - \tilde{X}(\lambda(1-r)+s)) \cdot (\pi_h(r,s,y) - \pi_{h0}(s,y) ). \notag\end{align}

In the first step, we substitute the result of Corollary 1 into (23) leading to (24). Next, we derive the generating function with respect to the number of customers at the end of a visit. After some manipulations and using the definitions of $G^{(0)}(r,s)$ , G(r, s), $ \pi_{h0}^{(n)}(s)$ , and $\pi_{h}^{(n)}(r,s)$ , we arrive at (25). In the final step, we use the definitions of $\pi_h(r,s,y) $ and $\pi_{h0}(s,y)$ and insert the explicit expressions for $G^{(0)}(r,s)$ and G(r, s) which were derived in Lemma 12.

Proof of Theorem 1 We prove the expression for $\beta^i({\textbf{z}})$ for a specific queue $Q_i$ as given in Theorem 1 by first deriving the conditional p.g.f. $\beta_\textbf{n}^i({\textbf{z}}) \,{:\!=}\, \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}\mid \textbf{N}_i^s = \textbf{n}]$ and then unconditioning on $\textbf{N}_i^s$ , the number of customers present at the start of a visit to $Q_i$ . For convenience, let us define $\xi^*_i$ as follows:

\begin{equation*}\xi^*_i \,{:\!=}\, \xi_i + \sum_{j \not= i} \lambda_j(1-z_j) .\end{equation*}

We recall that we refer to a specific queue $Q_i$ by adding an index i to a generic variable. Next, $\beta_\textbf{n}^i({\textbf{z}})$ can be expressed as follows.

Lemma 13. We have

(26) \begin{align}\beta_\textbf{n}^i({\textbf{z}})&= \dfrac{\xi_i}{\xi^*_i} \cdot \big( G_i^{(0)}(z_i,\xi^*_i) \cdot ( \pi_{n_i,0}(\xi^*_i,r^i({\textbf{z}})) + {\textbf{1}}_{\{ n_i=0 \}} )+ G_i(z_i, \xi^*_i) \cdot ( \pi_{n_i}(z_i,\xi^*_i,r^i({\textbf{z}})) + z_i^{n_i} \notag \\[3pt] & \qquad\,- \pi_{n_i,0}(\xi^*_i,r^i({\textbf{z}})) - {\textbf{1}}_{\{ n_i=0 \}}) \bigr) \cdot \prod_{j \not= i} z_j^{n_j}.\end{align}

Proof.Let $A_{i,j}(t)$ denote the number of arrivals to $Q_j$ (both external and internal arrivals) during a visit to $Q_i$ . Recall further that $D_i(t)$ denotes the number of departures at $Q_i$ from time 0 to t. Starting from the definition of the p.g.f., we condition on the timer $Y_i$ and introduce the number of departures from $Q_i$ until time t:

\begin{align*} \beta_\textbf{n}^i({\textbf{z}}) & = \sum_{m_1=0}^\infty \cdots \sum_{m_M=0}^\infty z_1^{m_1} \cdots z_M^{m_M} \mathbb{P}(\textbf{N}_i^e = \textbf{m} \mid \textbf{N}_i^s = \textbf{n}) \\[3pt] &= \int_0^{\infty} \xi_i \,{\textrm{e}}^{- \xi_i t} \sum_{m_1=0}^\infty \cdots \sum_{m_M=0}^\infty z_1^{m_1} \cdots z_M^{m_M} \sum_n \mathbb{P}(\textbf{N}_i(t) = \textbf{m},\, D_i(t)=n \mid \textbf{N}_i(0) = \textbf{n}) \,{\textrm{d}} t.\end{align*}

After some simple rearrangements and using that, given t and $D_i(t)$ , the queue-length process at $Q_i$ is independent of the aggregate arrival process to the other queues, we obtain the following:

\begin{align*} & \int_0^{\infty} \xi_i \,{\textrm{e}}^{- \xi_i t} \sum_n \sum_{m_1=0}^\infty \cdots \sum_{m_M=0}^\infty z_1^{m_1-n_1} \cdots z_M^{m_M-n_M} \\[3pt] & \quad\, \times \mathbb{P}( \{A_{i,j}(t) = m_j - n_j,\, \text{for } {j \not= i} \} \mid D_i(t)=n,\, \textbf{N}_i(0) = \textbf{n}) \\[3pt] & \quad\, \times \sum_{m_i} z_i^{m_i} \mathbb{P}(N_{i,i}(t) = m_i \mid D_i(t)=n,\, \textbf{N}_i(0) = \textbf{n}) \\[3pt] & \quad\, \times \mathbb{P}(D_i(t)=n \mid \textbf{N}_i(0) = \textbf{n})\,{\textrm{d}} t \cdot \prod_{j \not= i} z_j^{n_j}.\end{align*}

These aggregate arrivals to $Q_j$ , $ j\not= i$ , can be decomposed into two independent parts, namely a first part referring to external arrivals at each queue and a second part referring to customers that were served at $Q_i$ and routed to some other queue. The latter is represented by the term $(r^i({\textbf{z}}))^n$ . Also noting that $N_{i,i}(t)$ depends only on $\textbf{N}_i(0)$ through $N_{i,i}(0)$ , we retrieve $p_{n_i m_i}^{(n)}(t)$ and eventually find that

(27) \begin{equation} \beta_\textbf{n}^i({\textbf{z}}) = \int_0^{\infty} \xi_i \,{\textrm{e}}^{-\xi^*_i t} \sum_{n=0}^\infty \sum_{m_i=0}^{\infty} z_i^{m_i} (r^i({\textbf{z}}))^n p_{n_i m_i}^{(n)}(t) \,{\textrm{d}} t \cdot \prod_{j \not= i} z_j^{n_j}.\end{equation}

Then, we can apply Lemma 4 for $n \geq 1$ , while for $n=0$ we use

\begin{align*} & \sum_{m_i=0}^{\infty} z_i^{m_i} \int_0^{\infty} \xi_i \,{\textrm{e}}^{-\xi^*_i t} p_{n_i m_i}^{(0)}(t) \,{\textrm{d}} t \\[3pt] & \quad = {\textbf{1}}_{\{n_i=0\}} \cdot \sum_{m_i=0}^{\infty} z_i^{m_i} \int_0^{\infty} \xi_i \,{\textrm{e}}^{-\xi^*_i t} \mathbb{P}(A_i(t)=m_i, \, I_i + X_i \gt t) \,{\textrm{d}} t \\[3pt] & \quad\quad\, + {\textbf{1}}_{\{n_i \geq 1\}} \cdot \sum_{m_i=0}^{\infty} z_i^{m_i} \int_0^{\infty} \xi_i \,{\textrm{e}}^{-\xi^*_i t} \mathbb{P}(A_i(t)= m_i - n_i,\, X_i \gt t) \,{\textrm{d}} t \\[3pt] & \quad = \dfrac{\xi_i}{\xi^*_i} \cdot ( {\textbf{1}}_{\{n_i=0\}} \cdot G_i^{(0)}(z_i, \xi^*_i)+ {\textbf{1}}_{\{n_i \geq 1\}} \cdot z_i^{n_i} \cdot G_i(z_i, \xi^*_i) ) . \end{align*}

The final expression for $\beta_\textbf{n}^i({\textbf{z}})$ follows from inserting this result together with the result from Lemma 4 into (27) and some simple manipulations.

Proof of Theorem 1. The proof follows immediately by unconditioning $\beta_\textbf{n}^i({\textbf{z}})$ on the state $\textbf{n}=(n_1,\ldots,n_M)$ at the start of the visit. The result of this operation is shown below. Equation (28) follows by substitution of (26) into the definition of $\beta^i({\textbf{z}})$ . We note that the final expression, (29), follows from inserting the explicit expressions for $G_i^{(0)}(r,s)$ and $G_i(r,s)$ (see Lemma 12), inserting the expressions for $\pi_{h}(z_i,\xi^*_i,r^i({\textbf{z}}))$ and $\pi_{h0}(\xi^*_i,r^i({\textbf{z}}))$ , $h \geq 0,$ which are given in (2), (4), and (5), and some simple manipulations. That is,

(28) \begin{align}\beta^i({\textbf{z}})&= \sum_{n_1=0}^\infty \cdots \sum_{n_M=0}^\infty \beta_{\textbf{n}}^i({\textbf{z}}) \mathbb{P}(\textbf{N}_i^s =\textbf{n}) \notag \\[3pt] &= \sum_{n_1=0}^\infty \cdots \sum_{n_M=0}^\infty \mathbb{P}(\textbf{N}_i^s =\textbf{n}) \cdot \prod_{j \not= i} z_j^{n_j} \cdot \dfrac{\xi_i}{\xi^*_i} \notag \\[3pt] &\quad\, \times \big( G_i(z_i, \xi^*_i) \cdot ( \pi_{n_i}(z_i,\xi^*_i,r^i({\textbf{z}})) + z_i^{n_i} - \pi_{n_i,0}(\xi^*_i,r^i({\textbf{z}})) - {\textbf{1}}_{\{ n_i=0 \}}) \notag \\[3pt] &\quad\, \phantom{\times\,\big( } + G_i^{(0)}(z_i,\xi^*_i) \cdot ( \pi_{n_i,0}(\xi^*_i,r^i({\textbf{z}})) + {\textbf{1}}_{\{ n_i=0 \}} ) \big) \end{align}

(29) \begin{align}\hspace*{-45pt}&= \dfrac{\xi_i}{z_i - r^i({\textbf{z}}) \cdot \tilde{X}_i(\xi_i + \sum_j \lambda_j(1-z_j))} \notag \\[3pt] &\quad\, \times \bigg( \dfrac{\tilde{X}_i(\xi_i + \sum_j \lambda_j(1-z_j)) \cdot(z_i-r^i({\textbf{z}}))}{\lambda_i(1-\hat{\mu}_i(\xi_i,r^i({\textbf{z}}))) + \xi^*_i} \cdot \alpha^i({\textbf{z}}_i^*) \notag \\[3pt] &\quad\, \phantom{\times\, \bigg(} + \dfrac{(1 - \tilde{X}_i(\xi_i + \sum_j \lambda_j(1-z_j))) \cdot z_i}{\lambda_i(1-z_i) + \xi^*_i} \cdot \alpha^i({\textbf{z}}) \bigg) ,\hspace*{50pt} \end{align}

where

\[\alpha^i({\textbf{z}}_i^*) \,{:\!=}\, \mathbb{E}\big[z_1^{N^s_1} \cdots \hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))^{N^s_i} \cdots z_M^{N^s_M}\big]\]

and $\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))$ is the root x with the smallest absolute value less than one of $x=r^i({\textbf{z}})\cdot \tilde{X}_i(\xi^*_i+\lambda_i(1-x))$ .

Appendix C: Proofs of results in Section 4

For convenience, let us recall the following definitions for $t\gt0$ :

\begin{align*} q_{hk}^{(n)}(t) &\,{:\!=}\,\begin{cases}\mathbb{P}(x_t = k,\, D(t) = n,\, x_v>0,\, 0 \lt v \lt t \mid x_0 = h) & n=0,1,\ldots, h,k=1,2,\ldots \\[3pt] 0 & \mbox{otherwise,}\end{cases} \\[3pt] R_{hj}^{(n)}(t) &\,{:\!=}\, \mathbb{P}(z_{(n)}=j,\, r^{\prime}_n \le t,\, z_{(k)} \gt 0, 0 \lt k < n \mid z_{(0)} = h), \quad h,j,n=1,2,\ldots , \\[3pt] F_k(t) &\,{:\!=}\, \mathbb{P}(A(t)=k,\, X \gt t),\quad k=0,1,\ldots .\end{align*}

Proof of Lemma 5 Proof.The first observation is that each customer at $Q_j$ , $ j \not= i,$ will still be present at the end of the visit, which is accounted for in the term $\prod_{j \not= i} z_j^{n_j}$ . Second, each customer present at the start of the visit at $Q_i$ will effectively be replaced by a random population during the course of the visit in anidentical fashion. In particular, the size of this population is given by $\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))$ . To see this, recall that $\hat{\mu}_i(s,y)$ refers to the joint generating function of the busy period and the number of customers served during this period. The term $\xi^*_i$ in $\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))$ accounts for the exogenous arrivals to the other queues in the system during a busy period that endsbefore the timer expires. Similarly, the term $r^i({\textbf{z}})$ in $\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))$ accounts for the internal arrivals to the other queues (from $Q_i$ ) during this period. As initially there are $n_i$ identical customers present at $Q_i$ , this leads to $n_i$ independent contributions which are recognized in the power of $\hat{\mu}_i(\xi^*_i,r^i({\textbf{z}}))$ .

Proof of Lemma 6 Proof.Lemma 6 is readily proved by using arguments similar to those in the proof of Lemma 3:

\begin{align*}q_{hk}^{(n)}(t)&= \mathbb{P}(x_t = k,\, D(t)=n,\, x_v\gt0,\, 0 \lt v < t \mid x_0 = h) \\[3pt] &= \mathbb{P}(x_t = k,\, r^{\prime}_n \leq t,\, r^{\prime}_{n+1} \gt\t, \, x_v\gt0,\, 0 \lt v < t\mid z_{(0)} = h) \\[3pt] &= \int_{u=0}^t \sum_{j=1}^k \mathbb{P}(x_t = k,r^{\prime}_{n+1} \gt\t \mid r^{\prime}_n = u,z_{(0)} = h, z_{(m)} \gt 0,0 \leq m \leq n, \, z_{(n)}=j)\\[3pt] &\quad\, \times d_u \mathbb{P}( r^{\prime}_n \leq u,\, z_{(n)}=j, \, z_{(m)}\gt0,\, 0 \lt m < n \mid z_{(0)} = h) \\[3pt] &= \int_{u=0}^t \sum_{j=1}^k F_{k-j}(t-u) \,{\textrm{d}} R_{hj}^{(n)}(u) .\end{align*}

Let us define the following LSTs:

\begin{align*} \tilde{F}_k(s) &\,{:\!=}\, \int_{0-}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} F_{k}(t),\quad k=0,1,\ldots , \\[3pt] \gamma_{hj}^{(n)}(s) &\,{:\!=}\, \int_{0-}^\infty \,{\textrm{e}}^{-s t} \,{\textrm{d}} R_{hj}^{(n)}(t), \quad h,j,n=1,2,\ldots. \\[-40pt] \end{align*} \hfill\qed

Note that a direct consequence of Lemma 6 is the following.

Corollary 2. We have

(30) \begin{equation}\int_{t=0}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} q_{hk}^{(n)}(t) = \sum_{j=1}^k \gamma_{hj}^{(n)}(s) \tilde{F}_k(s) , \quad h,k,n=1,2,\ldots .\end{equation}

Proof of Lemma 7 Let us give several definitions which will be used in the proof of Lemma 7:

\begin{align*}\gamma_h^{(n)}(r,s) &\,{:\!=}\, \sum_{j=0}^\infty r^j \gamma_{hj}^{(n)}(s),\quad h,n=1,2,\ldots , \\[3pt] \gamma_h(r,s,y) &\,{:\!=}\, \sum_{n=1}^\infty y^n \gamma_h^{(n)}(r,s),\quad h=1,2,\ldots .\end{align*}

Proof of Lemma 7. The proof consists of three consecutive steps similar to the proof of Lemma 4:

(31) \begin{align} & \sum_{n=1}^\infty y^n \sum_{k=1}^\infty r^k \int_{t=0}^\infty \,{\mathrm{e}}^{-st} \,{\mathrm{d}} q_{hk}^{(n)}(t) \notag \\[3pt] &\quad = \sum_{n=1}^\infty y^n \sum_{k=1}^\infty r^k \sum_{j=1}^k \gamma_{hj}^{(n)}(s) \tilde{F}_{k-j}(s).\end{align}

(32) \begin{align} \hspace*{65pt}&\quad = \sum_{n=1}^\infty y^n \gamma_{h}^{(n)}(r,s) G(r,s) \notag\\[3pt] &\quad = \gamma_{h}(r, s, y) \cdot \dfrac{s}{\lambda(1-r) + s} \cdot (1 - \tilde{X}(\lambda(1-r) + s)).\end{align}

First we substitute (30) into (31). Next, using the definitions of $\gamma_{h}^{(n)}(r,s)$ and G(r, s) (see Lemma 12) immediately yields (32). The final step follows from the definition of $\gamma_{h}(r, s, y)$ and the substitution of the explicit expression for G(r, s).

Proof of Lemma 8 As a preliminary to proving Lemma 8, we present the following result for $h=1,2,\ldots,$ for the special case of $D(t)=0$ , that is, no departures occur before the timer expires.

Lemma 14. We have

\begin{equation*} \sum_{k=1}^\infty r^{k} \int_{t=0}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} q_{hk}^{(0)}(t)= r^{h} \cdot \dfrac{s}{\lambda(1-r) + s} \cdot (1 - \tilde{X}(\lambda(1-r) + s)) .\end{equation*}

Proof.

(33) \begin{align}& \sum_{k=1}^\infty r^{k} \int_{t=0}^\infty \,{\textrm{e}}^{-st} \,{\textrm{d}} q_{hk}^{(0)}(t) \notag \\*&\quad = r^{h} \cdot \int_{t=0}^\infty s \,{\textrm{e}}^{-s t} \sum_{k=h}^\infty r^{k-h} \mathbb{P}(A(t)= k-h,\, X \gt t) \,{\textrm{d}} t \end{align}

(34) \begin{align}= r^{h} \cdot \dfrac{s}{\lambda(1-r) + s} \cdot (1 - \tilde{X}(\lambda(1-r) + s)) .\end{align}

Elaborating on the definition of $q_{hk}^{(0)}(t)$ , we may obtain (33) after some simple manipulations. Equation (34) then follows directly from the earlier derivation of G(r, s) (see Lemma 12).

Proof of Lemma 8. To consider a specific queue $Q_i$ , we will again add an index i to the generic variables. Let $A_{i,j}(t)$ denote the number of arrivals to $Q_j$ (both external and internal arrivals) during a visit to $Q_i$ . Recall further that $D_i(t)$ denotes the number of departures at $Q_i$ from time 0 to t. Starting from the definition of the p.g.f., we condition on the timer $Y_i$ and introduce the number of departures from $Q_i$ until time t:

\begin{align*}& \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{timer}\}} \mid \textbf{N}_i^s = \textbf{n}] \\[3pt] &\quad = \sum_{m_1=0}^\infty \cdots \sum_{m_M=0}^\infty z_1^{m_1} \cdots z_M^{m_M} \mathbb{P}(\textbf{N}_i^e = \textbf{m},\, \{\text{timer}\}\mid \textbf{N}_i^s = \textbf{n}) \\[3pt] &\quad = \int_0^{\infty} \xi_i \,{\textrm{e}}^{- \xi_i t} \sum_{m_1=0}^\infty \cdots \sum_{m_M=0}^\infty z_1^{m_1} \cdots z_M^{m_M} \\[3pt] &\quad\quad\, \times \sum_n \mathbb{P}(\textbf{N}_i(t) = \textbf{m},\, \{\text{timer}\},\, D_i(t)=n \mid \textbf{N}_i(0) = \textbf{n}) \,{\textrm{d}} t.\end{align*}

Using that given t and $D_i(t)$ the queue-length process at $Q_i$ is independent of the aggregate arrival process to the other queues and working out the event $\{ \text{timer} \}$ , we obtain

\begin{align*}& \int_0^{\infty} \xi_i \,{\textrm{e}}^{- \xi_i t} \sum_n \sum_{m_1=0}^\infty \cdots \sum_{m_M=0}^\infty z_1^{m_1-n_1} \cdots z_M^{m_M-n_M} \\[3pt] &\quad\, \times \mathbb{P}( \{A_{i,j}(t) = m_j - n_j,\, \text{for }{j \not= i} \} \mid D_i(t)=n,\, \textbf{N}_i(0) = \textbf{n}) \\[3pt] &\quad\, \times \sum_{m_i} z_i^{m_i} \mathbb{P}(N_{i,i}(t) = m_i,\, N_{i,i}(v)>0,\, 0 \lt v < t \mid D_i(t)=n,\, \textbf{N}_i(0) = \textbf{n}) \\*&\quad\, \times \mathbb{P}(D_i(t)=n \mid \textbf{N}_i(0) = \textbf{n}) \,{\textrm{d}} t \cdot \prod_{j \not= i} z_j^{n_j}.\end{align*}

Exactly following the same reasoning that led to (27), we obtain

\begin{equation*} \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{timer}\}} \mid \textbf{N}_i^s = \textbf{n}] =\int_{t=0}^\infty \xi_i \,{\textrm{e}}^{-\xi^*_i t} \sum_{n=0}^\infty \sum_{m_i=1}^{\infty} z_i^{m_i} (r^i({\textbf{z}}))^n q_{n_i m_i}^{(n)}(t) \,{\textrm{d}} t \cdot \prod_{j \not=i} z_j^{n_j} .\end{equation*}

Then, we may apply Lemma 7 for $n\geq 1$ and Lemma 14 for $n=0$ . This yields the desired result in (9) after substituting the explicit expressions for $G_i(r,s)$ (see Lemma 12) and $\gamma_h(r,s,y)$ (see (2)) and performing some simple manipulations.

Proof of Theorem 2 The final result for $\beta^i({\textbf{z}})$ is obtained by first unconditioning the conditional p.g.f.s of the previous lemmas and then merging these outcomes. Let us define $\beta^i_{e}({\textbf{z}}) \,{:\!=}\, \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{empty}\}} ]$ and $\beta^i_{t}({\textbf{z}}) \,{:\!=}\, \mathbb{E}[{\textbf{z}}^{\textbf{N}_i^e}{\textbf{1}}_{\{\text{timer}\}} ]$ . Recall that $\alpha^i({\textbf{z}}_i^*) = \alpha^i(z_1,\ldots,z_{i-1},$ $ \hat{\mu}_i(\xi^*_i,r^i({\textbf{z}})),z_{i+1},\ldots,z_M)$ . By unconditioning the expressions in Lemmas 5 and 8, it follows immediately that

\begin{equation*}\beta^i_{e}({\textbf{z}}) = \alpha^i({\textbf{z}}_i^*)\end{equation*}

and

\begin{equation*}\beta^i_{t}({\textbf{z}}) = \dfrac{\xi_i \cdot z_i \cdot (1 - \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i))}{(\lambda_i(1-z_i) + \xi^*_i)(z_i - r^i({\textbf{z}}) \cdot \tilde{X}_i(\lambda_i(1-z_i) + \xi^*_i))}\cdot (\alpha^i({\textbf{z}}) - \alpha^i({\textbf{z}}_i^*)) .\end{equation*}

Proof of Theorem 2. The proof follows directly from $ \beta^i({\textbf{z}})= \beta^i_{e}({\textbf{z}}) + \beta^i_{t}({\textbf{z}})$ , where the last two terms are given in the latter two equations.

Proofs of results in Section 5.1

For convenience, let us recall that the batch sizes are assumed to be mutually independent and independent of the arrival and the service processes. Let $\lambda$ denote the arrival rate of batches and ${\hat \psi(\cdot)}$ the generating function of the batch size. Recall that the generating function of the service time of an individual customer is denoted by ${\tilde X(\cdot)}$

Let ${z_{(n)}}$ denote the number of customers left behind by the nth departing customer after time 0 and let ${r^{\prime}_{n}}$ be its departure time. We assume that at time $t=0$ customer 0 departs. Let $R_{hj}^{(n)}(t)$ denote the probability

\[R_{hj}^{(n)}(t) \,{:\!=}\, {{\mathbb P}}({z_{(n)}}=j, {r^{\prime}_{n}}\le t, {z_{(k)}}\gt0, 0\ltk\lt\n\mid {z_{(0)}}=h),\]

for $h=1,2,\ldots.$

Proof of Lemma 9. Let us denote

\[P_{hk}^{(n)}(t) \,{:\!=}\, {{\mathbb P}}({z_{(n)}}=k, {r^{\prime}_{n}} \le t\mid{z_{(0)}}=h).\]

Our objective is to find the joint generating function

\[\pi_h(r,s,y) \,{:\!=}\, \sum_{n=1}^\infty y^n \mathbb{E}[r^{{z_{(n)}}}\,{\textrm{e}}^{-s{r^{\prime}_{n}}}].\]

Define

\[\pi_{hk}(s,y) \,{:\!=}\, \sum_{n=1}^\infty y^n\int_0^\infty \,{\textrm{e}}^{-st}\,{\textrm{d}} P_{hk}^{(n)}(t).\]

Following [Reference Cohen7, pages 239–240, 386–387], we find that

(35) \begin{align}& \pi_h(r,s,y) (r-y{\tilde X ({s+\lambda(1-{\hat \psi (r) })})} ) \notag \\[3pt] &\quad =\dfrac{y{\tilde X ({s+\lambda(1-{\hat \psi (r) })})}}{\lambda+s} (\lambda\pi_{h0}(s,y)({\hat \psi (r) }-\lambda-s)+(\lambda+s)\delta_h(r,s) ),\end{align}

where $h=0,1,2,\ldots,$ and

\[\delta_h(r,s)=\begin{cases}\dfrac{\lambda{\hat \psi (r) }}{\lambda+s} & h=0,\\[6pt]r^h & h=1,2,\ldots.\end{cases}\]

For $\textrm{Re}(s)\ge0$ and $|y|<1$ , the equation $r=y{\tilde X ({s+\lambda(1-{\hat \psi (r) })} )}$ has a unique root $r=\hat\mu(s,y)$ with $|r|<1$ which can be seen by applying Takács’ lemma. Since for $\textrm{Re}(s)\ge0$ and $|y|<1$ the functions $\pi_h(r,s,y)$ , $h=0,1,\ldots$ are analytic in $|r|\le1$ , it follows that $\hat\mu(s,y)$ should also be a zero of the right-hand side of (35). After some algebra we find that

\begin{align*} \pi_{00}(s,y)&=\dfrac{\lambda}{\lambda-{\hat \psi ({\hat\mu(s,y)})}+s}\hat\mu(s,y),\\[3pt] \pi_{h0}(s,y)&=\dfrac{\lambda+s}{\lambda-{\hat \psi ({\hat\mu(s,y)})}+s}\hat\mu^h(s,y),\quad h=1,2,\ldots . \end{align*}

The latter yields that

\begin{align*}& \pi_h(r,s,y)\\[3pt] &\quad ={{\bigg(\!y{\tilde X ({s+\lambda(1-{\hat \psi (r)})})} \bigg(\!r^h-\dfrac{s+\lambda(1-{\hat \psi (r)})}{s+\lambda(1-{\hat \psi ({\hat\mu(s,y)})})}\hat\mu^h(s,y)\bigg)\bigg)}\!\bigg/\!{\big(r-y{\tilde X ({s+\lambda(1{-}\,{\hat \psi (r)})})}\big)}},\end{align*}

for $h=0,1,\ldots.$

An analysis similar to that in Appendix A gives the joint generating function $\gamma_h(r,s,y)$ of the probability $R_{hj}^{(n)}(t)$ , which completes the proof.