Page 231 - A First Course In Stochastic Models

224 MARKOV CHAINS AND QUEUES

other customers at node j. By the memoryless property of the exponential dis-
tribution and the assumption of service in order of arrival, the relation (5.6.20)
now follows. This relation enables us to calculate L m (j), W m (j) and λ m (j) in a
recursive manner. A direct consequence of (5.6.17) to (5.6.19) is the relation
m
γ m = . (5.6.21)
K

π j W m (j)
j=1
Mean-value algorithm
Step 0. Calculate first the equilibrium probabilities π j associated with the Markov
matrix P =(p ij ). Calculate W 1 (j) = 1/µ j for j = 1, . . . , K. Let m := 1.
Step 1. Calculate the constant γ m from (5.6.21). Next calculate λ m (j) and L m (j)
for j = 1, . . . , K from (5.6.17) and (5.6.18). If m < M, then go to step 2.
Step 2. m := m+1. Calculate W m (j) for j = 1, . . . K from (5.6.20). Repeat step 1.

EXERCISES

5.1 Consider the M/M/c/c + N queueing model with finite waiting room. This model is
the same as the M/M/c model except that there are only N waiting places for customers to
await service. An arriving customer who finds all c servers busy and all N waiting places
occupied is rejected. Denote by {p j , 0 ≤ j ≤ N + c} the equilibrium distribution of the
number of customers present.
(a) Give a recursion scheme for the computation of the p j .
(b) Verify that the limiting distribution of the delay in queue of an accepted customer is
given by
N+c−1 j−c k
1 −cµx (cµx)
W q (x) = 1 − p j e , x ≥ 0.
p N+c k!
j=c k=0
5.2 In the machine-repair queueing model there are N identical machines which are attended
by c repairmen, where N > c. The running time of a machine is exponentially distributed
with mean 1/ν. The running times of the machines are independent of each other. A stopped
machine is attended as soon as possible by a free repairman. Each repairman can handle
only one machine at a time. The service time of a machine is exponentially distributed with
mean 1/µ.
(a) Let p j = lim t→∞ P{j service requests are present at time t} for 0 ≤ j ≤ N. Give a
recursion scheme to compute the p j .
(b) Let π j denote the long-run fraction of service requests finding j other requests present
N
upon occurrence. Argue that π j = (N − j)p j / k=0 (N − k)p k for 0 ≤ j ≤ N − 1.
(c) What is the limiting distribution of the delay in queue of a service request when
service is in order of arrival? What is the long-run average number of busy repairmen?
5.3 Consider the following modification of the call-centre problem dealt with in Section 5.3.
If the service of a customer has not yet started, the customer becomes impatient after an
exponentially distributed time with mean 1/θ and then leaves the system. It is assumed
that the impatience time of the customer does not depend on their position in the queue
(call-centre customers cannot see each other).