# Rank-based Heuristics for Optimizing the Execution of Product Data Models

Konstantinos Varvoutas11footnotemark: 1 Anastasios Gounaris22footnotemark: 2
Georgia Kougka33footnotemark: 3 Hajo A. Reijers44footnotemark: 4 Aristotle
University of Thessaloniki, Greece
<EMAIL_ADDRESS>Universiteit Utrecht,The Netherlands
<EMAIL_ADDRESS>
###### Abstract

The Product Data Model (PDM) is an example of a data-centric approach to
modelling information-intensive business processes, which offers flexibility
and facilitates process optimization. Because the approach is declarative in
nature, there may be multiple, alternative execution plans that can produce
the desired end product. To generate such plans, several heuristics have been
proposed in the literature. The contributions of this work are twofold: (i) we
propose new heuristics that capitalize on established techniques for
optimizing data-intensive workflows in terms of execution time and cost and
transfer them to business processes; and (ii) we extensively evaluate the
existing solutions. Our results shed light on the merits of each heuristic and
show that our new heuristics can yield significant benefits.

###### keywords:

data-centric processes, process optimization , PDM

##  1 Introduction

Data-centric approaches have been emerging in the last two decades as an
alternative to the more mainstream activity-oriented modelling approaches for
business processes [1, 2, 3]. As stated in [1] _“The central idea behind data-
centric approaches is that data objects/elements/artifacts can be used to
enhance a process-oriented design or even to serve as the fundament for such a
design”_. Apart from better modelling processing where data element production
drives the whole process, data-centric approaches are reported to provide
increased reusability and flexibility in execution.

In this work, we focus on a particular data-centric modelling approach, namely
a Product Data Model (PDM)-oriented one. This approach is tailored to
information-intensive processes and is declarative in nature. The main driver
for PDM, as also reported in [1], is process optimization next to flexibility.
A PDM instance focuses on describing what is needed in order to deliver an
information product rather than the exact way to achieve this goal. The
declarative model is accompanied by a method to generate workflow designs,
which is referred to as _Product Based Workflow Support (PBWS)_ [4]. PBWS
presents a set of heuristics for PDMs with the purpose of enhancing the
performance on a case-by-case manner. PBWS improves upon a previous method,
called _Product Based Workflow Design (PBWD)_ [5], where the burden of
defining the sequence of actions rests with the workflow designer. While PBWD
merely assists in this task through presenting the alternatives, PBWS defines
the sequential order of task execution based on provided task metadata.

The problem we target in the present paper is to define the order of actions
(a.k.a. operations) to execute in a process described by a PDM. Our
optimization criteria include both execution cost and time duration. We aim to
improve the efficiency of existing heuristic techniques in [4] for defining
such an ordering. Heuristic solutions are intuitive in their rationale, easy
to implement and are of low computational complexity. However, the existing
solutions fail to benefit from established techniques in the areas of
optimization for workflows for data analytics and database query execution
plans. Techniques from these domains adopt principled cost-based approaches
[6, 7, 8] and provide polynomial approximate solutions to NP-hard problems.
Inspired by the existence of such techniques, in our heuristics, we suggest to
consider both the time and the cost of each operation in a PDM model and the
probability of this operation to lead to an early termination of the process
in a combined manner. This saves time and resources. More specifically, we
make a twofold contribution:

  1. 1.

We propose a new set of heuristics for choosing the next operation to be
performed in a PDM for a specific case to optimize time duration and/or cost.
Our proposals differ in the exact optimization criteria they take into
account, the capability to establish whether an execution of an operation is
meaningful, and in the manner they consider dependencies between the
successful execution of operations.

  2. 2.

We perform an extensive experimental evaluation of the available heuristics
and we show that our proposals yield benefits in terms of time, cost or a
combination of both compared to previous heuristics, for the average case.

Initial work to generate these contributions has appeared in [9]. The main
extensions to our initial work include (i) an investigation of additional
heuristics that differ in their rationale regarding the meaningfulness of
operations and grouping of operation; (ii) an entirely new implementation that
addresses a number of limitations, such as not considering a PDM graph as a
hypergraph555The implementation is publicly available from
https://github.com/kmvarvou/rank_based_heuristics ; (iii) new experiments
using additional, real-world PDM models and random parameterization, which
provide a deeper insight into the performance of our proposal; and (iv) an
investigation of the degree of approximation by the heuristics compared to the
optimal solution.

The remainder of this paper is structured as follows. In Section 2, we present
the PDM underpinnings of the techniques evaluated. Section 3 introduces our
proposal and Section 4 discusses implementation. We evaluate the candidate
techniques in Section 5. Section 6 deals with the related work and we conclude
in Section 7, where we also briefly discuss limitations and future work.

##  2 Background

In this section, we first introduce the main principles and notation regarding
the PDM in Section 2.1 and we then discuss PDM execution in Section 2.2.

###  2.1 The PDM

Figure 1: The PDM mortgage example from [4]

A PDM is used to represent the structure of a _workflow product_ in a rooted
graph-like manner, similar to a Bill of Material [4, 10]. A _workflow_ is a
term used in many different ways; in our work, we use this term to refer to a
(potentially software system-supported) process that passes information from
one participant to another for action emphasizing on how the tasks or
activities of the process are carried out; this is in line with textbooks such
as [11, 12]. The notion of a _workflow product_ covers the desired outcome of
the process and the corresponding workflow _without_ providing a concrete
execution plan on how this product is derived [4].

More specifically, PDMs describe the required elements for yielding the
desired product in the root, where example (informational) products include
decision on whether to grant an approval to a specific admission request,
approval of a mortgage application, and so on. In Figure 1, we present such an
example of a PDM for a classical mortgage application. The _vertices_ (or
graph _nodes_) in this structure correspond to data elements, which is the
information that is processed in the workflow. The _edges_ correspond to
operations to produce such data elements; operations are denoted as $Op$. Each
operation has a set of quantitative metadata assigned to it, which typically
differ between _process instances_ (or, equivalently, _process cases_).

The final product of the process is to determine the value of the root (or top
or end product) vertex. To this end, values of multiple other data elements
need to be determined from the leaves to the root, as specified by the edges
of the graph. In essence, operations correspond to actions that are applied on
the valued data elements to produce values for vertices downstream. Each
operation may have zero or more input data elements. However, it produces the
value for exactly one output data element at most; this occurs in the case
that its execution is successful.

Let us assume that there are $n$ operations $Op_{i},~{}i\in\\{1,\dots,n\\}$
and $m$ data elements in a PDM. An operation in a PDM is represented by a
sextuple, denoted as

$Op_{i}=<Out_{i},Input_{i},cost_{i},time_{i},prob_{i},cond_{i}>$

$Out_{i}$ is the data element $j\in\\{1,\dots,m\\}$ that can be produced by
$Op_{i}$. $Input_{i}$ contains the prerequisite data elements that serve as
input to $Op_{i}$. To avoid cycles, which correspond to execution deadlocks,
$Out_{i}$ cannot belong to the input set of any operations producing the
elements in its own input set as well. For example, in Figure 1, the tuple
$<A,\\{B,C,D\\},\dots>$ which corresponds to $Op_{01}$, describes the fact
that $Op_{01}$ can be applied only if data elements $B$, $C$ and $D$ are
available and the execution of $Op_{01}$ _may_ lead to the production of the
value of the $A$ data element. Each operation is also accompanied by the
following metadata, as defined in its sextuple; these metadata allow for cost-
based decisions:

  * 1.

_Cost ( $cost_{i}$)_, which represents the cost associated with executing the
operation $Op_{i}$, where $i\in\\{1,....,n\\}$.

  * 2.

_Time ( $time_{i}$)_, which represents the time required for the complete
execution of $Op_{i}$.

  * 3.

_Probability ( $prob_{i}$)_, which represents the probability that $Op_{i}$ is
executed _unsuccessfully_ , therefore not producing its output element.

  * 4.

_Conditions ( $cond_{i}$)_, which represent requirements regarding the value
of the input elements. These requirements must be met, if the operation
$Op_{i}$ is to be executed, meaning that the existence of all input elements
is not sufficient; this is crucial in rendering PDMs useful in practice.

Examples of these metadata are depicted in the table at the bottom right of
Figure 1. It is important to note that these metadata can refer to specific
cases, e.g., in a loan application scenario, the cost may change according to
the type of loan requested.

In the case where an element has zero input elements, it is called a _leaf
element_. Commonly, leaf elements are provided as input to the process (if
their production is always guaranteed); in the figure, elements such as $B$,
$F$ and $E$ are leaf elements. In addition, an operation is considered
_executable_ when all of its input data elements have been produced, e.g., the
operations that produce these elements have been successfully performed.
Finally, if an operation has multiple data element inputs, these inputs are
bundled in the graph, e.g., as is the case for elements $B$, $C$ and $D$ for
$Op_{01}$.

In summary, the PDM describes the operations that can be performed to produce
the root element, along with their inter-dependencies. Not all operations need
to be executed for the production of the root element. A data element may be
produced through multiple operations, e.g., in the same example of Figure 1,
$A$ which is the root element, can be determined in three manners, namely,
$Op_{01}$, $Op_{02}$ and $Op_{03}$. As a final note, we clarify that having a
single root element does not prevent to model processes with multiple final
outcomes through connecting all the corresponding final output elements to an
artificial root element with zero-cost operations.

###  2.2 Execution of a PDM

Product data models can be executed directly, without the need of a process
model to support the execution of the process they represent [13]. This is
attributed to their flexible structure, which allows for the existence of
multiple paths for the production of a particular element in a PDM. A _path_
is derived by a sub-graph of a PDM [14] after performing a topological
sorting. An ordered set, or equivalently, a sequence of operations that lead
to the production of the root element is called a _complete path_.

Each specific occurrence of the execution of a PDM is referred to as an
_instance_ and is associated with a distinct _execution path_ , i.e., a
sequence of operations chosen for this specific instance. Overall, a PDM does
not specify how the end information product is created exactly. In this sense,
it allows for multiple execution paths that produce the desired information
product. In general, the same data element in a PDM can be produced by
multiple operations, each having a different set of input data elements, which
allows for the existence of alternative ways of producing it. Therefore, PDMs
usually feature alternative complete execution paths, each with a different
cost and time duration.

The execution path of each instance may be determined either in an incremental
step-by-step manner, where the next operation is determined only after the
completion of the execution of the last operation, or before execution in
full. As will be explained shortly, in this work, we follow the former
approach, where the execution path is incrementally built. Given that the
execution path described the order of operation execution, in our context this
path coincides with the process _workflow_.

In order to evaluate the performance of our proposed approach, we also need to
introduce the notion of the _optimal path_. As explained above, a PDM usually
features several alternative paths that produce its root element. An optimal
path for a specific instance is a complete path that achieves the best
possible performance in terms of a specific objective, such as execution cost,
for that instance. A methodology to assess the extent of the approximation of
a heuristic is to calculate the optimal path, for each of the evaluation’s
instances, and use it as a reference point; i.e., detect all the complete
paths and find the best performing one between them. According to the formal
definition of the complete path, as presented by Comuzzi et al. [15], the PDM
mortgage example (Figure 1) contains at least 3 complete paths; these paths
may share some operations in common. These paths are presented in detail in
Table 1 and, without loss of generality, let us assume that for the purpose of
this work, we focus only on the cost metric only. According to the cost
metric, the total cost of a path is the sum of the cost of the operations it
contains.

A key observation is that paths differing in the ordering of their constituent
operations can be excluded from the minimal set of the complete paths because
they do not differ in their total cost.666Here, we assume that an operation’s
cost is constant and does not differ depending on its position in the path.
That is, when we are interested only in the cost of the complete paths, these
need not be interpreted in their typical sense in directed graphs but can be
deemed as sets rather than lists/ sequences. For example, we do not include
$Op_{08},Op_{09},Op_{10},Op_{02},Op_{05},Op_{06},Op_{01}$ as a separate path
in the table, because it is equivalent to _Path 1_ in terms of performance.
Ignoring the ordering of the operations does not have any impact on both the
cost and the time duration of the corresponding execution path, due to the
fact that operations are executed sequentially.

Path | Operations | Total Cost
---|---|---
_Path 1_ | $Op_{07},Op_{04}$ | 3
_Path 2_ | $Op_{10},Op_{03}$ | 12
_Path 3_ | $Op_{10},Op_{09},Op_{08},Op_{02},Op_{05},Op_{06},Op_{01}$ | 13
Table 1: Minimal set of complete Paths of the mortgage example PDM in Figure
1.

There are two additional important remarks when determining the optimal path
of a PDM instance. The first one relates to the specific attribute values that
are specific to this instance, which implies that the optimal path may be
different across multiple instances of the same PDM process. This typically
occurs when the time and durations of the operations fall into a certain
range, i.e., they are not the same for all instances. But even if the cost and
the duration of an operation is fixed, when the probability of failure is not
0 or 1, the execution of an operation is not deterministic in a manner that
may impact on the optimality of a path. The second remark extends the point
above and relates to the _feasibility_ of the optimal path, which may alter
during the instance’s execution, due to a failed operation. For example, _Path
1_ is the optimal path of the mortgage PDM in terms of cost, since it has a
total cost of 3. However, the feasibility of _Path 1_ depends on the
successful outcome of its operations. If $Op_{04}$ fails, then _Path 1_ is no
longer feasible, and another path becomes the optimal one. In this case, the
feasible path with the lowest cost for such an instance is _Path 2_. Overall,
the optimal path for a specific instance reflects this instance’s specif
details in terms of element availability, and therefore path feasibility.

##  3 Proposal

The optimization problem we deal with is: _which paths of operations to choose
for a specific PDM instance in order to optimize user-defined quantitative
objectives of cost and time?_

We address this problem in a case-by-case manner, i.e., if different instances
come with different metadata, such as $cost_{i}$, $time_{i}$ and $prob_{i}$
values, different sequences of operations may be devised. Moreover, the
execution path is built incrementally taking into account whether the last
operation chosen was executed successfully or not.

First, in Section 3.1 we describe the simpler form of our solutions, which
rely on the _rank_ metric. Then, in Sections 3.2 and 3.3, we extend our
solutions to allow for more judicious decisions.

###  3.1 Main solution

There are two high-level strategies for the calculation of an optimal
execution path corresponding to a PDM instance, namely a global and a local
one. A global strategy considers the effect of each decision on future steps.
It takes into account the complete set of alternative paths that produce the
end product to optimize the execution performance of each case. Instead, a
local strategy adopts a step-by-step approach, meaning that, at each step, it
examines the set of executable operations and chooses the best one, according
to a particular metric, e.g. cost of execution. As explained in [4], a global
strategy does not scale as the problem is NP-hard. For this reason, in this
work, we exclusively deal with low-polynomial local strategy heuristics. For
small-scale models, we also derive the optimal solution using exhaustive
techniques. This is done to provide insights into how closely our heuristics
approximate the optimal solutions.

Our approach to constructing execution paths relies on treating operations in
a manner similar to knock-out business process activities, and the manner
their optimal ordering is decided. This also bears similarities to the way
data analytics operators and database selections and joins are ordered [16,
17, 8, 6, 7]. A knock-out activity is an activity whose execution leads
directly to the completion of the process [16]. Typically, operators with low
cost and low selectivity (i.e., keeping as few tokens or data tuples as
possible) are ordered earlier. The metaphor in our case is that reaching the
root element is similar to knock-out activities eliminating tokens in the
sense that the path is completed. For example, the execution of $Op_{03}$ in
Figure 1, which produces the root element $A$ is a knock-out operation. Then,
the optimal ordering needs to take into account the probability of an
operation to produce the end element and the corresponding cost or execution
duration. An important point is that an operation may also contribute to the
production of the root element indirectly, e.g., through a sequence of
operations starting with that operation and ending to the root element.

More specifically, at each step where the next operation is selected, we
consider all the executable operations (i.e., those with all input elements
available) and we choose the one with the highest _rank_ value. The rank value
of an operation $Op_{i}$ is defined as follows:

$rank(Op_{i})=\frac{\prod_{Op^{\prime}\in\pi(Op_{i})}1-prob_{Op^{\prime}}}{\sum_{Op^{\prime}\in\pi(Op_{i})}Cost_{Op^{\prime}}}$
(1)

where $\pi(Op_{i})$ is the path from $Op_{i}$ (including) to an operation
directly producing the root. The function essentially defines that the rank
value is (i) proportional to the probability of $\pi(Op_{i})$ to execute
without any operation failures and (ii) inversely proportional to the sum of
the costs of the operations in the path.

operation | path | rank value
---|---|---
$Op_{02}$ | $Op_{02},Op_{01}$ | 0.09025
$Op_{03}$ | $Op_{03}$ | 0.105556
Table 2: The executable operations along with their rank values in the
example.

Figure 2: The two execution paths that lead to the production of the root
element and correspond to operations $Op_{02}$ and $Op_{03}$ respectively.

_Example:_ In the example in Figure 1, let us assume a state in which all leaf
elements have been produced already except element $E$, for which $Op_{07}$
was not executed successfully. Thus, in the next step, there are two
executable operations, namely $Op_{02}$ and $Op_{03}$. Table 2 presents the
alternatives, which are also highlighted in Figure 2. Based on its attributes,
$Op_{02}$ has the following ranking value: $rank(Op_{02})=0.9025/10=0.09025$.
This is because, while $Op_{02}$ may not lead to a process termination
directly, we consider $Op_{02}$ as part of a path that leads indirectly to the
root, that is the path: ($Op_{02},Op_{01}$). Therefore, we use as probability
of this path, the probability of _success_ of the operations in the whole path
as denoted in the nominator of the rank function, which is
$(1-prob_{Op_{02}})*(1-prob_{Op_{01}})=0.95*0.95=0.9025$ and as cost, the
aggregate cost of the whole path, which is
$Cost_{Op_{01}}+Cost_{Op_{02}}=5+5=10$. On the other hand,
$rank(Op_{03})=0.95/9=0.105556$. The probability 0.95, in the nominator, is
the probability of the _successful_ execution of $Op_{03}$ because it is the
successful execution of $Op_{03}$ that produces the root element $A$ and
therefore, completes the workflow execution. Based on these values, $Op_{03}$
is selected for execution.

Note that we have not discussed how we treat the case where there are multiple
paths starting from the same operation yet. The relevant explanations and
clarifications are provided in the next section.

In summary, the proposed rank-based heuristic chooses, at each step, the
operation, which is ready to be executed and has the highest rank value. This
heuristic comes in three variants. The first one uses the formula above. The
other two modify the denominator in the rank formula and employ (i) the sum of
the operation duration times and (ii) the sum of both the normalized operation
cost and times, respectively777In our preliminary work [9], the latter flavor
employed the product of the cost and times; we have modified this variant as
the sum of these attributes exhibits higher performance.. As such, the other
two variants focus more on time duration and a combination of both metrics,
respectively.

Building upon this three-flavored heuristic, we introduce an additional multi-
variant heuristic next. The extended rank-based heuristic employs the same
rank formula, but it is different in the fact that it relies on the notion of
_meaningless operations_.

###  3.2 Meaningful and meaningless operations

In this section, we introduce the notion of _meaningless_ operations, which
forms the basis for our extended rank-based heuristics. These heuristics do
not rely on the rank value solely to decide the next operation.

Remember that the execution of a PDM and the corresponding execution path
construction is dynamic and differs across multiple instances of the same
model even if the same heuristic is employed. Such variability is dependent on
whether an operation chosen for execution is successful or not. The failure of
a particular operation may render any complete path containing this operation
unfeasible and any operations belonging to unfeasible paths exclusively have
no reason to execute. For example, consider the PDM of Figure 1. Elements $F$,
$G$ and $H$ are all inputs to $Op_{02}$. We assume an execution instance where
the first operation selected for execution is $Op_{08}$, and it is executed
unsuccessfully. Consequently, regarding $Op_{09}$, which produces element $G$,
there is no reason to execute, despite being executable. Due to the failure of
$Op_{08}$, $Op_{02}$ cannot be executed, and therefore the execution of
$Op_{09}$ would not lead to the production of the root element in any case. On
the contrary, $Op_{10}$, which produces element $H$ can still be executed due
to its contribution to the possible execution of $Op_{03}$. Operations, such
as $Op_{02}$ will be referred to as meaningless operations. Below, we present
the formal definition.

More specifically, at any state while constructing an execution path referring
to a PDM instance, if an operation $Op_{i},~{}i\in\\{1,\dots,n\\}$, which
produces element _A_ has already been executed unsuccessfully, an operation
$Op_{j},~{}j\neq i$ and $i\in\\{1,\dots,n\\}$ that has not already executed,
which produces element _B_ , is a _meaningless_ operation if and only if both
conditions below hold:

  1. 1.

There exists at least one operation that has not executed yet, such that it
features both elements _A_ and _B_ as its inputs.

  2. 2.

There exists no operation that has not executed yet such that it features
element _B_ as its input without having element _A_ as its input.

The rationale behind the conditions above is as follows. First, we will reason
that if any of the two statements does not hold, then we cannot discard the
corresponding operation. If there is no operation that has both _A_ and _B_ in
its input, then the fact that _A_ cannot be produced does not block the path
from _OpB_ to the root. The second statement says that, for $Op_{j}$ to be
meaningless, for every operation that _B_ appears on its input list, _A_ has
to be on the same list as well. If this does not hold, then there is at least
one path connecting $Op_{j}$ to the root that remains feasible. Finally, we
have to also prove that when both conditions hold, then executing $Op_{j}$
does not contribute to the production of the root element. This is true, since
all paths to the root are blocked due to the co-presence of _A_ and _B_ in the
input list of an operation in such a path.

The notion of the meaningful operations is leveraged in two ways in the
extended rank-based heuristic. First, only operations deemed non-meaningless
are considered when choosing the next operation to be executed. In this
manner, the cost of operations, whose execution doesn’t contribute anything to
the production of the root element is saved. Therefore, the consideration of
only meaningful operations constitutes an effective pruning of sub-optimal
choices. Furthermore, it is also used to detect interdependent data elements.
This notion is explained in detail, in the next subsection, which provides the
complete view of the extended heuristic.

###  3.3 Grouping Interdependent Elements

A main idea behind the extended rank-based heuristic is, during deciding the
next operation to execute, to group elements, whose impact on the production
of the root element relies on the availability of each other. For example, the
usability of element $G$ depends upon the availability of element $F$ (and
vice versa) in order to have any impact on the production of the root element,
via $Op_{02}$. By contrast, element $H$’s impact is independent of the
availability of any other element because it can trigger an operation leading
to the root element, either directly or indirectly, without any further
prerequisites. Based on this observation, the group-based heuristic assigns a
rank value to the element $G$ taking into account its interdependence with
element $F$ (and vice versa).

In this heuristic, elements are grouped together whenever they are deemed to
be interdependent. More formally, two elements are interdependent when they
appear as inputs in exactly the same set of operations, like elements $F$ and
$G$ mentioned above. In practice, to detect which elements should be grouped
together, we rely on the notion of meaningless operations, which has been
introduced before. For each element $j$, $j\in\\{1,\dots,m\\}$, we determine
which elements are dependent upon its availability. That is, for each element
$j$, we determine the set of elements whose production would be _meaningless_
if this particular element $j$ could not be produced. For every element in the
latter set, its distance from the root is increased by the production cost of
element $j$. For example, a data element dependent on two other elements would
have its distance from the root increased by the sum of the production costs
of these two elements.

##  4 Implementation

To apply our heuristics described previously, which involve paths from
arbitrary vertices to the root element, we need a data model that represents a
PDM as a directed graph, on which traditional graph theoretical algorithms,
such as shortest paths can be computed. In this section, we first discuss the
transformation of PDMs to directed graphs in Section 4.1. Then, we continue
with explaining the exact manner we detect paths and meaningfulness of
operations in Section 4.2 and we close discussing the data structures and
complexities of the underlying algorithms in Section 4.3.

###  4.1 Representation of PDMs

A PDM is a special type of directed hypergraph [18], which generalize directed
graphs [19]. More specifically, the edge of a hypergraph, called hyperedge,
may have multiple source and destination vertices. Moreover, in a PDM, there
can be more than one edge connecting two vertices, similar to a multigraph.
For example, on the left pert of Figure 3, we focus on an excerpt of a social
insurance PDM, shown in full in Figure 4 and used in our evaluation. In this
part of the PDM, the elements $i11$ and $i18$ are connected directly by two
different operations. The same applies to elements $i15$ and $i18$. To
transform the PDM graph into a directed graph representation, we add a set of
_dummy_ , i.e. artificial, vertices in addition to the original data elements.
These vertices are added with the view to enforcing that the number of direct
edges between every pair of element vertices is at most one.

Figure 3: A part of an original PDM model (left) and the insertion of a dummy
vertex (right).

In Figure 3(right), we illustrate the addition of a dummy vertex in the
aforementioned case of the social insurance PDM of Figure 4. In the
transformed model, a new element $i50$ has been added. In addition to the new
element, a new artificial operation, which takes $i50$ as an input and
produces element $i18$, has also been added. Such artificial operations do not
modify any semantics of the original model. To ensure that the addition of
dummy elements has no impact on the execution behavior of the PDM, the
attributes of the corresponding artificial operations are set as follows: the
execution cost, the execution time and the probability of failure are all set
to 0.

###  4.2 Computing the rank value

In the rank-based solutions, we have used the notion of $\pi(Op_{i})$, which
is a path from $Op_{i}$ to an operation producing the root element. However,
in general, there is not a single such path, which implies that there is no
deterministic manner to compute $rank(Op_{i})$ and more importantly, costly
paths to be selected instead of less expensive ones.

To address this issue, that is to provide an efficient and deterministic
manner to compute $rank(Op_{i})$ in any PDM, we adopt the following
methodology. We use the probability of failure of data element production,
exactly as provided in the metadata table to assign weights to the graph
edges. Then, we choose the path for which the sum of these probabilities is
the smallest one as the representative path of the operator $Op_{i}$, i.e., we
reduce the problem to a shortest path one for which simple algorithms, such as
Dijkstra’s, can be employed. In addition, the path in the denominator need not
be the same as in the nominator and can be detected applying directly a
shortest path algorithm after assigning to each graph edge the corresponding
operation cost (or time duration) as its weight.

###  4.3 Data Structures and Complexities

There are four auxiliary data structures involved: (i) a dictionary structure,
e.g., implemented as a HashMap that stores the operation metadata for each
operation; (ii) a list that contains the operations ready to be executed;
(iii) a list that contains the elements already produced and (iv) a dictionary
that connects the output element of an operation to the operations that it
serves as their input. The latter is required to identify meaningless
operations.

In the beginning, the two lists are initialized through a simple traversal of
the operation metadata. The complexity of this is $O(nm)$ where $n$ is the
number of operations and $m$ the number of the vertices in the graph. The $n$
and $m$ values include also the dummy zero-cost operations and vertices.

Then, the heuristics repeat as many steps as the number of operations in the
execution path, which is up to $n$. In each step, the next operation is chosen
after examining $n$ operations at most. Also, after the selection and
execution of the next operation, $O(m)$ checks are performed to update the
list of eligible operations.888More efficient implementation can be devised,
but since PDMs are not particularly large containing a few dozens of
operations and elements, employing more sophisticated data structures does not
pay off. Finding the shortest path from a root element is at most $O(nlogm)$
using an algorithm such as Dijkstra. Identifying meaningless operations after
each failed operation execution is $O(nm)$ using the second dictionary. Thus
the overall complexity of the rank-based techniques is $O(n^{2}(n+m)logm)$,
which is $O(n^{3}logm)$, since $n\geq m$.

##  5 Evaluation

We begin this section with the description of the experimental setting and the
competitors in Section 5.1. The main results are presented in Sections
5.2-5.3. Section 5.4 investigates the impact of early termination and the
efficiency of our proposals. In Section 5.5, we discuss additional issues,
such as comparison against the results in our earlier work. Finally, Section
5.6 discusses issues regarding the deviation of optimal solutions, when it is
feasible to compute them.

Figure 4: The PDM social insurance example from [5]

###  5.1 Competitors, test PDMs and experimental settings

Our competitors are the local strategies used by the PBWS method in [4]
comprise the following heuristics, which are referred to as _existing
heuristics_ :

  1. 1.

_Random_ : the next operation is randomly selected from the set of executable
operations.

  2. 2.

_Lowest Cost_ : the operation with the lowest cost is selected to be executed
next.

  3. 3.

_Shortest Time_ : the operation with the shortest time is selected to be
executed next.

  4. 4.

_Lowest Failure Probability_ : the operation with the lowest probability of
not being executed successfully is selected.

  5. 5.

_Shortest Distance to Root Element_ : the operation with the shortest distance
to the root element (measured in the total number of operations) is selected.

  6. 6.

_Shortest Remaining Process Time_ : the operation with the shortest remaining
processing time (measured as the sum of the processing times of the operations
on the path to the root element) is selected.

  7. 7.

_Shortest Remaining Cost_ : the operation with the shortest remaining cost
(measured as the sum of the costs of the operations on the path to the root
element) is selected.

Note that the last heuristic is not explicitly mentioned in [4] but it is
trivial to devise it.

We evaluate our proposed approach using three PDMs found in the literature.
The first one is the mortgage example that was presented in Section 2, while
the second one, shown in Figure 4, represents a larger process from a social
insurance company [5]. These two PDMs constitute the evaluation set that was
also used in our previous work [9]. To provide a more thorough evaluation, we
expanded this set with an additional, third PDM, as shown in Figure 5, which
represents a monitoring process from [14].

To evaluate the 7 existing heuristics and our 6 rank-based flavors, we created
two experimental settings. Each consists of 10K random cases for each of the
aforementioned PDMs. The 6 rank-based flavors are the three ones, as described
in the main part of Section 3 along with their 3 extended counterparts that
perform grouping and leverage the detection of meaningless operations.

In the first setting, we rely on the original metadata included with each PDM,
as these are reported in their respective publications (see the Appendix).
Based on these metadata, we generate, for each operation’s cost, time, and
failure probability attributes, values according to a $N(\mu,\sigma^{2})$
(normal distribution). Here $\mu$ is the original value of that particular
operation and $\sigma^{2}$ is the variance of the data. For each of the three
PDMs the mean value of the cost and time attributes is derived from the
original metadata. In the first and the third PDM, the standard deviation was
set as a fraction of these mean values, 0.5X and 0.33X, respectively
(otherwise, the variance would be very large, something that we explore in the
second setting). In the second PDM, the variance was set according to the
original metadata accompanying the model.

In the second setting, and with a view to evaluating the behavior of the PDM
operation ordering solutions in a wider range of metadata values, we also rely
on synthetic values for the attributes of the PDMs’ operations. However, in
this case, the cost and time attributes were assigned (integer) values drawn
randomly from a uniform distribution in the [0,10] range, i.e., these
attributes may differ up to an order of magnitude. The probability of failure
was assigned values in the [0.0, 1.0] range, i.e., we consider the complete
range from guaranteed success to certain failure.

Figure 5: The PDM monitoring example from [14]

In both settings, we do not explicitly consider the probability of meeting
conditions, since this probability affects the production of the output data
element and it can be deemed as covered by the failure probability. Finally,
in order to conduct a fair comparison between the alternatives that
encapsulate the detection of meaningless operations and the other ones, we
initially report results only regarding the instances, in which the root
element could be successfully produced.

###  5.2 First Setting: operation attributes follow a Gaussian distribution

Heuristic | Aggregate | Aggregate | PDM1 | PDM1 | PDM2 | PDM2 | PDM3 | PDM3
---|---|---|---|---|---|---|---|---
| Cost | Time | Cost | Time | Cost | Time | Cost | Time
Existing heuristics
Random | 3.59 | 3.85 | 3.31 | 3.73 | 5.53 | 5.48 | 3.26 | 3.45
Lowest Cost | 1.93 | 3.12 | 1.82 | 3.10 | 3.07 | 4.53 | 1.67 | 2.70
Shortest Time | 2.58 | 1.85 | 2.11 | 1.65 | 4.57 | 3.08 | 2.41 | 1.66
Lowest Failure Probability | 3.50 | 3.61 | 4.61 | 4.91 | 2.19 | 2.38 | 1.36 | 1.34
Root Distance | 1.98 | 2.00 | 1.69 | 1.53 | 2.20 | 2.23 | 2.19 | 2.38
Remaining Cost | 1.46 | 1.78 | 1.16 | 1.21 | 1.55 | 2.28 | 1.72 | 2.19
Remaining Time | 1.93 | 1.59 | 1.67 | 1.36 | 2.31 | 1.57 | 2.07 | 1.82
Our proposals
Rank-Cost | 1.36 | 1.91 | 1.32 | 1.60 | 1.64 | 2.45 | 1.32 | 2.04
Rank-Time | 2.02 | 1.49 | 1.97 | 1.59 | 2.49 | 1.65 | 1.92 | 1.33
Rank-Combo | 1.55 | 1.52 | 1.58 | 1.51 | 1.72 | 1.72 | 1.46 | 1.45
Rank-Extended-Cost | 1.22 | 1.67 | 1.03 | 1.17 | 1.48 | 2.04 | 1.32 | 2.04
Rank-Extended-Time | 1.59 | 1.23 | 1.10 | 1.04 | 2.05 | 1.48 | 1.92 | 1.33
Rank-Extended-Combo | 1.33 | 1.31 | 1.11 | 1.08 | 1.59 | 1.59 | 1.46 | 1.45

Table 3: Normalized performance of each heuristic for the first setting (the
lowest the better).

We begin our discussion of the first experimental setting, where the operation
costs follow a gaussian distribution with mean values based on real-world
evidence, with the summary results in Table 3. The values are normalized, so
that, in each experiment instance, the value 1 corresponds to the most
efficient cost or time time, respectively. In the table, the best performing
existing heuristic and the best performing variant of our proposals are marked
in bold. There are two main observations that can be drawn:

  1. 1.

Our proposal consistently outperforms existing heuristics and more
importantly, there are variants that consistently outperform all other
variants: when the optimization objective is cost, our extended rank-based
variant aiming at cost yield the lowest cost both on the average case and when
checking each PDM case study separately; similarly, when the optimization
objective is time, the best performing variant is the extended variant aiming
at time explicitly. On average, the improvements over the best heuristic
overall are 16.5% lower cost (when aiming at cost) and 22.6% shorter time
(when aiming at time).

  2. 2.

There is no dominant solution among the existing heuristics. As shown in the
upper part of the table, a different existing heuristic is the best performing
one when considering all PDMS and when considering each PDM separately.
However, the best performing heuristics outperform the non-extended rank-based
proposals.

Next, we move to Figure 6, where we see the percentage of cases, where each
solution achieved the best performance. The values do not sum up to 100%
because, in a random instance, more than one solution may have yielded the
best performance and/or some instances do not lead to the production of the
root element, as already explained. As shown, our extended rank heuristics
yield better execution plans more frequently than the other variants.

Figure 6: The percentage of cases where each heuristic achieved the best
result in terms of cost (left) and time (right) in the first setting of the
evaluation.

###  5.3 Second Setting: operation attributes follow a uniform distribution

Heuristic | Aggregate | Aggregate | PDM1 | PDM1 | PDM2 | PDM2 | PDM3 | PDM3
---|---|---|---|---|---|---|---|---
| Cost | Time | Cost | Time | Cost | Time | Cost | Time
Existing heuristics
Random | 4.11 | 4.08 | 3.97 | 4.01 | 5.68 | 5.48 | 2.11 | 2.13
Lowest Cost | 2.39 | 3.66 | 2.02 | 3.62 | 3.61 | 4.86 | 1.65 | 1.94
Shortest Time | 3.68 | 2.39 | 3.57 | 2.00 | 5.08 | 3.66 | 1.88 | 1.61
Lowest Failure Probability | 2.89 | 2.80 | 2.82 | 2.73 | 3.84 | 3.72 | 1.63 | 1.63
Root Distance | 2.53 | 2.57 | 3.02 | 3.04 | 2.11 | 2.21 | 1.68 | 1.71
Remaining Cost | 1.55 | 2.39 | 1.49 | 2.57 | 1.75 | 2.48 | 1.40 | 1.68
Remaining Time | 2.40 | 1.56 | 2.54 | 1.48 | 2.59 | 1.81 | 1.68 | 1.41
Our proposals
Rank-Cost | 1.32 | 1.64 | 1.31 | 1.75 | 1.36 | 1.61 | 1.27 | 1.37
Rank-Time | 1.67 | 1.31 | 1.79 | 1.29 | 1.64 | 1.37 | 1.39 | 1.27
Rank-Combo | 1.44 | 1.42 | 1.47 | 1.45 | 1.44 | 1.43 | 1.31 | 1.30
Rank-Extended-Cost | 1.20 | 1.41 | 1.13 | 1.38 | 1.29 | 1.49 | 1.27 | 1.37
Rank-Extended-Time | 1.44 | 1.20 | 1.42 | 1.13 | 1.51 | 1.29 | 1.39 | 1.27
Rank-Extended-Combo | 1.28 | 1.27 | 1.13 | 1.24 | 1.34 | 1.33 | 1.31 | 1.30

Table 4: Normalized performance of each heuristic for the second setting (the
lowest the better).

In the second setting, the metadata values follow a uniform distribution. The
advantage of this setting is that it covers a broader range of values; the
disadvantage is that it may depart from real-world settings. Nevertheless, the
outcomes of these experiments further strengthen the evidence that our rank-
based variants advance the state-of-the-art. More specifically, the main
observation drawn from Table 4 is twofold:

  1. 1.

Our extended rank based variant continues to consistently outperform existing
heuristics. The average improvements over all random instances are lower cost
by 22.6% and shorter time by 23.1%.

  2. 2.

In this setting, there is a clear winner among the existing heuristics, namely
_Shortest Remaining Cost_ for the cost objective and _Shortest Remaining
Process Time_ for the time objective. However, these heuristics cannot
outperform event the non-extended rank-based heuristics, an observation
already made in [9].

Figure 7: The percentage of cases where each heuristic achieved the best
result in terms of cost (left) and time (right) in the second setting of the
evaluation.

Finally, as shown in Figure 7, in this setting, there is a stronger
correlation between the most frequent and the best performing solution.

###  5.4 Impact of early termination and time overheads

In this section, we discuss in detail the impact of the notion of meaningless
operations which is leveraged by our extended rank-based solutions. Thus far,
we have ignored all failed instances. Remember that an execution instance is
considered successful, if the root element is produced. On the contrary, when
the production of the root element is not possible, i.e. due to the failed
execution of some operations, the execution instance is considered
unsuccessful. In such cases, its execution may be terminated earlier, as
already discussed.

In failed instances, the performance of every heuristic that does not employ
early termination converges to the same cost and time duration. The extended
rank-based variants, which are equipped with the early termination capability,
are inherently more suited for such failed instances. In particular, our
proposals exhibit a 13.8% and 13.4% improvement in terms of cost and time,
respectively, in the first setting. In the second setting, the improvements
are even better; 23.5% lower cost and 23.4% shorter time. In PDM3, there are
no failed instances that lead to a benefit (we discuss this PDM further
below).

Finally, the overhead time to run the heuristics is extremely low: on a Ryzen
5 3600x CPU with 16GB RAM, our rank-based heuristics take less than 1.34
milliseconds for each case of the social insurance PDM; the other heuristics
are even faster and the times are negligible for the small PDM.

###  5.5 Additional Discussion

In this section, we discuss the performance of our revised and extended rank-
based solutions in comparison to the rank-based solutions, originally
presented in our earlier work [9]. In the mortgage and social insurance PDMs,
the extended techniques demonstrated significant improvements over the
original variants, performing on average, 13.52% better. In the monitoring
process PDM however, the new proposals did not manage to lead to any
improvements displaying exactly the same level of performance as the original
flavors. This can be attributed to the particular characteristics of the
structure of this PDM: (i) none of its elements are deemed as interdependent
and therefore, they cannot be grouped together; (ii) this PDM also does not
contain any operation pairings which comply with the notion of meaningless
operations. As a result, the PDM fails to benefit from the two novel notions
that were introduced in the extended rank-based techniques.

Finally, it should be noted that the performance of our approach was
significantly better in the second setting. This can be attributed to the
increased range of values in that setting. In particular, the higher range of
values in terms of probability of failure leads to an increase in path
variability, favoring our approach.

###  5.6 Deviation from Optimal Solutions

Figure 8: The average deviation of each heuristic compared to the optimal path
for the first setting (left) and the second setting (right) regarding the
mortgage PDM.

In this experiment, we rely on the notion of _optimal path_ , presented in
Section 2, to further evaluate our approach. For each execution instance, we
determine the optimal path, in terms of cost and path feasibility. Then, the
optimal path is directly compared to the paths discovered by each of the
heuristics, for that specific instance. This comparison is conducted for the
mortgage PDM only, presented in Figure 1, which is small enough so that
optimal paths can be derived.

Figure 8 presents the average deviation from the optimal path of each
heuristic, in terms of cost during the execution of the mortgage PDM. In the
first setting, the mean cost of the optimal path is 2.74. We can see that even
in this simple PDM, even the best performing rank-based heuristic deviate by
more than two times. However, narrower deviations are observed in the second
setting, where the best performing rank-based variant incurs a 42.9% higher
cost on average.

The main conclusion is that although our proposed heuristics significantly
outperform existing ones, there is still plenty of room for improvements.
Devising fast heuristics that yield results that are closer to the optimal
ones remains a challenging open issue.

##  6 Related Work

As stated in the introduction, an increasing amount of data-centric approaches
have been developed as part of a general trend in the area of Business Process
Management (BPM). Despite this recent interest, Business Process Improvement
or Redesign, one of the key areas of BPM remains relatively undeveloped in
terms of automated algorithmic solutions. In a recent survey that aims to
evaluate several data-centric process approaches, this lack of focus on
process optimization or redesign is highlighted [1]. Out of the 14 data-
centric methods examined, only 2 of them identify the objective of business
process optimization as a motive for their development. These two methods are
Product Based Workflow Design (PBWD) [5] and its extension, Product Based
Workflow Support (PBWS) [4], upon which we build our work.

In [14, 15], Comuzzi et. al. present an ant-colony based approach, which aims
to discover the optimal path in a PDM. A key element of this approach is the
distinction between the phases of path discovery and execution. However,
whenever an operation executes unsuccessfully, then the entire instance is
terminated. This is a limitation compared to the direct PDM execution approach
of [4] upon which we build our work, which allows to continue the execution
via considering the remaining operations. In a similar context, the work in
[20] follows an ant-colony based approach to optimize the execution of a
business process, represented as a Workflow Net rather than a PDM, as we do.

Regarding task ordering in declarative process models, the work of Barba et.
al. presents a recommendation approach that aims to optimally order the
remaining executable activities of an ongoing process instance [21, 22]. In a
subsequent work [23], the same authors present an approach that computes a set
of potentially optimal plans for a declarative model, discarding the sub-
optimal ones. This set of plans is then combined into a single, configurable,
BPMN model. In all these works, the task ordering heuristics are a subset of
those examined in [4], since the focus is mainly on producing valid execution
plans rather than optimal ones according to a cost function. However, contrary
to our solution, the focus is also on optimal resource scheduling.

An extensive part of recent business process literature focuses on process
model variability [24]. For example, the work in [24] is motivated by the fact
that different municipalities perform the same objective using different, but
equivalent, processes. To accommodate such variability, it introduces the
configurable process tree, a novel formalism capable of representing a family
of process variants in a single model. Additionally, this methodology allows a
specific set of process models to be selected according to a set of Key
Performance Indicators (KPIs). This bears some similarity to the way PBWS and
our solutions exploit the existence of alternative paths in order to optimize
each case’s performance. The main difference lies in the fact that, in our
case, these alternatives are different paths of a single, existing PDM model,
while in [24], there is an attempt to create a model that contains alternative
paths to cover all cases. In the same context, the work in [25] presents a set
of approaches for the extraction of a configurable process model from a
collection of event logs, which represents variants of a single process.
Furthermore, the issue of assessing the quality of different process model
configurations [26] has also been explored. Lastly, the work in [27] presents
an approach that produces a set of ranked imperative models based on an input
declarative model; the imperative models are, in turn, used to generate
recommendations. Such an approach focuses on flexibility and essentially
checks all possible plans, thus it cannot scale.

Additionally, there are proposals considering various optimization objectives,
such as the techniques in [28], where a set of heuristics for changing the
relative ordering of activities is introduced. However, these heuristics
cannot be applied to PDMs because they assume that all operations need to be
executed, whereas, in PDMs, it suffices to execute a subset of operations for
a process to complete. Finally, our work relates to declarative process models
[29, 30]; e.g., our workflow design solution can be seen as a promising means
to derive executable model structures out of such declarative models although
providing a complete methodology to achieve this remains an open issue.

Our rank-based solutions are inspired by solutions to optimize data analytics
workflows [8], but they constitute novel optimization variants tailored to
PDM-modeled business processed. The work in [31] highlights the benefits of
integrating BPM and data analytics, by proposing the utilization of Big Data
processing for the purpose of analyzing business process data. Similarly,
there have been efforts to transfer the results of data analytics workflow
optimization to business process workflows [17]. Despite these efforts, the
topic of fully exploiting the know-how in data-intensive workflows for
optimizing the execution of business processes still remains in its infancy.

In the more general research area of BPM, there has been a rise in research
related to the field of decision management. Many works are focusing on PDMs,
the recently introduced _Decision Model and Notation (DMN)_ and other decision
modelling approaches. The work in [32] proposes an automated methodology that
extracts the decision logic from an input PDM workflow and produces a BPMN/DMN
model as an output. The work in [33] proposes an automated approach that
derives decision models from enriched event logs. Moreover, the _Decision Data
Model (DDM)_ , an extension of the PDM, was introduced in [34]; this work
focuses on the data perspective of the decision making of a process. All these
efforts are orthogonal to our work.

##  7 Conclusion and Future Work

This work focuses on business processes modelled according to the declarative
PDM paradigm. PDM is a powerful modeling approach for business processes that
aim to produce informational products, e.g., whether to grant an approval to a
specific admission request, without specifying the workflow execution plan.
The contribution of this work is that it proposes and evaluates novel
heuristics for yielding optimized workflow designs, i.e., execution plans, in
terms of execution cost and time on a case-by-case basis. Our solution is
inspired by and extends optimization solutions in query processing and
workflows for data analytics. Its main novelty lies in the fact that, when
choosing the next operation to be executed, it takes into consideration both
the probability to produce the root element and the cost of the operation. We
also consider explicitly operation inter-dependencies and discuss
implementation issues. The evaluation is based on three real-world PDM
examples and tens of thousands of random metadata instantiations for these
PDMs following realistic probability distributions. Our experimental results
show that, although in specific cases different heuristics may perform better,
our proposals consistently outperform existing solutions. They yield, on
average, 16.5% lower cost and 22.6% shorter time, when the metadata are based
on real-world data. For random metadata following a uniform distribution
within a predefined range, the improvements are even higher.

This work aims to open a new avenue in which the execution of declarative
process models is optimized. However, to achieve this goal, two main
directions need to be explored in depth in the future. Firstly, our approach
needs to cover additional declarative modelling approaches, such as [29] and
also consider processes with multiple outputs. Secondly, and more importantly,
a complete cost and time optimization solution should also consider aspects,
such as resource utilization, parallel task execution and smaller deviations
from optimal solutions. Especially with regards to the issue of resource
allocation, the current solution presented in this work implicitly assumes
that all resources required for an operation execution are always available;
extending our algorithms to account for resource unavailability, non-
deterministic behavior, waiting times and fatigue is essential to increase the
applicability of the proposal in real-world settings. Additionally, we aim to
expand the scope of our work by investigating the composition of activities,
similarly to [35], which impacts on the PDMs themselves apart from their
execution only.

_Acknowledgment._ The research work was supported by the Hellenic Foundation
for Research and Innovation (H.F.R.I.) under the “First Call for H.F.R.I.
Research Projects to support Faculty members and Researchers and the
procurement of high-cost research equipment grant” (Project Number:1052,
Project Name: DataflowOpt).

## References

  * [1] H. A. Reijers, I. T. P. Vanderfeesten, M. G. A. Plomp, P. V. Gorp, D. Fahland, W. L. M. van der Crommert, H. D. D. Garcia, Evaluating data-centric process approaches: Does the human factor factor in?, Software and Systems Modeling 16 (3) (2017) 649–662.
  * [2] V. Künzle, M. Reichert, Philharmonicflows: Towards a framework for object-aware process management, Journal of Software Maintenance 23 (4) (2011) 205–244.
  * [3] R. Henriques, A. R. Silva, Object-centered process modeling: Principles to model data-intensive systems, in: Business Process Management Workshops - BPM 2010 International Workshops and Education Track, Hoboken, NJ, USA, September 13-15, 2010, Revised Selected Papers, 2010, pp. 683–694.
  * [4] I. T. P. Vanderfeesten, H. A. Reijers, W. M. P. van der Aalst, Product-based workflow support, Inf. Syst. 36 (2) (2011) 517–535.
  * [5] H. A. Reijers, S. Limam, W. M. P. van der Aalst, Product-based workflow design, J. Manag. Inf. Syst. 20 (1) (2003) 229–262.
  * [6] T. Ibaraki, T. Kameda, On the optimal nesting order for computing n-relational joins, ACM Trans. Database Syst. 9 (3) (1984) 482–502.
  * [7] R. Krishnamurthy, H. Boral, C. Zaniolo, Optimization of nonrecursive queries, in: VLDB, 1986, pp. 128–137.
  * [8] G. Kougka, A. Gounaris, A. Simitsis, The many faces of data-centric workflow optimization: a survey, Int. J. Data Sci. Anal. 6 (2) (2018) 81–107.
  * [9] K. Varvoutas, A. Gounaris, Evaluation of heuristics for product data models, in: Business Process Management Workshops - BPM 2020 International Workshops, Seville, Spain, September 13-18, 2020, Revised Selected Papers, Vol. 397 of Lecture Notes in Business Information Processing, Springer, 2020, pp. 355–366.
  * [10] J. A. Orlicky, G. W. Plossl, O. W. Wight, Structuring the bill of material for mrp, Operations management: critical perspectives on business and management 58 (2003).
  * [11] M. Dumas, M. L. Rosa, J. Mendling, H. A. Reijers, Fundamentals of Business Process Management, Second Edition, Springer, 2018.
  * [12] V. Stiehl, Process-Driven Applications with BPMN, Springer, 2014.
  * [13] I. Vanderfeesten, Product-based design and support of workflow processes, Ph.D. thesis, Industrial Engineering and Innovation Sciences, proefschrift. (2009).  doi:10.6100/IR640011.
  * [14] M. Comuzzi, I. T. P. Vanderfeesten, Product-based workflow design for monitoring of collaborative business processes, in: H. Mouratidis, C. Rolland (Eds.), Advanced Information Systems Engineering, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 154–168.
  * [15] M. Comuzzi, I. T. P. Vanderfeesten, T. Wang, Optimized cross-organizational business process monitoring: Design and enactment, Inf. Sci. 244 (2013) 107–118.  doi:10.1016/j.ins.2013.04.036.
URL https://doi.org/10.1016/j.ins.2013.04.036

  * [16] W. M. P. van der Aalst, Re-engineering knock-out processes, Decision Support Systems 30 (4) (2001) 451 – 468.  doi:https://doi.org/10.1016/S0167-9236(00)00136-6.
  * [17] G. Kougka, K. Varvoutas, A. Gounaris, K. Vergidis, G. Tsakalidis, On knowledge transfer from cost-based optimization of data-centric workflows to business process redesign, Trans. Large Scale Data Knowl. Centered Syst. 43 (2020) 62–85.
  * [18] M. Comuzzi, Optimal paths in business processes: Framework and applications, in: E. Teniente, M. Weidlich (Eds.), Business Process Management Workshops, Springer International Publishing, Cham, 2018, pp. 107–123.
  * [19] G. Ausiello, P. G. Franciosa, D. Frigioni, Directed hypergraphs: Problems, algorithmic results, and a novel decremental approach, in: Theoretical Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, 2001, pp. 312–328.
  * [20] Z. Huang, X. Lu, H. Duan, A task operation model for resource allocation optimization in business process management, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans 42 (5) (2012) 1256–1270.  doi:10.1109/TSMCA.2012.2187889.
  * [21] I. Barba, B. Weber, C. D. Valle, A. J. Ramirez, User recommendations for the optimized execution of business processes, Data Knowl. Eng. 86 (2013) 61–84.  doi:10.1016/j.datak.2013.01.004.
URL https://doi.org/10.1016/j.datak.2013.01.004

  * [22] I. Barba, B. Weber, C. D. Valle, Supporting the optimized execution of business processes through recommendations, in: F. Daniel, K. Barkaoui, S. Dustdar (Eds.), Business Process Management Workshops - BPM 2011 International Workshops, Clermont-Ferrand, France, August 29, 2011, Revised Selected Papers, Part I, Vol. 99 of Lecture Notes in Business Information Processing, Springer, 2011, pp. 135–140.  doi:10.1007/978-3-642-28108-2\\_12.
URL https://doi.org/10.1007/978-3-642-28108-2_12

  * [23] A. Jiménez-Ramírez, B. Weber, I. Barba, C. D. Valle, Generating optimized configurable business process models in scenarios subject to uncertainty, Inf. Softw. Technol. 57 (2015) 571–594.  doi:10.1016/j.infsof.2014.06.006.
URL https://doi.org/10.1016/j.infsof.2014.06.006

  * [24] D. Schunselaar, Configurable process trees : elicitation, analysis, and enactment, Ph.D. thesis, Department of Mathematics and Computer Science, proefschrift (10 2016).
  * [25] J. C. A. M. Buijs, B. F. van Dongen, W. M. P. van der Aalst, Mining configurable process models from collections of event logs, in: F. Daniel, J. Wang, B. Weber (Eds.), Business Process Management - 11th International Conference, BPM 2013, Beijing, China, August 26-30, 2013. Proceedings, Vol. 8094 of Lecture Notes in Computer Science, pp. 33–48.
  * [26] J. Buijs, B. Dongen, van, W. M. P. Aalst, van der, Discovering and navigating a collection of process models using multiple quality dimensions, in: Business Process Management Workshops (BPM 2013 International Workshops, Beijing, China, August 26, 2013, Revised Papers), Springer, 2014, pp. 3–14.
  * [27] S. Mertens, F. Gailly, G. Poels, Generating business process recommendations with a population-based meta-heuristic, in: F. Fournier, J. Mendling (Eds.), Business Process Management Workshops - BPM 2014 International Workshops, Eindhoven, The Netherlands, September 7-8, 2014, Revised Papers, Vol. 202 of Lecture Notes in Business Information Processing, Springer, 2014, pp. 516–528.  doi:10.1007/978-3-319-15895-2\\_44.
URL https://doi.org/10.1007/978-3-319-15895-2_44

  * [28] W. M. P. van der Aalst, Re-engineering knock-out processes, Decis. Support Syst. 30 (4) (2001) 451–468.
  * [29] M. Pesic, H. Schonenberg, W. M. P. van der Aalst, Declare: Full support for loosely-structured processes, in: 11th IEEE International Enterprise Distributed Object Computing Conference (EDOC 2007), 2007, pp. 287–300.
  * [30] N. Chawla, I. King, A. Sperduti, User-guided discovery of declarative process models, 2011.
  * [31] S. Sakr, Z. Maamar, A. Awad, B. Benatallah, W. M. P. van der Aalst, Business process analytics and big data systems: A roadmap to bridge the gap, IEEE Access 6 (2018) 77308–77320.
  * [32] H. van der Aa, H. Leopold, K. Batoulis, M. Weske, H. A. Reijers, Integrated process and decision modeling for data-driven processes, in: Business Process Management BPM Workshops, Vol. 256, 2015, pp. 405–417.
  * [33] J. Smedt, F. Hasić, S. V. Broucke, J. Vanthienen, Holistic discovery of decision models from process execution data, Knowl. Based Syst. 183 (2019).
  * [34] R. Petrusel, I. Vanderfeesten, C. C. Dolean, D. Mican, Making decision process knowledge explicit using the decision data model, in: W. Abramowicz (Ed.), Business Information Systems, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 172–184.
  * [35] H. van der Aa, H. A. Reijers, I. Vanderfeesten, Designing like a pro: The automated composition of workflow activities, Computers in Industry 75 (2016) 162–177.  doi:https://doi.org/10.1016/j.compind.2015.04.005.

##  Appendix A PDM original metadata

In this section, we present in Table 5 the original data of the product data
models that were used in the first setting of the evaluation in Section 5.2 of
our work.

ID | Output | Input | Cost | Failure Probability
---|---|---|---|---
Op01 | i01 | i25, i27 | 0.0 | 0.0
Op02 | i02 | i25, i37 | 0.0 | 0.0
Op03 | i03 | i33, i37 | 0.0 | 0.0
Op04 | i04 | i33, i37 | 0.0 | 0.0
Op05 | i05 | i37, i45 | 0.0 | 0.0
Op06 | i06 | i21, i37 | 0.0 | 0.0
Op07 | i07 | i24, i37 | 0.0 | 0.0
Op08 | i08 | i23, i37 | 0.0 | 0.0
Op09 | i24 | i39, i37 | 0.0 | 0.0
Op10 | i10 | i13, i14, i34, i37, i42 | 0.0 | 0.0
Op11 | i11 | i31 | 0.6 | 0.0
Op12 | i15 | i16 | 0.0 | 0.003
Op13 | i15 | i17 | 0.0 | 0.997
Op14 | i15 | i16, i17 | 0.0 | 0.0
Op15 | i16 | i25, i30, i35, i36, i44 | 5.61 | 0.0
Op16 | i17 | i25, i30 | 6.1 | 0.0
Op17 | i18 | i01 | 0.0 | 0.991
Op18 | i18 | i02 | 0.0 | 0.987
Op19 | i18 | i08 | 0.0 | 0.984
Op20 | i18 | i09 | 0.0 | 0.998
Op21 | i18 | i10 | 0.0 | 0.932
Op22 | i18 | i11 | 0.0 | 0.981
Op23 | i18 | i15 | 0.0 | 0.79
Op24 | i18 | i09, i11, i15 | 0.0 | 0.0
Op25 | i28 | i25, i37 | 0.0 | 0.0
Op26 | i29 | i25, i30, i35, i36 | 0.0 | 0.0
Op27 | i30 | i32, i37, i43 | 0.0 | 0.0
Op28 | i31 | i29, i40, i48 | 0.0 | 0.0
Op29 | i32 | i01, i02, i03, i04, i05, i06, i07, i08, i10, i27, i28 | 0.0 | 0.0
Op30 | i34 | i36, i37, i41 | 4.2 | 0.0
Op31 | i40 | i39, i41 | 0.3 | 0.0
Op32 | i42 | i47 | 0.3 | 0.0
Op33 | i43 | i39, i49 | 0.6 | 0.0
Op34 | i13 | - | 0.08 | 0.0
Op35 | i14 | - | 0.08 | 0.0
Op36 | i21 | - | 0.0 | 0.0
Op37 | i23 | - | 0.67 | 0.0
Op38 | i24 | - | 0.0 | 0.0
Op39 | i25 | - | 0.0 | 0.0
Op40 | i27 | - | 0.08 | 0.0
Op41 | i33 | - | 0.0 | 0.0
Op42 | i35 | - | 0.0 | 0.0
Op43 | i36 | - | 1.0 | 0.0
Op44 | i37 | - | 1.67 | 0.0
Op45 | i39 | - | 0.17 | 0.0
Op46 | i41 | - | 0.0 | 0.0
Op47 | i44 | - | 0.0 | 0.0
Op48 | i45 | - | 0.0 | 0.0
Op49 | i47 | - | 0.33 | 0.0
Op50 | i48 | - | 0.0 | 0.0
Op51 | i49 | - | 0.0 | 0.0

Table 5: Operation attributes of the social insurance PDM.

Next, in Table 6, we present the data of the monitoring process product data
model.

ID | Output | Input | Cost | Quality | Failure Probability
---|---|---|---|---|---
Op01 | i1 | i2, i3 | 0.0 | 1.0 | 0.0
Op02 | i3 | i4 | 0.6 | 0.3 | 0.0
Op03 | i3 | i4, i5 | 0.8 | 0.8 | 0.0
Op04 | i3 | i5 | 0.1 | 0.5 | 0.0
Op05 | i2 | i6 | 0.1 | 0.2 | 0.0
Op06 | i2 | i7 | 0.8 | 1 | 0.0
Op07 | i2 | i8, i10 | 0.8 | 1.0 | 0.0
Op08 | i2 | i8, i11 | 0.6 | 0.7 | 0.0
Op09 | i2 | i9, i10 | 0.6 | 0.7 | 0.0
Op10 | i2 | i9, i11 | 0.5 | 0.5 | 0.0
Op11 | i4 | - | 0.2 | 1.0 | 0.1
Op12 | i5 | - | 0.7 | 1.0 | 0.3
Op13 | i6 | - | 1.0 | 1.0 | 0.3
Op14 | i7 | - | 0.8 | 1 | 0.1
Op15 | i8 | - | 0.5 | 1 | 0.37
Op16 | i9 | - | 0.3 | 1 | 0.3
Op17 | i10 | - | 0.3 | 1 | 0.3
Op18 | i11 | - | 0.1 | 1 | 0.2
Table 6: Operation attributes of the monitoring process PDM.