SOFTWARE OPTIMIZATION TECHNIQUES - Software Design for Six-Sigma: A Roadmap for Excellence - page 452

17.3.5 Queuing Theory

Queuing theory is the study of waiting lines and analyzes several related processes,
including arriving at the queue, waiting in the queue, and being served by the server at
the front of the queue. 26 Queuing theory calculates performance measures including
the average waiting time in the queue or the system, the expected number waiting
or receiving service, and the probability of encountering the system in certain states,
such as empty, full, having an available server, or having to wait a certain time to
be served. Some different types of queuing theories include first-in-first out, last-
in-first-out, processor sharing, and priority.
A queuing model can be characterized by several different factors. Some of them
are: the arrival process of customers, the behavior of customers, the service times,
the service discipline, and the service capacity (Adan & Resing, 2002). Kendall
introduced a shorthand notation to characterize a range of queuing models, that is, a
three-part code a

c. The first letter specifies the interarrival time distribution,
and the second one specifies the service time distribution. For example, for a general
distribution, the letter G is used, M is used for the exponential distribution (M stands
for memoryless), and D is used for the deterministic times. The third letter specifies
the number of servers. Some examples are M

= b =

= M = 1, M = M = c, M = G = 1,

G 1. This notation can be extended with an extra letter to

cover other types of models as well.
One of the simplest queuing models is the M/M/1 model, which is the single-
server model. Letting

= M = 1, and M = D =

ρ = λ / µ , the average number of customers in a queue can be

calculated by:

ρ

N

= (17.1)

1 − ρ

Although the system's variance can be calculated by the following:

ρ

2
N

σ = (17.2)

(1 − ρ ) 2

The expected number of requests in the server is:

N S = λ

x = ρ

(17.3)

The expected number of requests in the queue 27

is

ρ

2

N Q =

(17.4)

− ρ

1

26 http://en.wikipedia.org/wiki/Queuing theory
27 http://en.wikipedia.org/wiki/M/M/1 model