Transcript C + K

An Optimal Design of the
M/M/C/K Queue for Call Centers
William A. Massey
Department of Operations Research
and Financial Engineering,
Princeton University
[email protected]
1
Acknowledgements
This is joint work with Rodney B. Wallace of IBM and
George Washington University.
Related paper to appear in QUESTA.
2
Telephone Call Centers
3
Our Research Goal
We have a call center manager who serves a given
customer base. The average calling rate and times
in service are known for these customers. Moreover,
they expect a specific level of service performance.
Our goal is to develop formulas and algorithms to
assist the manager in finding the minimal number of
call agents and telephone lines needed to provide
a given service level target.
4
Call Centers with Instant Answering:
The M/M/∞ Queueing Model
1
l
2
m Q∞
i
i
i
∞
We have a Poisson arrival rate l, mean service time
1/m, as well as an infinite number of call center agents
5
and telephone lines.
Steady State Properties of Q∞
• Setting r = l/m, the number of customers in the
system Q∞ has the Poisson distribution
r
e r
P(Q = n) =
.
n!
n
• The mean number of customers in the system Q∞
equals its variance and is called the mean offered
load or the mean number of requested call agents.
E[Q ] = Var[Q ] = r.
6
Call Centers with “Music” (Delays):
The M/M/C/∞ Queueing Model
1
l
∞
2
iii
2 1
m min(QC/ ∞, C)
i
i
i
C
We have a Poisson arrival rate l, mean service time
1/m, C call center agents and an infinite number of
7
telephone lines.
Steady State Properties of QC/∞
Let the random variable DC / ∞ be the delay for the
customer arriving to the M/M/C/∞ queue in steadystate, which holds if and only if r < C (i.e. the mean
number of requested call agents is less than the
number of available call agents). We define the
probability of delay to be
 C ( r )  P( DC /   0) = P(QC /   C ).
This is called the Erlang C-Formula.
8
Applications of the
Erlang C-Formula
• It can be shown that the probability of the delay
exceeding t is
 C /  ( r , m , t )  P( DC /   t ) =  C ( r )e
 ( C  r ) mt
.
• The mean queue length and delay are
r   C (r )
 C (r )
E[QC /  ] = r 
and E[ DC /  ] =
.
Cr
(C  r ) m
9
How to Compute the
Erlang C-Formula
C  C ( r )
 C (r ) =
C  r  r  C ( r )
where r < C and C(r) is the Erlang B formula,
which solves the recursion relation
r  C 1 ( r )
C ( r ) =
, where  0 ( r ) = 1.
C  r  C 1 ( r )
10
Call Centers with Music and
Busy Signals: The M/M/C/K Queue
1
l 1{Q
C/K < C+K}
2
K
iii
2 1
m min(QC/K, C)
i
i
i
C
We have a Poisson arrival rate l, mean service time
1/m, C call center agents, and C + K telephone lines.
11
The M/M/C/K Design Problem
l
m
e
d
The Design
Problem
(C,K) = ?
t
Given: l = customer calling rate,1/m = conversation
time, e = blocking probability, t = delay threshold,
d = conditional delay probability for exceeding t.
Find: The minimal number of agents C and phone
lines C+K needed for the e, d and t requirements. 12
Ad-Hoc Erlang Design Solution
1. Let the effective arrival rate be l*=l(1-e).
2. Using an arrival rate l* and a service rate m, find
the smallest C such that P(DC / ∞ > t) < d.
3. Compute E[DC / ∞].
4. Let the effective service time be 1/m*=1/m+ E[DC / ∞].
5. Using an arrival rate l and a service rate m*, find
the smallest L such that P(QL / 0 = L) < e.
6. Now let K = (L-C)+.
Now we replace this ad-hoc method with two
13
new approaches (exact and asymptotic).
Performance Variables
QC/K = random number of customers in the M/M/C/K
system in steady-state. This is also called the carried
load or the number of customers that gain access to
a call agent.
DC/K = random conditional delay for the M/M/C/K
queue in steady-state.
14
Performance Measures
C/K(r) = P(QC/K = C+K)
= blocking probability (call center availability).
C/K(r,m,t) = P( DC/K>t | QC/K < C+K ).
= conditional probability of delay exceeding t
(speed to answer).
C/K(r) = P( DC/K>0 | QC/K < C+K )
= conditional delay probability.
15
M/M/C/K Steady State Results
C ( r )  ( r / C ) K  (C  r )
C / K ( r ) =
,
K
C  r  C ( r )  (1  ( r / C ) )  r
C ( r )  (1  ( r / C ) K )  C
 C / K (r ) =
,
K 1
C  r  C ( r )  (1  ( r / C ) )  r
K 1
 C / K (r , m, t) =  C / K (r )  
i =0
1 ( r C )
K i
1 (r / C)
K

e
C m t
( rm t )
,
i!
i
and L’Hopital’s rule applies when r = C.
16
Blocking Probability Limit
It follows from our blocking probability formula that
lim C / K ( r ) = (1  C / r )

K 
and this is a decreasing limit.
Hence for all 0<e<1, we can say that C/K(r) < e
holds for some finite K if and only if r (1e) < C.
17
Delay and Blocking Monotonicity
Properties for (C,K)
If C1 < C2 and C1 + K1 < C2 + K2 , then
C / K ( r )  C
1
1
2 / K2
(r )
so the blocking probability for the first system is larger.
If C1 < C2 and C1 + K1 > C2 + K2 , then
 C / K (r, m, t)   C
1
1
2 / K2
(r , m, t)
and the delay for the first system is larger.
18
Defining a Minimal (C,K) Pair
The cost of an additional telephone line is insignificant
compared to the cost of an additional call agent. We
then define the pair (C1,K1) to be “smaller than” the
pair (C2,K2) if C1 < C2 or we have C1 = C2 and K1 < K2.
19
Exact Search Design Algorithm
K
Delay > d or
C < r(1e)
Region
3. First (C,K) Pair with
Blocking < e (and Delay < d?).
Smaller Blocking
Larger Delay
2. Last (C,K) Pair with
Delay < d and r(1e) < C.
0. Blocking=1
and Delay=0.
Blocking > e
Region
Smaller Blocking
Larger Blocking
Larger Delay
1. First (C,0) Pair with
Blocking < e and Delay = 0.
C
20
Square Root Rule of Thumb
for the M/M/C/K Design Problem
For instant answering (infinite number of agents), the
number of customers in the system has a Poisson
distribution with mean and variance equal to r.
The optimal number of agents required should be close to
the mean number in this system plus some constant x
times its standard deviation, which is C = r + x √r.
A well-designed system should only have people waiting as
an exceptional case so the amount of waiting spaces
should equal the standard deviation of this system times
some constant y or K = y √r.
21
Asymptotic Behavior of the
Erlang B-Formula
Taking the limit as the mean offered load becomes
large, while using the square root rule of thumb, we
have
lim r   r  x r ( r ) =
r 
 ( x)
( x)
,
where
1 x
 ( x) =
e
2
2
/2
and
1
 ( x) =
2
x
e
 y2 / 2
dy.

22
Defining the Special Function y
If we define the function y(y) for all positive y to be
 (y ( y ))
= y,
(y ( y ))
then it is the unique solution to the differential equation
1
y ( y) =
y( y y ( y ))
and y ( 2 /  ) = 0.
23
Blocking Asymptotics
We can show that
lim ρ   ρ  x
r 
ρ y
ˆ ( x, y ),
(
r
)
=

ρ
where
ˆ ( x, y ) =
xe  ( x) /  ( x)
,
 xy
x  (1  e ) ( x) /  ( x)
 xy
and setting x = y (z) gives us
ˆ (y ( z ), y ) =
y ( z )e y ( z ) y z
y ( z )  (1  e
y ( z ) y
)z
.
24
Asymptotic Blocking Level Curve
The (x,y) pairs where
ˆ ( x, y ) = e r
can be parameterized by
x = y ( z)
when y (z) > 0, and
(
)  .
 z  y ( z)  e r
1
y=
log 
 e r (y ( z )  z )
y ( z)



25
Delay Asymptotics
We can show that
lim  ρ  x
r 
ρ y ρ
( r , m
)
ρ = ˆ ( x, y, m ),
where
(e  xm  e  xy )   ( x) / ( x)
ˆ ( x, y, m ) =
,
 xy
x  (1  e ) ( x) / ( x)
and setting x = y (z) gives us
y ( z ) m
y ( z ) y 
e
) z
ˆ (y ( z ), y, m ) =
.
y ( z ) y
y ( z )  (1  e
)z
(e
26
Asymptotic Optimal
Design Solution
Find x and y such that
ˆ ( x, y) = e ρ and ˆ( x, y, m t ρ ) = d .
Using the blocking level curve, this problem
reduces to solving a fixed point equation for
some z
d y ( z )  e ρ )  (y ( z )  z )
(
z=
.
e
 (y ( z )  e ρ )
y ( z ) m t ρ
27
Numerical Design Comparisons
Let 1/m = 10.0 minutes, t = 0.5 minutes, e = 0.001 and d = 0.2.
28
Design Performance Comparisons
Let 1/m = 10.0 minutes, t = 0.5 minutes, e = 0.001 and d = 0.2.
29
Summary of Numerical Results
• All three methods do a good job in estimating the
number of call agents C.
• The ad-hoc method performs worst in estimating the
number of additional telephone lines K.
• As a result, ad-hoc performs worst in reaching the target
blocking level and can be off by a factor from 2 to 12.
• The asymptotic method gives answers close to the target
blocking and delay levels.
• Given a pre-computed table of values for y, the fixed
point iteration for the asymptotic method is the easiest
to compute and requires the least number of steps.
30
M/M/∞ State Space Diagram
l
0
l
1
m
l
iii
2m
l
n-1
(n-1)m
l
n
nm
iii
(n+1)m
n m · P(Q∞ = n) = l · P(Q∞ = n-1)
l l  l
(l /m )n
P(Q = n) =
 P(Q = 0) =
 P(Q = 0).
m  2m   nm
n!
31
M/M/C/∞ State Space Diagram
l
0
l
1
m
P(QC / 
l
C
iii
2m
l
Cm
l
C+1
Cm
iii
Cm
 (l /m ) n
 P(QC /  = 0) if n < C ,

n!
= n) = 
n
 (l /m )  P(Q = 0) if n  C.
C/
 C!C n C
32
M/M/C/K State Space Diagram
l
0
l
1
m
P(QC / K
l
C
iii
2m
l
Cm
l
C+1
Cm
l
C+K
iii
Cm
Cm
 (l /m ) n
 P(QC / K = 0) if 0  n < C ,

n!
= n) = 
n
 (l /m )  P(Q = 0) if C  n  C  K .
C/K
 C!C n C
33