Omis
Lecture
9
Jessica
Gahtan
Waiting
Lines/Queuing
Theory
(Ch.
13.0 -‐13.6,
13.9-‐13.12)
Introduction
to
Queuing
Theory
• It
is
estimated
that
Americans
spend
a
total
of
37
billion
hours
a
year
waiting
in
lines.
• Places
we
wait
in
line...
-‐
Stores
-‐
hotels
-‐
post
offices
-‐
Banks
-‐
traffic
lights
-‐
restaurants
-‐
Airports
-‐
theme
parks
-‐
on
the
phone
• Waiting
lines
do
not
always
contain
people...
-‐ Returned
videos
-‐ Subassemblies
in
a
manufacturing
plant
-‐ Electronic
message
on
the
Internet
• Queuing
theory
deals
with
the
analysis
and
managem ent
of
waiting
lines.
Queuing
theory
useful
in
both
manufacturing
and
service
areas
Queuing
models
are
used
to:
– Describe
the
behavior
of
queuing
systems
– Determine
the
level
of
service
to
provide
– Evaluate
alternate
configurations
for
providing
service
Lines
in
Operations
Management
Assembly
lines
Production
lines
Trucks
waiting
to
unload
or
load
Workers
waiting
for
parts
Customers
waiting
for
products
Broken
equipment
waiting
to
be
fixed
Customers
waiting
for
service
Common
Queuing
Situations
Server-‐
does
transaction
Customers
–
those
things
that
are
lining
up
Characteristics
of
Waiting-‐Line
Systems
1. Arrivals
or
inputs
to
the
system
Page
1
Omis
Lecture
9
Jessica
Gahtan
Population
size,
behavior,
statistical
distribution
–
if
a
population
is
large
enough
can
treat
as
being
infinite
–
if
it’s
a
small
population
–
if
10/20
are
there,
chances
are
smaller
that
someone
else
might
show
up
2. Queue
discipline,
or
the
waiting
line
itself
Limited
or
unlimited
in
length,
discipline
of
people
or
items
in
it
–
if
limited
length
–
only
certain
number
of
things
can
come
in
–
i.e.
busy
signal
on
a
phone
if
no
free
lines
3. The
service
facility
Design,
statistical
distribution
of
service
times
Parts
of
a
Waiting
Line
–
anything
served
or
in
queue
(not
yet
served)
=
system
Arrival
Characteristics
1. Size
of
the
population
Unlimited
(infinite)
or
limited
(finite)
Example
of
Unlimited
Population:
Shoppers
arriving
at
a
supermarket
Example
of
Limited
Population:
5
fax
machines
-‐>
Each
fax
machine
is
a
potential
customer
(it
may
break
down
and
require
servic e)
2. Pattern
of
arrivals
Scheduled
Random
(the
occurrence
can
not
be
predicted)
• Arrival
rate
-‐
the
manner
in
which
customers
arrive
at
the
system
for
service.
Exponential
Distribution
-‐ t
Density:
f(t)
=
λe
Mean:
1/
λ
2
Variance:
1/
λ where
λ
is
the
arrival
rate
• Time
between
arrivals
is
often
modeled
using
an
exponential
distribution
• Why?
Exponential
distribution
has
a
memoryless
property
-‐
the
probability
distribution
on
the
time
until
the
next
arrival
does
not
depend
on
how
long
it
has
been
since
the
la st
arrival,
which
significantly
simplifies
the
analysis
of
a
waiting
line
system
Page
2
Omis
Lecture
9
Jessica
Gahtan
Exponential
and
Poisson
• If
interarrival
times
are
exponentially
distributed
with
parameter
λ,
then
number
of
arrivals
per
unit
time
follows
a
Poisson
distribution
with
paramet er
λt.
Poisson
Distribution
• The
number
of
arrivals
per
unit
of
time
can
be
estimated
by
a
distribution
known
as
the
Poisson
Distribution.
Example
What
is
the
probability
that
5
students
arrive
in
any
random
hour
to
register
in
a
course
when
the
averag e
arrival
rate
is
3
students
per
hour
and
interarrival
times
are
exponentially
distributed?
P(x)
=
?
x
=
number
of
arrivals
per
unit
of
time
=
5
λ
=
Average
arrival
rate
=
3
e
=
0.0498
3. Behaviour
of
Arrivals
• Most
queuing
models
assume
that
an
arriv ing
customer
is
a
patient
customer.
(Waits
in
the
queue
and
does
not
switch
lines)
• Life
is
complicated
by
the
fact
that
people
have
been
known
to
balk
or
to
renege.
Page
3
Omis
Lecture
9
Jessica
Gahtan
Balk
–
refuse
to
join
a
waiting
line
because
it
is
too
long
to
suit
their
needs.
–
Reduces
amount
you
serve
(when
line
gets
to
a
certain
length)
–
dissatisfied
cust
-‐
ignoring
Renege
–
enter
the
queue
but
then
become
inpatient
and
leave
the
line.
Waiting
Line
Characteristics
Limited
or
unlimited
queue
length
Small/limited
number
of
waiting
chai rs
in
a
doctor
clinic.
Even
though
many
queues
may
have
practical
limits,
if
the
limit
is
large
we
can
treat
the
queue
as
unlimited.
Queue
discipline
(order
of
service)
FIFO
(FCFS):
First
in,
first
out.
(First
come,
first
served).
This
is
the
most
common
assumption.
LIFO
(Last-‐in,
First-‐out)
RANDOM:
Select
arrival
to
serve
at
random
from
those
waiting.
PRIORITY:
Give
some
arrivals
priority
for
service.
Service
Characteristics
Service
Times
Service
time
-‐
the
amount
of
time
a
customer
spends
receiving
ser vice
(not
including
time
in
the
queue).
Service
time
distribution
Constant
service
time
-‐
Non-‐random
Automatic
car
wash
Industrial
robots
engaged
in
vehicle
assembly
Random:
Use
Negative
Exponential
probability
distribution.
Mean
service
rate
=
m
e.g:
4
customers/hr
Mean
service
time
=
1/m
e.g:
1/4
hour
=
15
minutes
Continuous
distribution:
Page
4
Omis
Lecture
9
Jessica
Gahtan
Negative
Exponential
Distribution
Queuing
system
designs
Channels
-‐
How
many
paths
are
there
through
the
system
–
AFTER
you
are
in
line?
Phases
-‐
How
many
stops
must
a
customer
make?
(Single
phase
means
only
one
stop
for
service.)
• Single-‐channel
system,
multiple-‐channel
system
• Single-‐phase
system,
multiphase
system
Page
5
Omis
Lecture
9
Jessica
Gahtan
Single-‐channel,
Single-‐phase
Single-‐channel,
Multiphase
phase
system
Page
6
Omis
Lecture
9
Jessica
Gahtan
Multi-‐channel,
single-‐phase
system
Multi-‐channel,
multiphase
system
Common
Queuing
System
Configurations
http://www.youtube.com/watch?v=74AhY5xKbqY
Page
7
Omis
Lecture
9
Jessica
Gahtan
Why
the
other
line
is
likely
to
move
faster ?
http://www.youtube.com/watch?v=F5Ri_HhziI0
Performance
of
Queuing
Systems
Measuring
Queue
Performance
Queuing
analysis
can
obtain
many
measures
of
a
waiting -‐line
system’s
performance.
1. Average
time
that
each
customer
or
object
spends
in
the
queue
2. Average
queue
length
3. Average
time
each
customer
spends
in
the
system
4. Average
number
of
customers
in
the
system
5. Probability
that
the
service
facility
will
be
idle
6. Utilization
factor
for
the
system
7. Probability
of
a
specific
number
of
customers
in
the
system
Operating
Characteristics
Typical
operating
characteristics
of
interest
include:
ρ
=U
Utilization
factor,
%
of
time
that
all
servers
are
busy.
P 0
e
percentage
of
the
time
there
are
no
customers/units
in
the
system
(Probability
of
idle
service
facility)
L -‐
Avg
number
of
units
in
line
waiting
for
service.
q
L=L s -‐
Avg
number
of
units
in
the
system
(in
line
&
being
served).
W q
-‐
Avg
time
a
unit
spends
in
line
waiting
for
service.
W=W s
-‐
Avg
time
a
unit
spends
in
the
system
(in
line
&
being
served).
P w
-‐
Prob.
that
an
arriving
unit
has
to
wait
for
service.
Page
8
Omis
Lecture
9
Jessica
Gahtan
P n
-‐
Prob.
of
n
units
in
the
system.
P
-‐
Probability
of
more
than
k
units
in
system
(Also,
fraction
of
time
there
are
more
than
k
units
in
n >
k
the
system)
Queuing
Costs
Operations
managers
must
recognize
the
trade -‐off
that
takes
place
between
two
costs:
1. The
cost
of
providing
good
service
2. The
cost
of
customer
or
machine
waiting
time.
-‐ Managers
want
queues
that
are
short
enough
so
that
customers
do
not
become
unhappy
and
either
leave
without
buying
or
buy
but
never
return.
-‐ However,
managers
may
be
willing
to
allow
some
waiti ng
if
it
is
balanced
by
a
significant
savings
service
costs.
Kendall
Notation
• Queuing
systems
are
described
by
3
parameters:
1/2/3
– Parameter
1
M
=
Markovian
interarrival
times
( Negative
exponential
distribution
(Poisson
arrivals))
D
=
Deterministic
interarrival
times
– Parameter
2
M
=
Markovian
service
times
G
=
General
service
times
D
=
Deterministic
(scheduled)
service
times
– Parameter
3:
A
number
Indicating
the
number
of
servers.
Labeled
as
S
Examples:
M/M/3
D/G/4
M/G/2
Page
9
Omis
Lecture
9
Jessica
Gahtan
Types
of
Queuing
Models
A
wide
variety
of
queuing
models
may
be
applied
in
operations
management.
We
will
focus
on
the
following
models:
Simple
(M/M/1)
[(M/M/S
)
when
#
of
servers=1]
Example:
Information
booth
at
the
mall
Multi-‐channel
(M/M/S)
[when
S>1]
Example:
Airline
ticket
counter
General
Service
(M/G/1)
Example:
Car
oil
change
Constant
Service
(M/D/1)
Example:
Automated
car
wash
Assumptions
in
the
Basic
Model
M/M/1
Customer
population
is
homogeneous
and
infinite
Queue
capacity
is
infinite
Customers
are
well
behaved
(no
balking
or
reneging)
Arrivals
are
served
FIFO
(FCFS)
Poisson
arrivals.
The
time
between
arrivals
follows
a
negative
exponential
distribution
Exponential
service
times:
Services
are
described
by
the
negative
exponential
distribution
Steady
State
Assumptions
Mean
arrival
rate
λ,
mean
service
rate
μ,
and
the
number
of
servers
are
constant.
The
service
rate
is
greater
than
the
arrival
rate.
You
should
always
check
this.
Consider
–
what
would
happen
if
this
were
not
the
case?
These
conditions
have
existed
for
a
long
time.
Simple
(M/M/1)
Model
Characteristics
• Type:
Single-‐channel,
single-‐phase
system
• Input
source:
Infinite;
no
balks,
no
reneging
• Arrival
distribution:
Poisson
• Queue:
Unlimited;
single
line
• Queue
discipline:
FIFO
• Service
distribution:
Negative
exponential
Page
10
Omis
Lecture
9
Jessica
Gahtan
Model
A
–
Single-‐Channel
(M/M/1)
Remember:
λ
&
µ
Are
Rates
λ=
Mean
number
of
arrivals
per
time
period
e.g.,
3
units/hour
μ
=
Mean
number
of
people
or
items
served
per
time
period
e.g.,
4
units/hour
1/
μ
=
15
minutes/unit
Page
11
Omis
Lecture
9
Jessica
Gahtan
Single
Channel
In
Class
Example
1
The
manager
of
a
video
store
is
interested
in
providing
good
service.
On
a
Friday
or
Saturday
night,
on
average
30
customers
per
hour
arrive
at
the
counter
to
check
out
a
video.
The
customers
are
served
at
an
average
rate
of
35
customers
per
hour
from
a
single
cash
register.
Time
between
arrivals
follows
an
exponential
distribution,
as
does
service
time.
Determine
the
operating
characteristics
for
the
video
store.
1. Average
number
of
customers
in
line
2. Average
number
of
customers
in
the
system
3. Average
wait
time
in
line
4. Average
time
in
the
system
5. Server
utilization
6. Probability
of
0
customers
are
in
the
system
7. Probability
that
more
than
6
customers
are
in
the
system
8. Probability
that
there
are
exactly
2
customers
in
the
system
The
Q.xls
Queuing
Template
• Formulas
for
the
operating
characteristics
of
a
number
of
qu euing
models
have
been
derived
analytically.
• An
Excel
template
called
Q.xls
implements
the
formulas
for
several
common
types
of
models.
• Q.xlsx
was
created
by
Professor
David
Ashley
of
the
Univ.
of
Missouri
at
Kansas
City.
In
Class
Example
1
–
Q.xls
Single
Channel
Example
The
Case:
customers
arriving
at
a
repair
shop
with
1
service
bay
Page
12
Omis
Lecture
9
Jessica
Gahtan
More
Less
