Page 355 - A First Course In Stochastic Models

350 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

(a) By relation (8.4.5),
x
W q (x) = W q (0) + λ W q (x − y){1 − B(y)} dy, x ≥ 0 (9.2.14)
0

with W q (0) = 1 − ρ. This integral equation can be solved by using the dis-
cretization method discussed in Section 8.1.2. However, when a high accuracy
is required, this method is computationally rather demanding even when it is
combined with the asymptotic expansion for W q (x) to be given below.
(b) By (2.5.13), the Laplace transform of 1 − W q (x) is given by

∗
∞ ρs − λ + λb (s)

e −sx {1 − W q (x)} dx = , (9.2.15)
∗
0 s(s − λ + λb (s))

∞ −sx
∗
where b (s) = e b(x) dx is the Laplace transform of the service-time
0
density b(x). In Appendix F the computation of W q (x) by numerical Laplace
inversion is discussed.
(c) In Section 5.5 it was shown that any service-time distribution function B(x)
can be arbitrarily closely approximated by a distribution function of the form
 
∞ j−1 k
−µx (µx)
q j  1 − e  , x ≥ 0,
k!
j=1 k=0
∞
where q j ≥ 0 and j=1 j = 1. This distribution function is a mixture of Erlangian
q
distribution functions with the same scale parameters. It allows us to interprete the
service time as a random sum of independent phases each having the same expo-
nential distribution. Example 5.5.1 explains how to use continuous-time Markov
chain analysis for the computation of W q (x) when the service-time distribution has
the above form. This approach leads to a simple and fast algorithm.

A simple approximation to the waiting-time probabilities
Assume that Assumption 9.2.1 holds. Then, as was shown in Section 8.4,
−δx
1 − W q (x) ∼ γ e as x → ∞, (9.2.16)

with
σ
δ = λ(τ − 1) and γ = , (9.2.17)
τ − 1
where the constants τ and σ are given by (9.2.12) and (9.2.13).
We found empirically that the asymptotic expansion for 1 − W q (x) is accu-
rate enough for practical purposes for relatively small values of x. However, why