Let
N
i
(
t) denote the number of failed items of type
i=1,2 at time
t. Clearly, {(
N
1(
t),
N
2(
t)),
t≥0} is a Markov process. We restrict ourselves to the case that the total load
\(\rho := \frac{\lambda_{1} + \lambda_{2}}{ \mu} < 1\). Then the limiting distribution
P(
n
1,
n
2)=
P(
N
1=
n
1,
N
2=
n
2):=lim
t→∞
P(
N
1(
t)=
n
1,
N
2(
t)=
n
2|
N
1(0)=
k
1,
N
2(0)=
k
2) exists and is independent of the initial state; indeed, notice that the total number of customers has the same distribution as the number of customers in an
M/
M/1 queue with arrival rate
λ
1+
λ
2 and service rate
μ. The
P(
n
1,
n
2) satisfy the following balance equations: for
n
1,
n
2≥1, with
I(⋅) denoting an indicator function,
For
n
1=0 and/or
n
2=0, the same equations hold with minor adaptations. Multiplying these equations with
\(z_{1}^{n_{1}}z_{2}^{n_{2}}\) and summing, one gets:
We delay the solution of this equation, first showing how one can derive various special probabilities from this equation.
2.2 The probabilities P(n1,0) and P(0,n2)
Taking
z
1=
z and
z
2=0 in (
2), we obtain by carefully considering the 1/
z terms:
Hence,
$$ E\bigl[z^{N_1}I(N_1>0,N_2=0)\bigr] = - z \frac{\mu P(0,1) -(\lambda_1(1-z) +\lambda_2)P(0,0) + \frac{\mu}{2} z P(1,1)}{\lambda_1 z^2 -(\lambda_1+\lambda_2+\mu)z +\mu} . $$
(6)
Consider the denominator of the right-hand side of (
6). Partial fraction yields
$$ E\bigl[z^{N_1}I(N_1>0,N_2=0)\bigr] = \frac{C_1 z}{1-z/z_+} + \frac{C_2 z}{1-z/z_-}, $$
(7)
where
C
1 and
C
2 remain to be determined. From
M/
M/1 theory (cf. Cohen [
1], Chap. II.4), it follows that the zero
z
− with “minus the square root” of the denominator of (
6) is the Laplace–Stieltjes transform (LST) with argument
λ
2 of the length of the busy period
P
1 in an
M/
M/1 queue with arrival rate
λ
1 and service rate
μ:
\(z_{-} = E[\mathrm{e}^{-\lambda_{2} P_{1}}]\). It may also be interpreted as the probability of zero arrivals from base 2 during a busy period of type 1. Since this zero
z
− has absolute value less than one, and the left-hand side of (
6) is analytic inside the unit circle,
C
2 must be zero. The product of
z
+ and
z
− is
μ/
λ
1>1, so
z
+ has absolute value larger than one. Hence, we conclude that the probabilities
P(
N
1=
n
1,
N
2=0), for
n
1>0, are geometric with parameter
\(\frac{1}{z_{+}} = \frac{\lambda_{1} z_{-}}{\mu}\):
$$ P(j,0) = C_1 \biggl(\frac{1}{z_+}\biggr)^{j-1}, \quad j=1,2,\ldots. $$
(8)
Similarly,
\(P(0,j) = \tilde{C}_{1} (\frac{1}{\tilde{z}_{+}})^{j-1}\),
j=1,2,…, where
\(\tilde{z}_{+}\) is obtained from
z
+ by interchanging
λ
1 and
λ
2. It remains to determine the constants
C
1 and
\(\tilde{C}_{1} \). We shall return to this in Sect.
3.2, where an expression for all
P(
i+1,
i) and
P(
i,
i+1) is derived (cf. (
27)). An alternative approach to determining these two constants is to use the two equations
P(1,0)+
P(0,1)=
ρ(1−
ρ) and
P(2,0)+
P(1,1)+
P(0,2)=
ρ
2(1−
ρ) (cf. Sect.
2.1), in combination with an expression for
P(1,1) which will be obtained in Sect.
3.1. One thus gets two equations for
P(1,0)=
C
1 and
\(P(0,1) = \tilde{C}_{1}\).
2.3 P(N1−N2=n|N1>N2) and P(N2−N1=n|N2>N1)
Taking
z
1=
z=1/
z
2 in (
2), we get a relation between the generating functions
\(E[z^{N_{1}-N_{2}}I(N_{1}>N_{2})]\) and
\(E[z^{N_{1}-N_{2}}I(N_{2}>N_{1})]\):
Now observe that the terms in the left-hand side are analytic in
z for |
z|<1, whereas the term in the right-hand side is analytic in
z for |
z|>1. Application of Liouville’s theorem, using the fact that the right-hand side has a finite limit for |
z|→∞, yields that both sides are equal to a constant, say
C, respectively, for |
z|<1 and for |
z|>1. In particular, taking
y=1/
z,
$$ E\bigl[y^{N_2-N_1}I(N_2>N_1)\bigr] = \frac{Cy}{\lambda_1 +\mu - \lambda_2y}, $$
(10)
implying that
N
2−
N
1, when positive, is geom(
\(\frac{\lambda_{2}}{\lambda_{1}+\mu}\)) distributed. By symmetry (or by studying the left-hand side of (
9), which equals
C for |
z|<1, and by considering the
z
0 terms in the left-hand side) one may conclude that
N
1−
N
2, when positive, is geom(
\(\frac{\lambda_{1}}{\lambda_{2}+\mu}\)) distributed. In the symmetric case
λ
1=
λ
2, this was already observed in [
9]. Below we would like to interpret this result. Consider the system from the moment
N
2 reaches the value
N
1+
k for some positive
k, until the level
N
1+
k−1 is reached again for the first time. In between, the server will invariably be giving repaired items back to base 2, and never to base 1. The value
k, when positive, plays no role in this. Hence,
N
2−
N
1, when positive, is memoryless:
P(
N
2−
N
1≥
k+
l|
N
2−
N
1≥
k)=
P(
N
2−
N
1≥
l). In fact, all the time that
N
2−
N
1≥
k, the system behaves like an
M/
M/1 queue with arrival rate
λ
2 and service rate
λ
1+
μ: the difference
N
2−
N
1 decreases with rate
λ
1+
μ. The events when both queues are of equal length will be particularly important; in the next section, we shall derive
P(
N
1=
N
2=
i),
i=0,1,….
So far, we have not yet tackled the general problem of finding
\(E[z_{1}^{N_{1}}z_{2}^{N_{2}}]\); we only showed that various relevant performance measures have a geometric distribution. The natural approach to the general solution of (
2) seems to be to translate the problem into a boundary value problem, like a Riemann–Hilbert problem (cf. [
3]). That was also the approach chosen by Cohen [
2] in his analysis of the two-dimensional queue length process right after departures in the case of Poisson arrivals and
generally distributed service times; see also Flatto [
5] for the case of exponential service times.
When we compared (
2) with formula (1.7) of Cohen [
2], we came to the conclusion that his formula for exp(
μ) service times reduces to our formula (
2). This is surprising in view of Remark 1, where it is explained that the exchangeability feature of our repair system leads to different queue length behavior in both models. Below we shall show that, despite that different behavior, the steady-state joint queue length distributions in both models are
the same.
Cohen [
2] studies
\((x_{n}^{(1)},x_{n}^{(2)})\), where these are the numbers of customers of types 1 and 2 right after a service completion. He states in his formula (1.6): If
\(x_{n}^{(1)} > x_{n}^{(2)}\), then
$$ x_{n+1}^{(1)} = x_n^{(1)} - 1 + \nu_{n+1}^{(1)} ,\quad x_{n+1}^{(2)} = x_n^{(2)} + \nu_{n+1}^{(2)}, $$
(11)
where the
\(\nu_{n+1}^{(i)}\) are numbers of type-
i arrivals during the (
n+1)th service (actually, he distinguishes between arrivals during a service of type 1 and type 2, but we assume all service times are exp(
μ)). He has similar equations for the other cases. In particular, if
\(x_{n}^{(1)} = x_{n}^{(2)} = 0\), then
\(x_{n+1}^{(i)} = \nu_{n+1}^{(i)}\),
i=1,2.
In our repair system, we study (
N
1,
N
2), where
N
i
is the steady-state number of type-
i requests. Let us, however, instead look at subsequent departure epochs (i.e., repair completion epochs), with one significant difference: Remove the idle periods of the system. Moreover, ignore the customer who is the first to arrive after such an idle period (both his arrival and his departure). Call the numbers of requests waiting just
before the
nth departure epoch:
\((N_{n}^{(1)},N_{n}^{(2)})\). Since we now view the system at independent exp(
μ) intervals, PASTA (Poisson Arrivals See Time Averages) applies [
8]. PASTA states that the distribution of (
N
1,
N
2) equals the distribution of numbers of requests just before those exp(
μ) departure intervals. We claim that those satisfy exactly the same recursion as Cohen’s
\(x_{n}^{(i)}\). Indeed, one may easily verify that,
exactly as for the
\(x_{n}^{(i)}\) in (
11), one has: If
\(N_{n}^{(1)} > N_{n}^{(2)}\) then
$$ N_{n+1}^{(1)} = N_n^{(1)} - 1 + \nu_{n+1}^{(1)} ,\qquad N_{n+1}^{(2)} = N_n^{(2)} + \nu_{n+1}^{(2)}, $$
(12)
and other similar equations hold; in particular, if
\(N_{n}^{(1)} = N_{n}^{(2)} = 0\), then
\(N_{n+1}^{(i)} = \nu_{n+1}^{(i)}\),
i=1,2. The tricky case is when we have (1,0) or (0,1) just
before a service completion. Now an idle period will start. It will be ended with an arrival. As said before, we ignore the idle period
and the arrival that ends it. Just before the end of the next exp(
μ), we shall have
\((\nu_{n+1}^{(1)},\nu_{n+1}^{(2)})\) plus that one ignored customer. However, as he is ignored, we have exactly the same recursion relations for
\((N_{n}^{(1)},N_{n}^{(2)})\) as Cohen [
2] gets for
\((x_{n}^{(1)},x_{n}^{(2)})\).
So, although Cohen [
2] and we study different quantities (cf. Remark 1), the above reasoning shows that in the case of exp(
μ) service times, his
\((x_{n}^{(1)},x_{n}^{(2)})\) and our (
N
1(
t),
N
2(
t)) have the same limiting distribution. This is confirmed by the fact that Cohen’s formula (1.7) for the generating function, when taking exp(
μ) service times, agrees with our formula (
2).
For general service times, this reasoning fails because then successive service times do not generate a Poisson process, and PASTA cannot be applied.