Page 401 - A First Course In Stochastic Models

396 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

since the generating function of the compound Poisson probabilities r j (D) is given
by e −λD{1−β(z)} ; see Theorem 1.2.1. Before the discrete FFT method can be applied,
the unknown probabilities p 0 , . . . , p c−1 must be removed from (9.6.44). To do so,
we proceed in the same way as in Section 9.6.1 and rewrite P (z) in the explicit form

c(1 − ρ)(1 − z) c−1 z − z k !

P (z) = , (9.6.45)
1 − z e 1 − z k
c λD{1−β(z)}
k=1
where z 0 = 1, z 1 , . . . , z c−1 are the c distinct roots of z e = 1 inside
c λD{1−β(z)}
or on the unit circle. The computation of the (complex) roots z 1 , . . . , z c−1 is
discussed in Appendix G. The asymptotic expansion (9.6.41) follows from the
generating function (9.6.44) and Theorem C.1 in Appendix C. Also, we obtain
after considerable algebra from (9.6.44) that the long-run average queue size is
given by

c−2
1 2
L q =  (cρ) − c(c − 1) + {c(c − 1)
2c(1 − ρ)
j=2
2 !
E(X )
− j(j − 1)}p j + cρ − 1 ,
E(X)
where the random variable X denotes the batch size. This relation can be used as
an accuracy check on the calculated values of the probabilities p j .

X
Waiting-time probabilities in the M /D/c queue
X
In the batch-arrival M /D/c queue, the waiting-time probability W q (x) is defined
as the long-run fraction of customers whose waiting time in queue is no more than
x, x ≥ 0. The expression (9.6.9) for W q (x) in the M/D/c queue can be extended
X
to the M /G/c queue. For any x with (k − 1)D ≤ x < kD and k = 1, 2, . . . , it
holds that
kc−1 kc−1−m

W q (x) = η m+1 Q kc−1−m−j r j (kD − x) (9.6.46)
m=0 j=0
c+j

where Q j = p i for j = 0, 1, . . . and the probability η r is defined by
i=0
∞
1
η r = β j , r = 1, 2, . . . .
β
j=r
This result is due to Franx (2002). Its proof will be omitted. The asymptotic
expansion
1 − W q (x) ∼ γ e −λ[β(τ)−1]x as x → ∞ (9.6.47)