Page 387 - A First Course In Stochastic Models

382 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

(a) There are at least kc customers waiting in queue just after the epoch at which
the customer with label n − kc enters service. Then the customer with label
n must be among those waiting customers and its waiting time in queue is
D + (k − 1)D which is larger than x.
(b) There are i ≤ kc − 1 customers waiting in queue just after the epoch at
which the customer with label n−kc enters service. Denote this epoch by S .
∗
Since the customer with label n is the (kc)th customer to enter service after
epoch S , the customer with label n is not yet present at epoch S and is the
∗
∗
(kc − i)th customer to arrive after epoch S . Suppose that the customer with
∗
label n arrives at epoch S +y. Distinguish between the two cases y < kD−x
∗
and y ≥ kD − x.
(b1) y < kD−x. Since y < kD−x ≤ kD−(k−1)D = D the customer with label
n arrives during the service time of the customer with label n − kc. Thus the
waiting time in queue of the customer with label n equals D − y + (k − 1)D,
which is larger than x.
(b2) y ≥ kD − x. The amount of time that the customer with label n spends
in queue during the service time of the customer with label n − kc equals
max(D − y, 0). The customer with label n is the kth customer to be served
by the marked server after the customer with label n − kc. Hence
W n ≤ max(D − y, 0) + (k − 1)D
≤ max(D − (kD − x), 0) + (k − 1)D

= x − (k − 1)D + (k − 1)D = x.

Denote now by S j the epoch at which the customer with label j enters service
and let L + be the number of customers waiting in queue just after epoch S j ,
j
j = 1, 2, . . . . Under the condition that L + = i with i ≤ kc − 1 the customer
n−kc
with label n will be the (kc − i)th customer to arrive after epoch S n−kc . Denote by
A n the number of arrivals during the interval [S n−kc , S n−kc +kD −x]. The random
variable A n is Poisson distributed with mean λ(kD − x). The above arguments
show that
W n ≤ x if and only if L + ≤ kc − 1 and A n ≤ kc − 1 − L + .
n−kc n−kc
This leads to
kc−1 kc−1−i ℓ
−λ(kD−x) [λ(kD − x)]
P (W n ≤ x) = P (L + = i) e .
n−kc ℓ!
i=0 ℓ=0
For fixed x and k, we now let n → ∞. This gives
kc−1 kc−1−i ℓ
−λ(kD−x) [λ(kD − x)]
W q (x) = q i e , (9.6.10)
ℓ!
i=0 ℓ=0