Con gurable process models can be used to encode a multitude of (di erent) process models. After con guration, they can be used to support the execution of a particular process. A con gurable process model represents a space of instantiations (con gured process variants). Such an instantiation space can be used by an organisation to select the best instantiation(s) according to some Key Performance Indicators (KPIs), e.g., cost, throughput time, etc. Computing KPIs for all the instantiations in the space is time consuming, as it might require the analysis (e.g., simulation) of thousands (or more) of instantiations. Therefore, we would like to exploit structural characteristics to reduce the amount of instantiations which need to be analysed. This reduction only removes those instantiations which do not need to be considered by an organisation. This yields the same result (a collection of best con gurations), but in a faster way.
new passport, but they are not competing with each other as they only o er this service for their own inhabitants. As a result of the latter, municipalities are quite eager to share their processes with other municipalities, and to learn from each other. Although all municipalities o er the service to create a new passport, they do not all use the exact same process. Some \couleur locale" may exist between di erent municipalities. For example, the New New York municipality may create the passport rst and have Fry pay when he collects his passport, while the Spring eld municipality, being smaller, may require Homer to pay when he requests for it, that is, before they create it. Even though the steps in the process may be the same (request for a passport, pay for it, create it, and collect it), the process may still di er to some extent.
The combination of this \couleur locale" and the openness mentioned earlier makes municipalities natural candidates to bene t from co-called con gurable process models. A con gurable process model contains variation points which can be set to tailor the con gurable process model to the preferences of an organisation. Setting preferences for the variation points is called a con guration. If all variation points are set by a con guration, the resulting process model is called an instantiation. Please note that a con gurable process model that contains a multitude of variation points allows for an exponential amount of possible con gurations and instantiations.
A con gurable process model may contain instantiations that are not used
by any of the municipalities. An interesting question now is, whether some
instantiations score better for a given municipality than the instantiation they are
now using. Given a set of Key Performance Indicators (KPIs), we could check
how every instantiation scores on these KPIs, and return the corresponding best
con gurations. In [
As mentioned earlier, a con gurable process model may allow for many variation points and, as a result, very many con gurations and instantiations. As a result, the amount of instantiations may be too large to analyse, or it may simply take too much time to analyse them all. Therefore, in this paper, we aim to reduce the amount of instantiations which need to be analysed by exploiting the fact that they all stem from the same con gurable process model. For example, if we take the passport example as introduced earlier, it is clear that the Spring eld instantiation allows for less nancial risks than the New New York one. For this reason, if nancial risk would be the KPI at hand, it would make no sense to analyse the New New York instantiation, as it will be dominated anyways by the Spring eld instantiation.
To achieve this reduction in the amount of instantiations to analyse, we propose to exploit structural properties of the con gurable process model by means of a monotonicity notion. This paper introduces this monotonicity framework, applies it for a concrete KPI, and evaluates the application empirically on an arti cial con gurable process model. The monotonicity framework creates, per KPI, an ordering of the instantiations. This ordering starts with the instantiation most probably to have a high score on that KPI. Using these orderings, the monotonicity framework starts analysing the most promising instantiations. It keeps on analysing until no more instantiations can be found which score higher on a KPI than the already analysed models.
For our concrete KPI, we have selected throughput time and we show how the monotonicity can be computed between two instantiations. We apply this monotonicity notion on a running example to order the instantiations. Afterwards, we use simulation to obtain concrete values for the KPI. Using these values, we can conclude that we achieve a reduction of more than 90% on the amount of instantiations which need to be analysed for this particular model.
The remainder of this paper is organised as follows. In Sect. 2, we elaborate on related work. Afterwards, we present some preliminaries in Sect. 3. Sections 4 and 5 contain our monotonicity framework and concrete results for the concrete throughput time KPI. We nish the paper with an empirical evaluation and the conclusions and future work in Sect. 6 and Sect. 7. 2
Our research builds on three existing lines of research: con gurable process models, performance analysis, and business process reengineering. 2.1
Con gurable process models (see Sect. 3.1 for an example con gurable process
model) have been developed by extending existing modelling languages, e.g.,
C-EPC (Con gurable Event-driven Process Chain) [
Within the eld of queueing theory, work has been conducted in de ning
monotonicity notions between queueing networks and between queueing stations.
In [
The authors in [
Although the papers consider monotonicity in a similar way as us, they focus on the parameters instead of the topology of the network. However, one of our future directions is to take the parameters also into account in which this work might be applicable. 2.3
In [
In [
The approach closest to our approach is presented in [
Before introducing the monotonicity framework, this section introduces the congurable process models used by the framework and the Petra framework. 3.1
Con gurable process models contain prede ned variation points. By con guring these variation points, that is, by selecting appropriate values for these points, the con gurable process model can be tailored to an organisation (like a municipality). If all variation points have been con gured properly, that is, if the con guration is complete, the con gurable process model is instantiated into a process model ready that is ready for enactment (an instantiation).
As an example, Fig. 1 shows the control- ow of a con gurable process model using a BPMN (Business Process Model and Notation) notation augmented with curved arrows and no-entry signs. A curved arrow on an incoming edge indicates a variation point that allows the following part of the con gurable process model to be hidden. For example, the curved arrow on the incoming edge of the task labelled \B" indicates that this activity can be hidden. Note that if this curved arrow would have been positioned on the outgoing edge of this task, that then the entire following choice part, including the tasks labelled \C" and \D", would then have the option be hidden. Likewise, the no-entry sign indicates a variation point that allows the following part of the con gurable process model to be blocked.
If a part of the con gurable process model is hidden, this results in this part being substituted by an automatic task. If a part of the con gurable process model is blocked, this results in removing this part in total. As a result, if a part of a sequential execution of tasks is blocked, then the entire sequence is blocked, as we would run into a deadlock otherwise.
For our con gurable process model formalism, we use so-called Process Trees [
loopdef Automatic def seq and A
Z A
Z A
Z
D R E do redo exit A
Z A
Z A Z [ga]
A [ga] A a resource) or manual (with a resource). Blocks indicate the causal dependency of the children, i.e., the nodes directly underneath the block. Events indicate a point in the process where input from the environment is required. Only events that match the actual input will be executed, the other events will be dropped. In principle a block can have any number of children except for the loop nodes (loopxor and loopdef), which always have 3 children, and the event nodes, which have a single child. At the top of the Process Tree we have a root node.
Next to hiding and blocking, a Process Tree allows for a third type of variation
points, called placeholder nodes. Where hiding and blocking can be con gured by
selecting either \yes" or \no", a placeholder node can be con gured by selecting
one of its child nodes. As a result, the placeholder node will be replaced in an
instantiation by its selected child node. For instance, in a con gurable process
model, there may be the possibility to select a payment method from a set of
known payment methods (credit card, bank transfer, or cash). The Process Tree
formalism is richer than just the control- ow perspective [
Petra [
The monotonicity framework stems from the observation that it may be possible to check whether an instantiation dominates another instantiation by comparing the structure, control ows in or case, instead of the behaviour. This means that we want to compare two models with respect to a KPI without computing the actual values for that KPI. Consider, for example, two instantiations from the running example (see Fig 2), and assume that for the rst instantiation nothing has been blocked or hidden, and that for the second nothing has been blocked and only the task labelled \B" has been hidden. Clearly, the throughput time of the second instantiation is always better than the throughput time of the rst, as the only di erence is that the rst has to execute \B", which we assume takes some time, where the second does not. Based on structure, we could claim that the second instantiation is better as the rst w.r.t. the throughput KPI under all circumstances. As a result, when looking only at the throughput KPI, the rst cannot be better than the latter (assuming independence between the duration of an activity and the occurrence of another).
For this reason, the monotonicity framework introduces an acyclic (partial) order on the possible instantiations. Throughout the paper, we use the term \atleast-as-good" to denote the monotonicity ordering between instantiations/nodes for a particular KPI. We de ne this relation formally as: De nition 1 (At-least-as-good). A node n is at-least-as-good as another node n0 (denoted n n0) w.r.t. KPI K if 8cP [K(n) c] P [K(n0) c], i.e., the cumulative distribution function (CDF) of the distribution K(n) is for every point c at most the CDF of the distribution of K(n0) in that point. An instantiation M is at-least-as-good as another instantiation M 0 w.r.t. KPI K if and only if the root node of M is at-least-as-good as the root node of M 0 w.r.t. K. Note that it is possible that individual values of K(n0) are better than K(n), but overall the values for n are better than n0.
If we have that a model M is at-least-as-good as a model M 0 for all (relevant) KPIs, then clearly M should dominate (or at least equal) M 0 and as a result it only makes sense to analyse M 0 if M needs to be analysed. Later on, we will see how we can derive this at-least-as-good relation. First, however, we will show how Petra uses this relation.
Graphically, the monotonicity transforms the collection of possible instantiations to a collection of possible related instantiations. Since there might be multiple KPIs in the framework, we obtain (di erent) relations for each of the KPIs (Fig. 4). The dots are the instantiations and an arrow between two dots indicates that the instantiation at the tail of the arrow is at-least-as-good as the instantiation at its head. The open dots indicate the most promising instantiations. By transitivity, if there exists a directed path from one instantiation to another instantiation, then the former instantiation is at-least-as-good as the latter w.r.t. the corresponding KPI.
With the monotonicity framework added, Petra analyses the possible instantiations in a speci c order. If M is at-least-as-good as M 0 on all KPIs, then M will be analysed by Petra before M 0 will be analysed. If M 0 is to be analysed by Petra and if at that point in time M has been dominated by some other model M 00, then M 0 cannot dominate M 00 and there is no use in analysing it. Otherwise, if M is not dominated, M 0 is analysed by Petra.
When an instantiation is dominated by other models, it creates a cut-o point along the partial orders for the various KPIs, as this instantiation is atleast-as-good (w.r.t. the KPI at hand) as every instantiation that can be reached by a directed path. As a result, if an instantiation is below the cut-o points for all KPIs, it is dominated by the previously analysed models and there is no use in analysing it.
To determine whether an instantiation is at-least-as-good as another instantiation, we need to check whether its root node is at-least-as-good-as the other root node. To determine this, we use a bottom-up approach, which uses the fact that both are instantiations of the same con gurable process model. As a result of this, we can relate two nodes in both instantiations in a straightforward way by determining whether they stem from the same node in the con gurable process model: They are related if and only if they stem from the same node. Note that hiding a part of the con gurable process model results in an automatic task with duration 0 in the instantiation. As a result, such an automatic task can be related to any other node. Furthermore, note that if a placeholder node is con gured as a node of one type (like seq) in one instantiation, and as a node of another type (like and) in another instantiation, it is possible that a node of one type is related to another node of another type.
For a task node, it is usually quite straightforward to check whether or not they are at-least-as-good as their related nodes: As both stem from the same node, they are equal, and hence at-least-as-good. For a block node, we need to look whether all relevant child nodes are at-least-as-good as their related nodes, which is where the bottom-up approach comes in. Based on the structures of both instantiations and using the fact which child nodes are at-least-as-good as their related nodes, we determine whether a give node in one instantiation is atleast-as-good as its related node in the other instantiation. With this approach, we decompose the problem into smaller problems and basically use patterns to identify which of the elements is better. If we can conclude that the one root node is at-least-as-good as the second root node, then we can conclude that the one process model is at-least-as-good as the second process model.
In our monotonicity framework, we assume there is a correspondence between node types and the e ects on the value of a KPI. This stems from the observation that some KPIs behave monotone in two avours, i.e., more is better (monitoring activities in the process for compliance) or less is better (costs). KPIs which do not behave monotone in that respect, e.g., wait time which can increase and decrease with the addition/removal of activities, cannot be captured in this framework.
Because we only take the structure of the instantiations into account, we restrict ourselves to the control- ow perspective in this paper. However, to be able to compare choice nodes (xor, def, or), we assume there is a probability associated with the outgoing edges of the choice node. This probability indicates the (relative) probability that the ow of control follows that path. Likewise, to be able to compare loop nodes (loopxor and loopdef), we assume that there is a probability associated with the outgoing edges to the redo and exit blocks. In the next section, we demonstrate the applicability of our approach by focussing on a single KPI. 5
The example KPI to be used in our monotonicity framework is the throughput time (sometimes also called sojourn time or lead time). The throughput time is the time it takes a case from start to end. We have chosen the throughput time since this KPI is well-studied and often considered for analysing process models. Using our monotonicity framework, we need to be able to take two instantiations (two Process Trees) and decide which instantiation is at-least-as-good (if any). As mentioned, we focus on the control- ow perspective. Therefore, we assume the other perspectives do not change between di erent instantiations. However, we do not disregard the other perspectives as this might lead to counter-intuitive results, e.g., if we have a choice between a fast and a slow branch, then reducing the amount of work for the slow branch and increasing the amount of work for the fast branch might actually increase the throughput time since the fast branch cannot handle more work. Therefore, we focus on reducing the amount of work for branches without increasing the amount of work for other branches. We go through the collection of nodes and present when a node is at-least-as-good as the related node (w.r.t. throughput time). A silent task (an automatic task with duration 0) is always at-least-as-good as any node, and can be ignored (when not related) in a seq or and block. Any other automatic task can be compared according Def. 1 with another automatic task. In all other cases, we cannot say whether an automatic task is at-least-asgood as the other node.
A manual task is at-least-as-good as the same manual task. In all other cases, we cannot say whether a manual task is at-least-as-good as the other node. Please note that, as mentioned earlier, we only take the control- ow perspective into account. If we would take the resource perspective into account, then we could check whether the same manual task would be performed by generally faster or less overloaded employees. In Fig. 5, the general case is depicted where every comparison between block nodes has to adhere to. A block node b is at-least-as-good as a related block node b0 if every child node c of b (except for silent tasks) is related to a child node c0 of b0 such that node c is at-least-as-good as node c0.
The general case is su cient for the seq, and, and event nodes which are related to nodes of the same type. Next to this, if b is an and node and b0 is a seq node and the general case holds, then we can also conclude that b is at-least-as-good as b0 since doing things is parallel is at-least-as-good as doing things in sequence for the throughput time. Finally, if b is a seq or and node and P1 P2
P3 τ ≥ ≥ ≥
P01 P02
P03 b0 is a loop node (loopxor, loopdef) and the do and the exit are the only children related of the loop, then b is at-least-as-good as b0. This comparison to the loop stems from the fact that do is executed at least once and is eventually followed by exit. Thus they are in a sequence.
For choices, we need more information, i.e., we need to know the probability of executing a particular child. Therefore, we extend the general case with probabilities yielding Fig. 6. Note that implicitly the general case also contains probabilities but these are all 1, e.g., in a sequence there is no option to not execute a particular child.
Comparing two xor/def nodes with each other requires that, apart from the comparison of the general case, the probabilities for the related nodes are the same. Note that in the general case, unrelated children of b are only allowed to be silent tasks, which means that these have a throughput time of 0 making them at-least-as-good as any unmapped child of b0. From this, with the requirement of equal probability between the related nodes, we know the same fraction of cases goes to unrelated nodes in both b and b0. For this fraction of cases, we know the unrelated children in b are at-least-as-good as the unrelated children in b0. Comparing two or nodes is similar to two xor/def nodes, only the probabilities of the children in b have to be at most the probabilities of the related children of b0. Note that the sum of the probabilities on the outgoing edges of an or is at least 1. The reasoning behind this at most is that more cases having to be executed by a particular node (i.e., a higher probability) does not lower the throughput time and thus is that node at-least-as-good as the related node. This also holds when comparing a xor/def with an or, i.e., the probabilities of the children of the xor/def have to be at most the probabilities of the related children in or whilst adhering to the general case.
Next to comparing choices with each other, we can also compare choices to seq and and using the earlier observation that the children of the seq and and have implicitly a probability of 1. The rules are the same as for the comparison with the or, i.e., the probabilities are at most the probabilities of the seq and and, and the general case is adhered to.
We can also compare choices to loop nodes. For this it is su cient to adhere to the general case and the probability of the child of b related to the redo should be at most the probability of the redo in b0. The intuition behind this is that the probability of the do and exit are both 1, i.e., they both are executed at HHHHH b seq and event loop xor/def or seq least once. Thus we have to make sure the child related to the redo is executed at most as often as the redo, i.e., the probability of the node related to the redo is at most the probability of the redo.
Finally, in order to compare two loop nodes, we need to have the general case. On top of this, we need that the probability of executing the redo of b is at most the probability of executing the redo of b0. The idea behind this is that the higher the probability of the redo, the more often the loop will be executed yielding a higher throughput time.
The requirements on the relation between two blocks are summarised in Table 1. The numbers indicate which requirements are to be adhered to in order for b to be at-least-as-good as b0. An explanation of the numbers is at the bottom of Table 1. 6
We have chosen an empirical evaluation over an asymptotic analysis since worstcase we still have to analyse all the possible instantiations. This comes from the fact that some models are incomparable (due to choices), and that, although some are at-least-as-good, the models have values for a KPI which are too close to each other making none of the models strictly better than another model.
For our empirical evaluation, we use the con gurable process model from Fig. 2. We want to show that we can prune a signi cant part of the instantiation space prior to analysis. To analyse an instantiation, we simulate it at least 30 Fig. 7: The various rounds of analysis with the instantiations which were analysed and their 95% con dence intervals. We started in round 1 with the 4 most promising instantiations. In round 2, we continued with the 5 most promising instantiations from the only model that survived the rst round. Finally, in round 3, we could conclude that all other instantiations are dominated. times using L-SIM: a simulation tool developed by Lanner3. To enable simulation, we have extended our con gurable process model with resource and timing information.
There are 144 possible instantiations from our running example (Fig. 2). Thus the collection of possible instantiations in Fig. 4 contains 144 dots. In Fig. 7, the various analysis rounds of our approach are depicted. Each round corresponds to analysing a group of instantiations which do not share an at-least-as-good relation and for which all instantiations that are at-least-as-good have already been analysed and are not dominated (yet) by another model. In the rst round, we start with 4 instantiations (depicted by the 4 ovals at the top) which were most promising, i.e., there was no instantiation which was at-least-as-good as one of these 4 instantiations.
After simulating the most promising instantiations (the 95% con dence intervals of the throughput times are depicted in the ovals), only 1 of these instantiations was signi cantly better than the other instantiations and was kept as one of the best models. For the second round, we obtained 5 other models which were most promising (and not yet analysed) from our monotonicity. Simulating each of these models resulted in 1 model being better than the other models in the second round. This model was added to the set of best models. In the third round, again 5 models were most promising and not yet analysed. By our monotonicity notion, we knew 4 of them did not need to be analysed as non-best models from the second round were at-least-as-good as these 4. The remaining 3 http://www.lanner.com/en/l-sim.cfm model was simulated and was signi cantly worse than the best models. Since none of the models from the third round made it to the set of best models, we could conclude that all other 130 instantiations were dominated. Therefore, there was no need to analyse the other models.
From the 144 instantiations, we only had to analyse 10, which means that only 6.9% of the possible instantiations had to be analysed. Analysing all models took a bit more than 50 minutes on a single core of 2.80 GHz (including some I/O handling). The average time per model is a little bit more than 20 seconds. Computing the monotonicity of the 144 models took a bit more than 2 seconds. Only analysing the 10 models, took around 3 minutes. Note that, in Def. 1, we used the CDF for determining whether one model is at-least-as-good as another model. Since with simulation we cannot determine the CDF, we have used the con dence intervals as an approximation of this CDF. 7
Within Petra, we analyse large amounts of instantiations from a con gurable process model. These analysed instantiations are projected on a Pareto front to only keep the instantiations that are most promising, according to some Key Performance Indicators (KPIs), for an organisation. Due to the possible large amount of variation point in a con gurable process model, and the resulting very large amount of possible instantiations, analysing each and every instantiation is very time consuming and unnecessary as most will never be considered by an organisation.
To prevent having to analyse all possible instantiations, using the fact that most instantiations will never be considered, we sort them according to their likelihood of appearing on the Pareto front. The sorting of the instantiations happens using our monotonicity framework. This framework can be extended to work with a multitude of KPIs.
We have applied our framework with a concrete KPI (throughput time) on the con gurable process model that was used as running example, and have shown that we can achieve a signi cant decrease in the amount of instantiations which need to be analysed (exceeding 90%). But these results are highly dependent on the model and on the characteristics of the KPIs.
This work shows promising results and we plan to extend this into a multitude of directions. We brie y sketch a panorama of future extensions. Currently, we still need to traverse the entire instantiation space to compute the ordering between models. In the ideal case, we can constructively create the con guration for the instantiations most promising for a particular KPI. Next to this, we also want to incorporate more KPIs into the framework. Furthermore, we want to generalise this work to also be able to compute monotonicity between two process models which are not necessarily instantiations from a single con gurable process model. Finally, we want to leverage some of the related work which de nes monotonicity on the parameters of the con gurable process model to our framework.