4.1 The joint queue-length distribution
In the polling literature, the probability generating function (PGF) of the joint queue-length distribution at various epochs is extensively studied (for example., [
11,
13,
18]). Let
\(\widetilde{LB}^{\left( V_{i}\right) }\left( \varvec{z}\right) \) and
\(\widetilde{LC}^{\left( V_{i}\right) }\left( \varvec{z}\right) \) be the joint queue-length PGF at
visit beginnings and completions at
\(Q_{i}\), where
\(\varvec{z}=\left( z_{1},\dots ,z_{N}\right) \) is an
N-dimensional vector with
\(\left| z_{i}\right| \le 1\). Similarly, let
\(\widetilde{LB}^{\left( S_{i}\right) }\left( \varvec{z}\right) \) and
\(\widetilde{LC}^{\left( S_{i}\right) }\left( \varvec{z}\right) \) be the joint queue-length PGFs at
switch-over beginnings and completions at
\(Q_{i}\), respectively. Because of the branching property [
16], these PGFs can be related to each other as follows:
$$\begin{aligned} \widetilde{LC}^{\left( V_{i}\right) }\left( \varvec{z}\right)&= \widetilde{LB}^{\left( V_{i}\right) }\left( z_{1},\dots ,z_{i-1},\right. \nonumber \\&\quad \,\left. \widetilde{BP}_{i}\left( \lambda -\lambda \widetilde{K}\left( z_{1},\dots ,z_{i-1},1,z_{i+1},\dots ,z_{N}\right) \right) ,z_{i+1},\dots ,z_{N}\right) , \end{aligned}$$
(2)
$$\begin{aligned} \widetilde{LB}^{\left( S_{i}\right) }\left( \varvec{z}\right)&= \widetilde{LC}^{\left( V_{i}\right) }\left( \varvec{z}\right) ,\end{aligned}$$
(3)
$$\begin{aligned} \widetilde{LC}^{\left( S_{i}\right) }\left( \varvec{z}\right)&= \widetilde{LB}^{\left( S_{i}\right) }\left( \varvec{z}\right) \widetilde{S}_{i}\left( \lambda -\lambda \widetilde{K}\left( \varvec{z}\right) \right) ,\end{aligned}$$
(4)
$$\begin{aligned} \widetilde{LB}^{\left( V_{i+1}\right) }\left( \varvec{z}\right)&= \widetilde{LC}^{\left( S_{i}\right) }\left( \varvec{z}\right) , \end{aligned}$$
(5)
where
\(i=1,\dots ,N\) and
\(\widetilde{BP}_{i}\left( .\right) \) is the LST of a busy period in
\(Q_{i}\), equals that of an
\(M^{X}/G/1\) queue initiated by the service of a customer and is given by
$$\begin{aligned} \widetilde{BP}_{i}\left( \omega \right)&=\widetilde{B}_{i}\left( \omega +\lambda -\lambda \widetilde{K}_{i}\left( \widetilde{BP}_{i}\left( \omega \right) \right) \right) . \end{aligned}$$
(6)
Equations (
2)–(
5) are referred to in the polling literature as the
laws of motion. The interpretation of (
2) is that the queue-length in
\(Q_{j}\),
\(j\ne i\), at the end of visit period
\(V_{i}\) is given by the number of customers already at
\(Q_{j}\) at the visit beginning plus all the customers who arrive in the system during visit period
\(V_{i}\). For
\(Q_{i}\), all customers who are already in
\(Q_{i}\) or arrive during
\(V_{i}\) will be served before the end of the visit completion, and therefore,
\(Q_{i}\) will contain no customers at the end of the visit period. Equation (
3) simply states that the PGF of a visit completion corresponds to the PGF of the next switch-over beginning (see also Fig.
1). Finally, the queue-length vector at a switch-over completion corresponds to the sum of customers already present at the switch-over beginning plus all the customers who arrive during this switch-over period (
4), and by definition the queue-length vector at a switch-over completion is the same for the next visit beginning (
5). Note that Eqs. (
2)–(
5) can be differentiated with respect to
\(z_{1},\dots ,z_{N}\) to compute moments of the queue-length distributions on embedded points [
14] or numerically inverted for the queue-length probability distributions (for example, [
6] for the case for non-simultaneous arrivals).
Let
\(\widetilde{LB}^{\left( B_{i}\right) }\left( \varvec{z}\right) \) and
\(\widetilde{LC}^{\left( B_{i}\right) }\left( \varvec{z}\right) \) be the joint queue-length PGFs at
service beginnings and completions at
\(Q_{i}\). Eisenberg [
8] proved that besides the laws of motion, there exists a simple relation between the joint queue-length distributions at
visit- and
service beginnings and completions. He observed that each visit beginning either starts with a service beginning, or with a visit completion in the case where there are no customers at the queue. Similarly, each visit completion coincides with either a visit beginning or a service completion. Eisenberg [
8] only considered polling systems either with exhaustive or gated service at all queues and individual arriving customers, but [
4] has proven that the relation is not restricted to a particular service discipline and also holds for general branching-type service disciplines. In this section, we generalize this result for the case of simultaneous batch arrivals. Similarly to [
8], the four PGFs are related as follows:
$$\begin{aligned} \widetilde{LB}^{\left( V_{i}\right) }\left( \varvec{z}\right) +\lambda _{i}E\left( C\right) \widetilde{LC}^{\left( B_{i}\right) }\left( \varvec{z}\right)&=\lambda _{i}E\left( C\right) \widetilde{LB}^{\left( B_{i}\right) }\left( \varvec{z}\right) +\widetilde{LC}^{\left( V_{i}\right) }\left( \varvec{z}\right) , \end{aligned}$$
(7)
where the term
\(1/\left( \lambda _{i}E\left( C\right) \right) \) is the long-run ratio between the number of service beginnings/completions and visit beginnings/completions in
\(Q_{i}\), for every
\(i=1,\dots ,N\).
Furthermore, the joint queue-length distribution at service beginnings and completions are related via
$$\begin{aligned} \widetilde{LC}^{\left( B_{i}\right) }\left( \varvec{z}\right)&=\widetilde{LB}^{\left( B_{i}\right) }\left( \varvec{z}\right) \left[ \widetilde{B}_{i}\left( \lambda -\lambda \widetilde{K}\left( \varvec{z}\right) \right) /z_{i}\right] . \end{aligned}$$
(8)
Substituting (
8) in (
7) and rearranging terms, the joint queue-length distribution at a service beginning can be written as
$$\begin{aligned} \widetilde{LB}^{\left( B_{i}\right) }\left( \varvec{z}\right)&=\frac{z_{i}\left( \widetilde{LC}^{\left( V_{i}\right) }\left( \varvec{z}\right) -\widetilde{LB}^{\left( V_{i}\right) }\left( \varvec{z}\right) \right) }{\lambda _{i}E\left( C\right) \left( \widetilde{B}_{i}\left( \lambda -\lambda \widetilde{K}\left( \varvec{z}\right) \right) -z_{i}\right) }. \end{aligned}$$
(9)
Next, we can find the PGFs of the joint queue-length distributions at an arbitrary moment during
\(V_{i}\) and
\(S_{i}\), denoted by
\(\tilde{L}^{\left( V_{i}\right) }\left( \varvec{z}\right) \) and
\(\tilde{L}^{\left( S_{i}\right) }\left( \varvec{z}\right) \), by noticing that the queue-length at an arbitrary moment in
\(V_{i}\) or
\(S_{i}\) is equal to the queue-length at service/switch-over beginning plus the number of customers who arrived in the past service/switch-over time,
$$\begin{aligned} \tilde{L}^{\left( V_{i}\right) }\left( \varvec{z}\right)&=\widetilde{LB}^{\left( B_{i}\right) }\left( \varvec{z}\right) \frac{1-\widetilde{B}_{i}\left( \lambda -\lambda \widetilde{K} \left( \varvec{z}\right) \right) }{E\left( B_{i}\right) \left( \lambda -\lambda \widetilde{K} \left( \varvec{z}\right) \right) }, \end{aligned}$$
(10)
$$\begin{aligned} \tilde{L}^{\left( S_{i}\right) }\left( \varvec{z}\right)&=\widetilde{LB}^{\left( S_{i}\right) }\left( \varvec{z}\right) \frac{1-\widetilde{S}_{i}\left( \lambda -\lambda \widetilde{K} \left( \varvec{z}\right) \right) }{E\left( S_{i}\right) \left( \lambda -\lambda \widetilde{K} \left( \varvec{z}\right) \right) }. \end{aligned}$$
(11)
Using these results,
\(\tilde{L}\left( \varvec{z}\right) \), which is the PGF of the joint queue-length distribution at an arbitrary moment, can be obtained. By conditioning on periods
\(V_{1},S_{1},\dots ,V_{N},S_{N}\) and using (
10) and (
11)
\(\tilde{L}\left( \varvec{z}\right) \) can be written as
$$\begin{aligned} \tilde{L}\left( \varvec{z}\right)&=\frac{1}{E\left( C\right) }\sum _{i=1}^{N}\left( E\left( V_{i}\right) \tilde{L}^{\left( V_{i}\right) }\left( \varvec{z}\right) +E\left( S_{i}\right) \tilde{L}^{\left( S_{i}\right) } \left( \varvec{z}\right) \right) , \end{aligned}$$
(12)
with
\(E\left( V_{i}\right) =\rho _{i}E\left( C\right) \) as the expected visit time to
\(Q_{i}\).
4.2 Batch sojourn-time distribution
In order to determine the LST of the steady-state batch sojourn-time distribution, we follow the method of Boon et al. [
2] by conditioning on the location of the server and determining the time it takes until the last customer in a specific batch is served. These results are then used to determine the batch sojourn-time distribution of an arbitrary batch. Boon et al. [
2] developed this method to study the steady-state waiting time distribution for polling systems with rerouting. For these kinds of models, the distributional form of Little’s Law [
10] cannot be applied, since the combined processes of internal and external arrivals do not necessarily form a Poisson process. However, by studying the evolution of the system after a customer arrival, this problem can be avoided and the waiting time distribution can be obtained. Important in their analysis is the concept of
descendants from the theory of branching processes, which are defined as all the customers who arrive during the service of a tagged customer, plus the customers who arrive during the service of those customers, etc. (i.e., the total progeny of the tagged customer).
The approach of Boon et al. [
2] is suitable to determine the steady-state batch sojourn-time distribution, since for a specific customer batch the location where the last customer in the batch will be served varies with the location of the server at the arrival of the batch (for example, in Fig.
2 depending of the location of the server the batch is either fully served in
\(Q_{1}\) or
\(Q_{i}\)). We explicitly condition on the location of the server; the LST of the batch sojourn-time distribution of a specific customer batch
\(\varvec{k}\) can be written as
$$\begin{aligned} \widetilde{T}_{\varvec{k}}\left( \omega \right)&=\frac{1}{E\left( C\right) }\sum _{j=1}^{N}\left( E\left( V_{j}\right) \widetilde{T}_{\varvec{k}}^{\left( V_{j}\right) }\left( \omega \right) +E\left( S_{j}\right) \widetilde{T}_{\varvec{k}}^{\left( S_{j}\right) }\left( \omega \right) \right) , \end{aligned}$$
(13)
where
\(\widetilde{T}_{\varvec{k}}^{\left( V_{j}\right) }\left( .\right) \) is the LST of the batch sojourn-time for customer batch
\(\varvec{k}\)
given that the batch arrived during
\(V_{j}\), and where
\(\widetilde{T}_{\varvec{k}}^{\left( S_{j}\right) }\left( .\right) \) is
given that the customer batch arrived during
\(S_{j}\). The remainder of this section will focus on how to determine
\(\widetilde{T}_{\varvec{k}}^{\left( V_{j}\right) }\left( .\right) \),
\(\widetilde{T}_{\varvec{k}}^{\left( S_{j}\right) }\left( .\right) \), and the LST of an arbitrary batch
\(\widetilde{T}\left( .\right) \).
From the theory of branching processes, we denote
\(B_{j,i,}\)
\(i,j=1,\dots ,N\), as the service of a tagged customer in
\(Q_{j}\) plus all its descendants that will be served before or during the next visit to
\(Q_{i}\). Combining this gives the following recursive function:
where
\(BP_{j}\) is the busy period initiated by the tagged customer in
\(Q_{j}\),
\(N_{l}\left( BP_{j}\right) \) denotes the number of customers who arrive in
\(Q_{l}\) during this busy period in
\(Q_{j}\), and
\(B_{l_{m},i}\) is a sequence of (independent)
\(B_{l,i}\)’s. Let
\(\widetilde{B}_{j,i}\left( .\right) \) be the LST of
\(B_{j,i}\), which is given by
$$\begin{aligned} \widetilde{B}_{j,i}\left( \omega \right) =&\widetilde{BP}_{j}\left( \omega +\lambda (1-\widetilde{K}(\varvec{B_{j+1,i}}))\right) , \end{aligned}$$
(15)
where
\(\varvec{B_{j+1,i}}\) is an
N-dimensional vector defined as follows:
$$\begin{aligned} (\varvec{B_{j,i}})_{l}&={\left\{ \begin{array}{ll} \widetilde{B}_{l,i}\left( \omega \right) , &{} \text{ if } l=j,\dots ,i,\,\text{ and } j\ne i+1,\\ 1, &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$
(16)
A similar LST can also be formulated for a switch-over time
\(S_{j}\) and the service of all its descendants that will be served before the end of the visit to
\(S_{i}\),
$$\begin{aligned} \widetilde{S}_{j,i}\left( \omega \right)&=\widetilde{S}_{j}\left( \omega +\lambda (1-\widetilde{K}(\varvec{B_{j+1,i}})\right) , \end{aligned}$$
(17)
Finally, let
\(\varvec{B_{j,i}^{*}}\) be an
N-dimensional vector defined as
$$\begin{aligned} (\varvec{B_{j,i}^{*}})_{l}&={\left\{ \begin{array}{ll} \widetilde{B}_{i}\left( \omega \right) , &{} \text{ if } l=i,\\ (\varvec{B_{j,i-1}})_{l}, &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$
(18)
The key difference with (
16) is that (
18) excludes any new customer arrivals in
\(Q_{i}\). This is needed to omit customers who arrive in
\(Q_{i}\) after the batch arrival; these customers do not influence the batch sojourn-time of the arriving customer batch since they will be served afterwards.
We first focus on the batch sojourn-time of a customer batch that arrives during a visit period. Assume than an arriving customer batch \(\varvec{k}\) enters the system while the server is currently within visit period \(V_{j}\) and the last customer in the batch will be served in \(Q_{i}\). Formally, this means \(k_{i}>0\) and all the other customer arriving in the same batch should be served before the next visit to \(Q_{i}\); \(k_{l}\ge 0\), \(l=j,\dots ,i-1\), and \(k_{l}=0\) elsewhere. Whenever all the customers arrive in the same queue that is currently visited, then \(k_{i}=k_{j}>0\), and \(k_{l}=0\) elsewhere.
The batch sojourn-time of customer batch
\(\varvec{k}\) consists of (i) the residual service time in
\(Q_{j}\), (ii) the service of all the customers already in the system in
\(Q_{j},\dots ,Q_{i}\), (iii) the service of all new customer arrivals that arrive after customer batch
\(\varvec{k}\) in
\(Q_{j},\dots ,Q_{i-1}\) before the server reaches
\(Q_{i}\), (iv) the switch-over times
\(S_{j},\dots ,S_{i-1}\), and (v) the service of the customers in the customer batch
\(\varvec{k}\). From (
10), we know that at the arrival of the customer batch, the PGF of the joint queue-length distribution is the equal to the queue-lengths at a service beginning,
\(\widetilde{LB}^{\left( B_{j}\right) }\left( .\right) \), plus the number of customers who arrived in the elapsed part of the service time,
\(\widetilde{B}_{j}^{P}\left( .\right) \). On the other hand, we also need to consider the residual part of the service time,
\(\widetilde{B}_{j}^{R}\left( .\right) \), and if
\(i\ne j\) the arrivals that occur in
\(Q_{j},\dots ,Q_{i-1}\) during this period as well. Therefore, similarly to [
2], we need to consider the PGF-LST of the joint queue-length distribution at an arrival epoch
and the residual service time;
\(\widetilde{L}^{\left( V_{i}\right) }\left( \varvec{z},\omega \right) \). First, since the number of customers who arrive in the elapsed and residual part of the service time are independent of each other and from the queue-lengths at a service beginning, we can write the LST of the joint distribution of
\(\widetilde{B}_{j}^{P}\left( .\right) \) and
\(\widetilde{B}_{j}^{R}\left( .\right) \) as [
7]
$$\begin{aligned} \widetilde{B}_{j}^{PR}\left( \omega _{P},\omega _{R}\right)&=\frac{\widetilde{B}_{j}\left( \omega _{P}\right) -\widetilde{B}_{j}\left( \omega _{R}\right) }{E\left( B_{j}\right) \left( \omega _{R}-\omega _{P}\right) }, \end{aligned}$$
Then, because of independence between
\(\widetilde{B}_{j}^{PR}\left( \omega _{P},\omega _{R}\right) \) and
\(\widetilde{LB}^{\left( B_{j}\right) }\left( \varvec{z}\right) \), we have
$$\begin{aligned} \widetilde{L}^{\left( V_{j}\right) }\left( \varvec{z},\omega \right)&=\widetilde{LB}^{\left( B_{j}\right) }\left( \varvec{z}\right) \widetilde{B}_{j}^{PR}\left( \lambda -\lambda \widetilde{K}\left( \varvec{z}\right) ,\omega \right) . \end{aligned}$$
(19)
Now, consider a customer batch that arrives during a switch-over period. Assume an arriving customer batch \(\varvec{k}\) enters the system while the server is currently within switch-over period \(S_{j-1}\) and the last customer in the batch will be served in \(Q_{i}\). The reason that we consider \(S_{j-1}\) is that batch \(\varvec{k}\) will finish service in the same queue had it arrived in \(V_{j}\) because of the exhaustive service discipline.
In this case, the batch sojourn-time consists of the same components (ii), (iii), (iv), and (v). Component (i) is however different and is now defined as the residual switch-over time between
\(Q_{j-1}\) and
\(Q_{j}\). Similarly, we define
\(\widetilde{L}^{\left( S_{j-1}\right) }\left( \varvec{z},\omega \right) \) as the PGF-LST of the joint queue-length distribution of customers present in the system at an arbitrary moment during
\(S_{j-1}\)
and the residual switch-over time
\(\widetilde{S}_{j-1}^{R}\left( .\right) \). From (
11), we have the joint queue-length distribution at a switch-over beginning,
\(\widetilde{LB}^{\left( S_{j-1}\right) }\left( .\right) \), and the number of customers who arrived in the elapsed part of the switch-over time,
\(\widetilde{S}_{j-1}^{P}\left( .\right) \). Similarly to
\(\widetilde{B}_{j}^{PR}\left( .\right) \), we define
\(\widetilde{S}_{j-1}^{PR}\left( \omega _{R},\omega _{P}\right) \) as the LST of the joint distribution of the elapsed and residual switch-over time
\(S_{j-1}\) as
$$\begin{aligned} \widetilde{S}_{j-1}^{PR}\left( \omega _{P},\omega _{R}\right)&=\frac{\widetilde{S}_{j-1}\left( \omega _{P}\right) -\widetilde{S}_{j-1}\left( \omega _{R}\right) }{E\left( S_{j-1}\right) \left( \omega _{R}-\omega _{P}\right) }. \end{aligned}$$
Then, due to independence, the PGF-LST of the joint queue-length distribution present at an arbitrary moment during
\(S_{j-1}\) and the residual switch-over time is given by
$$\begin{aligned} \widetilde{L}^{\left( S_{j-1}\right) }\left( \varvec{z},\omega \right)&=\widetilde{LB}^{\left( S_{j-1}\right) }\left( \varvec{z}\right) \widetilde{S}_{j-1}^{PR}\left( \lambda -\lambda \widetilde{K}\left( \varvec{z}\right) ,\omega \right) . \end{aligned}$$
(22)
From Propositions
1 and
2, it can be seen that the LST of the batch sojourn-time distribution of batch
\(\varvec{k}\) conditioned on a visit/switch-over period is comprised of two terms: a term independent of batch
\(\varvec{k}\)
and a term that corresponds to the additional contribution batch
\(\varvec{k}\) makes to the batch sojourn-time:
where
\(1_{\left( \varvec{k}\in \mathcal {K}_{j,i}\right) }\) is an indicator function that is equal to one if all customers in batch
\(\varvec{k}\) are served in
\(Q_{j},\dots ,Q_{i}\) and the last customer will be served in
\(Q_{i}\), and zero otherwise. The terms
\(\widetilde{W}_{i}^{\left( V_{j}\right) }\left( \omega \right) \) and
\(\widetilde{W}_{i}^{\left( S_{j-1}\right) }\left( \omega \right) \) can be considered as the time between the batch arrival epoch and the service completion of the last customer in
\(Q_{i}\) that was already in the system at the arrival of the customer batch, excluding batch
\(\varvec{k}\) and any arrivals to
\(Q_{i}\) after the arrival epoch, conditioned on the location of the server. In the case where there are only individually arriving customers, this would correspond to the LST of the waiting time distribution of a customer arriving in
\(Q_{i}\) conditional on the server being in a visit or switch-over period. The LST of the batch sojourn-time distribution of a specific customer batch
\(\varvec{k}\) can now be calculated using (
13).
Finally, we focus on the LST of the batch sojourn-time of an arbitrary batch \(\widetilde{T}\left( .\right) \).
Differentiating (
27) will give the mean batch sojourn-time; however, in the next section, an alternative, more efficient way to determine the mean batch sojourn-time is presented.
4.3 Mean batch sojourn-time
In this section, we derive the mean batch sojourn-time of a specific batch and an arbitrary batch using
MVA. MVA for polling systems was developed by Winands et al. [
23] to study mean waiting times in systems with exhaustive, gated service, or mixed service. The main advantage of MVA is that it has a pure probabilistic interpretation and is based on standard queueing results, i.e., the Poisson arrivals see time averages (PASTA) property [
25] and Little’s Law [
15]. Furthermore, MVA evaluates the polling system at arbitrary time periods and not on embedded points such as visit beginnings, like in the buffer occupancy method [
18] and the descendant set approach [
12].
Central in MVA [
23] is the derivation of
\(E\left( \bar{L}_{i}^{\left( S_{j-1},V_{j}\right) }\right) \), the mean queue-length at
\(Q_{i}\) (excluding the potential customer currently in service) at an arbitrary epoch within switch-over period
\(S_{j-1}\) and visit period
\(V_{j}:\)
$$\begin{aligned} E\left( \bar{L}_{i}^{\left( S_{j-1},V_{j}\right) }\right) =\frac{E\left( S_{j-1}\right) }{E\left( S_{j-1}\right) +E\left( V_{j}\right) }E\left( \bar{L}_{i}^{\left( S_{j-1}\right) }\right) \nonumber \\ +\frac{E\left( V_{j}\right) }{E\left( S_{j-1}\right) +E\left( V_{j}\right) }E\left( \bar{L}_{i}^{\left( V_{j}\right) }\right) , \end{aligned}$$
(29)
where
\(E\left( \bar{L}_{i}^{\left( S_{j-1}\right) }\right) \) and
\(E\left( \bar{L}_{i}^{\left( V_{j}\right) }\right) \) are the expected queue-length in
\(Q_{i}\) during, respectively, a switch-over/visit period and
\(E\left( V_{j}\right) =\rho _{j}E\left( C\right) \). Subsequently, with
\(E\left( \bar{L}_{i}^{\left( S_{j-1};V_{j}\right) }\right) \) the mean queue-length
\(E\left( \bar{L}_{i}\right) \) in
\(Q_{i}\) can be determined:
$$\begin{aligned} E\left( \bar{L}_{i}\right)&=\sum _{j=1}^{N}\frac{E\left( S_{j-1}\right) +E\left( V_{j}\right) }{E\left( C\right) }E\left( \bar{L}_{i}^{\left( S_{j-1},V_{j}\right) }\right) ,\quad i=1,\dots ,N, \end{aligned}$$
(30)
and by Little’s law, also the mean waiting time
\(E\left( W_{i}\right) \) of a random customer in
\(Q_{i}\), which is defined as the time in steady state from the customer’s arrival until the start of his/her service.
For notational purposes, we introduce
\(\theta _{j}\) as short-hand for the intervisit period
\(\left( S_{j-1},V_{j}\right) \); the expected duration of this period
\(E\left( \theta _{j}\right) \) is given by
$$\begin{aligned} E\left( \theta _{j}\right)&=E\left( S_{j-1}\right) +E\left( V_{j}\right) ,\quad j=1,\dots ,N. \end{aligned}$$
(31)
Notice that
\(\sum _{j=1}^{N}E\left( \theta _{j}\right) =E\left( C\right) \). In addition, we define
\(\theta _{j,i}\) as the duration of an intervisit period starting in
\(\theta _{j}\) and ending in
\(\theta _{i}\), the expected duration of this period
\(E\left( \theta _{j,i}\right) \) is equal to
and where
\(E\left( \theta _{j,i}^{R}\right) =E\left( \theta _{j,i}^{2}\right) /2E\left( \theta _{j,i}\right) \) is the mean residual duration of this period. However,
\(E\left( \theta _{j,i}^{2}\right) \) is unknown and not straightforward to derive directly. In the MVA, based on probabilistic arguments,
\(E\left( \theta _{j,i}^{2}\right) \) will be expressed in terms of
\(E\left( \bar{L}_{i}^{\left( \theta _{j}\right) }\right) \).
We denote
\(E\left( B_{j,i}\right) \) as the mean service of a customer in
\(Q_{j}\) and all its descendants
before the server starts serving
\(Q_{i}\). Let
\(E\left( B_{j,j}\right) =E\left( B_{j}\right) \) and
\(E\left( B_{j,j+1}\right) =E\left( B_{j}\right) /\left( 1-\rho _{j}\right) \) be the expected busy period initiated by a customer in
\(Q_{j}\). Then,
\(E\left( B_{j,j+2}\right) \) equals the busy period in
\(Q_{j}\) plus all the customers who arrive during this busy period in
\(Q_{j+1}\) and the busy periods that they trigger:
$$\begin{aligned} E\left( B_{j,j+2}\right)&=\frac{E\left( B_{j}\right) }{1-\rho _{j}}\left( 1+\frac{\rho _{j+1}}{1-\rho _{j+1}}\right) =\frac{E\left( B_{j}\right) }{\left( 1-\rho _{j}\right) \left( 1-\rho _{j+1}\right) }. \end{aligned}$$
In general, we can write
\(E\left( B_{j,i}\right) \) for
\(i\ne j\) as
Also, let
\(E\left( S_{j,i}\right) \) denote the switch-over in
\(Q_{j}\) and the service of all the customers who arrive during
\(E\left( S_{j}\right) \) and their descendants
before the server starts serving
\(Q_{i}\). Then
\(E\left( S_{j,j+1}\right) =E\left( S_{j}\right) \) and, in general, for
\(i\ne j+1\),
Finally,
\(E\left( B_{j,i}^{R}\right) \) is the mean residual service of a customer in
\(Q_{j}\) and all its descendants
before the server starts serving
\(Q_{i}\) and is given by replacing
\(E\left( B_{j}\right) \) by
\(E\left( B_{j}^{R}\right) =E\left( B_{j}^{2}\right) /2E\left( B_{j}\right) \) in
\(E\left( B_{j,i}\right) \). In addition,
\(E\left( S_{j,i}^{R}\right) \) is defined as
\(E\left( S_{j,i}\right) \) and by replacing
\(E\left( S_{j}\right) \) by
\(E\left( S_{j}^{R}\right) =E\left( S_{j}^{2}\right) /2E\left( S_{j}\right) \).
In MVA, a set of
\(N^{2}\) linear equations is derived for
\(E\left( \bar{L}_{i}\right) \) in terms of unknowns
\(E\left( \bar{L}_{i}^{\left( \theta _{j}\right) }\right) \). For this, we have to consider the waiting time of an arbitrary customer and make use of the arrival relation and the PASTA property. Assume that an arbitrary customer enters the system in
\(Q_{i}\). The waiting time of the customer consists of (i) the service of
\(E\left( \bar{L}_{i}\right) \) customers already at
\(Q_{i}\) upon its arrival to the system, (ii) the service of
\(E\left( K_{ii}\right) /2E\left( K_{i}\right) \) customers who arrived in the same customer batch, but are placed before the arbitrary customer in
\(Q_{i}\), (iii) if the server is currently in intervisit period
\(\theta _{i}\), then the arbitrary customer has to wait with probability
\(\rho _{i}\) for the residual service time
\(E\left( B_{i}^{R}\right) \) and with probability
\(E\left( S_{i-1}\right) /E\left( C\right) \) for the residual switch-over time
\(E\left( S_{i-1}^{R}\right) \). Finally, (iv) whenever the server is not in intervisit period
\(\theta _{i}\), the arbitrary customer has to wait for the expected residual duration before the server returns at
\(Q_{i}\). Based on these components, the mean waiting time
\(E\left( W_{i}\right) \) of a customer in
\(Q_{i}\),
\(i=1,\dots ,N\), is given by
$$\begin{aligned} E\left( W_{i}\right)= & {} E\left( \bar{L}_{i}\right) E\left( B_{i}\right) +\frac{E\left( K_{ii}\right) }{2E\left( K_{i}\right) }E\left( B_{i}\right) +\rho _{i}E\left( B_{i}^{R}\right) \nonumber \\&+\frac{E\left( S_{i-1}\right) }{E\left( C\right) }E \left( S_{i-1}^{R}\right) +\left( 1-\frac{E\left( \theta _{i}\right) }{E\left( C\right) }\right) \left( E\left( \theta _{i+1,i-1}^{R}\right) +E\left( S_{i-1}\right) \right) .\nonumber \\ \end{aligned}$$
(35)
The next step to derive the equations is to relate the unknowns
\(E\left( \theta _{i+1,i-1}^{R}\right) \) to
\(E\left( \bar{L}_{i}^{\left( \theta _{j}\right) }\right) \). Consider
\(E\left( \theta _{j,i}^{R}\right) \), the expected residual duration of an intervisit period starting in
\(\theta _{j}\) and ending in
\(\theta _{i}\) given that an arbitrary customer batch just entered the system. Then with probability
\(E\left( \theta _{l}\right) /E\left( \theta _{j,i}\right) \), the server is during this period in intervisit period
\(\theta _{l}\),
\(l=j,\dots ,i\), and the expected residual duration until the intervisit ending of
\(\theta _{i}\), conditional on the server being in intervisit period
\(\theta _{l}\), is defined as follows. First, with probability
\(E\left( V_{l}\right) /E\left( \theta _{l}\right) \), the server is busy serving a customer in
\(Q_{l}\) and with probability
\(E\left( S_{l-1}\right) /E\left( \theta _{l}\right) \), the server is in switch-over period
\(S_{l-1}\). During the residual service/switch-over time, new customers can arrive who will be served before the intervisit ending in
\(\theta _{i}\), which equals
\(E\left( B_{l,i+1}^{R}\right) \) and
\(E\left( S_{l-1,i+1}^{R}\right) \), respectively. In addition, the expected number of customers in
\(Q_{n}\) given the server is in
\(\theta _{l}\),
\(E\left( \bar{L}_{n}^{\left( \theta _{l}\right) }\right) \), and the expected number of customers
\(E\left( K_{nl}\right) /E\left( K_{n}\right) \) who arrived in
\(Q_{n}\) in the arbitrary customer batch will increase the duration of
\(E\left( \theta _{j,i}^{R}\right) \) by
\(E\left( B_{n,i+1}\right) \). Finally, the customer also has to wait for all the switch-over times
\(E\left( S_{n,i+1}\right) \),
\(n=j,\dots ,i\), between
\(Q_{n}\) to
\(Q_{n+1}\) plus the customers who arrive during the switch-over times and their descendants that will be served before the end of
\(E\left( \theta _{j,i}^{R}\right) \). Combining this gives the following expression for
\(i\ne j-1\):
It is now possible to set up a set of
\(N^{2}\) linear equations. First, after the server has visited
\(Q_{i}\), there will be no customers present in the queue. Therefore, the number of customers in
\(Q_{i}\) given an arbitrary moment in an intervisit period starting in
\(\theta _{i+1}\) and ending in
\(\theta _{j}\) equals the number of Poisson arrivals during the age of this period [
23]. Because the age is equal to the residual time in distribution, we have, for
\(i=1,\dots ,N,\,j=1,\dots ,N\), and
\(i\ne j\),
Second, by (
35) and using Little’s Law,
\(\lambda _{i}E\left( W_{i}\right) =E\left( \bar{L}_{i}\right) \). Substituting this into (
30) gives, for
\(i=1,2\dots ,N\),
$$\begin{aligned} \sum _{j=1}^{N}\frac{E\left( \theta _{j}\right) }{E\left( C\right) }E \left( \bar{L}_{i}^{\left( \theta _{j}\right) }\right)= & {} \frac{\lambda _{i}}{1-\rho _{i}} \left( \frac{E\left( K_{ii}\right) }{2E\left( K_{i}\right) }E \left( B_{i}\right) +\rho _{i}E\left( B_{i}^{R}\right) \right. \frac{E\left( S_{i-1}\right) }{E\left( C\right) }E\left( S_{i-1}^{R}\right) \nonumber \\&\left. \left. +\left( 1-\frac{E\left( \theta _{i}\right) }{E\left( C\right) }\right) \left( E\left( \theta _{i+1,i-1}^{R}\right) \right. +E\left( S_{i-1}\right) \right) \right) . \end{aligned}$$
(38)
With (
37) and (
38), a set of
\(N^{2}\) linear equations for unknowns
\(E\left( \bar{L}_{i}^{\left( \theta _{j}\right) }\right) \) are now defined. Solving the set of linear equations and by (
30) and (
35) will give the expected queue-lengths and waiting times.
In order to derive the mean batch sojourn-time
\(E\left( T_{\varvec{k}}\right) \) of customer batch
\(\varvec{k}\),
\(E\left( \bar{L}_{i}^{\left( \theta _{j}\right) }\right) \) also plays an integral role. Similarly to (
13), in order to calculate the expected batch sojourn-time distribution of a specific customer batch
\(\varvec{k}\), we explicitly condition on the location on the server:
$$\begin{aligned} E\left( T_{\varvec{k}}\right)&=\frac{1}{E\left( C\right) }\sum _{j=1}^{N}E\left( \theta _{j}\right) E\left( T_{\varvec{k}}^{\left( \theta _{j}\right) }\right) , \end{aligned}$$
(39)
where
\(E\left( T_{\varvec{k}}^{\left( \theta _{j}\right) }\right) \) is the expected batch sojourn-time distribution of a specific customer batch
\(\varvec{k}\) given that the server is in intervisit period
\(\theta _{j}\).
\(E\left( T_{\varvec{k}}^{\left( \theta _{j}\right) }\right) \) can be derived in a similar way to (
36). This gives the following expression:
Note that the same decomposition as (
24) and (
25) also holds for the expected batch sojourn-time:
where
\(E\left( W_{i}^{\left( \theta _{j}\right) }\right) \) is the expected time between the batch arrival epoch and the service completion of the last customer in
\(Q_{i}\) that is already in the system, excluding any arrivals to
\(Q_{i}\) after the arrival epoch. The term
can be interpreted as the total contribution batch
\(\varvec{k}\) makes to the batch sojourn-time.
Finally, the expected batch sojourn-time of an arbitrary customer batch is obtained by multiplying
\(E\left( T_{\varvec{k}}\right) \) with the probability that a particular batch
\(\varvec{k}\) enters the system:
$$\begin{aligned} E\left( T\right)&=\sum _{\varvec{k}\in \mathcal {K}}\pi \left( \varvec{k}\right) E\left( T_{\varvec{k}}\right) . \end{aligned}$$
(41)
However, if there are many different realizations of customer batches possible, (
41) might not be computationally feasible, since for every
\(\varvec{k}\) we have to determine the mean batch sojourn-time given that the server starts in intervisit period
\(\theta _{j}\) and ends in
\(\theta _{i}\); in total, there are
\(\left| \mathcal {K}\right| \times N\times N\) combinations to consider, where
\(\left| \mathcal {K}\right| \) denotes the size of set
\(\mathcal {K}\). Instead, by using
\(E\left( K_{l}|\mathcal {K}_{j,i}\right) \), we can rewrite (
41) as follows:
The advantage is that the number of combinations reduces to
\(N\times N\), and
\(\pi \left( \mathcal {K}_{j,i}\right) \) can be determined in
\(\left| \mathcal {K}\right| \) steps.