Queueing Theory

Basic Queuing Relationships

Resident
items

Waiting
items

Residence
time

Single server
Little’s formulae are
Utilisation
the most important
equation in queuing
theory
System
Utilisation

1
M/G/1 … M/M/1 … M/D/1

2
Single server – queue size as function of σ

3
Single server – residency time as function of
σ

4
M/M/N Analysis

5
M/M/N Analysis

6
 Variability
• Definition: Variability is anything that causes the system
to depart from regular, predictable behavior.

• Sources of Variability:
– setups － workpace variation
– machine failures － differential skill levels
– materials shortages － engineering change orders
– yield loss － customer orders
– rework － product differentiation
– operator unavailability － material handling

7
 Measuring Process Variability

t = mean
σ = standard deviation

σ
c = = coefficient of variation, CV
t

σ 2
c = 2 = squared coefficient of variation, SCV
2

t
8
 Kendall's Classification
Characterization of a queueing station
A/B/m/b B
A: arrival process A
B: service process
m: number of machines
b: maximum number of jobs Queue m
that can be in the system Server

M: exponential (Markovian) distribution

G: completely general distribution
D: constant (deterministic) distribution.

9
 Queueing Parameters
ra = the rate of arrivals in customers (jobs) per unit time
ta = 1/ra = the average time between arrivals.
ca = the CV of inter-arrival times.
m = the number of machines.
b = buffer size (i.e., maximum number of jobs allowed in system.)
te = mean effective process time.
re = the rate of the station in jobs per unit time = m/te.
ce = the CV of effective process times.
u = utilization of station = ra/re.

10
 Queueing Measures
• Measures:
Tq = the expected waiting time spent in queue.
T = the expected time spent at the process center, i.e., queue
time plus process time.
N = the average jobs at the station.
Nq = the expected jobs in queue.
• Relationships:
T = Tq + te
N = ra × T
Nq = ra × Tq
• Result: If we know Tq, we can compute N, Nq, T.

11
 The G/G/1 Queue
• Formula:
⎛ ca2 + ce2 ⎞ ⎛ u ⎞ ⎛ ca2 + ce2 ⎞
Tq ≈ ⎜⎜ ⎟⎟ ⎜ ⎟ te = ⎜⎜ ⎟⎟ Tq ( M/M/ 1)
⎝ 2 ⎠ ⎝1− u ⎠ ⎝ 2 ⎠
V U T

• Observations:
– Refer to as Kingman’s equation or VUT equation.
– Separate terms for variability, utilization, process time.
– Tq (and other measures) increase with ca2 and ce2 .
– Variability causes congestion!

12
 The M/M/m Queue
• Systems with multiple machines in parallel.
• All jobs wait in a single queue for the next
available machine.
2 ( m +1) −1
u
Tq ( M/M/m) ≈ te
m(1 − u )

13
 The G/G/m Queue
• Formula:
⎛ ca2 + ce2 ⎞ ⎛⎜ u 2( m +1) −1 ⎞⎟ ⎛ ca2 + ce2 ⎞
Tq ≈ ⎜⎜ ⎟⎟ te = ⎜⎜ ⎟⎟ Tq ( M/M/m)
⎝ ⎠⎝⎜ m − u ⎟
2 (1 ) ⎠ ⎝ 2 ⎠
V U T
• Observations:
– Useful model of multi-machine workstations
– Extremely general.
– Fast and accurate.
– Easily implemented in a spreadsheet (or packages).

14
 Effects of Blocking
• VUT Equation:
– characterizes stations with infinite space for queueing
– useful for seeing what will happen to N, T without
restrictions
• But real world systems often constrain N:
– physical constraints
– logical constraints
• Blocking Models:
– estimate N and ra for given set of rates, buffer sizes
– much more complex than non-blocking (open) models, often
require simulation to evaluate realistic systems

15
 The M/M/1/b Queue

B buffer spaces

u (b + 1)u b +1 Goes to u/(1－u) as b → ∞

N ( M/M/ 1/b) = −
1− u 1 − u b +1 Always less than N(M/M/1)
1− ub
Thoughput ( M/M/ 1/b) = r
b +1 a Goes to r as b → ∞
1− u a
Always less than Throughput(M/M/1)
N ( M/M/ 1/b) Little’s law
T ( M/M/ 1/b) =
Throughput ( M/M/ 1/b)
16
 Variability Pooling
• Variability pooling: combine multiple sources of
variability.
• Basic idea: the CV of a sum of independent random
variables decreases with the number of random
variables.
• Example:
– Batch processing
– Safety stock aggregation
– Queue sharing

17
 Conclusions
• Variability is a fact of life.
• There are many sources of variability in manufacturing
systems.
• The coefficient of variation is a key measure of item
variability.
• Variability propagates.
• Waiting time is frequently the largest component of the
total time in the system.
• Limiting buffers reduces total time in the system at the
cost of decreasing throughput.
• Variability pooling reduces the effect of variability.
18