Page 67 - A First Course In Stochastic Models

58 RENEWAL-REWARD PROCESSES

To conclude this section, we use the PASTA property to derive in a heuristic
way one of the most famous formulas from queueing theory.

2.5 THE POLLACZEK–KHINTCHINE FORMULA
Suppose customers arrive at a service facility according to a Poisson process with
rate λ. The service times of the customers are independent random variables having
2
a common probability distribution with finite first two moments E(S) and E(S ).
There is a single server and ample waiting room for arriving customers finding the
server busy. Each customer waits until service is provided. The server can handle
only one customer at a time. This particular queueing model is abbreviated as the
M/G/1 queue; see Kendall’s notation in Section 9.1. The offered load ρ is defined
by

ρ = λE(S)
and it is assumed that ρ < 1. By Little’s formula (2.3.5) the load factor ρ can be
interpreted as the long-run fraction of time the server is busy. Important perfor-
mance measures are

L q = the long-run average number of customers waiting in queue,
W q = the long-run average time spent per customer in queue.

The Pollaczek–Khintchine formula states that
2
λE(S )
W q = . (2.5.1)
2(1 − ρ)
This formula also implies an explicit expression for L q by Little’s formula

L q = λW q ; (2.5.2)
see Section 2.3. The Pollaczek–Khintchine formula gives not only an explicit
expression for W q , but more importantly it gives useful qualitative insights as
well. It shows that the average delay per customer in the M/G/1 queue uses
the service-time distribution only through its first two moments. Denoting by
2
2
2
c = σ (S)/E (S) the squared coefficient of variation of the service time and
S
using the relation (2.1.10), we can write the Pollaczek–Khintchine formula in the
more insightful form
1 2 ρE(S)
W q = (1 + c ) . (2.5.3)
S
2 1 − ρ
Hence the Pollaczek–Khintchine formula shows that the average delay per cus-
2
tomer decreases according to the factor 1 (1 + c ) when the variability in the
2 S
service is reduced while the average arrival rate and the mean service time are kept