Transcript Service Analysis and Simulation in Process Mining

Service Analysis and Simulation
in Process Mining
Doctoral Consortium, BPM14’
Arik Senderovich
Advisers: Avigdor Gal and Avishai Mandelbaum
7.9.2014
Contents
 Introduction:
o Services
o Operational process mining
 Research Goal
 Research Outline
 Preliminary Work:
o Queue Mining: Predicting Delays in Services
 Future Work
2
What are services?
Services 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)
3
Services in Call Centers
4
Services in Emergency Departments
5
Services in Transportation
6
Characteristics of Services
 Services require participation (of both sides),
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
The Essence of Process Mining
Process-Aware
Information-System
Process Modeling
and Analysis
Process Mining
Data Mining
Extract non-trivial
information on business
processes from event data
Process Mining:
Discovery, Conformance and Enhancement of Business Processes (van der Aalst, 2011)
8
PM: Compliance vs. Performance
9
Illustration by Wil van der Aalst
Types of Performance Analysis
 We aim at data-driven:
o Capacity analysis (e.g. utilization of
resources, bottleneck identification)
o Time analysis (e.g. predicting delays, sojourn
times)
o Sensitivity analysis (directions for process
improvement)
o Optimization with respect to some goal
10
Operational (Data-Driven) Analysis
Events
Business
Process
Event Log
Operational Goals
Model Specification
Model,
e.g. QNet, PNet
Event log
Discovery
Data-driven Model
Selection
Validation
Valid Model
Improve/Predict/Recommend
11
Operational
Support
Up-to-date Event Log
Mind the Gap
 Control-flow
Queues areperspective
not treated separately from service
1.
2. Resource
activitiesperspective
in analytic and simulation performance
3. Time
perspective
models
(e.g. for time prediction)
4. Queueing perspective
Agent
Mean=30 seconds
Sojourn time
= Activity Time + Delay
12
Research Goal
 Integrating service analysis techniques (e.g.
Service
andprocess
Simulation
Queueing Analysis
Theory) into
mining by
discovering
analytic and
simulation models
in Process
Mining
from event data
13
Research Outline
 Queue mining: discovery and analysis of service
processes via analytical or approximated queueing
models
 Discovery of simulation models of service processes
from event data
 Development of a single modeling framework for
discovery, conformance and performance analysis of
business processes with queues that combines:
o Current process mining perspectives (e.g. control-flow,
time, resources) – at the instance level
o with the queueing perspective – at an aggregate level
o Simulation being the common denominator
14
Queue Mining
“Queue Mining – Predicting delays in service processes” (CAiSE14’)
15
Service Modeling and Analysis
via the queueing perspective
Data Mining
Queue Mining
Queue mining – predicting delays in service processes
(Senderovich, Weidlich, Gal, Mandelbaum, 2014)
16
Goals of the Preliminary Work
 Introducing the queueing perspective to
process mining
 Showing that queue mining techniques
improve prediction accuracy in service
processes
 Validating well-established results in Queueing
Theory against real-world data
17
Steps towards our goal
1. Target a relevant operational problem: online
delay prediction
2. Explore Queueing Data (Q-Log) that comes
from a real-world service process
3. Consider delay prediction methods
4. Empirical evaluation of the methods
18
Online Delay Prediction
 A target-customer arrives into the queue:
1
s
Problem:
Predict the waiting time of the target-customer
o Important in service processes
o Simple, but not too simple (can be generalized)
19
Steps towards our goal
1. Target an operational problem
2. Explore Queueing Data (Q-Log) that comes
from a real-world service process
20
Queueing Data (Q-Log)
 ILDUBank (Israeli Daily Updated Bank) data,
coming from the Technion SEELab
 Focus on a single customer type
o “General Banking” (70% of bank’s customers)
 Training log of 250488 delays; test log of
117709 delays (January-March, 2011)
21
Q-Log: Example
CaseID
1000227
1000227
1000227
1000230
1000230
1000230
1000237
1000237
1000246
1000246
1000246
Timestamp
24-01-10 07:10:43
24-01-10 07:11:36
24-01-10 07:17:04
24-01-10 07:10:51
24-01-10 07:11:05
24-01-10 07:11:50
24-01-10 07:16:01
24-01-10 07:17:04
24-01-10 07:17:50
24-01-10 07:18:56
24-01-10 07:21:41
Activity
Queue
Service
End
Queue
Service
End
Queue
End
Queue
Service
End
Agent
Service
540
1
Queue
546
s
Abandonments
563
22
Steps towards our goal
1. Target a relevant operational problem (e.g.
the online delay prediction problem)
2. Explore a real-life Q-Log
3. Predict delays via several methods:
o Extensions for existing Process Mining techniques
o “Classical” queueing models
o Heavy-traffic approximations of queueing models
4. Empirical evaluation of the methods
23
Method 1: Transition System
Based on van der Aalst et al., 2011
Delays ={45,4,56,78,…}
Predictor is the average over past delays;
suitable for systems in steady-state
24
Method 1 vs. Real Data
25
25
Method 2: Extending the Transition System
QL&Delays ={(10,45),
(12,4),…}
Prediction based on K-Means clustering of queue-lengths
26
Method 1 vs. Method 2 (RASE)
27
M3: Queue-Length Predictor
Based on the G/M/s+M model (Whitt, 1999)
Service
1

Queue

s

Abandonments
QL
1

i  0 s  i 
28
Statistical vs. Queueing Model (RASE)
QLM is accurate for Moderate Load (model assumptions)
29
Approximations of queueing models
(Heavy-Traffic)
 “Classical” queueing models
suffer from oversimplifying
assumptions:
o Exponential service times/patience
o Poisson arrivals
 Realistic queueing models are
rarely tractable mathematically;
however these models can be approximated
 The idea: analyzing the queueing model under limits of its
parameters
30
M4: Last-to-Enter-Service
(Armony et al., 2009; Ibrahim and Whitt, 2009)
 A target-customer arrives into the queue:
The last customer to enter service waited w in queue
Prediction: the target-customer will wait w
31
Results (Root Average Squared Error)
 Queueing models and their approximations
are valuable when mining service event logs
 Current process mining techniques can be
extended with queueing features
 Model assumptions are of essence and must
be validated before using the model
32
More on Queue Mining
 Work-in-progress:
o Delay prediction in queueing networks (buses) / multi-
class services (call centers)
o Mining RTLS hospital data
 Future work: Automatic model selection from a
possible set of analytical queueing models
o Search for analytically tractable queueing networks
(somewhat analogous to searching for sound PNets)
o vs. search for simple models that aggregate complex
realities yet work well in practice
34
Towards Data-Driven Simulation
Models of Services
(and Business Processes with Queues)
35
The need to Simulate Service Processes
 Complex service environments often result in
analytically intractable queueing models
 Solutions:
o Approximations (e.g. snapshot principle) with
(sometimes) unrealistic assumptions
o Simulation
36
Discovering Simulation Models of Services
1. Service network structure (control-flow from
both a customer and a resource perspective)
2. Building blocks (arrival rates, service times,
routing probabilities)
3. Scheduling protocols (rules by which
customers and resources are matched with
each other)
o “Mining Resource-Scheduling Protocols”, BPM14’
37
Long-Term Future Work:
Business Process Simulation with Queues
Data-driven
simulation models
of business
Business
process
Simulation mining
of services
processes with queues simulation
(Rozinat et al., 2009)
38
Business Process Simulation with Queues
Main challenges:
 Defining a unified modeling framework
(combination of instance level and aggregate
level models)
 Discovery of queueing information from event
logs without explicit queueing events
 Discovery, conformance checking and
performance analysis methods for all process
mining perspectives (control-flow, resources,
time, queues,…)
39
Thank you!
[email protected]
40