1. INTRODUCTION
In this article, we study a model that involves one server alternating
between two service points. The model applies in many real-life situations
and it is described by a Lindley-type equation. This equation is identical
to the original Lindley equation except for a plus sign that is changed
into a minus sign. To better illustrate the model, we give a simple
example.
Consider an ophthalmologist who performs laser surgeries for
cataracts. Since the procedure lasts only 10 min and is rather simple, he
will typically schedule many consecutive surgeries in one day. Before
surgery, the patient undergoes a preparation phase, which does not require
the surgeon's attendance. In order to optimize the doctor's
utilization, the following strategy is followed. There are two operating
rooms that work nonstop. While the surgeon works in one of them, the next
patient is being prepared in the other one. As soon as the surgeon
completes one operation, he moves to the other room and a new patient
starts his preparation period in the room that has just been emptied.
Apart from the above example, we may think of a hairdresser that has
an assistant to help with the preparation of the customers or of a canteen
with one employee and two counters that the employee serves in turns. This
model arises naturally also in a two-carousel bidirectional storage
system, where a picker serves in turns two carousels; see, for example,
Park et al. [9] and Vlasiou et al.
[14].
We want to analyze the waiting time of the server (i.e., the surgeon
in the above example). We assume that except for the customer that is
being served, there is always at least one more customer in the system. In
other words, there is always at least one customer in the preparation
phase, which means that the server has to wait only because the next
customer may not have completed his preparation phase. Furthermore, the
server is not allowed to serve two consecutive customers at the same
service point and must alternate between the service points.
This condition is crucial. If we remove this condition, then the
problem turns out to be the classical machine repair problem. In that
setting, there is a number of machines working in parallel (two in our
situation) and one repairman. As soon as a machine fails, it joins the
repair queue in order to be served. The machine repair problem, also known
as the computer terminal model (see, e.g., Bertsekas and Gallager
[3]) or the time sharing system
(Kleinrock [6, Sect.4.11]), is a
well-studied problem in the literature. It is one of the key models to
describe problems with a finite input population. A fairly extensive
analysis of the machine repair problem can be found in Takács
[12, Chap.5]. In the following, we
will compare the two models and discuss their performances.
The issue that is usually investigated in the machine repair problem
is the waiting time of a machine until it becomes operational again. In
our situation, we are concerned with the waiting time of the repairman.
This question has not been treated in the classical literature, perhaps
because in the machine repair problem, the operating time of the machine
is usually more valuable than the utilization of the repairman. In Section
5, we compare the waiting times of the repairman in the classical machine
repair problem and our model. We show that the random variables for the
waiting time in the two situations are not stochastically ordered.
However, on average, the alternating strategy leads to longer waiting
times for the server. Furthermore, we will show that the probability that
the server does not have to wait is larger in the alternating service
system than in the nonalternating one. This result is perhaps
counterintuitive, since the inequality for the mean waiting times of the
server in the two situations is reversed.
In the following section, we introduce the model and explain the
interesting aspects of it and the implications in the analysis of the
different sign in the Lindley-type equation for the waiting time. In
Section 3, we derive the distribution of the waiting time of the server,
provided that the preparation time of a customer follows an Erlang or a
phase-type distribution. Continuing with Section 4, we introduce the
machine repair model and analyze the waiting time of the repairman; in
other words, we remove the restriction that the server alternates between
the service points. We compare the two models in Section 5 and we conclude
with some numerical results in Section 6.
2. THE MODEL
We consider a system consisting of one server and two service points.
At each service point, there is an infinite queue of customers that needs
to be served. The server alternates between the service points, serving
one customer at a time. Before being served by the server, a customer must
undergo a preparation phase first. Thus, the server, after having finished
serving a customer at one service point, may have to wait for the
preparation phase of the customer at the other service point to be
completed. We are interested in the waiting time of the server. Let
Bn denote the preparation time for the
nth customer and let An be the time
the server spends on this customer. Then the waiting times
Wn of the server satisfy the following
relation:
We assume that {An} and
{Bn} are independent and identically
distributed (i.i.d.) sequences of nonnegative random variables, which are
mutually independent and have finite means. Further, for every n,
An follows some general distribution
FA(·) and
Bn follows a phase-type distribution denoted
by FB(·). Clearly, the stochastic
process {Wn} is an aperiodic regenerative
process with a finite mean cycle length with the time points where
Wn = 0 being the regeneration points.
Therefore, there exists a unique limiting distribution. In the following
we shall suppress all subscripts when we refer to the system in
equilibrium. Let W be the random variable with this limiting
distribution; then
where A and B are independent and distributed
according to FA(·) and
FB(·) respectively.
Note the striking similarity to Lindley's equation for the
waiting times in a single-server queue. If only the sign of
Wn were different, then we would be analyzing
the waiting time in the GI/PH/1 model.
Lindley's equation is one of the most studied equations in queueing
theory. For excellent textbook treatments we refer to Asmussen [2] and Cohen [4] and the references therein. It is a
challenging problem to investigate the implications of this subtle
difference between the two equations.
For this model we shall try to obtain an explicit expression for the
distribution FW(·) of the waiting time
W. Let ω(·) denote the Laplace transform of
W; that is,
The derivative of order i of the transform is
ω(i)(·), and by definition
ω(0)(·) = ω(·). Similarly, we define
the Laplace transform α(·) of the random variable A.
To keep expressions simple, we also use the function φ(·),
defined as φ(s) = ω(s)α(s). We
can now proceed with the analysis.
3. THE WAITING TIME DISTRIBUTION
In the following we shall derive the distribution of the waiting time
of the server, assuming that the service time A follows some
general distribution and the preparation time B follows a
phase-type distribution. The phase-type distributions that we will
consider are mixtures of Erlang distributions with the same scale
parameters. Therefore we will first consider the case where B
follows an Erlang-n distribution, which we denote by
En(·).
3.1. Erlang Preparation Times
Let B be the sum of n independent random variables
X1,…,Xn that are
exponentially distributed with parameter μ. The use of Laplace
transforms is a standard approach for the analysis of Lindley's
equation. Hence it is natural to try this approach for equation (2.1).
Then we can readily prove the following theorem.
Theorem 1 (Alternating service system): The waiting time
distribution has a mass p0 at the origin, which is
given by
and has a density fW(·)
on [0,∞) that is given by
In the above expression
and the parameters ω(i)(μ)
for i = 0,…,n − 1 are the unique
solution to the system of equations
Proof: We use the following notation:
.
Consider the Laplace transform of (2.1); then we have that
Using standard techniques and the memoryless property of the
exponential distribution, one can show that
Additionally, for Yi =
X1 + ··· +
Xi we have that
Finally, we calculate the probability
by substituting s = 0 in (3.3) and using equations (3.4) and
(3.5). Straightforward calculations give us now that
Inverting the transform yields the density (3.1).
Furthermore, the terms ω(i)(μ),
i = 0,…,n − 1, that are included in
φ(i)(μ) still need to be determined. To
obtain the values of ω(i)(μ), for i
= 0,…,n − 1, we differentiate (3.6) n
− 1 times and we evaluate ω(i)(s),
i = 0,…,n − 1 at the point s =
μ. This gives us the system of equations (3.2). The fact that the
solution of the system is unique follows from the general theory of Markov
chains that implies that there is a unique equilibrium distribution and
thus also a unique solution to (3.2). █
Corollary 1: The throughput θ
satisfies
It is quite interesting to note that the density of the waiting time
can be rewritten as
is the probability that directly after a service completion exactly
i exponential phases of B remain.
As is clear from Figure 1, with probability
pi the distribution of the waiting time is
Erlang-i, for i = 1,…,n. Furthermore,
the probability p0 that the server does not have to
wait, or equivalently that at least n exponential phases have
expired, is
.
The waiting time has a mixed Erlang distribution.
So practically the problem is reduced to obtaining the solution of an
n × n linear system. Extending the above result to
mixtures of Erlang distributions is simple.
3.2. Phase-Type Preparation Times
For n = 1,…,N, let the random variable
Xn follow an Erlang-n distribution
with parameter μ and let the random variable B of the
preparation times be equal to Xn with a
probability κn. In other words, the distribution
function of B is given by
This class of phase-type distributions may be used to approximate any
given distribution for the preparation times arbitrarily close; see
Schassberger [10]. Below we show that
Theorem 1 can be extended to service distributions of the form (3.7).
By conditioning on the number of phases of B, we find
that
Since Xn now follows an Erlang-n
distribution, the last equation is practically a linear combination of
equation (3.3), summed over all probabilities κn
for n = 1,…,N. This means that we can directly
use the analysis of Section 3 to calculate the Laplace transform of
W in this situation (cf. equation (3.6)). So we have that
where the terms φ(i)(μ) can be calculated
in a similar fashion as previously. Inverting (3.8) yields the density of
the following theorem (cf. Theorem 1).
Theorem 2: Let (3.7) be the distribution of the random
variable B. Then the distribution of the server's waiting time has
mass p0 at zero, which is given by
and has a density on [0,∞) that is given
by
One can already see from Theorem 2 the effect of the different sign in
the Lindley-type equation that describes our model. The waiting time
distribution for the GI/PH/1 queue is a mixture
of exponentials with different scale parameters (cf. Adan and Zhao
[1]). In our case we have that the
waiting time distribution is a mixture of Erlang distributions with the
same scale parameter for all exponential phases.
As we have mentioned, the practice of alternating between the service
points is inevitably followed in many situations. Still it seems
reasonable to argue that it would be more efficient to choose to serve the
first customer that has completed his preparation time. If we drop the
assumption that the server alternates between the service points, then we
have the classical machine repair problem.
4. THE MACHINE REPAIR PROBLEM
In the machine repair problem there are a number of machines that are
served by a unique repairman when they fail. The machines are working
independently and as soon as a machine fails, it joins a queue formed in
front of the repairman where it is served in order of arrival. A machine
that is repaired is assumed to be as good as new. The model described in
Section 2 is exactly the machine repair problem after we drop the
assumption that the server alternates between the service points. There
are two machines that work in parallel (the two service points), the
preparation time of the customer is equivalent to the lifetime of the
machine until it fails and the service time of the customer is the time
the repairman needs to repair the machine.
What we are interested in is the waiting time of the repairman until a
machine breaks down or, in other words, the waiting time of the server
until the preparation phase of one of the customers is completed. It is
quite surprising that although the machine repair problem under general
assumptions is thoroughly treated in the literature, this question remains
unanswered. We would like to compare the two models and to this end we
first need to derive the distribution of the waiting time of the server,
when the system is in steady state. In the following we will refer to the
server or customers instead of the repairman or machines in order to
illustrate the analogies between the two models.
Let B be the random variable of the time needed for the
preparation phase and R be the remaining preparation time just
after a service has been completed. Then, obviously, the waiting time of
the server is W = min{B,R}. The random
variables B and R are independent, so in order to
calculate the distribution of W we need the distribution of
R. In agreement with the alternating service model, B
follows an Erlang-n distribution. Note that we do not have a
simple Lindley-type recursion for W and therefore this system
cannot be easily treated with Laplace transforms. That means that we have
to try an alternative approach.
The system can be fully described by the number of remaining phases of
preparation time that a customer has to complete, immediately after a
service completion. The state space is finite, since there can be at most
n phases remaining and the Markov chain is aperiodic and
irreducible, so there is a unique equilibrium distribution
{πi,i = 0,…,n}. After
completing a service, the other customer may be already waiting for the
server (so the n exponential phases of the Erlang-n
distribution of the preparation have expired) or he is in one of the
n phases of the preparation time. This means that the remaining
preparation time R that the server sees immediately after
completing a service follows the mixed Erlang distribution
FR(x) = π0 +
π1 E1(x) +
··· + πn
En(x).
So in order to derive the distribution of R (and consequently
the distribution of W), we need to solve the equilibrium
equations πi = [sum ]k
πk pki, i =
0,…,n, in conjunction with the normalizing equation
[sum ]k πk = 1, where
pki are the one-step transition
probabilities. Let us determine the probabilities
pij, for all i,j ∈
{0,…,n}.
A transition from state i to state j, for
i,j ∈ {1,…,n}, can be achieved in
two ways: either the customer that has just been served or the other one
will finish the preparation phase first. Suppose that the customer that
has just been served finishes first. In that case we know that the last
event just before the service starts is that the nth phase of
that customer expired. The other customer was in phase k, and
during the service time the other customer reached state j (i.e.,
k − j phases of that customer have expired). The
probability of this event is given by
where α(·) is as before the Laplace transform of the
service time. Note that in the above expression we have that
Similarly, we can determine the probability of a transition from state
i to state j in the second case. So in the end we have
that for all i,j ∈ {1,…,n},
The transition probabilities from state 0 to any state i =
1,…,n are
since starting from state 0 means that the other customer was already
waiting when the repairman finished a service and reaching state
i means that during the service time, exactly n −
i exponential phases expired. For the transition from state 0 to
state 0 we have that during the service time at least n
exponential phases expired, so
Similarly, we have that, for i = 1,…,n,
where
.
With the one-step transition probabilities one can determine the
equilibrium distribution and thus
FR(·). Then we have that the
distribution of the waiting time of the server, if we drop the assumption
that he is alternating between the service points, is given by the
following theorem.
Theorem 3 (Nonalternating service system): The waiting
time distribution is
where FR(·) is the
distribution of the remaining preparation time of a customer and is equal
to
In the above expression,
{πi,i = 0,…,n} is the
unique solution to the system of equations
where pij are given by equations
(4.1)–(4.4).
Remark 1: The above results can be easily extended to
phase-type preparation times of the form (3.7). However this extension
does not contribute significantly to the analysis, since it is along the
same lines of the analysis in this section.
This method of defining a Markov chain through the remaining phases of
the preparation time after a service has been completed and using the
equilibrium distribution in order to calculate the mixing probabilities of
R can, of course, also be used in the alternating service system.
In that case, the waiting time W is exactly the remaining
preparation time R. Then the probabilities
pi, for i = 0,…,n as
defined in Section 3, will be the equilibrium distribution of the
underlying Markov chain. Furthermore, the system of equations (3.2) can be
rewritten as
In the next section we shall study various performance characteristics
of the two systems.
5. PERFORMANCE COMPARISON
One may wonder if there is any connection between the waiting time of
the server in the two models that can help in understanding how the models
perform. From this point on we will use the superscript A (NA) for all
variables associated with the (non)alternating service system when we
specifically want to distinguish between the two situations. Otherwise the
superscript will be suppressed. So, for example, the random variable
WA will be the waiting time of the server in the
alternating service system.
5.1. Stochastic Ordering
Suppose that the distributions of the two random variables X
and Y have a common support. Then the stochastic ordering
X ≥st Y is defined as (cf. [7,8,11])
and we say that X dominates Y.
Intuitively one may argue that WA
≥st WNA since one expects that large
waiting times occur with higher probability in the alternating service
system. However this is not true. Let us imagine the situation where the
service times are equal to zero. Then in the alternating service system we
will have that the waiting time of the server is zero if
Bi ≥ Bi+1 for
some i. So, since
,
we have
.
In the nonalternating system however, we will have zero waiting time only
if both preparation phases finish at exactly the same instant. Since the
preparation times are continuous random variables, we have that
for every i and thus
.
In Figure 2 we have plotted the distribution of
the waiting time for both situations in the case where the service times
are equal to zero and B follows an Erlang-5 distribution with
μ = 5.
WA and WNA are not
stochastically ordered.
The situation that we have described above is not a rare example. In
fact, the following result holds.
Theorem 4: For any distribution of the preparation and
the service time, we have that
.
Proof: Both processes regenerate when a zero waiting time of
the server occurs. Therefore in a cycle there is precisely one customer
for whom the server did not have to wait. This means that the fraction of
customers for whom the server does not wait is
where
is the average number of customers in a cycle (i.e., the mean cycle
length). So it suffices to show that
.
To prove this, we will couple the two systems and use sample path
arguments. We will show that, for a given initial state and for any
realization of preparation and service times, the number of customers in a
cycle is greater in the alternating case than in the nonalternating case.
To couple the systems we will use the same realizations for the
preparation and the service times. To this end, let
{Bi} be a sequence of preparation times and
{Ai} a sequence of service times. We need to
observe the system until the completion of the first cycle. For both
systems assume that the server starts servicing the first customer at time
0 while at the other service point a customer has just started his
preparation phase B1. Additionally, let
Rn be the remaining preparation time for the
nth customer, immediately after the service of the n
− 1 customer has finished. As long as
Rn ≤ Bn+1,
both processes are identical, since both servers will alternate between
the two service points. In addition, all waiting times until that point
will be strictly positive. As soon as Rn >
Bn+1, the alternating service system will
regenerate for the first time, since we will have that
WnA =
Rn and
Wn+1A = 0. The nonalternating
system, however, does not necessarily regenerate. For this system we have
that WnNA =
Bn+1 and
Rn+1NA =
Rn − Bn+1
− An. Therefore, if
Rn+1NA = 0, then
Wn+1NA = 0 and both processes
regenerate. Otherwise the nonalternating system will not regenerate.
Hence, for each realization we have that NNA ≥
NA, which implies that the mean cycle length
of the nonalternating system is at least as long as the mean cycle
length
of the alternating system. █
5.2. Mean Waiting Times
Although the waiting times in the two situations are not
stochastically ordered, we have however that the mean waiting time of the
server of the alternating service model
is larger than or equal to the mean waiting time of the server in the
nonalternating system
.
This is quite natural since we expect the nonalternating system to
perform better in terms of throughput, regardless of the distribution of
the preparation phase.
To prove this result for the mean waiting times, we will again couple
the two systems. We will make use of the same realizations
{Bi} and {Ai}
for the preparation and the service times respectively and we will
continue with sample path arguments. We assume that the initial conditions
for both systems are the same; that is, at time 0 the server starts
servicing the first customer, while at the other service point a customer
has just started his preparation phase. Then, for the alternating service
system, define:
DiA: the ith
departure time
HiA: the time the
server can start serving the other service point after time
DiA.
Also define in the same way
DiNA and
HiNA for the nonalternating
system. We need the following lemma.
Lemma 1: For all i, we have that
DiA ≥
DiNA and
HiA ≥
HiNA.
Proof: We will apply induction. For i = 1 we have
that D1A ≥
D1NA and H1A
≥ H1NA, since
and thus
Suppose that for some i we have that
Di−1A ≥
Di−1NA and
Hi−1A ≥
Hi−1NA. We will prove that
DiA ≥
DiNA and
HiA ≥
HiNA and this will conclude the
proof.
The first relation is obvious. From the induction hypothesis we have
Hi−1A ≥
Hi−1NA, so
For the second inequality, first notice that
because, for example, in the nonalternating case the other service
point will either be ready at time
DiNA when the previous customer
departs or it will be ready after the preparation phase at this point is
completed, at the time point equal to the maximum of
Hi−1NA and
Di−1NA +
Bi.
To prove that
we will show that the maximum term of the left-hand side of the
inequality (5.1) is greater than or equal to any term of the right-hand
side, thus also greater than or equal to the maximum of them.
Assume that HiA =
DiA. Then
DiA ≥
DiNA as we have proven above;
furthermore DiA =
Hi−1A +
Ai ≥
Hi−1NA since
Hi−1A ≥
Hi−1NA; and finally, since
HiA =
DiA, then
DiA ≥
Di−1A +
Bi ≥
Di−1NA +
Bi. The case for
HiA =
Di−1A +
Bi follows similarly. █
A corollary of the previous result follows.
Corollary 2: For all i,
.
Proof: The proof is a direct consequence of the fact that for
the coupled systems
So, although the random variables WA and
WNA are not stochastically ordered, the partial sums
of the sequences WiA and
WiNA are.
It is also interesting to note that Lemma 1 immediately implies that
the throughput is greater in the nonalternating system than in the
alternating system since
Moreover, we have that
,
so we can readily establish the following result:
Theorem 5: Given any distribution for the preparation and
the service time, we have that
.
Figure 3 demonstrates a typical situation.
For two values of the ratio
we have plotted the normalized waiting time
versus the squared coefficient of variation
cA2 of the service time
A. We have chosen the mean service time to be
and the preparation time to be composed of five exponential phases. As
before, A stands for the alternating service system and NA for the
nonalternating system. One can see from these two examples that the
average waiting time in the alternating service system is longer than in
the nonalternating system. As in the case for the
GI/G/1 queue, the waiting time depends almost
linearly on cA2. As
cA2 increases, the waiting time
also increases, and for the alternating case the rate of change is
greater. The difference in the mean waiting times in the alternating and
the nonalternating cases is eventually almost constant and this difference
increases as the value of r decreases. In the Appendix we give
more details on the way we chose the distribution for the service
time.
is greater than or equal to
.
Remark 2: From Theorems 4 and 5 we can conclude that there is
at least one point where the waiting time distributions of both systems
intersect. However, Figure 2 suggests that this
point is unique. So, because both mean waiting times are finite, this
implies that WNA is smaller than
WA with respect to the increasing convex
ordering, namely
for all increasing convex functions φ for which the mean exists.
This follows as a direct application of the Karlin–Novikoff cut
criterion (cf. Szekli [11]).
6. NUMERICAL RESULTS
This section is devoted to some numerical results. In Figure 3 we have already shown how the normalized
waiting time changes when the squared coefficient of variation of the
service time is modified.
Figure 4 shows the normalized waiting time
plotted against the squared coefficient of variation of the preparation
time. The preparation time is assumed to follow an Erlang distribution. We
chose
and we fitted a mixed Erlang distribution according to the procedure
described in the Appendix. We have plotted the normalized waiting time for
three different values of the ratio r; namely for r =
0.4, which implies that the service time is 40% of the preparation time,
up to r = 1.2. The latter implies that for the alternating
service model the server in general does not have to wait long. One can
see that the normalized waiting time depends almost linearly on
cB2 for the alternating service
system, but for the nonalternating system it is almost insensitive to
cB2 and thus to the number of
exponential phases of the preparation time. This can be explained by the
fact that Erlang loss models are insensitive to the service time
distribution apart from its first moment; see, for example, Kelly
[5]. More specifically, one can view
the machine repair model that we have described, as an
En /G/2/2 loss system.
Here the repairman would act as the Poisson source of an Erlang loss model
if B would follow an exponential distribution. However the
preparation times are a sum of exponentials and that causes the slight
fluctuation in the mean waiting time.
The normalized waiting time is almost insensitive to
cB2 in the nonalternating
system.
Figure 5 shows the normalized waiting time
plotted against the mean preparation time. We have chosen
cA2 to be equal to 0.8 and we have
fitted a mixed Erlang distribution to the mean service time and the
squared coefficient of service. As expected, the normalized waiting time
depends almost linearly on the mean preparation time. For larger values
of the mean preparation time, the normalized waiting time increases.
The normalized waiting time versus
.
APPENDIX: Fitting Distributions
In Figure 3 we chose the mean service time
to be equal to one and we plotted the normalized waiting time versus
cA2. For each setting we fitted a
mixed Erlang or hyperexponential distribution to
and cA2, depending on whether the
squared coefficient of variation was less than or greater than 1 (see,
e.g., Tijms [13]). More specifically,
if 1/n ≤ cA2 ≤
1/(n − 1) for some n = 2,3,…, then the
mean and squared coefficient of variation of the mixed Erlang
distribution
matches with
,
provided the parameters p and μ are chosen as
On the other hand, if cA2 >
1, then the mean and squared coefficient of variation of the
hyperexponential distribution
match with
provided the parameters μ1, μ2,
p1, and p2 are chosen as
