Page 429 - A First Course In Stochastic Models

424 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

provided that ρ = λα/r is smaller than 1. It is an open problem whether the asymptotically
exponential expansion for π rej (K) holds when the amount of work brought in by a customer
has a general distribution with a non-heavy tail.
(b) Let K(α) be the smallest value of K for which π rej (K) ≤ α. Use the discretization
method from Example 5.5.2 to investigate the performance of the two-moment approxima-
2
2
2
tion K(α) ≈ (1 − c )K det (α) + c K exp (α) for α small and 0 ≤ c ≤ 2, where K det (α)
S S S
2
and K exp (α) are determined by the asymptotic expansions in (a). Here c is the squared
S
coefficient of variation of the amount of work brought in by a customer. This problem is
based on De Kok and Tijms (1985).
9.10 Consider the M/G/c queue with service in order of arrival. Prove that relation (2.5.14)
remains valid. Derive from this relation that
(∞) (∞) (∞) k k
E[L q (L q − 1) · · · (L q − k + 1)] = λ E(D ), k = 1, 2, . . . .
∞
9.11 Consider the M/G/c queue with service in order of arrival. Let V (x) denote the
conditional waiting-time distribution function of a delayed customer. That means V (x) =
[W q (x) − W q (0)]/P delay . Denote by v(x) the derivative of V (x) for x > 0.
(a) Use relation (2.5.14) to verify that
∞
∞
j −λ(1−z)x
p c+j z = P delay e v(x) dx.
0
j=0
app
(b) Let p denote the approximation to p j from Theorem 9.6.1 and let v app (x) be the
j
corresponding approximation to v(x). Use (9.6.21) and (9.6.23) to verify that the Laplace
transform of v app (x) is given by
∗
∞ (1 − ρ)α (s)

e −st v app (t) dt = ,
∗
0 1 − ρβ (s)
where the Laplace transforms α (s) and β (s) are given by
∗
∗
c ∞ c ∞
∗ −st c−1 ∗ −st
α (s) = e {1 − B e (t)} {1 − B(t)} dt, β (s) = e {1 − B(t)} dt.
µ 0 µ 0
Here B e (t) is the excess equilibrium distribution function of the service time.
(c) Verify by inversion of the Laplace transform of v app (x) that
x
c
V app (x) = (1 − ρ){1 − (1 − B e (x)) } + λ V app (x − y){1 − B(cy)} dy, x ≥ 0.
0
Assuming that the service-time distribution is not heavy-tailed, use the same arguments as
in Section 8.4 to verify that
e [1 − ρB e (cy) − (1 − ρ){1 − (1 − B e (y)) }] dy
e −δx
0 ∞ δy c
1 − V app (x) ∼
∞ δy
λ 0 ye {1 − B(cy)} dy

∞ δt
as x → ∞, where δ > 0 is the solution to λ 0 e {1 − B(ct)} dt = 1. This problem is
based on Van Hoorn and Tijms (1982).