3.1. Erlang Preparation Times

Let B be the sum of n independent random variables X₁,…,X_n 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 p₀ at the origin, which is given by

and has a density f_W(·) on [0,∞) that is given by

In the above expression

and the parameters ω⁽ⁱ⁾(μ) 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 Y_i = X₁ + ··· + X_i 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 = 0,…,n − 1, that are included in φ⁽ⁱ⁾(μ) still need to be determined. To obtain the values of ω⁽ⁱ⁾(μ), for i = 0,…,n − 1, we differentiate (3.6) n − 1 times and we evaluate ω⁽ⁱ⁾(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 p_i the distribution of the waiting time is Erlang-i, for i = 1,…,n. Furthermore, the probability p₀ 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 X_n follow an Erlang-n distribution with parameter μ and let the random variable B of the preparation times be equal to X_n 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 X_n 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 φ⁽ⁱ⁾(μ) 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 p₀ 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.

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 W^A ≥_st W^NA 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 B_i ≥ B_i+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 {B_i} be a sequence of preparation times and {A_i} 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 B₁. Additionally, let R_n be the remaining preparation time for the nth customer, immediately after the service of the n − 1 customer has finished. As long as R_n ≤ B_n+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 R_n > B_n+1, the alternating service system will regenerate for the first time, since we will have that W_n^A = R_n and W_n+1^A = 0. The nonalternating system, however, does not necessarily regenerate. For this system we have that W_n^NA = B_n+1 and R_n+1^NA = R_n − B_n+1 − A_n. Therefore, if R_n+1^NA = 0, then W_n+1^NA = 0 and both processes regenerate. Otherwise the nonalternating system will not regenerate. Hence, for each realization we have that N^NA ≥ N^A, 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 {B_i} and {A_i} 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:

Also define in the same way D_i^NA and H_i^NA for the nonalternating system. We need the following lemma.

Lemma 1: For all i, we have that D_i^A ≥ D_i^NA and H_i^A ≥ H_i^NA.

Proof: We will apply induction. For i = 1 we have that D₁^A ≥ D₁^NA and H₁^A ≥ H₁^NA, since

and thus

Suppose that for some i we have that D_i−1^A ≥ D_i−1^NA and H_i−1^A ≥ H_i−1^NA. We will prove that D_i^A ≥ D_i^NA and H_i^A ≥ H_i^NA and this will conclude the proof.

The first relation is obvious. From the induction hypothesis we have H_i−1^A ≥ H_i−1^NA, 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 D_i^NA 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 H_i−1^NA and D_i−1^NA + B_i.

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 H_i^A = D_i^A. Then D_i^A ≥ D_i^NA as we have proven above; furthermore D_i^A = H_i−1^A + A_i ≥ H_i−1^NA since H_i−1^A ≥ H_i−1^NA; and finally, since H_i^A = D_i^A, then D_i^A ≥ D_i−1^A + B_i ≥ D_i−1^NA + B_i. The case for H_i^A = D_i−1^A + B_i 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 W^A and W^NA are not stochastically ordered, the partial sums of the sequences W_i^A and W_i^NA 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 c_A² 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 c_A². As c_A² 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 W^NA is smaller than W^A 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]).