Page 357 - A First Course In Stochastic Models

352 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

However, such approximations should not be used blindly. Numerical experiments
indicate that the waiting-time probabilities are rather insensitive to more than the
first two moments of the service time S provided that the squared coefficient of
2
2
variation c is not too large (say, 0 ≤ c ≤ 2) and the service-time density satisfies
S S
a reasonable shape constraint. The sensitivity becomes less and less manifest when
the traffic intensity ρ gets closer to 1.
The motivation for the two-moment approximation is provided by the Pollaczek–
Khintchine formula for the average delay in queue. The expression (9.2.10) for W q
can be written as
1 2 E(S)
W q = (1 + c ) , (9.2.20)
S
2 1 − ρ
2
2
2
where c = σ (S)/E (S). Denote by W q (exp) and W q (det) the average delay
S
2
in queue for the special cases of exponential services (c = 1) and deterministic
S
2
services (c = 0). The formula (9.2.20) is equivalent to the representations
S
1 2
W q = (1 + c )W q (exp), (9.2.21)
S
2
and
2
2
W q = (1 − c )W q (det) + c W q (exp). (9.2.22)
S
S
A natural question is whether the representations (9.2.21) and (9.2.22) can be
used as a basis for approximations to the waiting-time probabilities. Numerical
investigations reveal that the waiting-time probabilities themselves do not allow for
two-moment approximations of the forms (9.2.21) and (9.2.22), but the waiting-
time percentiles do allow for such two-moment approximations. The pth percentile
ξ(p) of the waiting-time distribution function W q (x) is defined as the solution to
W q (x) = p. In statistical equilibrium the percentage of customers having a delay
in queue no more than ξ(p) is 100p%. Since W q (0) = 1 − ρ, the percentile ξ(p)
is only defined for 1 − ρ ≤ p < 1. Denote by ξ exp (p) and ξ det (p) the percentile
ξ(p) for the cases of exponential services and deterministic services with the same
means E(S). The representation (9.2.21) suggests the first-order approximation
1 2
ξ app1 (p) = (1 + c )ξ exp (p), (9.2.23)
S
2
while the representation (9.2.22) suggests the second-order approximation
2
2
ξ app2 (p) = (1 − c )ξ det (p) + c ξ exp (p). (9.2.24)
S S
In Section 5.1 it was shown that 1 − W q (x) = ρ exp [−µ(1 − ρ)x] for all x ≥ 0
when the service time has an exponential distribution with mean 1/µ = E(S).
Hence ξ exp (p) is simply computed as ξ exp (p) = E(S) ln[ρ/(1 − p)]/(1 − ρ).
A relatively simple algorithm for the computation of ξ det (p) is given in
Section 9.6.2 in the more general context of the M/D/c queue. For higher values