Page 365 - A First Course In Stochastic Models

360 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

This gives the following expression for the derivative of p K (x):
K−x
′
p (x) = −λp K (x) + λ p K (x + y)b(y) dy, 0 < x < K.
K
0
Mimicking the derivation of (8.4.4) gives
d K−x
′
p (x) = λ p K (x + y){1 − B(y)} dy, 0 < x < K.
K
dx 0
Letting q K (x) = p K (K − x) for 0 < x < K, we thus have
d x
q (x) = λ q K (x − y){1 − B(y)} dy, 0 < x < K.
′
K
dx 0
This equation has a unique solution since it can be reduced to a renewal-type
equation. Comparing this equation with equation (9.2.34) reveals that, for some
constant c,

q K (x) = cV ∞ (x), 0 < x < K.
Since lim x→0 p K (x) = 1, the result (9.2.38) now follows. It remains to verify
(9.2.37). To do so, note that

K
P {V max > K} = 1 − p K (x)b(x) dx
0

K
V ∞ (K) − 0 V ∞ (K − x)b(x) dx
= . (9.2.39)
V ∞ (K)
The numerator of the last expression equals λ −1 V (K) by relation (9.2.34). This
′
∞
completes the verification of (9.2.37).
The probability distribution (9.2.37) of V max can be calculated by numerical
′
inversion of the Laplace transforms of V ∞ (x) and V (x). The Laplace transform
∞
of 1 − V ∞ (x) is given by (9.2.33). Letting v ∞ (x) denote the derivative of V ∞ (x)

x
for x > 0 and noting that V ∞ (x) = V ∞ (0) + v ∞ (y) dy, we find
0

∗
∞ (1 − ρ) λ − λb (s)
e −sx v ∞ (x) dx = .
∗
0 s − λ + λb (s)
X
9.3 THE M /G/1 QUEUE
Queueing systems with customers arriving in batches rather than singly have many
applications in practice, for example in telecommunication. A useful model is
X
the single-server M /G/1 queue where batches of customers arrive according
to a Poisson process with rate λ and the batch size X has a discrete probability
distribution {β j , j = 1, 2, . . . } with finite mean β. The customers are served