Page 369 - A First Course In Stochastic Models

364 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

of a constant batch size of 2. Then P {D n > 0} = 1 for n even and P {D n > 0} < 1
for n odd. The limit
n
1
W q (x) = lim P {D k ≤ x}, x ≥ 0
n→∞ n
k=1
always exists. To see this, fix x and imagine that a reward of 1 is earned for each
customer whose delay in queue is no more than x. Using renewal-reward theory,
it can be shown that the limit W q (x) exists and represents the long-run fraction of
customers whose delay in queue is no more than x. If the batch size distribution
is non-arithmetic, then lim n→∞ P {D n ≤ x} exists and equals W q (x).
Denote by
∞

∗ −sx
b (s) = e b(x) dx
0
the Laplace transform of the probability density b(x) of the service time of a
customer. Let β ∗ (s) be the Laplace transform of the probability density of the
SC
total time needed to serve all customers from one batch. It is left to the reader to
verify that
∞
k
∗
∗
∗
β SC (s) = β k [b (s)] = G(b (s)).
k=1
The following result now holds:
∗
∞ 1 − W ∗ (s)W (s)

r
e −sx {1 − W q (x)} dx = SC , (9.3.7)
0 s
where
∗
(1 − ρ)s 1 − G(b (s))
∗ ∗
W SC (s ) = and W (s) =
r
s − λ + λβ ∗ (s) β[1 − b (s)]
∗
SC
∞

with β = k=1 kβ k denoting the average batch size. The waiting-time probabili-
ties W q (x) can be numerically obtained from (9.3.7) by using numerical Laplace
inversion.
We give only a heuristic sketch of the proof of (9.3.7). A rigorous treatment
is given in Van Ommeren (1988). An essential part of the proof is the following
result. For k = 1, 2, . . . , let
η k = the long-run fraction of customers taking the kth position in their batch.
Then it holds that
∞
1
η k = β j , k = 1, 2, . . . . (9.3.8)
β
j=k