Page 427 - A First Course In Stochastic Models

422 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

of time that j customers are in orbit during a given service time when k customers were
left behind in orbit at the completion of the previous service time.)
(b) Use generating functions to verify that
2 1
λ α(z)
p 00 = (1 − ρ) exp − dz ,
ν 0 1 − λα(z)
∞ −λt(1−z)

where α(z) = e {1 − B(t)} dt.
0
(c) Instead of the M/G/1 queue with a linear retrial rate, consider the M/G/1 queue
with a constant retrial rate. That is, retrials occur according to a Poisson process with rate
ν when the orbit is not empty. Modify the above results. This problem is based on De Kok
(1984).
9.5 Consider the M/G/1 queue with exponential first service from Exercise 9.1 again.
Assume that service is in order of arrival. Let W q (x) denote the limiting distribution function
of the delay in queue of a customer.
p
∞ j
(a) Verify that the generating function P(z) = j=0 j z is given by
p 0 [1 − λ(α(z) − zα 0 (z))]
P(z) = ,
1 − λα(z)
∞ −λ(1−z)t ∞ −λ(1−z)t

where α(z) = 0 e {1 − B(t)} dt and α 0 (z) = 0 e {1 − B 0 (t)} dt.
(b) Verify that the relation (2.5.14) also applies to the M/G/1 queue with server vacations,
(∞) 1
where E(z L q ) = p 0 + [P(z) − p 0 ]. Next prove that
z
∞ −sx 1 λp 0 (1 − b (s))
∗
0
e {1 − W q (x)} dx = 1 − p 0 − ,
∗
0 s s − λ + λb (s)

∞ −sx
∗
where b (s) = e b 0 (x) dx is the Laplace transform of the density of the exceptional
0 0

∞ −sx
∗
first service and b (s) = 0 e b(x) dx is the Laplace transform of the density of the
ordinary service.
9.6 Consider again the M/G/1 queue with server vacations from Exercise 9.2. Assuming
that service is in order of arrival, let W q (x) denote the limiting distribution function of the
delay in queue of a customer.
∞ j ∞ j
(a) Letting P 0 (z) = p 0j z and P 1 (z) = p 1j z , verify from the recursion
j=0 j=1
scheme in Exercise 9.2 that
1 − ρ λα(z)
P 0 (z) = ν(z) and P 1 (z) = zP 0 (z) ,
E(V ) 1 − λα(z)
∞ −λ(1−z)t ∞ −λ(1−z)t

where ν(z) = e {1 − V (t)} dt and α(z) = e {1 − B(t)} dt. Argue
0 0
(∞)
that relation (2.5.14) also applies to the M/G/1 queue with server vacations where E(z L q )
is given by P 0 (z) + P 1 (z)/z.
(b) Verify that the Laplace transform of 1 − W q (x) is given by
∞ 1 − η (s)ξ (s)
∗
∗

−sx
e {1 − W q (x)} dx =
0 s
where ξ (s) = (1 − ρ)s/[s − λ + λb (s)] and η (s) is the Laplace transform of the density
∗
∗
∗
[1 − V (x)]/E(V ). Here b (s) is the Laplace transform of the service-time density, ξ (s)
∗
∗
∗
corresponds to E(e −sD ∞ ) in the standard M/G/1 queue without vacations and η (s) is the