Page 381 - A First Course In Stochastic Models

376 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

D n = the delay in queue of the nth customer,
S n = the service time of the nth customer,
A n = the interarrival time between the nth and (n + 1)th customers.

For ease, let us assume that the service times and interarrival times have probability
densities b(t) and a(t). In the same way as in Section 8.4, we obtain

D n+1 = max(0, D n + U n ), n = 1, 2, . . . , (9.5.17)
where U n = S n −A n . Using this recurrence equation, it is not difficult to show that
the waiting-time distribution function W q (x) satisfies the so-called Lindley integral
equation

x
W q (x) = W q (x − t)c(t) dt, x ≥ 0, (9.5.18)
−∞
where c(t) is the probability density of the U n . Note that c(t) is the convolution
of a(−t) and b(t). A discretized version of Lindley’s integral equation can be
effectively solved by using the discrete FFT method. The details will not be given
here, but can be found in Ackroyd (1980) and Tran-Gia (1986). In De Kok (1989)
a moment-approximation method is suggested to solve Lindley’s integral equation.
This method is generally applicable and yields good approximations to the waiting-
time probabilities. In particular, the moment-approximation method is well suited
for both the GI/D/1 queue and the D/G/1 queue.

KLB approximation

Using a hybrid combination of basic queueing results and experimental analysis,
the following two-moment approximations for the delay probability and the aver-
age delay in queue per customer were obtained by Kr¨ amer and Langenbach-Belz
(1976):

1 + c + ρc
 2 2
 A S 2
 if c ≤ 1,
 2 2 2 2 A
 1 + ρ(c − 1) + ρ (4c + c )
2
P KLB = ρ + (c − 1)ρ(1 − ρ) × S A S
delay A
4ρ

 2
 if c > 1,
 2 2 2 2 A
c + ρ (4c + c )
A A S
 2 2
−2(1 − ρ)(1 − c )
 A 2
exp if c ≤ 1,


2
2
 3ρ(c + c ) A
ρE(S)  A S
KLB 2 2
W = (c + c ) ×
q A S
2(1 − ρ)  2
A
 −(1 − ρ)(c − 1) 2
exp if c > 1.


A
c + 4c
 2 2
A S