Page 354 - A First Course In Stochastic Models

THE M/G/1 QUEUE 349

Asymptotic expansion for the state probabilities
The representation (9.2.8) shows that the generating function P (z) is the ratio of
two functions, N(z) and D(z). These functions allow for an analytic continuation
outside the unit circle when the following assumption is made.

∞ st
Assumption 9.2.1 (a) e {1 − B(t)} dt < ∞ for some s > 0.
0
∞ st

(b) lim s→B 0 e {1 − B(t)} dt = ∞, where B is the supremum over all s with
∞

st
e {1 − B(t)} dt < ∞.
0
The assumption requires that the service-time distribution is not heavy-tailed. This
is the case in most situations of practical interest. Under Assumption 9.2.1, it can
be obtained from Theorem C.1 in Appendix C that
p j ∼ στ −j as j → ∞, (9.2.11)
where τ is the unique solution of the equation

∞ 1
−λ(1−τ)t
e {1 − B(t)} dt = (9.2.12)
0 λ
on the interval (1, 1 + B/λ) and the constant σ is given by
−1

(1 − ρ) ∞ −λ(1−τ)t
σ = 2 te {1 − B(t)} dt . (9.2.13)
λ 0
It is empirically found that the asymptotic expansion (9.2.11) already applies for
relatively small values of j. The asymptotic expansion can be used to reduce the
computational effort of the recursion scheme (9.2.1). Since p j−1 /p j ≈ τ for j
large enough, the recursive calculations can be halted as soon as the ratio p j−1 /p j
has sufficiently converged to the constant τ.

9.2.2 The Waiting-Time Probabilities
In this subsection we discuss the computation of the waiting-time probabilities
under the assumption that customers are served in order of arrival. Both exact
methods and approximate methods are discussed.

Exact methods
The following exact methods can be used for the computation of W q (x):

(a) discretization,
(b) Laplace-inversion,
(c) phase method.