=Paper=
{{Paper
|id=Vol-1701/paper18
|storemode=property
|title=Conformance Checking and Performance Improvement in Scheduled Processes: A Queueing-Network Perspective (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-1701/paper18.pdf
|volume=Vol-1701
|authors=Arik Senderovich,Matthias Weidlich,Liron Yedidsion,Avigdor Gal,Avishai Mandelbaum,Sarah Kadish,Craig A. Bunnell
|dblpUrl=https://dblp.org/rec/conf/emisa/SenderovichWYGM16
}}
==Conformance Checking and Performance Improvement in Scheduled Processes: A Queueing-Network Perspective (Extended Abstract)==
https://ceur-ws.org/Vol-1701/paper18.pdf
Jan Mendling and Stefanie Rinderle-Ma, eds.: Proceedings of EMISA 2016,
Gesellschaft für Informatik, Bonn 2016
Conformance Checking and Performance Improvement in
Scheduled Processes: A Queueing-Network Perspective
(Extended Abstract)
Arik Senderovich1 Matthias Weidlich2 Liron Yedidsion3 Avigdor Gal4
Avishai Mandelbaum5 Sarah Kadish6 Craig A. Bunnell7
Abstract: Conceptual models of service processes enable operational analysis and may be constructed
automatically from event logs containing recorded traces of process execution. In this work, we target
the analysis of resource-driven, scheduled processes based on event logs. Specifically, we approach
the questions of conformance checking (how to assess the conformance of the schedule and the
actual process execution) and performance improvement (how to improve the operational process
performance). The first question is addressed based on a comparative analysis of queueing networks
for both the schedule and the actual process execution. These results of this analysis are used to
improve the operational performance of a process: we suggest adaptations of the scheduling policy of
the service process to decrease the tardiness (non-punctuality) and lower the flow time. The work
summarized in this extended abstract has been published in [Se16].
1 Operational Analysis of Scheduled Processes
Service systems play a fundamental role in domains such as transportation and the health
sector. Services are provisioned by a service process [Du13, Da11], broadly defined by a
set of activities that are executed by a service provider to serve particular clients. We focus
on service processes that are multi-stage and scheduled. The former means that there is
a series of interactions between a client and a service provider, or specific resources at a
provider’s end. Scheduled processes, in turn, are structured such that the arrival of clients
as well as the basic activities of handling their requests are largely known in advance.
In this work, we target operational analysis of such multi-stage scheduled service processes.
Specifically, we elaborate on methods to answer the following two questions: how to assess
the conformance of a pre-defined schedule of a service process to its actual execution? and
how to improve operational performance of the scheduled process?
We address the above questions with a model-driven approach, exploiting a specific type of
queueing networks. This choice is motivated by the need to capture the key actors of service
1 Technion - Israel Institute of Technology, Haifa, Israel, sariks@tx.technion.ac.il
2 Humboldt-Universität zu Berlin, Germany, matthias.weidlich@hu-berlin.de
3 Technion - Israel Institute of Technology, Haifa, Israel, lirony@ie.technion.ac.il
4 Technion - Israel Institute of Technology, Haifa, Israel, avigal@ie.technion.ac.il
5 Technion - Israel Institute of Technology, Haifa, Israel, avim@ie.technion.ac.il
6 Dana-Farber Cancer Institute, Boston, Massachusetts, United States, sarah kadish@dfci.harvard.edu
7 Dana-Farber Cancer Institute, Boston, Massachusetts, United States, craig bunnell@dfci.harvard.edu
Conformance Checking Performance Improvement
Hypotheses Scheduling
Discovery
Testing / Policy
of Queueing
Similarity Diagnostics Adaptation
Networks
Assessment
Event Log Schedule
Figure 1: Overview of the approach to conformance checking and process improvement
processes (clients and providers), their interactions, and the dependencies of different
stages of the service process, including parallel processing of activities [Bo06]. Against
this background, we rely on Fork/Join networks [AG89], which serve as the foundation for
analysis of parallel queueing systems [AMZ12].
2 Conformance Checking & Process Improvement
To address the question of conformance, we present a method that is grounded in queueing
networks that are discovered for both the schedule and the actual process execution. We
then apply statistical inference (hypotheses testing) and similarity assessment to validate the
scheduling assumptions of the process. As outlined in Figure 1, the conformance checking
step yields diagnostics on operational deviations between the schedule and the execution of
the process. The identified deviations then guide the efforts to answer the question of how
to improve the operational performance of a process. In particular, we target improvements
in terms of decreased tardiness (lateness with respect to due dates) and lower flow time by
adapting the scheduling policy. Our contributions can be summarized as follows:
Conformance Checking: Following the existing theory for validating (simulation-based)
operational models against execution data [Sa11], we decompose the conformance checking
problem along two dimensions, namely conceptual and operational. Conceptual confor-
mance checks the assumptions and theories that underlie the schedule. To assess this type of
conformance, we compare the schedule and the event log indirectly by means of Fork/Join
networks that are discovered for both. These networks are compared through the lenses of
their corresponding components: structure, routing, and server dynamics, which enables
general insights beyond the level of instance-based conformance checking. Operational
conformance checks the ‘predictive power’ of a schedule with respect to various perfor-
mance measures (e.g., delay predictions). To this end, we measure deviations between the
observed and the scheduled performance indicators.
Process Improvement: Conformance checking detects parts of the process that fail to con-
form (conceptually or operationally) to a given schedule. We handle lack of conformance
by combining data-driven analysis via the Fork/Join model, and principles from scheduling
research [Pi12]. Specifically, we target local improvement of service policy, whenever con-
formance is lacking. By default, scheduled processes often operate under the Earliest-Due
Date first (EDD) service policy per node, thus ‘optimizing’ schedule-related performance
measures (e.g., non-punctuality). Assuming that all cases are available at the beginning of
the scheduling horizon, it is indeed optimal to use the EDD policy. However, when cases
Jan Mendling and Stefanie Rinderle-Ma, eds.: Proceedings of EMISA 2016,
Gesellschaft für Informatik, Bonn 2016
arrive into the system at different times (according to schedule), we show that the EDD
policy can be improved to achieve lower tardiness. Moreover, we show that without losing
punctuality, our algorithms also improve other performance measures such as flow time.
3 Discussion
This work presents methods for conformance checking and performance improvement of
scheduled multi-stage service processes, as they are observed in such domains as healthcare
and transportation. We explore the value of the proposed approach by a two-step evaluation.
First, we apply the conformance checking techniques to RTLS-based data from a real-world
use-case of a large outpatient oncology clinic namely, the Dana-Farber Cancer Institute.9
Our experiments demonstrate the usefulness of the validation method for detection of
operational deviations and identification of root causes of deviations. As a second step, we
evaluate the proposed process improvement technique by means of simulation and show
that tardiness and flow time can be reduced by more than 20% using our scheduling policy.
Acknowledgement. We are grateful to the SEELab members, Dr. Valery Trofimov, Igor
Gavako and especially Ella Nadjharov, for their help with the statistical analysis. We also
thank Kristen Camuso, from Dana-Faber Cancer Institute for the insightful data discussions.
References
[AG89] Ammar, Mostafa H; Gershwin, Stanley B: Equivalence relations in queueing models of
fork/join networks with blocking. Performance Evaluation, 10(3):233–245, 1989.
[AMZ12] Atar, Rami; Mandelbaum, Avishai; Zviran, Asaf: Control of fork-join networks in heavy
traffic. In: Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton
Conference on. IEEE, pp. 823–830, 2012.
[Bo06] Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S.: Queueing Networks
and Markov Chains - Modeling and Performance Evaluation with Computer Science
Applications; 2nd Edition. Wiley, 2006.
[Da11] Daskin, Mark S: Service Science. Wiley.com, 2011.
[Du13] Dumas, Marlon; Rosa, Marcello La; Mendling, Jan; Reijers, Hajo A.: Fundamentals of
Business Process Management. Springer, 2013.
[Pi12] Pinedo, Michael L: Scheduling: theory, algorithms, and systems. Springer Science &
Business Media, 2012.
[Sa11] Sargent, Robert G.: Verification and validation of simulation models. In (Jain, S.; Jr.,
Roy R. Creasey; Himmelspach, Jan; White, K. Preston; Fu, Michael C., eds): Winter
Simulation Conference. WSC, pp. 183–198, 2011.
[Se16] Senderovich, Arik; Weidlich, Matthias; Yedidsion, Liron; Gal, Avigdor; Mandelbaum,
Avishai; Kadish, Sarah; Bunnell, Craig A.: Conformance checking and performance
improvement in scheduled processes: A queueing-network perspective. Information
Systems, 2016. DOI: http://dx.doi.org/10.1016/j.is.2016.01.002
9 http://www.dana-farber.org/.