Queueing Review

(mostly from BCNN)

Christos Alexopoulos and Dave Goldsman

Georgia Institute of Technology, Atlanta, GA, USA

10/25/17

1 / 26
Outline

1 Introduction

2 Queueing Notation

3 Transient System Example

4 Steady-State Results
Little’s Law
M/G/1 System
Special Cases of M/G/1
M/M/c System
M/M/1/N System
M/M/c/N System
M/M/∞ System

2 / 26
 Introduction

Introduction

Goal: Review basics of Queueing Theory for very simple systems,

mostly in steady-state.

Interested in the usual system performance measures that we’ve

already discussed in earlier modules:
server utilization (% of time server is busy)
length of waiting lines
delays of customers

For simple queueing systems, these measures can be computed

analytically. But simulation is the method of choice for
more-complicated models.

3 / 26
 Introduction

Some Definitions
The calling population is the set of potential customers that will
arrive to the system. It is usually regarded as infinite. Sometimes
it’s finite, in which case the arrival rates of the customers may
depend on the current size.
The system capacity is the limit on the number of customers that
the system can contain. The system includes all servers and their
associated queues. This limit can be infinite or finite.
The arrival process can consist of scheduled arrivals (like a
doctor’s office) or random arrivals like a Poisson process or a
nonhomogeneous Poisson process.
Recall that the times between arrivals of a Poisson process are
i.i.d. exponential.
Arrivals can also occur in batches of either constant or random
size.
4 / 26
Introduction

Queue behavior describes possible customer actions while

waiting in line for service.
Balking — the customer leaves when he sees that the queue is too
long.
Reneging — the customer leaves when he feels that the line is
progressing too slowly.
Jockeying — the customer moves from line to line when he thinks
he can do better.
Queue discipline describes how customers are ordered in the
queue. Who gets served first?
FIFO — first-in-first-out.
LIFO — last-in-first-out.
SPT — shortest processing time.
Random order of service, service by priority class, etc., etc.

5 / 26
Introduction

Service times are usually modeled as i.i.d. something with mean

1/µ and variance σ 2 , but not necessarily exponential. A service
station can have multiple parallel servers of varying skills and
schedules.
For most of this module, we’ll only look at individual
queue/service stations, but of course these can be networked
together in arbitrary generality.
Students are encouraged to read up on open and closed Jackson
networks, which are simplified network structures for which
there are analytical results.
For the rest of this module, we assume that all queues are FIFO.

6 / 26
 Queueing Notation

Outline

1 Introduction

2 Queueing Notation

3 Transient System Example

4 Steady-State Results
Little’s Law
M/G/1 System
Special Cases of M/G/1
M/M/c System
M/M/1/N System
M/M/c/N System
M/M/∞ System

7 / 26
 Queueing Notation

Queueing Notation
A/B/c/N/K
A is the interarrival-time distribution.
B is the service-time distribution.
Common symbols for A and B
M = exponential (memoryless or Markov)
D = deterministic (constant)
Ek = Erlang of order k
G = general distribution with mean 1/µ and variance σ 2
c = the number of parallel servers.
N = system capacity (queue + server)
K = size of calling population

Example: M/M/1 = M/M/1/∞/∞

8 / 26
Queueing Notation

Pn (t) = probability of n customers in system at time t.

Pn = limt→∞ Pn (t) = steady-state probability of n customers.

λ = arrival rate

µ = service rate, and 1/µ = mean arrival time

ρ = server utilization = traffic intensity = % time server is busy.

In = interarrival time between customers n − 1 and n

An = arrival time of customer n.

Sn = service time of customer n.

9 / 26
Queueing Notation

Wn = cycle time = time in system (Q + server) of customer n.

WnQ = waiting time in queue of customer n.

L(t) = number of customers in system at time t.

LQ (t) = number of customers in queue at time t.

Steady-State Stuff:
w = limn→∞ E[Wn ], wQ = limn→∞ E[WnQ ]

L = limt→∞ E[L(t)], LQ = limt→∞ E[LQ (t)]

L(∞) = steady-state number of customers in the system (this is a

random variable, not an expected value)

10 / 26
 Transient System Example

Outline

1 Introduction

2 Queueing Notation

3 Transient System Example

4 Steady-State Results
Little’s Law
M/G/1 System
Special Cases of M/G/1
M/M/c System
M/M/1/N System
M/M/c/N System
M/M/∞ System

11 / 26
 Transient System Example

Transient System Example

Most of what we’ll talk about in the remainder of this module
concerns steady-state analysis, but for some simple models, it is
possible to undertake exact transient analysis (in addition to the
hand-simulation analysis that we worked on in earlier modules).

Example: M/M/1/1 system in which an arriving customer will leave

if he sees someone already in service. It can be shown (after solving
certain differential equations) that
 
µ µ
P0 (t) = + P0 (0) − e−(λ+µ)t ,
λ+µ λ+µ
and P1 (t) = 1 − P0 (t), where P0 (0) is an initial condition and where
the last term disappears as t → ∞. Thus, in steady-state, we have
µ λ
P0 = and P1 = .
λ+µ λ+µ
12 / 26
 Steady-State Results

Outline

1 Introduction

2 Queueing Notation

3 Transient System Example

4 Steady-State Results
Little’s Law
M/G/1 System
Special Cases of M/G/1
M/M/c System
M/M/1/N System
M/M/c/N System
M/M/∞ System

13 / 26
Steady-State Results
Little’s Law

Little’s Law (also known as the Conservation Equation) is

L = λw or LQ = λwQ ,
so that the long-run average number of customers equals the product
of the arrival rate and the long-run average time in system. If you let
a = λ, you have the amazing form L = aw.

“Proof”: Suppose N customers go through the system during time

interval [0, T ]. Then the obvious estimator for L (from our hand
simulation module) is
N
1 T N 1 T
Z Z
N 1 X
L̂ = L(t) dt = L(t) dt = Wi ,
T 0 T N 0 T N
i=1
RT PN
since both 0 L(t) dt and i=1 Wi = total time in system.
PN
As T → ∞, we have L̂ → L, N/T → λ, and i=1 Wi /N → w. 2
14 / 26
Steady-State Results
M/G/1 System

M/G/1: Here we have i.i.d. service times from some general

distribution with mean 1/µ and variance σ 2 .

The traffic intensity ρ = λ/µ, and we will assume that ρ < 1, so that
the queue is stable. Then the Pollaczek-Khintchine Equation gives

ρ = λ/µ
ρ2 (1 + σ 2 µ2 )
L = ρ+
2(1 − ρ)
LQ = L − ρ (obvious)
w = L/λ (Little)
1
wQ = LQ /λ = w −
µ
P0 = 1 − ρ

Remark: The M/G/1 is actually easier to analyze than the G/M/1.

15 / 26
Steady-State Results
M/G/1 System

Example: Arrivals occur as a Poisson process with λ = 1.5/hour.

The service rate is µ = 2/hr, and the variance of the i.i.d. service
times is σ 2 = (1/9) hr2 .

Then ρ = 1.5/2 = 0.75, so the queue is stable.

The steady-state probability that the server is idle is

P0 = 1 − ρ = 0.25.

The steady-state average number of customers in the system is

9 4


ρ2 (1 + σ 2 µ2 ) 3 1 +
L = ρ+ = + 16 9
= 2.375,
2(1 − ρ) 4 2/4

and (try this at home) the avg wait in queue is wQ = 1.08 hours. 2

16 / 26
Steady-State Results
Special Cases of M/G/1

M/M/1: This is a special case of the M/G/1 with Exp(µ) services

so that the mean is still 1/µ, while σ 2 = 1/µ2 .

Plugging these into the P-K Equation and simplifying gives

ρ
L =
1−ρ
ρ2
LQ = L − ρ −
1−ρ
1
w = L/λ =
µ(1 − ρ)
ρ
wQ = LQ /λ =
µ(1 − ρ)
Pn = (1 − ρ)ρn ,

where the result for Pn is a bonus because the M/M/1 is so simple.

17 / 26
Steady-State Results
Special Cases of M/G/1

Example: Arrivals occur at a one-man barbershop as a Poisson

process with λ = 2/hour.

The services are i.i.d. Exp(µ = 3/hr).

Then ρ = 2/3 = 0.75.

The steady-state probability of n customers in the system is

Pn = 13 ( 23 )n , n = 0, 1, . . ..

So the s-s P (barber is idle) = P0 = 1/3.

P3
Moreover, P (at least 4 guys in the shop) = 1 − n=0 Pn = 16/81.

The steady-state average number of customers in the system is

ρ
L = = 2. 2
1−ρ
18 / 26
Steady-State Results
Special Cases of M/G/1

M/D/1: This is a special case of the M/G/1 with mean service time
1/µ and σ 2 = 0. Then we have

ρ2 L LQ
L = ρ+ , LQ = L − ρ, w = , wQ =
2(1 − ρ) λ λ

Remark: Less variability in the M/D/1 compared to the M/M/1

makes for better performance. For instance, for a given λ and µ, the
M/D/1’s value of L is < the M/M/1’s.

Proof: Need to show that

ρ2 ρ
ρ+ < ,
2(1 − ρ) 1−ρ

which easily follows after a little algebra. 2

19 / 26
Steady-State Results
Special Cases of M/G/1

M/Ek /1: This is another special case of the M/G/1. Let’s suppose
Ek ∼ Erlangk (ν) denotes the sum of k i.i.d. Exp(ν) random
variables. Then the mean service time is
1 k
= E[Ek ] = ,
µ ν
and the variance is
k
σ 2 = Var(Ek ) = .
ν2
Note that ρ = λ/µ = λk/ν. Then

1 + k ρ2 L LQ
L = ρ+ , LQ = L − ρ, w = , wQ =
2k 1 − ρ λ λ

20 / 26
Steady-State Results
M/M/c System

M/M/c: Multiple servers with exponential interarrivals and services.

P-K doesn’t apply here, so tables get a little messy, but not too bad.
ρ = λ/(cµ)
c−1 −1
(cρ)i (cρ)c
X  
P0 = +
i! (c!)(1 − ρ)
i=0
(cρ)c P0
P (L(∞) ≥ c) =
(c!)(1 − ρ)
(cρ)c+1 P0
L = cρ +
c(c!)(1 − ρ)2
(cρ)c+1 P0
LQ = L − cρ =
c(c!)(1 − ρ)2
w = L/λ
1
wQ = LQ /λ = w −
µ
21 / 26
Steady-State Results
M/M/c System

Example: Suppose we have a Poisson arrival process with λ = 5/hr

who go to a station with c = 2 parallel servers, who can provide
services that are i.i.d. Exponential at the rate of 5 per hour. What’s the
steady-state expected number of customers that will be in the queue?

This is an M/M/2 with λ = 5 and µ = 5. Here ρ = λ/(2µ) = 0.5,

and the queueing table (with c = 2) gives
(" 1 # )−1
X1
P0 = +1 = 1/3.
i!
i=0

Then
(cρ)c+1 P0
LQ = L − cρ = = 1/3. 2
c(c!)(1 − ρ)2

22 / 26
Steady-State Results
M/M/1/N System

M/M/1/N : P-K doesn’t apply, since now we only have finite

capacity. Just believe the table abstracted from BCNN, where we use
a = λ/µ and define λe as the effective arrival rate, i.e., the rate of
arrivals who enter and remain in the system. Of course, λe ≤ λ.
(1−a)an
(
1−aN +1
if λ 6= µ
Pn = , n = 0, 1, 2, . . . , N
1/(N + 1) if λ = µ
λe = λ(1 − PN ) = µ(1 − P0 ) = µe
ρ = λe /µ = 1 − P0
( a[1−(N +1)aN +N aN +1 ]
(1−aN +1 )(1−a)
if λ 6= µ
L =
N/2 if λ = µ
1
w = L/λe , wQ = w −
µ
LQ = λe wQ = L − (1 − P0 )

23 / 26
Steady-State Results
M/M/1/N System

Example: Suppose we’re dealing with a single-server queueing

system in which the arrivals are Poisson with a mean of 12 minutes,
and the services are exponential with rate 10 per hour. Suppose that
the system can only hold 4 customers (in line + being served). Find
the expected number of customers in line.

This is an M/M/1/4 with a = λ/µ = 5/10. Then from the table,

1−a
P0 = = 0.516,
1 − a5
and
a[1 − 5a4 + 4a5 ]
L = = 0.839,
(1 − a5 )(1 − a)
so that LQ = L − (1 − P0 ) = 0.355. 2

24 / 26
Steady-State Results
M/M/c/N System

M/M/c/N : Use a = λ/µ and define λe as the effective arrival rate.

ρ = λ/(cµ)
c N
an ac X n−c −1
 X 
P0 = 1 + + ρ
n! c!
n=1 n=c+1
N
a P0
PN =
c!cN −c
ac ρP0
 
LQ = 1 − ρN −c − (N − c)ρN −c (1 − ρ)
c!(1 − ρ)2
λe = λ(1 − PN )
wQ = LQ /λe
1
w = wQ +
µ
L = λe w

25 / 26
Steady-State Results
M/M/∞ System

M/M/∞: Think of this as a self-service system.

L = λ/µ
LQ = 0
w = 1/µ
wQ = 0
e−λ/µ (λ/µ)n
Pn = , n = 0, 1, 2, . . .
n!


Remark: Note the Poisson probabilities, Pn = P Pois(λ/µ) = n .

Remark: By the way, you might want to go to BCNN’s website

[Link] to take a look at their [Link]. Lots of
good stuff there.

26 / 26