Page 399 - A First Course In Stochastic Models

394 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

Next we discuss the computation of the steady-state probability distribution func-
tion W q (x) of the waiting time of a customer. The function W q (x) is defined in
the same way as in Section 9.3.2. To find W q (x), we need the probabilities
z j = the long-run fraction of customers who have j other customers in
front of them just after arrival, j = 0, 1, . . . .

The delay in queue of a customer who has j ≥ c other customers in front of him just
after arrival is the sum of j − c + 1 independent exponentials with common mean
1/(cµ). Hence this conditional waiting time has an E j−c+1 distribution and so
j−c
∞ k
−cµx (cµx)
1 − W q (x) = z j e , x ≥ 0.
k!
j=c k=0
A computationally better representation for W q (x) is
 
∞ k k+c−1
−cµx (cµx)
1 − W q (x) = e  1 − z j  , x ≥ 0. (9.6.37)
k!
k=0 j=0
The probabilities z j are easily expressed in terms of the p j . To do so, let
∞
1
η k = β j , k = 1, 2, . . . .
β
j=k
Then, as shown in Section 9.3.2, the probability η k gives the long-run fraction of
customers who take the kth position in their batch. Since the long-run fraction of
batches finding m other customers present upon arrival equals p m , we find
j

z j = p m η j−m+1 , j = 0, 1, . . . .
m=0
For the case of exponential services this formula can be considerably simplified.
Using the recursion relation (9.6.32), we have
µ
z j = min(j + 1, c)p j+1 , j = 0, 1, . . . . (9.6.38)
λβ
This completes the specification of the exact algorithm (9.6.37) for the computation
of the waiting-time probabilities W q (x). The computational effort can further be
reduced by using an asymptotic expansion for 1 − W q (x). Inserting (9.6.34) and
(9.6.38) into (9.6.37), we find after some algebra that

στ −c −cµ(1−1/τ)x
1 − W q (x) ∼ e as x → ∞, (9.6.39)
τ − 1
where τ and σ are given by (9.6.35) and (9.6.36).