(8.27)

Also using the fact that ∑j=1kLm-1(j)=m-1 (why?) we obtain, from Equation (8.26), the following:

m-1=λm-1∑j=1kπjWm-1(j)

or

λm-1=m-1∑i=1kπiWm-1(i) (8.28)

(8.28)

Hence, from Equation (8.27), we obtain the recursion

Wm(j)=1μj+(m-1)πjWm-1(j)μj∑i=1kπiWm-1(i) (8.29)

(8.29)

Starting with the stationary probabilities πj,j=1,…,k, and W1(j)=1/μj we can now use Equation (8.29) to determine recursively W2(j),W3(j),…,Wm(j). We can then determine the throughput rate λm by using Equation (8.28), and this will determine Lm(j) by Equation (8.26). This recursive approach is called mean value analysis.

Example 8.9

Consider a k-server network in which the customers move in a cyclic permutation. That is,

Pi,i+1=1,i=1,2…,k-1,Pk,1=1

Let us determine the average number of customers at server j when there are two customers in the system. Now, for this network,

πi=1/k,i=1,…,k

and as

W1(j)=1μj

we obtain from Equation (8.29) that

W2(j)=1μj+(1/k)(1/μj)μj∑i=1k(1/k)(1/μi)=1μj+1μj2∑i=1k1/μi

Hence, from Equation (8.28),

λ2=2∑l=1k1kW2(l)=2k∑l=1k1μl+1μl2∑i=1k1/μi

and finally, using Equation (8.26),

L2(j)=λ21kW2(j)=21μj+1μj2∑i=1k1/μi∑l=1k1μl+1μl2∑i=1k1/μi■

Another approach to learning about the stationary probabilities specified by Equation (8.22), which finesses the computational difficulties of computing the constant Cm, is to use the Gibbs sampler of Section 4.9 to generate a Markov chain having these stationary probabilities. To begin, note that since there are always a total of m customers in the system, Equation (8.22) may equivalently be written as a joint mass function of the numbers of customers at each of the servers 1,…,k-1, as follows:

Pm(n1,…,nk-1)=Cm(πk/μk)m-∑nj∏j=1k-1(πj/μj)nj=K∏j=1k-1(aj)nj,∑j=1k-1nj⩽m

where aj=(πjμk)/(πkμj),j=1,…,k-1. Now, if N=(N1,…,Nk-1) has the preceding joint mass function then

P{Ni=n∣N1=n1,…,Ni-1=ni-1,Ni+1=ni+1,…,Nk-1=nk-1}=Pm(n1,…,ni-1,n,ni+1,…,nk-1)∑rPm(n1,…,ni-1,r,ni+1,…,nk-1)=Cain,n⩽m-∑j≠inj

It follows from the preceding that we may use the Gibbs sampler to generate the values of a Markov chain whose limiting probability mass function is Pm(n1,…,nk-1) as follows:

1. Let (n1,…,nk-1) be arbitrary nonnegative integers satisfying ∑j=1k-1nj⩽m.

2. Generate a random variable I that is equally likely to be any of 1,…,k-1.

3. If I=i, set s=m-∑j≠inj, and generate the value of a random variable X having probability mass function

P{X=n}=Cain,n=0,…,s

4. Let nI=X and go to step 2.

The successive values of the state vector (n1,…,nk-1,m-∑j=1k-1nj) constitute the sequence of states of a Markov chain with the limiting distribution Pm. All quantities of interest can be estimated from this sequence. For instance, the average of the values of the jth coordinate of these vectors will converge to the mean number of individuals at station j, the proportion of vectors whose jth coordinate is less than r will converge to the limiting probability that the number of individuals at station j is less than r, and so on.

Other quantities of interest can also be obtained from the simulation. For instance, suppose we want to estimate Wj, the average amount of time a customer spends at server j on each visit. Then, as noted in the preceding, Lj, the average number of customers at server j, can be estimated. To estimate Wj, we use the identity

Lj=λjWj

where λj is the rate at which customers arrive at server j. Setting λj equal to the service completion rate at server j shows that

λj=P{jis busy}μj

Using the Gibbs sampler simulation to estimate P{jis busy} then leads to an estimator of Wj.

8.5 The System M/G/1

8.5.1 Preliminaries: Work and Another Cost Identity

For an arbitrary queueing system, let us define the work in the system at any time t to be the sum of the remaining service times of all customers in the system at time t. For instance, suppose there are three customers in the system—the one in service having been there for three of his required five units of service time, and both people in queue having service times of six units. Then the work at that time is 2+6+6=14. Let V denote the (time) average work in the system.

Now recall the fundamental cost Equation (8.1), which states that the

average rate at which the system earns=λa×average amount a customer pays

and consider the following cost rule: Each customer pays at a rate of y/unit time when his remaining service time is y, whether he is in queue or in service. Thus, the rate at which the system earns is just the work in the system; so the basic identity yields

V=λaE[amount paid by a customer]

Now, let S and WQ∗ denote respectively the service time and the time a given customer spends waiting in queue. Then, since the customer pays at a constant rate of S per unit time while he waits in queue and at a rate of S-x after spending an amount of time x in service, we have

E[amount paid by a customer]=ESWQ∗+∫0S(S-x)dx

and thus

V=λaE[SWQ∗]+λaE[S2]2 (8.30)

(8.30)

It should be noted that the preceding is a basic queueing identity (like Equations (8.2)– (8.4)) and as such is valid in almost all models. In addition, if a customer’s service time is independent of his wait in queue (as is usually, but not always the case),^∗ then we have from Equation (8.30) that

V=λaE[S]WQ+λaE[S2]2 (8.31)

(8.31)

8.5.2 Application of Work to M/G/1

The M/G/1 model assumes (i) Poisson arrivals at rate λ; (ii) a general service distribution; and (iii) a single server. In addition, we will suppose that customers are served in the order of their arrival.

Now, for an arbitrary customer in an M/G/1 system,

customer’s wait in queue=work in the system when he arrives (8.32)

(8.32)

This follows since there is only a single server (think about it!). Taking expectations of both sides of Equation (8.32) yields

WQ=average work as seen by an arrival

But, due to Poisson arrivals, the average work as seen by an arrival will equal V, the time average work in the system. Hence, for the model M/G/1,

WQ=V

The preceding in conjunction with the identity

V=λE[S]WQ+λE[S2]2

yields the so-called Pollaczek–Khintchine formula,

WQ=λE[S2]2(1-λE[S]) (8.33)

(8.33)

where E[S] and E[S2] are the first two moments of the service distribution.

The quantities L,LQ, and W can be obtained from Equation (8.33) as

LQ=λWQ=λ2E[S2]2(1-λE[S]),W=WQ+E[S]=λE[S2]2(1-λE[S])+E[S],L=λW=λ2E[S2]2(1-λE[S])+λE[S] (8.34)

(8.34)

Remarks

(i) For the preceding quantities to be finite, we need λE[S]<1. This condition is intuitive since we know from renewal theory that if the server was always busy, then the departure rate would be 1/E[S] (see Section 7.3), which must be larger than the arrival rate λ to keep things finite.

(ii) Since E[S2]=Var(S)+(E[S])2, we see from Equations (8.33) and (8.34) that, for fixed mean service time, L,LQ,W, and WQ all increase as the variance of the service distribution increases.

(iii) Another approach to obtain WQ is presented in Exercise 38.

8.5.3 Busy Periods

The system alternates between idle periods (when there are no customers in the system, and so the server is idle) and busy periods (when there is at least one customer in the system, and so the server is busy).

Let I and B represent, respectively, the length of an idle and of a busy period. Because I represents the time from when a customer departs and leaves the system empty until the next arrival, it follows, since arrivals are according to a Poisson process with rate λ, that I is exponential with rate λ and thus

E[I]=1λ (8.35)

(8.35)

To determine E[B] we argue, as in Section 8.3.3, that the long-run proportion of time the system is empty is equal to the ratio of E[I] to E[I]+E[B]. That is,

P0=E[I]E[I]+E[B] (8.36)

(8.36)

To compute P0, we note from Equation (8.4) (obtained from the fundamental cost equation by supposing that a customer pays at a rate of one per unit time while in service) that

average number of busy servers=λE[S]

However, as the left-hand side of the preceding equals 1-P0 (why?), we have

P0=1-λE[S] (8.37)

(8.37)

and, from Equations (8.35)– (8.37),

1-λE[S]=1/λ1/λ+E[B]

or

E[B]=E[S]1-λE[S]

Another quantity of interest is C, the number of customers served in a busy period. The mean of C can be computed by noting that, on the average, for every E[C] arrivals exactly one will find the system empty (namely, the first customer in the busy period). Hence,

a0=1E[C]

and, as a0=P0=1-λE[S] because of Poisson arrivals, we see that

E[C]=11-λE[S]

8.6 Variations on the M/G/1

8.6.1 The M/G/1 with Random-Sized Batch Arrivals

Suppose that, as in the M/G/1, arrivals occur in accordance with a Poisson process having rate λ. But now suppose that each arrival consists not of a single customer but of a random number of customers. As before there is a single server whose service times have distribution G.

Let us denote by αj,j⩾1, the probability that an arbitrary batch consists of j customers; and let N denote a random variable representing the size of a batch and so P{N=j}=αj. Since λa=λE(N), the basic formula for work (Equation (8.31)) becomes

V=λE[N]E(S)WQ+E(S2)2 (8.38)

(8.38)

To obtain a second equation relating V to WQ, consider an average customer. We have that

his wait in queue=work in system when he arrives+his waiting time due to those in his batch

Taking expectations and using the fact that Poisson arrivals see time averages yields

WQ=V+E[waiting time due to those in his batch]=V+E[WB] (8.39)

(8.39)

Now, E(WB) can be computed by conditioning on the number in the batch, but we must be careful because the probability that our average customer comes from a batch of size j is not αj. For αj is the proportion of batches that are of size j, and if we pick a customer at random, it is more likely that he comes from a larger rather than a smaller batch. (For instance, suppose α1=α100=12, then half the batches are of size 1 but 100/101 of the customers will come from a batch of size 100!)

To determine the probability that our average customer came from a batch of size j we reason as follows: Let M be a large number. Then of the first M batches approximately Mαj will be of size j,j⩾1, and thus there would have been approximately jMαj customers that arrived in a batch of size j. Hence, the proportion of arrivals in the first M batches that were from batches of size j is approximately jMαj/∑jjMαj. This proportion becomes exact as M→∞, and so we see that

proportion of customers from batches of sizej=jαj∑jjαj=jαjE[N]

We are now ready to compute E(WB), the expected wait in queue due to others in the batch:

E[WB]=∑jE[WB∣batch of sizej]jαjE[N] (8.40)

(8.40)

Now if there are j customers in his batch, then our customer would have to wait for i-1 of them to be served if he was ith in line among his batch members. As he is equally likely to be either 1st, 2nd, … , or jth in line we see that

E[WB∣batch is of sizej]=∑i=1j(i-1)E(S)1j=j-12E[S]

Substituting this in Equation (8.40) yields

E[WB]=E[S]2E[N]∑j(j-1)jαj=E[S](E[N2]-E[N])2E[N]

and from Equations (8.38) and (8.39) we obtain

WQ=E[S](E[N2]-E[N])/2E[N]+λE[N]E[S2]/21-λE[N]E[S]

Remarks

(i) Note that the condition for WQ to be finite is that

λE(N)<1E[S]

which again says that the arrival rate must be less than the service rate (when the server is busy).

(ii) For fixed value of E[N],WQ is increasing in Var(N), again indicating that “single-server queues do not like variation.”

(iii) The other quantities L,LQ, and W can be obtained by using

W=WQ+E[S],L=λaW=λE[N]W,LQ=λE[N]WQ

8.6.2 Priority Queues

Priority queueing systems are ones in which customers are classified into types and then given service priority according to their type. Consider the situation where there are two types of customers, which arrive according to independent Poisson processes with respective rates λ1 and λ2, and have service distributions G1 and G2. We suppose that type 1 customers are given service priority, in that service will never begin on a type 2 customer if a type 1 is waiting. However, if a type 2 is being served and a type 1 arrives, we assume that the service of the type 2 is continued until completion. That is, there is no preemption once service has begun.

Let WQi denote the average wait in queue of a type i customer, i=1,2. Our objective is to compute the WQi.

First, note that the total work in the system at any time would be exactly the same no matter what priority rule was employed (as long as the server is always busy whenever there are customers in the system). This is so since the work will always decrease at a rate of one per unit time when the server is busy (no matter who is in service) and will always jump by the service time of an arrival. Hence, the work in the system is exactly as it would be if there was no priority rule but rather a first-come, first-served (called FIFO) ordering. However, under FIFO the preceding model is just M/G/1 with

λ=λ1+λ2,G(x)=λ1λG1(x)+λ2λG2(x) (8.41)

(8.41)

which follows since the combination of two independent Poisson processes is itself a Poisson process whose rate is the sum of the rates of the component processes. The service distribution G can be obtained by conditioning on which priority class the arrival is from—as is done in Equation (8.41).

Hence, from the results of Section 8.5, it follows that V, the average work in the priority queueing system, is given by

V=λE[S2]2(1-λE[S])=λ((λ1/λ)E[S12]+(λ2/λ)E[S22])2[1-λ((λ1/λ)E[S1]+(λ2/λ)E[S2])]=λ1E[S12]+λ2E[S22]2(1-λ1E[S1]-λ2E[S2]) (8.42)

(8.42)

where Si has distribution Gi,i=1, 2.

Continuing in our quest for WQi let us note that S and WQ∗, the service and wait in queue of an arbitrary customer, are not independent in the priority model since knowledge about S gives us information as to the type of customer, which in turn gives us information about WQ∗. To get around this we will compute separately the average amount of type 1 and type 2 work in the system. Denoting Vi as the average amount of type i work we have, exactly as in Section 8.5.1,

Vi=λiE[Si]WQi+λiE[Si2]2,i=1,2 (8.43)

(8.43)

If we define

VQi≡λiE[Si]WQi,VSi≡λiE[Si2]2

then we may interpret VQi as the average amount of type i work in queue, and VSi as the average amount of type i work in service (why?).

Now we are ready to compute WQ1. To do so, consider an arbitrary type 1 arrival. Then

his delay=amount of type 1 work in the system when he arrives+amounts of type 2 work in service when he arrives

Taking expectations and using the fact that Poisson arrivals see time average yields

WQ1=V1+VS2=λ1E[S1]WQ1+λ1E[S12]2+λ2E[S22]2 (8.44)

(8.44)

or

WQ1=λ1E[S12]+λ2E[S22]2(1-λ1E[S1]) (8.45)

(8.45)

To obtain WQ2 we first note that since V=V1+V2, we have from Equations (8.42) and (8.43) that

λ1E[S12]+λ2E[S22]2(1-λ1E[S1]-λ2E[S2])=λ1E[S1]WQ1+λ2E[S2]WQ2+λ1E[S12]2+λ2E[S22]2=WQ1+λ2E[S2]WQ2from Equation(8.44)

Now, using Equation (8.45), we obtain

λ2E[S2]WQ2=λ1E[S12]+λ2E[S22]211-λ1E[S1]-λ2E[S2]-11-λ1E[S1]

or

WQ2=λ1E[S12]+λ2E[S22]2(1-λ1E[S1]-λ2E[S2])(1-λ1E[S1]) (8.46)

(8.46)

Remarks

(i) Note that from Equation (8.45), the condition for WQ1 to be finite is that λ1E[S1]<1, which is independent of the type 2 parameters. (Is this intuitive?) For WQ2 to be finite, we need, from Equation (8.46), that

λ1E[S1]+λ2E[S2]<1

Since the arrival rate of all customers is λ=λ1+λ2, and the average service time of a customer is (λ1/λ)E[S1]+(λ2/λ)E[S2], the preceding condition is just that the average arrival rate be less than the average service rate.

(ii) If there are n types of customers, we can solve for Vj,j=1,…,n, in a similar fashion. First, note that the total amount of work in the system of customers of types 1,…,j is independent of the internal priority rule concerning types 1,…,j and only depends on the fact that each of them is given priority over any customers of types j+1,…,n. (Why is this? Reason it out!) Hence, V1+⋯+Vj is the same as it would be if types 1,…,j were considered as a single type I priority class and types j+1,…,n as a single type II priority class. Now, from Equations (8.43) and (8.45),

VI=λIE[SI2]+λIλIIE[SI]E[SII2]2(1-λIE[SI])

where

λI=λ1+⋯+λj,λII=λj+1+⋯+λn,E[SI]=∑i=1jλiλIE[Si],E[SI2]=∑i=1jλiλIE[Si2],E[SII2]=∑i=j+1nλiλIIE[Si2]

Hence, as VI=V1+⋯+Vj, we have an expression for V1+⋯+Vj, for each j=1,…,n, which then can be solved for the individual V1,V2,…,Vn. We now can obtain WQi from Equation (8.43). The result of all this (which we leave for an exercise) is that

WQi=λ1E[S12]+⋯+λnE[Sn2]2∏j=i-1i(1-λ1E[S1]-⋯-λjE[Sj]),i=1,…,n (8.47)

(8.47)

8.6.3 An M/G/1 Optimization Example

Consider a single-server system where customers arrive according to a Poisson process with rate λ, and where the service times are independent and have distribution function G. Let ρ=λE[S], where S represents a service time random variable, and suppose that ρ<1. Suppose that the server departs whenever a busy period ends and does not return until there are n customers waiting. At that time the server returns and continues serving until the system is once again empty. If the system facility incurs costs at a rate of c per unit time per customer in the system, as well as a cost K each time the server returns, what value of n,n⩾1, minimizes the long-run average cost per unit time incurred by the facility, and what is this minimal cost?

To answer the preceding, let us first determine A(n), the average cost per unit time for the policy that returns the server whenever there are n customers waiting. To do so, say that a new cycle begins each time the server returns. As it is easy to see that everything probabilistically starts over when a cycle begins, it follows from the theory of renewal reward processes that if C(n) is the cost incurred in a cycle and T(n) is the time of a cycle, then

A(n)=E[C(n)]E[T(n)]

To determine E[C(n)] and E[T(n)], consider the time interval of length, say, Ti, starting from the first time during a cycle that there are a total of i customers in the system until the first time afterward that there are only i-1. Therefore, ∑i=1nTi is the amount of time that the server is busy during a cycle. Adding the additional mean idle time until n customers are in the system gives

E[T(n)]=∑i=1nE[Ti]+n/λ

Now, consider the system at the moment when a service is about to begin and there are i-1 customers waiting in queue. Since service times do not depend on the order in which customers are served, suppose that the order of service is last come first served, implying that service does not begin on the i-1 presently in queue until these i-1 are the only ones in the system. Thus, we see that the time that it takes to go from i customers in the system to i-1 has the same distribution as the time it takes the M/G/1 system to go from a single customer (just beginning service) to empty; that is, its distribution is that of B, the length of an M/G/1 busy period. (Essentially the same argument was made in Example 5.25.) Hence,

E[Ti]=E[B]=E[S]1-ρ

implying that

E[T(n)]=nE[S]1-λE[S]+nλ=nλ(1-ρ) (8.48)

(8.48)

To determine E[C(n)], let Ci denote the cost incurred during the interval of length Ti that starts with i-1 in queue and a service just beginning and ends when the i-1 in queue are the only customers in the system. Thus, K+∑i=1nCi represents the total cost incurred during the busy part of the cycle. In addition, during the idle part of the cycle there will be i customers in the system for an exponential time with rate λ,i=1,…,n-1, resulting in an expected cost of c(1+⋯+n-1)/λ. Consequently,

E[C(n)]=K+∑i=1nE[Ci]+n(n-1)c2λ (8.49)

(8.49)

To find E[Ci], consider the moment when the interval of length Ti begins, and let Wi be the sum of the initial service time plus the sum of the times spent in the system by all the customers that arrive (and are served) until the moment when the interval ends and there are only i-1 customers in the system. Then,

Ci=(i-1)cTi+cWi

where the first term refers to the cost incurred due to the i-1 customers in queue during the interval of length Ti. As it is easy to see that Wi has the same distribution as Wb, the sum of the times spent in the system by all arrivals in an M/G/1 busy period, we obtain

E[Ci]=(i-1)cE[S]1-ρ+cE[Wb] (8.50)

(8.50)

Using Equation (8.49), this yields

E[C(n)]=K+n(n-1)cE[S]2(1-ρ)+ncE[Wb]+n(n-1)c2λ=K+ncE[Wb]+n(n-1)c2λρ1-ρ+1=K+ncE[Wb]+n(n-1)c2λ(1-ρ)

Utilizing the preceding in conjunction with Equation (8.48) shows that

A(n)=Kλ(1-ρ)n+λc(1-ρ)E[Wb]+c(n-1)2 (8.51)

(8.51)

To determine E[Wb], we use the result that the average amount of time spent in the system by a customer in the M/G/1 system is

W=WQ+E[S]=λE[S2]2(1-ρ)+E[S]

However, if we imagine that on day j,j⩾1, we earn an amount equal to the total time spent in the system by the jth arrival at the M/G/1 system, then it follows from renewal reward processes (since everything probabilistically restarts at the end of a busy period) that

W=E[Wb]E[N]

where N is the number of customers served in an M/G/1 busy period. Since E[N]=1/(1-ρ) we see that

(1-ρ)E[Wb]=W=λE[S2]2(1-ρ)+E[S]

Therefore, using Equation (8.51), we obtain

A(n)=Kλ(1-ρ)n+cλ2E[S2]2(1-ρ)+cρ+c(n-1)2

To determine the optimal value of n, treat n as a continuous variable and differentiate the preceding to obtain

A′(n)=-Kλ(1-ρ)n2+c2

Setting this equal to 0 and solving yields that the optimal value of n is

n∗=2Kλ(1-ρ)c

and the minimal average cost per unit time is

A(n∗)=2λK(1-ρ)c+cλ2E[S2]2(1-ρ)+cρ-c2

It is interesting to see how close we can come to the minimal average cost when we use a simpler policy of the following form: Whenever the server finds the system empty of customers she departs and then returns after a fixed time t has elapsed. Let us say that a new cycle begins each time the server departs. Both the expected costs incurred during the idle and the busy parts of a cycle are obtained by conditioning on N(t), the number of arrivals in the time t that the server is gone. With C¯(t) being the cost incurred during a cycle, we obtain

E[C¯(t)∣N(t)]=K+∑i=1N(t)E[Ci]+cN(t)t2=K+N(t)(N(t)-1)cE[S]2(1-ρ)+N(t)cE[Wb]+cN(t)t2

The final term of the first equality is the conditional expected cost during the idle time in the cycle and is obtained by using that, given the number of arrivals in the time t, the arrival times are independent and uniformly distributed on (0,t); the second equality used Equation (8.50). Since N(t) is Poisson with mean λt, it follows that E[N(t)(N(t)-1)]=E[N2(t)]-E[N(t)]=λ2t2. Thus, taking the expected value of the preceding gives

E[C¯(t)]=K+λ2t2cE[S]2(1-ρ)+λtcE[Wb]+cλt22=K+cλt22(1-ρ)+λtcE[Wb]

Similarly, if T¯(t) is the time of a cycle, then

E[T¯(t)]=E[E[T¯(t)∣N(t)]]=E[t+N(t)E[B]]=t+ρt1-ρ=t1-ρ

Hence, the average cost per unit time, call it A¯(t), is

A¯(t)=E[C¯(t)]E[T¯(t)]=K(1-ρ)t+cλt2+cλ(1-ρ)E[Wb]

Thus, from Equation (8.51), we see that

A¯(n/λ)-A(n)=c/2

which shows that allowing the return decision to depend on the number presently in the system can reduce the average cost only by the amount c/2. ■

8.6.4 The M/G/1 Queue with Server Breakdown

Consider a single server queue in which customers arrive according to a Poisson process with rate λ, and where the amount of service time required by each customer has distribution G. Suppose, however, that when working the server breaks down at an exponential rate α. That is, the probability a working server will be able to work for an additional time t without breaking down is e-αt. When the server breaks down, it immediately goes to the repair facility. The repair time is a random variable with distribution H. Suppose that the customer in service when a breakdown occurs has its service continue, when the sever returns, from the point it was at when the breakdown occurred. (Therefore, the total amount of time a customer is actually receiving service from a working server has distribution G.)

By letting a customer’s “service time” include the time that the customer is waiting for the server to come back from being repaired, the preceding is an M/G/1 queue. If we let T denote the amount of time from when a customer first enters service until it departs the system, then T is a service time random variable of this M/G/1 queue. The average amount of time a customer spends waiting in queue before its service first commences is, thus,

WQ=λE[T2]2(1-λE[T])

To compute E[T] and E[T2], let S, having distribution G, be the service requirement of the customer; let N denote the number of times that the server breaks down while the customer is in service; let R1,R2,… be the amounts of time the server spends in the repair facility on its successive visits. Then,

T=∑i=1NRi+S

Conditioning on S yields

E[T∣S=s]=E∑i=1NRiS=s+s,Var(T∣S=s)=Var∑i=1NRiS=s

Now, a working server always breaks down at an exponential rate α. Therefore, given that a customer requires s units of service time, it follows that the number of server breakdowns while that customer is being served is a Poisson random variable with mean αs. Consequently, conditional on S=s, the random variable ∑i=1NRi is a compound Poisson random variable with Poisson mean αs. Using the results from Examples 3.10 and 3.17, we thus obtain

E∑i=1NRiS=s=αsE[R],Var∑i=1NRiS=s=αsE[R2]

where R has the repair distribution H. Therefore,

E[T∣S]=αSE[R]+S=S(1+αE[R]),Var(T∣S)=αSE[R2]

Thus,

E[T]=E[E[T∣S]]=E[S](1+αE[R])

and, by the conditional variance formula,

Var(T)=E[Var(T∣S)]+Var(E[T∣S])=αE[S]E[R2]+(1+αE[R])2Var(S)

Therefore,

E[T2]=Var(T)+(E[T])2=αE[S]E[R2]+(1+αE[R])2E[S2]

Consequently, assuming that λE[T]=λE[S](1+αE[R])<1, we obtain

WQ=λαE[S]E[R2]+λ(1+αE[R])2E[S2]2(1-λE[S](1+αE[R]))

From the preceding, we can now obtain

LQ=λWQ,W=WQ+E[T],L=λW

Some other quantities we might be interested in are

(i) Pw, the proportion of time the server is working;

(ii) Pr, the proportion of time the server is being repaired;

(iii) PI, the proportion of time the server is idle.

These quantities can all be obtained by using the queueing cost identity. For instance, if we suppose that customers pay 1 per unit time while actually being served, then

average rate at which system earns=Pw,average amount a customer pays=E[S]

Therefore, the identity yields

Pw=λE[S]

To determine Pr, suppose a customer whose service is interrupted pays 1 per unit time while the server is being repaired. Then,

average rate at which system earns=Pr,average amount a customer pays=E∑i=1NRi=αE[S]E[R]