Transcript Document

Using Simulation-based Stochastic
Approximation to Optimize Staffing of
Systems with Skills-Based-Routing
WSC 2010, Baltimore, Maryland
Avishai Mandelbaum (Technion)
Zohar Feldman (Technion, IBM Research Labs)
Technion SEE Laboratory
.
Contents





Skills Based Routing (SBR) Model
SBR Staffing Problem
Stochastic Approximation (SA) Solution
Numerical Experiments
Future Work
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
2
SBR Model
Service System with SBR – Basic Model


i

DiP

DiS, j
Nj


I – set of customer classes
J – set of server pools
Arrivals for class i:
renewal (e.g. Poisson),
rate λi
Servers in pool j: Nj, iid
Service of class i by pool j:
DiS, j
(Im)patience of class i:
DiP
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
3
SBR Model
Routing

Arrival Control: upon
customer arrival, which of
the available servers, if
any, should be assigned to
serve the arriving
customer

Idleness Control: upon
service completion, which
of the waiting customers, if
any, should be admitted to
service
?
?
Feldman et. al.
?
?
?
?
Winter Simulation Conference, Baltimore, MD
December 2010
4
SBR Staffing Problem
Cost-Optimization Formulation
K
min cT N   f k  N 
N
k 1
s.t. AT N  b
N


J

k
f (N) – service level penalty functions
Examples:
• f k(N) = ckλkPN{abk} – cost rate of abandonments
• f k(N) = λkEN[ck(Wk)] – waiting costs
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
5
SBR Staffing Problem
Constraints-Satisfaction Formulation
min cT N
N
s.t. f k  N    k , k  1,
K
AT N  b
N


J

k
f (N) – service level objective
Examples
•
•
k
f (N) = PN{Wk>Tk} – probability of waiting more than T
time units
k
f (N) = EN[Wk] – expected wait
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
6
SA Based Solution
Stochastic Approximation (SA)

Uses Monte-Carlo sampling techniques to
solve (approximate)


min f  x  : E  F  x,  
xX

analytically intractable
X  -n convex set
ξ – random vector (probability distribution
P) supported on set Ξ
 F : X    - almost surely convex

Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
7
SA Based Solution
SA Basic Assumptions


There is a sampling mechanism that can be used to generate
iid samples from Ξ
There is an Oracle at our disposal that returns for any x and ξ
• The value F(x,ξ)
• A stochastic subgradient G(x,ξ)
G  x,ξ    x F  x,  
F  y,    F  x,    G  x,ξ 
T
Feldman et. al.
 y  x  , y  X
Winter Simulation Conference, Baltimore, MD
December 2010
8
SA Based Solution
SBR Simulation

Simulation Artifacts
• Service Consumer: arrival process, patience distribution
• Resource: availability function
• Resource Skills: service distribution depending on resource
type and requestor type
• Router: arrival control, idleness control
• Event Engine: sorts and executes events (arrivals, service
completions, abandonment, shift change…)
• Statistics: data series gathered by intervals (e.g. number of
arrivals, number of abandonment, waiting times etc.)

Use random streams to enable common number
generation
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
9
SA Based Solution
SBR Simulation


Ω - the probability space formed by arrival, service and patience times.
f(N) can be represented in the form of expectation. For instance,
f  N  : PN W  0 
 D  N ,   dP  

 A   dP  
:  F  N ,  dP  




D(N,ω) is the number of Delayed customers
A(ω) is the number of Arrivals
Use simulation to generate samples ω and calculate F(N,ω)
Sub-gradients are approximated by Finite Differences
G  N ,    i  F  N  ei ,    F  N ,  
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
10
SA Based Solution
Cost Optimization Algorithm
Problem
Solution
K
min cT N   f k  N 
N
k 1
s.t. AT N  b
N
J

K

 T

k
min  f  N  : E c N   F  N  
N X
k 1



X :  x 


Feldman et. al.
J

: AT N  b
Use Robust SA
For simulation, realvalued points are
rounded to integers
Winter Simulation Conference, Baltimore, MD
December 2010
11
SA Based Solution
Constraints Satisfaction Algorithm
Problem
min cT N
N
s.t. f k  N    k , k  1,
K
Solution
 There exist a solution with
cost C that satisfies the
Service Level constraints if”f
xX C k 1, , K
A N b
T
N
Feldman et. al.
J



min max f k  x    k  0

where X C :  x  J : cT x  C , AT x  b
Look for the minimal C via
binary search
Winter Simulation Conference, Baltimore, MD
December 2010
12
Numerical Experiments
Numerical Study

Goal
• Examine algorithms performance
• Explore convexity and its affect on performance

Method
• Run the algorithms by several examples
• For each example run simulation
• To identify the best solution by calculating confidence
intervals of all possible solutions
• To evaluate solutions and approximate gradients to test for
convexity
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
13
Numerical Experiments
Simple Example: Penalizing Abandonments


N-model (I=2, J=2)
Control: Static Priority
λ1 =100
θ1 = 1
• Class 1: pool 1, pool 2
• Pool 2: class 1, class 2

µ11=1
λ2 =100
θ2 = 1
µ21=1.5
µ22=2
Optimization problem
min 1N1  2 N 2  3 100 PN  AB1  2 100 PN  AB2 
N
s.t. AN  b
N
Feldman et. al.
J

Winter Simulation Conference, Baltimore, MD
December 2010
14
Numerical Experiments
Simple Example: Objective Function
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
15
Numerical Experiments
Simple Example: Solution

Convergence Rate
Convergence Point

Solution: N=(98,58), 0.5% above optimal
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
16
Numerical Experiments
Realistic Example


100’s-agents Call Center (US Bank: SEE Lab –
open data source)
2 classes of calls
• Business
• Quick & Reilly (Brokerage)

2 pools of servers
• Pool 1- Dedicated to Business
• Pool 2 - Serves both
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
17
Numerical Experiments
Realistic Example

Arrival Process: Hourly Rates
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
18
Numerical Experiments
Realistic Example

Service Distribution (via SEE Stat)
Business
Brokerage
LogN(3.9,4.3)
LogN(3.7,3.4)
Patience: Exp(mean=7.35min)
Feldman et. al.
Exp(mean=19.3min)
Winter Simulation Conference, Baltimore, MD
December 2010
19
Numerical Experiments
Realistic Example: Optimization Models

Daily SLA

24
24
t 1
t 1
Hourly SLA
24
24
t 1
t 1
min  N1,t   N 2,t
min  N1,t   N 2,t
s.t. PN W1  0  0.2
s.t. PN W1,t  0  0.2
N
PN W2  0  0.5
N
Feldman et. al.
T J

N
PN W2,t  0  0.5
t  1,
N
Winter Simulation Conference, Baltimore, MD
, 24
T J

December 2010
20
Numerical Experiments
Realistic Example: SLA

Daily SLA
Feldman et. al.

Hourly SLA
Winter Simulation Conference, Baltimore, MD
December 2010
21
Numerical Experiments
Realistic Example: Staffing Levels

Daily SLA

Hourly SLA

Staffing cost: 510

Staffing cost: 575
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
22
Summary



We developed simulation-based algorithms
for optimizing staffing of systems with skillsbased-routing
These algorithms apply to very general
settings, including time-varying models and
general distributions
In most cases, the algorithms attained the
optimal solutions even when the service
levels were not convex
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
23
Future Work




Incorporating scheduling mechanism
Complex models
Optimal Routing
Enhance algorithms
• Relax convexity assumption
• More efficient

Convexity Analysis
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
24
Backup
Cost Optimization Algorithm
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
26
Cost Optimization Algorithm

Denote:
DX : max x  x0
xX
2

M : sup E  G  x,   2 


xX
2

 DX M 
J 




2
Theorem: using
, and
we achieve P  f  xˆ   f  x      
Feldman et. al.
Winter Simulation Conference, Baltimore, MD

DX M
J
December 2010
27
Constraints Satisfaction Algorithm
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
28
Constraints Satisfaction Algorithm

Denote:
M *2 : 2M *,2 x ln J  2M *,2 y ln K
2
E  Gxk  x,     M *,2 x k , x



2
E  F k  x,     M *,2 y k , x



20M *2
2
Theorem: using J  2 2 , and  :
 
M * 5J
we achieve
• 
• P c
P max
k 1, , K
Feldman et. al.
T
 f  xˆ         1  1   
k
log Cmax
k

xˆ  c    1  1  2 
log Cmax
Winter Simulation Conference, Baltimore, MD
December 2010
29
Constraints Satisfaction Algorithm
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
30
Summary Results
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
31
Summary Results
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
32
Constraint Satisfaction: Delay Threshold with FQR
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
33
Constraint Satisfaction: Delay Threshold with FQR

Feasible region and optimal solution

Algorithm solution: N=(91,60), cost=211
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
December 2010
34
Constraint Satisfaction: Delay Threshold with FQR

Comparison of Control Schemes
FQR control
Feldman et. al.
Winter Simulation Conference, Baltimore, MD
SP control
December 2010
35