Digitalization is advancing in todays business. Small and medium-sized enterprises (SMEs) appear to be lagging behind compared to large companies. Process-aware information systems (PAIS, [1]) are well established for standardized processes, but they lack support for flexibility, which is often required in SMEs and may lead to competitive advantages. Additionally, in SMEs there are often few experts which are responsible for certain processes. The knowledge about how things are done is implicit, but not stored digitally and information is simply shared orally. As stated by da Silva et al. [23], these experts usually deviate and perform processes due to their expertise and experiences without losing control or missing the objective, but rather optimizing the process. Tracing these processes automatically and using them for process control may simplify the transfer and preservation of "best practices". This in turn may lead to an increase of efficiency and enhanced assistance possibilities especially for inexperienced users. Furthermore, bypassing the system and thus a loss of knowledge and transparency is prevented.
A main characteristic of an adequate approach for SMEs is to allow unexpected deviations and support unforeseen changing circumstances. Thereby, the key challenge is to determine how to continue with the workflow, while still achieving a successful completion. For an automated handling of such deviations without the demand for expert knowledge that needs to be integrated manually, an option is to use past experiences, more specifically completed processes. Applying case-based reasoning (CBR) to solve the described problem seems to be promising, as previous made experiences are exploited for adapting to unknown situations. Our objective is to develop an approach based on case-based reasoning that detects and handles deviations which occur in a flexible workflow, but still guides the user by recommending adequate work items.
The remainder of the paper is organized as follows. The notions of workflow flexibility and deviation management including related work will be introduced in section 2. Our approach of flexible workflow management allowing deviations is presented in section 3, while the proposed case-based deviation management including three promising methods, that could be exploited, are outlined in chapter 4. We conclude with a summary and an insight into our future work.
In this section our previous work on workflow flexibility and a specification of the underlying terminology will be presented. Furthermore the notion of deviation will be introduced and related work will be sketched.
Flexible Workflows have been focussed in research for more than a decade [22]. Schonenberg et al. [22] distinguish four different flexibility principles. Flexibility by Design, Change and Underspecification either require an entire awareness about all possible upcoming situations at design-time in order to manually model all possible alternatives, or a remodeling of the workflow is necessary at run-time. Flexibility by Deviation in contrast "is the ability for a process instance to deviate at run-time from the execution path prescribed by the original process without altering its process definition" [22]. Thus, single instances may not fit to the process model. Therefore we explicitly distinguish between modeled workflow, denoted as de jure, and executed workflow, called de facto [1]. Based on this definition we developed a workflow engine that facilitates flexibility by deviation.
During the SEMAFLEX3 [12] and the SEMANAS 4 [13] project we developed a flexible workflow engine based on constraints. We presented an approach [10,11], that allows flexible deviations from prescribed workflows, but still maintains control and recommends valid work items to a limited extent.
The proposed method is applied to imperatively modeled workflows, restricted to block-oriented ones. The paradigm of regular block structuring introduced by [20] is applied to guarantee model correctness by construction [16] and achieve a simplified handling of workflow models. Block-oriented workflows are constructed through a single root block element, which in turn consists of a single task node, a sequence of two block elements or a control-flow block. Start and end of control-flow blocks are clearly defined through control-flow nodes. An example of a block-oriented workflow is shown in Fig. 1.
The exemplary workflow consists of four task nodes (rectangles), two data nodes (ovals) and two control-flow nodes (rhombuses), which represent a parallel control-flow block ("+"). Additionally, the edges denote either control-flow (solid lines) or data-flow (dashed lines, input or output relation).
In our approach we transform these imperative workflow models into declarative constraints, which indicate sequential dependencies, to be able to determine task activations and thus possible executions in a specific unterminated state of the workflow. A constraint satisfaction problem (CSP) is constructed on the basis of these generated constraints and logged task enactments. A solution of the CSP is searched for, which tries to calculate a valid sequential enactment of all already executed and possible future executions of tasks. Thus, with a solution we are able to recommend valid task enactments. Consider the example of Fig. 1, the constraint set as logical formula is constructed as follows:
executed, a value is assigned, in this case t 1 = 1, and added to the constraint set. Task recommendations are calculated by regarding possible task assignments of the next sequential value, in this case 2. Considering the constraint set either with t 2 = 2 or with t 3 = 2 a solution is found. Thus, t 2 and t 3 are added as work items to the work list.
An additional advantage of using a CSP is that it is relatively easy and fast to retract violated constraints at run-time in order to restore consistency in case of a deviation. Still, by regarding the remaining constraints valid solutions can be computed. In our work, we therefore described a method, which detects deviations and retracts violated constraints to restore consistency and re-enable the workflow engine to recommend work items. But, a categorization of deviations and a determination of the cause is not considered until now. Thus, in addition to the restoration of consistency and overcoming a possible deadlock through system failure, no adequate reaction is possible. Different strategies for resolving inconsistencies, that are implemented until now, and their limitations are presented in section 3.1. Due to these limitations, deviation management needs to be elaborated in more detail and we propose a case-based approach.
The notion of deviation is not clearly defined and often included in the term exception, as a special type. To clarify our used classification of exceptions and deviations several specifications will be quoted. A process deviation is defined by da Silva et al. [23] as mismatch between executed process and process model. In contrast to exceptional behaviour deviations cannot be anticipated. According to Marrella et al. [17] exception handling is implemented manually at designtime, whereas deviation handling requires ad-hoc changes at run-time. Eder et al. [8] describe unexpected exceptions, what we call deviations, as an important aspect which should be handled to gain possible benefits.
Deviation Management in general can be split up into 3 phases: deviation detection, deviation handling and deviation analysis. Most of the related work focus on the detection and handling of deviations by either adapting running workflow instances or proposing corrective measures. Zhu et al. [27] developed a process behaviour space expression based on algebra to identify deviations and provide simple methods like tolerating or adjusting deviations that handle such exceptions to a limited extent.
Several existing approaches utilise ECA rules [4,7,19] to determine a reaction to detected deviations. Da Silva et al. [23] use logical formulae as rule basis for the detection and recommend manually created correction plans. Grambower et al. [9] present a flexible variant of ECA rules, which is enhanced through contextual semantic information and reasoning. Actions to perform are additionally adapted on the basis of semantic knowledge. A similar approach is developed by Adams et al. [3]. The manual handling of deviation is circumvented by so-called worklets, which represent exception handling patterns that are inserted automatically in running workflow instances on the basis of contextual information.
Depaire et al. [6] focus on deviation diagnosis or as they refer to the "managerial view" and investigate and analyse characteristics of deviations on purpose of searching for control weaknesses. Workflow instances are mined and business rules representing the deviations are derived subsequently, reducing the amount of data drastically, which in turn may be analysed.
CBRFlow [25] is a system that exploits conversational case-based reasoning to react to changing circumstances. Business rules are used to model necessary workflow run-time changes and may then be recommmended in similar future situations. But still the user has to intervene manually to trigger a deviation and to resolve the issues.
All of the presented related work considers manually created knowledge or even requires manual intervention in a running workflow for the management of deviations. As we address SMEs our aim is to automatically adapt to changing circumstances without the need of modeling process fragments or adaptation knowledge in any form. Our objective is to create an approach that relies on experience and thus previously executed workflows and exploits available data to provide further workflow control and recommendations of work items even in unexpected situations.
Two different and very simple constraint violation scenarios will be presented in combination with strategies, which we already implemented, for restoring consistency in the CSP.
For handling detected deviations in a simple sequential workflow or in sequential parts of a workflow, we developed two different strategies for restoring consistency. Consider the example in Fig. 2, where the first row shows the initial situation and the second row represents one step further with an additional executed task. Circles indicate tasks and edges represent the execution order. Blue filled nodes were already executed, pink ones are currently recommended and grey nodes are not activated yet. In the lower row there is a task executed, which is not in a valid order, thus a deviation occurred. The cause of the violation is not explicit without semantic knowledge and needs to be specified by the user. Without necessary user intervention we are able to derive two possible reasons, which are handled in different strategies.
1. Skipped Tasks. Tasks may have become obsolete and are therefore skipped or have been executed but without notice of the system (cf. Fig. 3a). All constraints concerning skipped tasks are irrelevant for continuing with the workflow and simply may be omitted. 2. Changed Order. Task order may have changed due to unknown reasons.
Remaining tasks need to be connected sequentially, as if the current executed task (second blue one) would have been inserted after the last executed one (first blue one, cf. new edges in Fig. 3b). Which strategy is applied needs to be determined either prior to the start of a workflow or at run-time. If the applied strategies differ for single deviations of the same type, further user interaction is necessary for each occurrence at run-time, which reduces the advantages of allowed flexibility and an additional obstacle for an easy-to-use system emerges.
Another example scenario of a simple violation that might occur is depicted in Fig. 4. In this simplified sketch at first both exclusive paths might be chosen, followed by the execution of the upper task, which implies the exclusion of the lower tasks. The deviation occurs in the last step, as nevertheless a task of the lower path has been executed. Which path should be pursued for workflow continuation without further knowledge can only be guessed by the system. Possible reasons are that either some task was completed by mistake or eventually certain circumstances changed that demand an adjustment and caused the execution of an excluded task or rather whole path. Constraints need to be adapted in case of such a violation according to one of the strategies pointed out in Fig. 5a and 5b.
The described scenarios have shown two types of deviations and thus constraint violations with a simple structure and a limited number of resolving possibilities. These strategies are straight-forward and easy to implement, but require user interaction. Besides, deviations might lead to additional deviations or even might be more complex from ground up, which makes it impossible to determine similar strategies to handle all possible deviation scenarios. Furthermore, it is not our aim to construct strategies, which need to be picked by the user, but rather some methods, which can be applied in an automated manner and support the user invisibly without the need of manual intervention. In our ongoing work we focus on case-based reasoning as technique to overcome the previously mentioned disadvantages.
Case-Based Reasoning [2] is a method that exploits previously made experiences to adapt to currently upcoming and partly unforeseen situations. As we pursue an approach where users are allowed to deviate flexibly, but still guidance through recommending work items is to be achieved on the basis of formerly traced workflows, CBR seems promising. De facto workflows may be used as case base, which is searched for similar cases compared to a running workflow instance. Furthermore, retrieved cases may be used to adapt the running workflow instance, either considering the work items or the underlying workflow model. Our aim is to create a learning workflow engine, which automatically handles unforeseen deviations and nevertheless guides the user to a successful completion of the workflow by recommending work items by reuse of previous cases.
In the following, we sketch some characteristics of a case-based approach to deviation management for flexible workflows.
Case As cases we regard all de facto workflows and their corresponding de jure workflow. The de jure workflow is block-oriented and the de facto workflow is a simple sequence of tasks, which were traced at run-time.
Query A running workflow instance, which is not completed yet, will be used as query. The associated de jure workflow is also available. This instance is a subsequence of a future de facto workflow and contains at least one deviation concerning its de jure workflow, that occurred at the time of the request. With case-based reasoning we aim at recommending work items to continue with the running workflow instance of the query, by searching for similar de facto workflows whose subsequences match the current instance. Successive tasks to those subsequences in the case may be reused as possible recommendations.
instances have to be compared to ongoing and not completed processes which are only subsequences and will not match exactly considering the length. Several local similarity measures are used for each attribute of the observed elements, that are part of the traces. For each observed element a global similarity value is computed on the basis of local values with use of a weighted average function. These similarity values of single elements are furthermore used in the SWA to calculate the overall similarity of traces. This method can be transferred to our pursued deviation management, if de facto workflows are considered as traces, for retrieving the best matching cases.
As adaptation method, Zarka [26] proposes a simple extraction method, that takes a subsequence of actions from the most similar retrieved case, which follows the part of the matched trace. Some values of this subsequence are adapted by more adequate ones on the basis of contextual information. As last step in the adaptation process, actions are filtered, e.g. invalid actions or unnecessary repetitions.
In our case of deviation management this subsequence can be extracted from the retrieved de facto workflow and first tasks of this subsequence can then be recommended as work items. Furthermore, if case and query do not match exactly, edit steps, which are necessary for aligning query and case, are part of the solution of the SWA. These additional differences relate to previously happened deviations, but might be required for a successful completion of the workflow as well. Therefore, these edit steps possibly might be transformed adequately into additional work items to ultimately provide further workflow control.
Dynamic Time Warping Dynamic Time Warping (DTW, [21]) may be used as alternative similarity measure for sequence comparison. DTW is already applied in various CBR approaches, for example for patient case matching in the medical domain [24]. It is a method which is used for aligning two time series, in our case de facto workflows can be regarded as such, by finding the best possible matching. For local comparison of different elements a cost function is defined. An optimal warping path is then searched for in the constructed cost matrix. The algorithm follows the same principle compared to the SWA with the main difference of values that are used in the matrix. A main advantage of both methods is the resistance to noise.
Vector Similarity Measure for Sequences A completely different approach is adopted by Gundersen [14]. In his research work, he presents a similarity measure for sequences on the basis of vectors. The main objective is to create a similarity measure which is suitable for real-time analysis relying on the assumption that events that happened near-time are more important than events from longer time ago. This is realized by a weighting function, that considers the position of events, related to the start and end of a sequence. The nearer the occurrence of an event is to the end of a sequence, the higher the weight value. For each event type this weight is computed as sum of single weights of single event occurrences. These weights of event types are then combined into a vector, that in turn may be compared to other vectors with common methods, like cosine similarity.
The approach is lacking semantic similarity between single tasks, as only whole sequences are compared considering their properties of task occurrences. Only self-referential characteristics of tasks can be included in the single weights of tasks, like e.g. importance or severity.
The vector similarity measure is developed on the basis of requirements for recognizing failure causes and recommending adequate solutions in the oil-well drilling domain. As specific characteristics are addressed, cf. [15], the approach is not generally applicable, but some properties might be transferable, especially for the relevance of task similarity dependent on the distance to the currently focused task.
To fit the needs of our proposed case-based deviation management the presented similarity measures and adaptation methods need to be investigated in detail and evaluated against our requirements. But as described previously some characteristics of each of the approaches might be adopted and combined for an adequate handling of deviations. Until now, we consider TBR as the technique with the most potential for an application to our proposed deviation management, as the similarity measure includes semantics of tasks and is also resistant to noise. Furthermore, adaptation opportunities are already available. We will consider to slightly adjust the similarity function with weights, indicating the distance to the deviation, analogously to the vector similarity measure of Gundersen [14].
Additionally to these challenging requirements some opportunities arise. An important aspect that should not be neglected is the performance of the applied algorithm as our approach will be used in real-time. To improve retrieval time, an option may be to filter the case base during execution, as the beginning of the trace is already available and enhanced step by step.
Another potential which will be investigated is, if the work list can be optimized through using CBR methods even if no deviation occurs, e.g. through a priorization and ranking of work items one the basis of previous traces. Perhaps even deviations could be explicitly triggered. Consider a best practice, and thus optimized, workflow, which is executed through experienced employees, will be traced and enhance the case base. This workflow might not be an exact mapping of the designed workflow model, but may still be used for workflow control with the use of CBR methods.
In this paper we presented our vision of a case-based approach to deviation management in the context of flexible workflows. We described our ongoing research
work about constraint-based workflow flexibility and the need for an integration of a thorough deviation management. We investigated the potential of applying methods of case-based reasoning and sequence similarity and therefore introduced three existing techniques, that may be used after an adequate adoption. Finally we sketched some challenges and potentials of the approach, that we will face in our future work.
Additional Knowledge Semantic descriptions and contextual information of the task and data nodes are accessible as additional knowledge. In certain cases there might be stored some kind of evaluation, i.e. if the workflow completed successful or failed. Furthermore, a categorization of the deviation might be derived, e.g. skipping of a task. Besides the de jure workflow, the declarative constraints, which are created and processed by the workflow engine, might be considered. Therefore, violated constraints are identifiable as well, if a deviation occurred. All of this additional information may be consulted for similarity calculation and enhance the retrieval process.
The similarity measure has to deal with a subset relation between query and case, as the de facto workflow of the query has not terminated yet, whereas the de facto workflows of the cases are complete. For the comparison of the de facto workflows we propose to use a sequence similarity measure, but local semantic similarity of tasks should be considered as well in a global similarity measure for the whole workflows. Furthermore, differences in subsequences that are not related directly to the deviation, when comparing query and case, might not be relevant. This relevance might be expressed by the distance to the currently focussed task or the position concerning its level. For example, consider the workflow in Fig. 1, where a parallel control-flow block is included. Valid de facto workflows could be f 1 = ⟨t 1 , t 2 , t 3 , t 4 ⟩ as well as f 2 = ⟨t 1 , t 3 , t 2 , t 4 ⟩, where the order of the tasks of the control-flow block may differ. If a deviation occurs in the part after t 4 , which is omitted in the figure, differences in the preceding part of the de facto workflow of case and query, like f 1 and f 2 , might not be relevant for the deviation and should nevertheless be regarded as highly similar.
Additionally, as the technique will be applied during workflow execution, the retrieval and adaptation needs to fulfill real-time constraints, otherwise users will be tempted to bypass the system.
In the following, we will investigate three methods for the retrieval of the most similar cases and adaptations of the query concerning their applicability to the described case-based deviation management.
Trace-based Reasoning (TBR), which was first introduced by Mille [18], is a special form of case-based reasoning, where traces serve as case base. An important aspect as extension to standard CBR is the introduction of a temporal aspect. In TBR similarity measures are used that base upon temporal sequences. Cordier et al. [5] and Zarka [26] presented an approach with the objective of finding contextual recommendations for users that interact with web applications. Therefore an algorithm was developed that is based on the Smith-Waterman-Algorithm (SWA) and was adapted for retrieving similar traces. The SWA is used for local sequence alignment and compares traces in all possible lengths. This characteristic perfectly matches the requirements of trace-based reasoning as terminated