Controlling Time-Awareness
in Modularized Processes
Andreas Lanz1, Roberto Posenato2, Carlo Combi2, and Manfred Reichert1
1Institute of Databases and Information Systems, Ulm University, Germany
2Department of Computer Science, University of Verona, Italy
Abstract.
The proper handling of temporal process constraints is crucial
in many application domains. A sophisticated support of time-aware
processes, however, is still missing in contemporary information systems.
As a particular challenge, temporal constraints must be also handled for
modularized processes (i.e., processes comprising subprocesses), enabling
the reuse of process knowledge as well as the modular design of complex
processes. This paper focuses on the representation and support of such
time-aware modularized processes.
Keywords:
Process-aware Information System, Temporal Constraints,
Subprocess, Process Modularity, Controllability
1 Introduction
The proper support of temporal process constraints is indispensable in many
application domains. Although it has received increasing attention in the research
community [
6
][
8
][
1
], a sophisticated support of time-aware processes is still
missing in contemporary process-aware information systems (PAIS). It is further
widely acknowledged that the capability to modularly design process schemata
constitutes a fundamental requirement for obtaining comprehensible and re-usable
process schemas [14].
At first glance, temporal process constraints and process modularity seem to
be orthogonal features that may be managed in an independent way. When taking
a closer view on them, however, it turns out that modularity in combination with
the reuse of time-aware processes requires the ability to represent the overall
temporal behavior of a process. This way, temporal constraints of a process
containing time-aware subprocesses can be evaluated in a true modular way, i.e.,
without replacing the subprocess tasks with their (temporal) components.
To the best of our knowledge, the issue of representing the overall temporal
properties of a process has not been considered in literature so far. This paper,
therefore, focuses on the representation and support of time-aware modularized
processes. In particular, we introduce a sound and complete method to derive
the duration restrictions of a time-aware process in such a way that its temporal
properties are completely described. Then, we show how this characterization of
a process can be merged with other temporal constraints when re-using it as a
(a) Main process.
Z
T0
:PatEv
[2,4][6,8]1
[1,1]
P0P1
P2T8
:TrExp
[1,3][5,5]
1
[1,1] E
E[1,4]S E[1,1]S
E[1,4]S
E[1,4]S
E[1,4]S
E[1,4]S
E[1,5]S
E[1,5]S
E[1,1]S
S[30,45]S
Process Repository
. . .
NonPharmR
Z
1
[1,1]
T1
:ADLsEv
[1,2][3,4]
T2
:DevId
[2,2][3,3]
T3
:ThermMod
[1,3][9,9]
1
[1,1] E
E[1,1]S
E[1,2]S
E[1,4]S
E[1,2]S
E[1,5]S
E[1,5]S
E[1,1]S
(b) Subprocess P0.
PharmR
Z
T6
:CntrEv
[1,2][4,5]
T7
:DrgSp
[1,1][7,7]E
E[1,1]S E[1,5]S E[1,1]S
(c) Subprocess P2.
PhysEx
Z
T4
: AqEx
[1,1][4,4]
T5
: LndEx
[1,2][4,5]E
E[1,1]S E[1,8]S E[1,1]S
(d) Subprocess P1.
. . .
Fig. 1. Motivating example: The process for managing osteoarthritis.
subprocess of a modularized process. In accordance with recent research contribu-
tions, we focus on the dynamic controllability (DC) of time-aware processes [
10
].
In general, DC corresponds to the capability of a process engine to execute a
process schema for all allowed durations of all tasks, while still satisfying all
temporal constraints; i.e., DC ensures that it is possible to execute a process
schema without any need to restrict the allowed durations of a task for satisfying
all temporal constraints. In this context, task durations are called contingent as
they are not under the control of the process engine.
As a motivating scenario, consider a high-level specification of an excerpt of a
clinical guideline related to the management of osteoarthritis of the hand, hip and
knee [
7
]. A possible schema for this process is depicted in Fig. 1. After completing
the initial Patient Evaluation (task
T0
:
PatEv
) two parallel branches become
activated. The first one is composed of process Non-Pharmacologic Recommenda-
tion (
P0
:
NonPharmR
) followed by process Specification of Physical Exercises (
P1
:
PhysEx
). The second one consists of process Pharmacologic Recommendation (
P2
:
PharmR
) followed by a Treatment Explanation to the patient (task
T8
:
TrExp
).
As depicted in Fig. 1,
P0
,
P1
, and
P2
constitute subprocesses from a process
repository which, in turn, are composed of other tasks and are re-usable in other
clinical processes (e.g., related to other pathologies). In detail, Non-Pharmacologic
Recommendation
P0
consists of two parallel branches: The first one evaluates
the patient’s ability to perform activities of daily live (task
T1
:
ADLsEv
) followed
by the identification of needed assistive devices (task
T2
:
DevId
). The second
branch consists of giving instructions to the patient related to the use of thermal
modalities (task
T3
:
ThermMod
). In turn, the Specification of Physical Exercises
(i.e.,
P1
) consists of the specification of aquatic exercises (task
T4
:
AqEx
) followed
by the specification of land exercises (task
T5
:
LndEx
). Finally, Pharmacologic
Recommendation (i.e.,
P2
) consists of the evaluation of contraindications (task
T6:CntrEval) followed by a drug specification (task T7:DrgSp).
We enrich these process schemas with temporal constraints that need to be
obeyed to guarantee the successful completion of each step of the therapy. They
allow for the temporal characterization of tasks, edges and gateways, according
to the concepts introduced in [
10
]. Note that the durations of tasks are not
completely under the control of the process engines as these tasks are carried out
by human users (e.g., doctors, nurses). Therefore, task durations are represented
as guarded ranges. Such a duration range may be partially restricted by the
system during process execution to ensure successful completion of the processes.
For example, task T6has temporal constraint [1,2][4,5]meaning that prior to
the execution of the task its duration may be restricted, but in any case the
minimum required duration must not exceed 2time units and the maximum
duration cannot be constrained below 4(e.g., a duration of [3,5] or [1,2] would
not be allowed). As another example consider task T7with temporal constraint
[1
,
1][7
,
7]
. The latter means that this task may last 1to 7time units and
all possible durations shall be allowed during process execution. This ensures
that the user executing the task has enough flexibility to successfully complete
the task. Constraints on gateways and edges are standard temporal constraints,
specifying the possible durations (within a range), which are under the control of
the process engine. The two main research questions addressed in this paper are:
1.
How can the overall temporal behavior of a process be represented (cf. Sect. 3)?
Addressing this question is a fundamental prerequisite for being able to
provide some kind of modularity from the temporal perspective as well. Note
that without such characterization, it would be necessary to re-compute the
temporal features of a subprocess each time it is used in a modularized process.
As will be shown, a subprocess can be represented as a kind of extended
guarded range. On one hand the duration of the subprocess can be controlled
to some extent due to the nature of the contained temporal constraints; on
the other, it cannot be completely controlled since the contingent durations
of the contained tasks must be guaranteed.
2.
How to apply such knowledge when using a process as a subprocess inside
a modularized process, in order to avoid having to re-analyze the internal
constraints of the subprocess (Sect. 4)? This will, for example, enable us to
store time-aware processes including their overall temporal properties inside
a process repository and to reuse them in a truly modular fashion.
2 Background and Related Work
In literature, there exists considerable work on managing temporal constraints for
business processes [
3
][
8
][
1
]. These approaches focus on issues like the modeling
and verification of time-aware processes. In [
5
], an extended version of the
Critical Path Method known from project planning is used. Simple Temporal
Networks with Uncertainty (STNU) [
13
] are used as basic formalism in [
3
], whereas
authors in [
2
][
8
] use Conditional Simple Temporal Networks with Uncertainty
for checking the DC of process schemas. This paper relies on Simple Temporal
Network with Partially Shrinkable Uncertainty (STNPSU), an extension of STNU
where contingent links are extended for a more flexible management of temporal
constraints [10].
An STNPSU [
10
] is a directed weighted graph (cf. Fig. 2) where nodes
represent time-point variables (timepoints), usually corresponding to the start
or end of activities, and edges
A[x, y]B
, called requirement links, represent a
lower and an upper bound constraint on the distance between the two timepoints
it connects; e.g.,
A[x, y]B
represents the constraint that timepoint
B
has to
occur between
x
and
y
time units after the occurrence of
A
(i.e.,
x≤B−A≤y
).
In an STNPSU, it is possible to characterize certain timepoints as contingent
timepoints, meaning that their value cannot be decided by the system executing
the STNPSU, but is decided by the environment at run time. Each contingent
timepoint has one incoming edge, called guarded link, drawn with a double line,
e.g.,
A[x, x0][y0, y]C
. A guarded link
A[x, x0][y0, y]C
consists of a pseudo-contingent
duration range [
x, y
]augmented with two guards, the lower guard
x0
and the upper
guard
y0
[
10
].
A
is called the activation timepoint. Before executing a guarded
link, its duration range [
x, y
]can be modified. However, any modification must be
done in a way respecting the corresponding guards, i.e.,
x≤x0
and
y≥y0
. When
activating a guarded link
A[x∗, x0][y0, y∗]C
(i.e., when executing timepoint
A
), the
current value [
x∗, y∗
]of the duration range becomes a fully contingent range,
which is then made available to the environment for executing timepoint
C
. That
is, once
A
is executed,
C
is guaranteed to be executed such that
C−A∈
[
x∗, y∗
]
holds. However, the particular time at which
C
is executed is uncontrollable since
it is decided by the environment; i.e., it can be only observed when it happens.
More formally, an STNPSU is a triple
(T,C,G)
, where
T
is a set of timepoints,
C
is a set of requirement links
X[u, v]Y
, and
G
is a set of guarded links each having
the form
A[x, x0][y0, y]C
with
A
and
C
being timepoints and 0
< x ≤y < ∞
,
x≤x0
, and 0
< y0≤y
. It is noteworthy that guarded links may be used to
represent two different types of constraints: If
x0< y0
holds, a guarded link
represents a temporal constraint with a partially contingent range. Particularly,
the guarded link represents a constraint with a contingent (i.e., unshrinkable)
core [
x0, y0
]
⊆
[
x, y
]. In turn, if
x0≥y0
holds, a guarded link represents a temporal
constraint with a partially shrinkable range with a guarded core [y0, x0].
Furthermore, each STNPSU is associated with a distance graph
D
= (
T,E
),
derived from the upper and lower bound constraints [
10
][
13
]. In the distance
graph, each link between a pair of timepoints
A
and
B
is represented as two
ordinary edges in
E
:
AyB
, representing the constraint
B≤A
+
y
, and
A−xB
,
for the constraint
B≥A
+
x
,
x, y ∈R
. Moreover, for each guarded link between
a pair of timepoints
A
and
C
,
E
contains two other labeled edges, called lower
and upper case labeled values. A lower case labeled value,
Ac:x0C
, represents
the fact that
C
cannot be forced to be executed at a time greater than
x0
after
A
, i.e., it is not possible to add a constraint
A−x00 C, x0< x00
to the network. In
turn, an upper case labeled value,
AC:−y0C
, represents the fact that
C
cannot
be forced to be executed at a time less than
y0
after
A
, i.e., it is not possible to
add a constraint Ay00 C, y00 < y0to the network.
Algorithm 1: STNPSU-DC-Check(G)
Input: G= (T,C,G): STNPSU graph instance to analyze.
Output: the dynamic controllability of G.
1D:= distance graph of G;
2for 1to CutOffBound do // CutOffBound=O(|T |)
3D0:= Dwithout lower case labels and with upper ones as normal labels ;
4if (D0has a negative cycle) then return false;
5Generate new edges in Dusing edge-generation rules;
6if (no edges generated) then return true;
7return false;
These two kinds of labels are fundamental for determining the dynamic
controllability of the network as explained in the following. Note that these two
representations of an STNPSU can be used interchangeably.
An STNPSU is denoted as dynamically controllable (DC), if there exists a
strategy for executing its timepoints in such a way that: i) all constraints in the
network can be satisfied, no matter how the execution of any guarded link turns
out, and ii) for any other guarded link
A[x, x0][y0, y]C
the lower bound
x
never
must be increased beyond its lower guard
x0
and the upper bound
y
never must
be decreased below its upper guard
y0
[
10
]. Note that in [
10
], we showed that it
is possible to adapt Morris et al.’s edge-generation rules and algorithm MM5 for
STNU [
13
] to check the DC of a STNPSU in polynomial time. Due to lack of
space, we do not report the adapted edge-generation rules (cf. [
10
] for details),
but only the new version of the algorithm (cf. Alg. 1).
For each process exhibiting temporal constraints, a time-aware process schema
needs to be defined [
8
]. In the context of this work, a process schema corresponds
to a directed graph that comprises a set of nodes—representing tasks and gateways
(e.g., AND-Split/Join)—as well as a set of control edges linking these nodes and
specifying precedence relations between them. Each process schema contains a
unique start and end node, and may be composed of control flow patterns like
sequence, parallel split, and synchronization. Moreover, [
12
] elaborated the need
for a proper run-time support of time-aware processes. In this work, we focus on
the most fundamental category of time patterns, i.e., durations and time lags.
3 Characterization of Time-Aware Processes
This section shows how to determine a proper representation for the duration
of a process. For this purpose, we consider a process schema
P
with a single
start and a single end node. Note that in this paper we do not consider the
choices pattern, but we are currently extending STNPSU to support choices
as well. Moreover, preliminary analysis shows that the results presented in this
paper will be applicable to this extended kind of STNPSU. First, we show how
to verify the dynamic controllability (DC) of process schema
P
and, if
P
is DC,
how to derive its minimal constraints. This can be done by transforming
P
into
Table 1. STNPSU transformation rules.
Process
Schema STNPSU Process Schema STNPSU
Start/End node Time Lag
ZEZ E
[0,∞][0,∞]A B
E[t, u]S
end-start
ASAEBSBE
[t, u]
Task
A
[x, x0][y0, y]ASAE
[x, x0][y0, y]
[0,∞] [0,∞]A B
S[t, u]S
start-start
ASAEBSBE
[0,∞]
[t, u]
ANDsplit
[1,1] +S+E
[0,∞][1,1]
[0,∞]
[0,∞]
A B
E[t, u]E
end-end
ASAEBSBE
[0,∞]
[t, u]
ANDjoin
[1,1] +S+E
[0,∞]
[0,∞]
[1,1] [0,∞]
A B
S[t, u]E
start-end ASAEBSBE
[0,∞]
[t, u]
Control Edge
A B ASAEBSBE
[0,∞]
an STNPSU
S
using the transformation rules depicted in Table 1. The resulting
STNPSU is characterized by having a single initial timepoint that occurs before
any other one—called
Z
—and a single ending timepoint—called
E
—that occurs
after any other timepoint. This STNPSU is then checked for DC by applying
the standard algorithm for DC checking [
10
]. In particular, using a constructive
proof analogous to the one presented in [
8
], one can easily show that the process
will be DC if and only if the corresponding STNPSU is DC.
Note that the DC checking algorithm also derives the minimum and maximum
duration between timepoints
Z
and
E
, i.e., the minimum and maximum durations
of the process. However, these bounds are not sufficient for characterizing the
temporal behavior of the process as they do not represent its possible non-
restrictable duration ranges. As an example consider the STNPSU depicted
in Fig. 2c, which corresponds to process
P2
of Fig. 1. One can easily show
that the duration range between
Z
and
E
corresponds to [5
,
19]. However, this
range cannot be reduced to [5
,
10], for example, since the internal task
T7
has a
contingent duration of 1to 7, which cannot be controlled (i.e., restricted) by the
process engine. In particular, if
T7
lasts exactly 7, process
P2
lasts at least 11
time units. On the other hand, representing a subprocess by considering the
duration range between
Z
and
E
to be a contingent one would make the overall
process over-constrained, and thus limit the overall temporal flexibility of the
modularized process.
We, therefore, suggest representing the duration of a process by a guarded
range with proper guards in order to prevent unacceptable restrictions of the
duration range of the process. In the following, we propose a method to deter-
mine the lower and upper guard of such guarded range based on the STNPSU
representation of the process schema. In this context, the upper guard for the
duration range of a process
P
represents the lowest value the maximum duration
of the process may be decreased to. In other words, considering the corresponding
STNPSU
S
of
P
, the upper guard corresponds to the lowest value the upper
Z+1S+1E
T1ST1ET2ST2E
T3ST3E
+2S+2EE
[1,1] [1,1]
[1,4]
[1,2] [1,2][3,4][1,2] [2,2][3,3]
[1,3][9,9]
[1,5]
[1,5]
[1,1] [1,1]
(a) STNPSU corresponding to P0.
ZT4ST4ET5ST5EE
[1,1] [1,1][4,4][1,8] [1,2][4,5][1,1]
(b) STNPSU corresponding to P1.
ZT6ST6ET7ST7EE
[1,1] [1,2][4,5][1,5] [1,1][7,7][1,1]
(c) STNPSU corresponding to P2.
Fig. 2. STNPSUs corresponding to subprocesses P0, P1and P2depicted in Fig. 1.
bound of the requirement link, which is derived between
Z
and
E
by the DC
checking algorithm, may be decreased to. It can be determined considering the
maximum guards of any guarded link and the lower bounds of any requirement
link in Sas outlined in Example 1.
Example 1
(Upper Guard). Consider the STNPSU depicted in Fig. 2c. While
the upper bounds of the internal requirement links may be restricted to their
lower bounds (i.e., 1) by the process engine, the upper bounds of the two
guarded links cannot be restricted below their upper guards (i.e., 4and 7,
respectively). Therefore, the value we obtain when summing the lower bound
values of the requirement links and the upper guards of the guarded links, i.e.,
1+4+1+7+1=
14
, represents the minimal value the upper bound of the link
between Zand Emay be restricted to.
In turn, the lower guard for the duration range of a process
P
represents
the greatest value the minimum duration of the process may be increased to. In
the STNPSU
S
, therefore, the lower guard corresponds to the greatest value the
lower bound of the requirement link between Zand Emay be increased to.
If there are several paths leading from
Z
to
E
, it is necessary to consider the
maximum/minimum such value considering all paths. Therefore, Defs 1 and 2
specify the concept of lower/upper guard for any timepoint of an STNPSU.
Definition 1 (Upper Guard).
Given a dynamically controllable STNPSU
S
with distance graph
D
= (
T,E
)and a timepoint
C
. Then: The minimum value
that may be set for the upper bound
v
of a requirement link
Z[u, v]C
is called the
upper guard of C:
upperGuardS(C)=max
B∈T
0if Z≡C
upperGuardS(B)+xif (B−xC)∈E
upperGuardS(B)+y0if (BD:−y0C)∈E
Definition 2 (Lower Guard).
Given a dynamically controllable STNPSU
S
with distance graph
D
= (
T,E
)and a timepoint
C
. Then: The maximum value
that may be set for the lower bound
u
of a requirement link
Z[u, v]C
is called the
lower guard of C:
lowerGuardS(C) = min
B∈T
0if Z≡C
lowerGuardS(B) + yif (ByC)∈ E
lowerGuardS(B) + x0if (Bd:x0C)∈ E
Definitions 1 and 2 allow determining to which extent the upper/lower bound
of the derived requirement link between
Z
and a timepoint
C
in an STNPSU
S
may be reduced/increased, without affecting the DC of
S
(cf. Lemmas 1 and 2).
Lemma 1 (Upper Guard).
Let
S
be a dynamically controllable STNPSU,
Z
be the initial timepoint and
C
be a timepoint in
S
. Then: The upper bound
v
of the
distance
Z[u, v]C
between
Z
and
C
may be reduced to at most
upperGuardS
(
C
),
preserving the DC of S.
Lemma 2 (Lower Guard).
Let
S
be a dynamically controllable STNPSU,
Z
be the initial timepoint and Cbe a timepoint in S. Then: The lower bound uof
distance
Z[u, v]C
between
Z
and
C
may be increased to at most
lowerGuardS
(
S
),
preserving the DC of S.
Sketch of Proof
(see a technical report [
9
] for the full proof). By considering
the AllMax-Projection
D0
used by Alg. 1, one can show that if
y
is restricted
beyond its guard
upperGuardS
(
C
),
S
can no longer be DC. On the other hand,
assuming that
y
is restricted to
upperGuardS
(
C
)and the network is not DC,
one can show that in this case the value of
upperGuardS
(
C
)must have been
greater than assumed, which contradicts the assumption. The proof of Lemma 2 is
analogous considering the AllMin-Projection. The AllMin-Projection is similar to
the AllMax-Projection
D0
, but considers only ordinary and lower-case edges.
ut
Using Defs 1 and 2, it now becomes possible to determine to which extent the
lower/upper bound of the duration range of a process can be restricted, while
preserving its DC as illustrated by Example 2.
Example 2.
The minimum and maximum durations of the processes depicted in
Fig. 1 are determined by the DC checking algorithm as
P0
:[11
,
20],
P1
:[5
,
19],
and
P2
:[5
,
19]. Using Defs 1 and 2, it now becomes possible to determine to
which extent these duration ranges may be restricted: the minimum duration
of
P0
may be restricted to
lowerGuardP0
(
E
) =
15
at most, while its maximum
duration may be restricted to
upperGuardP0
(
E
) =
15
; the duration of
P1
may be
restricted to
lowerGuardP1
(
E
) =
13
and
upperGuardP1
(
E
) =
11
, respectively;
and the duration of P2to lowerGuardP2(E) = 10 and upperGuardP2(E) = 14.
Based on the definitions of
lowerGuard
and
upperGuard
, one can easily verify
that their value is always non-negative. Moreover, it is easy to verify that the
upperGuard
(
C
)value is given by value
u
of edge
Z−uC
in the AllMax-Projection
graph of the network, while
lowerGuard
(
C
)value is given by value
v
of edge
ZvC
in the AllMin-Projection graph. Using standard STN algorithms [
4
], therefore,
the computational cost of determining
lowerGuard
(
C
)and
upperGuard
(
C
)is at
most
O
(
n3
), with
n
being the number of timepoints in the considered STNPSU.
Given a range [
u, v
]that represents the overall duration of a DC process,
Defs. 1 and 2 assure that it is always possible to reduce one of the two bounds of
the respective duration range to the corresponding guard (i.e.,
upperGuard
(
E
)
or
lowerGuard
(
E
)) without affecting the DC of the process. However, it is not
possible to restrict both bounds simultaneously since the restriction of one bound
may change the guard of the other bound as shown by Example 3.
Example 3.
Let us consider the STNPSU from Fig. 2c that corresponds to
subprocess
P2
. One can easily determine that
lowerGuardP2
(
E
) =
10
and
upperGuardP2
(
E
) =
14
hold. Moreover, the duration range of the process is
[5
,
19] as determined by the DC checking algorithm. Considering Lemmas 1 and
2, it then can be easily shown that the minimum duration of the process may
be increased to
10
or its maximum duration may be restricted to
14
. However,
for process
P2
it is not possible to increase the minimum duration to
10
, while
at the same time restricting the maximum duration to
14
. In particular, if the
minimum duration is increased to
10
, due to the partially contingent guarded link
between timepoints
T7S
and
T7E
(representing task
T7
), the maximum duration
must not be decreased below 16 to further guarantee the DC of the process. On
the other hand, the maximum duration may be decreased to
14
, but then the
minimum duration must not be increased beyond 8. In detail, a span of at least
6must be ensured for the final duration range of the process.
To fully represent the overall temporal properties of a process we suggest consid-
ering an additional value that represents the minimal span to be guaranteed for
the duration range. We denote this value as the contingency span of the process.
It can be defined using the link contingency span and path contingency span of
the corresponding STNPSU.
Definition 3 (Link Contingency Span).
A positive link contingency span
∆
corresponds to the span that needs to be guaranteed for a link in order to ensure
the DC of an STNPSU. In turn, a negative link contingency span corresponds to
the maximum span provided by a link that can be used to reduce the contingency
span of previous guarded link.
a)
For a guarded link
A[a, a0][b0, b]B
, the link contingency span
∆AB
is defined
as ∆AB =b0−a0.
b)
For a requirement link
A[a, b]B
, the link contingency span
∆AB
is defined
as ∆AB =a−b.
Next, we need to find a way to determine the contingency span of a path based
on the link contingency span of its links. First, let us consider a guarded link
A[a, a0][b0, b]B
followed by a requirement link
B[c, d]C
. In this case, the contingency
span required by the guarded link can be partially or fully compensated by the
subsequent requirement link, as the duration of the latter can be decided based
on the actual duration of the former. Thus, the contingency of the path from
A
to
C
is given by
∆AB
+
∆BC
. In turn, for a requirement link
A[a, b]B
followed by
a guarded link
B[c, c0][d0, d]C
we must differentiate two subcases: If the guarded
link is partially contingent (i.e.,
c0< d0
) the previous requirement link cannot be
used to compensate its contingency span as the duration of the requirement link
must be decided before executing the guarded link. Therefore, the contingency
span of the path from
A
to
C
is given by
∆BC
. However, if the guarded link is
partially shrinkable (i.e.,
d0≤c0
), its link contingency
∆BC
is negative. In this
case, the contingency span of the path from
A
to
C
is again given by
∆AB
+
∆BC
as both links could be used to reduce the contingency of a previous guarded link.
Finally, the combination of two requirement links (guarded links) is similar to
the above cases. When considering a path that consists of more than two links,
the link contingency spans need to be combined in an incremental way starting
from the inital timepoint
Z
. When considering two or more parallel paths, in
turn, it becomes necessary to consider the most demanding case, i.e., the path
with the largest contingency span. This leads to the following recursive approach
for calculating the contingency span of a path.
Definition 4 (Path Contingency Span).
Let
S
be a dynamically controllable
STNPSU and
Z
be its initial timepoint. By definition the path contingency span
of
Z
is
contS
(
Z
)=0. Then: The path contingency span
contS
(
C
)of any other
timepoint Cis given by
contS(C) = max 0,max
B∈T {contS(B) + ∆BC }
It is noteworthy that the path contingency span of any timepoint is always
greater or equal to zero, i.e.,
contS
(
C
)
≥
0. Moreover, the problem of determining
the value of
contS
(
C
)can be reduced to the problem of finding the minimal
distance between
Z
and
C
in a weighted graph considering the negative link
contingency spans as edge values [
9
]. Using the Bellman–Ford algorithm, the
computational cost of determining
contS
(
C
)is at most
O
(
n3
), with
n
being the
number of timepoints in the STNPSU.
Example 4.
Regarding the STNPSUs from Fig. 2, the path contingency span of
timepoints Eare as follows: contP0(E)=2,contP1(E)=2, and contP2(E)=6.
Based on Def. 4, it becomes possible to describe the admissible duration
ranges between two timepoints in an STNPSU.
Lemma 3. Let Sbe a dynamically controllable STNPSU, Zbe its initial time-
point, and
C
be any other timepoint. Then: In order to preserve the DC of
S
, any
restriction
Z[u∗, v∗]C
(
u≤u∗≤lowerGuardS
(
C
),
upperGuardS
(
C
)
≤v∗≤v
) of
the distance between
Z
and
C
must be done in such a way that
v∗−u∗≥contS
(
C
)
holds.
Sketch of Proof
(see [
9
] for the full proof). By induction it can be shown that
when restricting [
u, v
]to [
u∗, v∗
](with
v∗−u∗<contS
(
C
)),
S
is no longer
DC. ut
From the previous observations, we can derive important relationships between
lowerGuard(C),upperGuard(C)and cont(C)values:
Lemma 4. Let Sbe a dynamically controllable STNPSU, Zbe its initial time-
point and
C
be any other timepoint. If
T
is the network derived from
S
by
restricting upper bound
v
of the distance
Z[u, v]C
between
Z
and
C
to
v∗
, with
upperGuardS(C)≤v∗≤v, in Tit holds
lowerGuardT(C) = min {lowerGuardS(C); v∗−contS(C)}
Lemma 5. Let Sbe a dynamically controllable STNPSU, Zbe its initial time-
point and
C
be any other timepoint. If
T
is the network derived from
S
by
restricting the lower bound
u
of the distance
Z[u, v]C
between
Z
and
C
to
u∗
,
with u≤u∗≤lowerGuardS(C), in Tit holds
upperGuardT(C) = max {upperGuardS(C); u∗+ contS(C)}
Sketch of Proof
(see [
9
] for the full proof). The proofs of Lemmas 4 and 5
are similar. In particular, assuming that
u
/
v
is restricted to
lowerGuardT
(
C
)/
upperGuardT
(
C
)and the resulting network is not DC, one can show that in this
case contS(C)<0holds.
The previous results give rise to the following theorem that enables a complete
description of the overall temporal properties of a process.
Theorem 1 (Overall Temporal Properties of a Process).
Considering a pro-
cess
P
and the corresponding STNPSU
S
, let
Z
and
E
be the single start and
single end timepoints of
S
. Then: The overall temporal properties of
P
can be
described by a guarded range with contingency [x, x0][y0, y]lc, where
–x
and
y
are the bounds of the requirement link
Z[x, y]E
between initial
timepoint
Z
and ending timepoint
E
in
S
, as derived by the DC checking
algorithm,
–x0= lowerGuardS(E)and y0= upperGuardS(E), and
–c= contS(E).
Proof.
Defs. 1 and 2 show how to use the values of
lowerGuardS
(
E
) =
x0
and
upperGuardS
(
E
) =
y0
to specify the possible restrictions regarding the lower
and upper bounds of the duration range [
x, y
]of a process (i.e., its minimum
and maximum duration). This way, we can fully represent the possible duration
ranges of the process as a guarded range
[
x, x0
][
y0, y
]
. Moreover, Lemmas 3–5
show how to use the path contingency span
contS
(
E
) =
c
in order to ensure
that any possible restriction of the duration range
[
x, x0
][
y0, y
]
lc
of the process
preserves its DC. ut
Based on Theorem 1, it becomes possible to represent the overall temporal
properties of a process using a single guarded range with contingency, as illustrated
by Example 5.
Example 5.
First, consider process
P1
as depicted in Fig. 1 together with the
corresponding STNPSU shown in Fig. 2. The overall temporal properties of this
process may be described by guarded range with contingency
[5
,13
][
11,
19]
l
2.
Since the contingency span of this process corresponds to 2, it is possible to
restrict the overall duration range of the process to [
13,
15] or [9
,11
], while still
preserving its DC. In turn, the overall temporal properties of process
P2
(cf. Figs. 1
and 2) can be described by a guarded range with contingency
[5
,10
][
14,
19]
l
6.
For example, the duration range of the process, therefore, can be restricted to
[6
,14
],[
10,
17], or [8
,14
]. However, due to the required contingency span of 6, for
example, it must not be restricted to [10,14], or [10,15].
Such kind of compact representation of the overall temporal properties of
a process schema is crucial for being able to reuse it as part of a modularized
process. In particular, when adding a subprocess task to a process schema, a
duration range must be specified. Based on the guarded range with contingency
determined for the subprocess it is now possible to determine a proper duration
range for it when it is insert in the main process.This duration range ensures
that, without having to reanalyze the subprocess schema, any restriction of the
duration of the subprocess task in the main process will be made in such a way
that the subprocess remains dynamically controllable.
4 DC-Checking of Modularized Time-Aware Processes
As shown in the previous section, for each time-aware process, it is possible to
derive a guarded range with contingency that fully describes the overall temporal
properties of the process. In this section we show how this knowledge may be
utilized for enabling a sophisticated support of modularized time-aware processes
in a PAIS.
In a PAIS, the available process schemas are generally stored in a central
process model repository. Based on the results presented in Sect. 3, it now
becomes possible to enhance the information about the process schemas in such a
repository with the overall temporal properties of the process schema represented
as a guarded range with contingency. Such information can then be utilized
when re-using a process schema as part of a modularized time-aware process. In
particular, during design time a process designer may select a process schema
from the repository to be used as a subprocess task. Similar to an atomic task, the
designer then has to configure the subprocess task within the process schema; i.e.,
he must specify the duration range of the particular subprocess task. In order to
ensure the executability of the modularized process the designer must guarantee
that the duration range set for the subprocess task is compliant with the overall
temporal properties of the (sub
-
)process schema. In this context, the repository
information about the overall temporal properties of the (sub
-
)process schema
may be used to support the process designer in choosing a proper duration range
for the respective subprocess task. In other words, the designer must select a
guarded range as duration range of the subprocess task, which satisfies the guards
as well as the contingency of the guarded range with contingency representing
the overall temporal properties of the (sub
-
)process schema as stored in the
repository.
In general, the duration range
[
x, x0
][
y0, y
]
of a subprocess task needs to
be selected with respect to the overall temporal properties of the respective
(sub
-
)process schema
[
u, u0
][
v0, v
]
lc
such that
u≤x≤x0≤u0
and
v≥y≥y0≥
v0
hold. Moreover, if
c >
0holds,
y0−x0≥c
must hold as well. When observing
these constraints, it is guaranteed that, during the execution of a subprocess task
of a modularized process, the respective subprocess instance may be completed
without violating any of its temporal constraints (i.e., the subprocess is DC).
Z
T0
[2,4][6,8]1
[1,1]
P0
[10,14][16,20]
P1
[5,9][9,9]
P2
[8,10][17,17]T8
[1,3][5,5]
1
[1,1] E
E[1,4]S E[1,1]S
E[1,4]S
E[1,4]S
E[1,4]S
E[1,4]S
E[1,5]S
E[1,5]S
E[1,1]S
S[30,45]S
Process Repository
. . . NonPharmR
[10,15][15,20]l2. . . PharmR
[5,10][12,17]l6. . . PhysEx
[5,10][9,14]l0. . .
Fig. 3. Modularized process.
Example 6.
Fig. 3 depicts the modularized process from Fig. 1 where proper
duration ranges have been selected for the three subprocess tasks
P0
,
P1
and
P2
, which are related to (sub
-
)process schemas
NonPharmR
,
PhysEx
and
PharmR
.
For example, for subprocess task
P0
, duration range
[10
,
14][16
,
20]
is used.
This range has the same outer bounds as the overall temporal properties of the
respective process schema, i.e.,
[10
,
15][15
,
20]
l
2. Moreover, the lower and upper
guard of the duration range ensure that the guards as well as contingency value
determined for the process schema are observed. In turn, for subprocess task
P1
the designer decides to further restrict the upper bound of the duration range to
9(thus also decreasing the lower guard to 9). Note that this still guarantees the
DC of subprocess schema
PhysEx
as it complies with the respective guards and
contingency. Finally, for subprocess
P2
, the designer increased the lower bound to
8and the upper guard to 17, thus providing a possible contingency of 7instead
of the required contingency of 6.
After completing the design of the modularized process schema, the dynamic
controllability of the parent process schema itself needs to be verified. Then, the
overall temporal properties of the modularized process schema may be determined
based of the approach presented in Sect. 3.
Finally, the modularized process itself may be added to the process repository.
It may then be reused as a subprocess in the context of another modularized
process. This enables the definition of hierarchically structured modularized
time-aware process schemas comprising multiple levels.
5 Proof of Concept
The presented approach was implemented as a proof-of-concept prototype in the
ATAPIS Toolset [
11
]. This prototype enables users to create time-aware process
schemas and to automatically transform them to a corresponding STNPSU. The
STNPSU can then be checked for dynamic controllability. Moreover, the overall
temporal properties of the process can be determined.
Fig. 4. Determining Process Overall Temporal Properties in ATAPIS Toolset.
The screenshot from Fig. 4 shows the ATAPIS Toolset
3
: at the top, the
process schema from Fig. 1b is shown. At the bottom, the automatically generated
STNPSU and its minimal network are depicted. Finally, the dialog in the middle
shows the overall temporal properties of the process schema which have been
determined based on the STNPSU.
Moreover, using the ATAPIS prototype it becomes possible to create modular-
ized time-aware processes and to assign a proper duration range to each subprocess
task based on the overall temporal properties of the respective (sub
-
)process
schema. The resulting modularized time-aware process schema can then be
checked for dynamic controllability and its overall temporal properties be deter-
mined. It is then possible to reuse this modularized time-aware process schema
for a subprocess task in another modularized process.
First simulations based on the ATAPIS prototype show a significantly im-
proved performance of our modularization-based approach compared to the
“classical approach” where each subprocess task has to be replaced by it respec-
tive (temporal) components. Overall, the prototype demonstrates the applicability
of our approach.
6 Conclusions
Time and modular design constitute two fundamental aspects for properly support-
ing business processes by PAIS. So far, these aspects have only been considered in
isolation, although the overall temporal behaviour of a (sub
-
)process significantly
differs from the one of simple tasks. This paper closes this gap by considering
modularization and time-awareness of processes in conjunction with each other.
In particular, we propose a novel approach for determining and representing the
3A screencast demonstrating the toolset is available at http://dbis.info/atapis
overall temporal behavior of a process, called guarded range with contingency.
Using this representation, we can specify the possible durations of a (sub
-
)process
as well as any permissible restriction that may be applied to it, while still ensuring
the executability of the process. Moreover, we show how this may be used in the
context of process repositories and multilayered process hierarchies.
We are currently extending STNPSU to consider conditional aspects as well.
In future work, we want to study the integration of (modularized) time-aware
processes in PAISs, specifically focusing on aspects like scalability and usability.
References
1.
Combi, C., Gambini, M., Migliorini, S., Posenato, R.: Representing business pro-
cesses through a temporal data-centric workflow modeling language: An application
to the management of clinical pathways. IEEE T. Systems, Man, and Cybernetics:
Systems 44(9), 1182–1203 (Sep 2014)
2.
Combi, C., Hunsberger, L., Posenato, R.: An algorithm for checking the dynamic
controllability of a conditional simple temporal network with uncertainty. In: Filipe,
J., Fred, A.L.N. (eds.) ICAART 2013 - Proc of the 5th Int. Conf. on Agents and
Artificial Intelligence, Vol. 2. pp. 144–156. SciTePress (Feb 2013)
3.
Combi, C., Posenato, R.: Towards temporal controllabilities for workflow schemata.
In: Markey, N., Wijsen, J. (eds.) TIME 2010 - 17th Intern. Symp. on Temporal
Representation and Reasoning. pp. 129–136. IEEE Computer Society (Sep 2010)
4.
Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. Artificial Intelligence
49(1-3), 61–95 (1991)
5.
Eder, J., Gruber, W., Panagos, E.: Temporal modeling of workflows with conditional
execution paths. In: Proc. DEXA’00. pp. 243–253. Springer (Sep 2000)
6.
Eder, J., Panagos, E., Rabinovich, M.: Workflow time management revisited. In:
Seminal Contr. to Inf. Sys. Eng., pp. 207–213 (2013)
7.
Hochberg, M.C., et al.: American college of rheumatology 2012 recommendations
for the use of nonpharmacologic and pharmacologic therapies in osteoarthritis of
the hand, hip, and knee. Arthritis Care & Research 64(4), 465–474 (2012)
8.
Lanz, A., Posenato, R., Combi, C., Reichert, M.: Controllability of time-aware
processes at run time. In: On the Move to Meaningful Internet Systems: OTM 2013
Conf.-Confed. Int. Conf.: CoopIS, DOA-Trusted Cloud, and ODBASE. pp. 39–56
(Sep 2013)
9.
Lanz, A., Posenato, R., Combi, C., Reichert, M.: Controlling time-awareness in
modularized processes (extended version). Tech. Rep. UIB-2015-01, Ulm University
(Mar 2015), http://dbis.eprints.uni-ulm.de/1133/
10.
Lanz, A., Posenato, R., Combi, C., Reichert, M.: Simple temporal networks with
partially shrinkable uncertainty. In: ICAART 2015-Proc of the Int. Conf. on Agents
and Artificial Intelligence, Vol. 2. pp. 370–381. SciTePress (2015)
11.
Lanz, A., Reichert, M.: Dealing with changes of time-aware processes. In: Proc
BPM’14. LNCS, vol. 8659, pp. 217–233 (2014)
12.
Lanz, A., Weber, B., Reichert, M.: Time patterns for process-aware information
systems. Requirements Engineering 19(2), 113–141 (2014)
13.
Morris, P.H., Muscettola, N.: Temporal dynamic controllability revisited. In: Na-
tional Conf on Artificial Intelligence (AAAI’05). pp. 1193–1198 (2005)
14.
Reichert, M., Weber, B.: Enabling Flexibility in Process-aware Information Systems:
Challenges, Methods, Technologies. Springer (2012)
