Transcript Service Analysis and Simulation in Process Mining

Mining Resource-Scheduling Protocols
Arik Senderovich, Matthias Weidlich,
Avigdor Gal, and Avishai Mandelbaum
Technion – Israel Institute of Technology
Imperial College London
Our Playground: Services
Services are economic interactions
between customers and service providers
that create added value in return for
customer’s time, money and effort.
Service management – operations, strategy, and information technology
(Fitzsimmons and Fitzsimmons, 2006)
2
Services in Call Centers
3
Services in Emergency Departments
4
Services in Transportation
5
Operational Data-Driven Analysis of Services
 Capacity analysis (e.g. utilization of
resources)
 Time analysis (e.g. predicting delays)
 Sensitivity analysis (directions for process
improvement)
 Optimization with respect to some goal
6
Service Characteristics
 Services require participation (of both
customers and resources), perish if not
handled online and cannot be stored (lost
business)
 Scarce resources and uncertainty in demand
formulate Queues in front of service activities:
Service
7
Service Modeling and Analysis
via the queueing perspective
Data Mining
Queue Mining
Queue mining – predicting delays in service processes
(S. et al., 2014)
8
Queue Mining
 How can it be done? By discovering:
o Analytical models (e.g. from Queueing Theory)
o Simulation models
 Discovery requires:
1. Building blocks (arrival rates, service times,…)
2. Structure (control-flow)
3. Scheduling protocols (rules by which customers
and resources are matched for service)
9
Why do protocols matter?
Q: How long will the red customer wait?
A: Depends on the scheduling protocol!
N
10
Protocol: First-Come First-Served
Q: How long will the red customer wait?
A: At least two service times…
N
11
Protocol: Strict Priorities
Q: How long will the red customer wait?
A: At most one service time
Emergency
N
Regular
12
Outline
 Introduction:
o Services and Queues
o Motivation
 Problem Definition
 Proposed Solution
 Empirical Evaluation
 Future Work
13
Mining Resource Scheduling Protocols
 A resource becomes available and “observes” the
pool of waiting customers of various types
 Mining Resource-Scheduling Protocols Problem:
Predict the next customer-type that will enter
service
 Intra-queueing policy (within types) is assumed to
be First-Come First-Served (FCFS)
14
Mining Protocols as a Classification Problem
 Protocol mining can be viewed as the
following classification problem:
o Given a feature vector (that includes
resource type and queueing parameters)
o Provide a decision on the customer class to
enter service
15
Solution Overview
1. Selecting a use-case: Call Center
2. Extracting features from service event logs
3. Mining the Resource-Scheduling Protocol:
o Data mining techniques for classification
o Protocol approximation via queueing heuristics
16
Back to Call Centers…
17
Service From a Customer Perspective
18
Customer-Resource Choreography
19
Service from a Resource perspective
“Pick customer” follows Resource Scheduling Protocols;
In call centers, the selection is often predefined and automatic
20
W-Queue Architecture
If a resource becomes available,
which customer is picked for service?
Red/Blue/Green?
21
Solution Overview
1. Selecting a use-case: Call Center
2. Extracting features from service event logs
3. Mining the Resource-Scheduling Protocol:
o Data mining techniques for classification
o Protocol approximation via queueing heuristics
22
Goals of Resource-Scheduling Protocols
 We assume that there are two competing
goals:
o Reducing Delays: supported by research on the
relation of delays to customer satisfaction in
services (Larson, 1987)
o Optimizing Quality of Service: customers are to
be served by the most suitable resource (e.g.
senior physicians for complex patients)
 These goals define relevant features for
protocol mining (e.g. resource skills, queuelength)
23
Event Logs: Customer-Resource Duality
 For protocol mining both customer and
resource event logs are required:
o Queueing features and customer types
come from the customer log
o Decisions (outcomes) and resource skills
come from the resource log
24
Customer S-Log
CaseID
1894039726
1894039726
1894039731
1894039731
1894039745
1894039745
1894039748
1894039748
1894039756
1894039756
1894039759
1894039759
Timestamp
1205047967
1205047968
1205047973
1205047984
1205047982
1205048063
1205047990
1205048049
1205047944
1205047950
1205047937
1205047938
Queue
Regular
Regular
VIP
VIP
Low
Low
Regular
Regular
VIP
VIP
Regular
Regular
Queueing_Event
qEntry
sStart
qEntry
sStart
qEntry
qAbandon
qEntry
sStart
qEntry
sStart
qEntry
sStart
25
Queueing Features
 Queue-Length (customers that had
qEntry only)
 Head-of-line delay (the time in queue for
customers that had qEntry only)
QL=1
HOL = 3 minutes
N
HOL = 2 minutes
QL=2
26
Resource S-Log: Skill and Decision
ServerID
20024
20024
20024
20024
20102
20102
20102
20102
20102
20102
20102
20102
Timestamp
1205066301
1205066303
1205066303
1205066354
1205049510
1205049510
1205049636
1205049641
1205049641
1205049664
1205049664
1205049665
Skill
Senior
Senior
Senior
Senior
Regular
Regular
Regular
Regular
Regular
Regular
Regular
Regular
Queue
None
None
None
None
None
None
None
None
None
None
Low
Regular
Event
Available
Available
Idle
Idle
Back-Office
Back-Office
Idle
Idle
Available
Available
Serving
Serving
27
Solution Overview
1. Selecting a use-case: Call Center
2. Extracting features from service event logs
3. Mining the Resource-Scheduling Protocol:
o Data mining techniques for classification
o Protocol approximation via queueing heuristics
28
DM Methods
 Linear models:
o Linear Discriminant Analysis (LDA)
o Multinomial Logistic Regression (MLR)
 Tree-based models:
o Classification (or Decision) Trees
o Random Forests
The Elements of Statistical Learning
(Hastie, Tibshirani, Friedman, 2014)
29
Queueing Heuristics
 The heuristics originate in protocols that
minimize delays in overloaded queues
 Two simple rules that can be used to
approximate real (complex) protocols:
o Longest-Queue First
o Most-Delayed First
30
Longest-Queue First (LQF)
N
31
Most-Delayed First (MDF)
Wait of head-of-line:
3 minutes
2 minutes
N
32
Evaluation
33
Data Set
 The data comes from a large Israeli
telecommunication company:
o 50000 service requests per weekday
o 700 agent positions per day
o Multiple services: Private, Business, Content,…
 We focus on the Private sector that follows
the W architecture:
34
Experiment Setting
 Feature selection imposed the scenarios:
1. Resource type only
2. Queue lengths + resource types
3. Head-of-line delays + resource types
4. All the above
 Dependent variable = misclassification rate
(due to a 0-1 loss function)
35
Misclassification Rate: Linear Models
36
Misclassification Rate: Tree Methods
37
Exploring Protocol via Decision Tree
Regular
Q_1 – Low
Q_2 – Regular
Q_3 - VIP
Regular
VIP
38
38
Delay Time Distribution: VIP
39
39
Misclassification Rate: Queueing Heuristics
40
40
Value of Queueing Heuristics
Simple Approximations to Complex Protocols
 Both queueing heuristics are easily
calculated online (no learning phase)
 The Longest-Queue-First heuristic is
comparable to Decision Methods
 Tree-based methods require offline
learning, online adjustments (concept
drift) and are more difficult to
understand
41
Results Overview
 Resource-Scheduling Protocols can be
accurately deciphered via Decision Trees (and
their extensions)
 Simple queueing heuristics can serve as good
approximations for complex Decision Trees
42
Future Work
 Decomposing complex networks of services
into queueing architectures (e.g. the W
architecture)
43
Future Work
 Decomposing complex networks of services
into queueing architectures (e.g. the W-Queue
architecture)
 Extending delay prediction techniques by
considering the mined resource protocols
44
Thank you!
[email protected]
45