Managing time-awareness in modularized processes [original]

Software and Systems Modeling manuscript No.

(will be inserted by the editor)

Managing Time-Awareness in Modularized Processes

Roberto Posenato ·Andreas Lanz ·

Carlo Combi ·Manfred Reichert

the date of receipt and acceptance should be inserted later

Abstract

Managing temporal process constraints in a suitable way is crucial

for long-running business processes in many application domains. However,

proper support of time-aware processes is still missing in contemporary in-

formation systems. This paper tackles a particular challenge existing in this

context, namely the handling of temporal constraints for modularized processes

(i.e., processes comprising subprocesses), which shall enable both the reuse of

process knowledge and the modular design of complex processes. In detail, this

paper focuses on the representation and support of time-aware modularized

processes in process-aware information systems. To this end, we present a

Andreas Lanz, Manfred Reichert

Institute of Databases and Information Systems, Ulm University, Germany

E-mail: {andreas.lanz,manfred.reichert}@uni-ulm.de

Roberto Posenato, Carlo Combi

Department of Computer Science, University of Verona, Italy

E-mail: {carlo.combi,roberto.posenato}@univr.it

2 Roberto Posenato et al.

sound and complete method to derive the duration restrictions of a time-aware

(sub

process in such a way that its temporal properties are completely spec-

ified. We then show how this characterization of a process can be utilized

when reusing it as a subprocess within a modularized process. As a motivating

example, we consider a compound process from healthcare. Altogether the

proper handling of temporal constraints for modularized processes is crucial

for the enhancement of time- and process-aware information systems.

Keywords

Process-aware Information System, Temporal Constraints,

Subprocess, Process Modularity, Controllability

1 Introduction

It is widely acknowledged that the capability to modularly design process

schemas constitutes an important requirement for creating comprehensible

and reusable process schemas [

][

]. Thus, the support of complex processes,

which may comprise subprocesses at different levels, is essential for process-

aware information systems (PAIS) as it allows for the reuse of existing process

knowledge from a process repository as well as the modular design of such

processes.

On the other hand, temporal process constraints, such as deadlines and

maximum allowable delays between task executions, must be suitably handled

in many application domains. Even tough this topic has received increasing

attention in the research community during the last years [

][

], a

Managing Time-Awareness in Modularized Processes 3

complete support of time-aware processes is still missing in contemporary PAIS.

At first glance, temporal process constraints and process modularity seem to

be orthogonal features that may be managed in an independent way. However,

when getting to the heart of these two features, 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 [

]. Only then, it

becomes possible to evaluate the temporal constraints of a process containing

time-aware subprocesses in a truly modular way, i.e., without replacing the

subprocess tasks with their (temporal) components. Moreover, one may then

attach temporal information to the process schema when storing it in a central

process repository. This knowledge can, for example, be essential in the context

of business process analysis and optimization [32].

In [

], the issue of representing the temporal properties of a process has

been considered. This paper extends and completes the approach for the

representation and support of time-aware modularized processes, which we

presented in [

]. In particular, we introduce and prove 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 reusing it as a subprocess of a modularized process. In

accordance with recent research contributions, we focus on the issue of dynamic

controllability (DC) of time-aware processes [

][

]. In general, DC corresponds

4 Roberto Posenato et al.

to the capability of a PAIS to execute a process schema in a way such that all

allowed durations of all tasks are possible, 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 PAIS (i.e., its process engine).

The two main research questions addressed in this paper are:

How can the overall temporal behavior of a process be represented (cf.

Sect. 5)? Addressing this issue constitutes a fundamental prerequisite for

providing some kind of modularity from the temporal perspective as well.

Note that without such characterization, it would be necessary to recompute

the temporal features of a subprocess schema each time it is used in a

modularized process. More particularly, this paper focuses on providing a

formal description of how to represent and derive temporal constraints

for modularized processes. As will be shown, a process duration can be

represented as a kind of range composed of two parts. One part represents

all possible durations, while the second one, which often constitutes a

restriction of the first part, represents the core of durations the PAIS cannot

restrict at runtime. 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 fully controlled as the contingent

durations of the contained tasks cannot be controlled by the PAIS and must

be guaranteed.

Managing Time-Awareness in Modularized Processes 5

With respect to the informal proposal made in [

], this paper provides a

formal and complete description of how to represent and derive the overall

temporal behavior of a process.

How to apply knowledge about the temporal behavior of a process when

reusing its schema as a subprocess inside a modularized process in order

to avoid having to re-analyze the internal constraints of the subprocess (cf.

Sect. 6)? This will, for example, enable us to store time-aware processes

including their overall temporal properties in a process repository and to

reuse them in a truly modular fashion.

In addition to our preliminary work on managing time-awareness in mod-

ularized processes [

], this paper presents all proofs related to the formal

part of the approach. Moreover, we reorganize the structure applied in [

] to

provide a more insightful and detailed discussion of each relevant aspect and

we describe the design and implementation of a proof-of-concept prototype of

the approach (cf. Sect. 7). In detail, the remainder of this work is organized as

follows: Sect. 2 introduces a clinical guideline dealing with the management of

osteoarthritis of the hand, hip and knee as an example of a process schema

with subprocesses and temporal properties. We use this clinical example for

illustration purposes throughout the paper. Sect. 3 extends the discussion of

existing work related to the management of temporal constraints in business

processes. In Sect. 4 we present, in an extended way, the Simple Temporal

Network with Partially Shrinkable Uncertainty (STNPSU) model. In particular,

this model is used for temporal reasoning on subprocesses. In turn, Sect. 5

6 Roberto Posenato et al.

constitutes the core of the paper. It discusses how to characterize time-aware

processes by mapping them to corresponding STNPSUs extended with the

concept of contingency span. In this context, all relevant concepts are formally

described and formal statements are proven. Sect. 6 then discusses how the

temporal properties of a (sub

process can be utilized in order to check the

controllability of the overall process without unfolding its subprocesses. As

another novel contribution, Sect. 7 presents the architecture of ATAPIS, which

is an open framework for the design, verification and enactment of modularized

temporal processes. Finally, Sect. 8 summarizes the main results of our work

and gives an outlook on future work.

2 Motivating Example

As a motivating scenario, we consider a high-level specification of an excerpt

of a clinical guideline related to the management of osteoarthritis of the hand,

hip and knee [16]. A possible schema of this process is depicted in Fig. 1.

After completing the initial Patient Evaluation (task

PatEv

), two par-

allel branches become activated. The first one is composed of process Non-

Pharmacologic Recommendation (

NonPharmR

) followed by process Specifi-

cation of Physical Exercises (

PhysEx

). The second one consists of process

Pharmacologic Recommendation (

PharmR

) followed by a Treatment Expla-

nation to the patient (task

TrExp

). As depicted in Fig. 1,

and

correspond to subprocesses (from a process repository) that comprise other

tasks and may be reused in the context of other clinical processes (e.g., related

Managing Time-Awareness in Modularized Processes 7

:PatEv

[2,4][6,8]

[1,1]

:TrExp

[1,3][5,5]2

[1,1]

E[1,4]S

E[1,1]S

E[1,4]SE[1,4]S

E[1,4]S

E[1,5]SE[1,5]S

E[1,1]S

S[30,45]S

(a) Main process

Process Repository

. . .

PharmR

:CntrEv

[1,2][4,5]

:DrgSp

[1,1][7,7]E

E[1,1]S E[1,5]S E[1,1]S

(b) Subprocess P2

NonPharmR

[1,1]

:ADLsEv

[1,2][3,4]

:DevId

[2,2][3,3]

:ThermMod

[1,3][9,9]

[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,1]S

PhysEx

: AqEx

[1,1][4,4]

: 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.

to other pathologies). In detail, Non-Pharmacologic Recommendation

con-

sists of two parallel branches. The first branch evaluates the patient’s ability to

perform activities of daily live (task

ADLsEv

) followed by the identification

of needed assistive devices (task

DevId

). The second branch consists of

giving instructions to the patient related to the use of thermal modalities

(task

ThermMod

). In turn, the Specification of Physical Exercises (i.e.,

)

consists of the specification of aquatic exercises (task

AqEx

) followed by

the specification of land exercises (task

LndEx

). Finally, Pharmacologic

8 Roberto Posenato et al.

Recommendation (i.e.,

) consists of the evaluation of contraindications (task

T6:CntrEval) followed by a drug specification (task T7:DrgSp).

We enrich the process schemas with temporal constraints that need to be

obeyed in order to guarantee the clinically successful completion of each step of

the therapy. Furthermore, such temporal constraints will help practitioners (e.g.,

doctors and nurses) in planning their daily work as they can anticipate how

long previous steps will take and how much freedom they have for performing

their tasks. The temporal constraints allow for the temporal characterization

of tasks, edges and gateways according to the concepts introduced in [

]. Note

that the durations of tasks are not completely under the control of the PAIS

as these tasks are carried out by practitioners.

Therefore, task durations are represented as guarded ranges. Such a duration

range may be partially restricted by the system during process execution in

order to ensure successful completion of the processes. For example, task

has temporal constraint



2][4



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 be disallowed). As

another example consider task

with temporal constraint



1][7



. The

latter expresses 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 sufficient flexibility to successfully complete the task.

Constraints on gateways and edges constitute standard temporal constraints,

Managing Time-Awareness in Modularized Processes 9

specifying the possible durations (within a range), which are under the control

of the PAIS (i.e., its process engine).

As already discussed, two challenges emerge in this context.

–

The first challenge concerns the representation of the overall temporal

behavior of (sub

processes. One must be able to describe how a subprocess

like, for example,

PhysEx

behaves temporally if it shall be reusable inside

any time-aware processes. Note that

PhysEx

involves physical therapists and

is usually required in the context of many other healthcare processes. For

example, the activities of this (sub

process with the same internal temporal

constraints might be also required when managing patients that suffer from

multiple sclerosis [

] or sarcopenia (loss of muscular mass and decline in

associated muscular function occurring with aging [

]). Furthermore, the

subprocess is relevant for managing patients with osteogenesis imperfecta

(a pathology caused by a mutation in a gene that affects bone formation,

bone strength, and the structure of other tissues [

]) often undergoing

multiple rehabilitation periods after bone fractures. These three clinical

scenarios only constitute few examples of real-world clinical processes whose

definition could make use of subprocess

PhysEx

. In general, the designers of

a clinical process schema would benefit from the establishment of a clinical

process library that collects reusable, suitably defined clinical subprocesses.

To allow for the proper reuse of such subprocesses, in turn, their temporal

behavior needs to be part of their overall description. Note that similar

10 Roberto Posenato et al.

considerations can be made for other subprocesses as well. For example,

subprocess PharmR is common to many decision-based care processes.

–

The second challenge is related to the efficient temporal analysis of the

top-level (i.e., main) process. Ideally, this analysis can be accomplished

without need for unfolding all used subprocesses

P0, P1,

and

. Only

then, the temporal analysis can be accomplished effectively and quickly.

In general, the provision of modularized clinical (sub

processes will allow

checking temporal properties of the main process, while only considering

a reduced number of constraints and tasks/subprocesses. Regarding the

running example, for instance, it should be possible to verify the temporal

properties of the process for managing osteoarthritis patients without need

to consider the internal structure and constraints of

PharmR

NonPharmR

and PhysEx.

3 Related Work

In literature, there is considerable work on the management of temporal

constraints in PAIS [

][

]. Issues these approaches are

focusing on include the modeling and verification of time-aware processes.

For each process exhibiting temporal constraints, a time-aware process

schema needs to be defined [

]. 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

Managing Time-Awareness in Modularized Processes 11

Category I: Durations and Time Lags

TP1 Time Lags between two Activities

TP2 Durations

TP3 Time Lags between Events

Category II: Restricting Execution

Times

TP4 Fixed Date Elements

TP5 Schedule Restricted Elements

TP6 Time-based Restrictions

TP7 Validity Period

Category III: Variability

TP8 Time-dependent Variability

Category IV: Recurrent Process

Elements

TP9 Cyclic Elements

TP10 Periodicity

Table 1 Process Time Patterns [24]

process schema contains unique start and end nodes, and may be composed of

control flow patterns like sequence, parallel split, and synchronization.

Lanz et al. [

][

] introduced 10 time patterns representing common tempo-

ral constraints of time-aware processes (cf. Tab. 1). In particular, time patterns

facilitate the comparison of existing approaches based on a universal set of

notions with well-defined semantics. While [

] introduced the empirically evi-

denced time patterns informally, [

] additionally provided a formal semantics

for them. Moreover, the need for a sophisticated run-time support for the time

patterns was elaborated in [24].

Marjanovic et al. [

] defined a conceptual model for temporal constraints

on a process schema, which is tailored to check for temporal consistency.

Considering the time pattern classification (cf. Tab. 1), [

] dealt with time

lags between activities (TP1), activity and process durations (TP2), and fixed

date elements (TP4). Furthermore, [

] proposed a set of rules for verifying

time-aware process schemas, whereas no run-time support was considered.

12 Roberto Posenato et al.

Eder et al. [

] presented an extended version of the Critical Path Method,

which is known from the project planning domain. In detail, [

] proposed the

use of Timed Workflow Graphs (TWG) for representing the temporal properties

of activities and their control flow relations. Regarding the time patterns, [

]

considered time lags between activities (TP1), activity durations (TP2), fixed

date elements (TP4), and schedule restricted elements (TP5). Note that [

]

presumes that activity durations are deterministic, i.e., activity durations are

the same for all process instances. As for activity durations, in [

][

] authors

discussed a probabilistic approach based on duration histograms to deal with

temporal information about tasks.

Bettini et al. [

] proposed an approach based on Simple Temporal Network

(STN) [

]. In particular, this differs significantly from the aforementioned ones.

In an STN, nodes represent time points, whereas each directed edge

−→ b

between time points

and

represents a temporal constraint

b−a≤v

with

being a real value. If

v≥

0holds, the constraint represents the maximum

allowable delay between

and

; otherwise (i.e.,

v <

0), it represents the

minimum time span to be elapsed after

before

may occur. In [

], each

process activity is represented by two nodes of the respective STN, which

correspond to the starting and ending time point of the activity. In turn, the

edges of the STN represent temporal constraints and precedence relations

between the corresponding nodes. Finally, [

] considered time lags between

activities (TP1), activity durations (TP2), and fixed date elements (TP4).

Managing Time-Awareness in Modularized Processes 13

Combi et al. [

][

] proposed a temporal conceptual model for specifying

time-aware process schemas. In this conceptual model, time lags between

activities (TP1), activity durations (TP2), fixed date elements (TP4), schedule

restricted elements (TP5), and periodicity (TP10) are considered. First of all,

[

] shows how to check consistency of time-aware processes at design time,

Furthermore, [

] argues that different strategies for ensuring consistency of a

process instance during run-time may be applied, depending on the considered

kind of consistency of a process schema. In [

], in turn, the authors extended

their work considering also tasks for which the execution time cannot be

decided, but only observed, analyzing the computational complexity of the

dynamic controllability problem (cf. Sect. 1) and proposing a general algorithm

to check for the dynamic controllability of a time-aware process schema.

Zhang et al. [

] addressed the issue of determining whether a business

activity is eligible for relocation in a business process in order to optimize

overall execution performance. Note that even in this case, it is crucial to

characterize the temporal behavior of each activity.

The concept of temporal controllability has been mainly investigated in

the AI area in connection with temporal constraint networks. In [

], Morris

et al. proposed an STN [

] extension, the Simple Temporal Network With

Uncertainty (STNU). Regarding STNUS, it is also possible to specify a new

kind of constraint, the contingent links. The latter are not under the control of

the system and, hence, the concept of consistency is extended to the concept

of dynamic controllability.

14 Roberto Posenato et al.

Finally, Combi et al. [

] transferred the concept of dynamic controllability

to time-aware process schemas. Recently, in [

][

] authors extended STNU

to Conditional Simple Temporal Network with Uncertainty (CSTNU), which

additionally consider alternative execution paths.

4 Backgrounds

This work relies on Simple Temporal Network with Partially Shrinkable Un-

certainty (STNPSU), an extension of STNU that enlarges contingent links to

enable a more flexible management of temporal constraints [

]. This section

provides a detailed discussion on STNPSU. Moreover, it presents the definitions

required to understand the formal proofs given in the following sections.

An STNPSU [

] is a directed weighted graph (cf. Fig. 2a) whose nodes

represent time-point variables (timepoints), usually corresponding to the start or

end of activities, and whose 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 a constraint expressing that

timepoint

must occur between

and

time units after the occurrence of

(i.e.,

x≤B−A≤y

). For 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; instead, the value is decided by the

environment during run-time. Each contingent timepoint has one incoming

edge, which is called guarded link and drawn as 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

Managing Time-Awareness in Modularized Processes 15

[

x, y

]augmented with two guards, the lower guard

and the upper guard

[

is called the activation timepoint. Before executing a guarded link,

its duration range [

x, y

]may be modified. However, any modification must

be accomplished 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

. That means, once

is executed,

is guaranteed to be executed

such that

C−A∈

[

x∗, y∗

]holds. Note that the specific time at which

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

–Tis a set of timepoints;

–Cis 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

, where

and

Ccorrespond to timepoints, and 0<x≤y <∞,x≤x0,0<y0≤y.

Moreover, if

A1[x1, x0

1][y0

1, y1]C1

as well as

A2[x2, x0

2][y0

2, y2]C2

are distinct guarded

links in

and

will be distinct timepoints. 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 then represents a constraint with a contingent

(i.e., unshrinkable)core [

x0, y0

]

⊆

[

x, y

]. In turn, if

x0≥y0

holds, a guarded

16 Roberto Posenato et al.

A B

C D

[1,2][4,6]

[0,1]

[−1,2]

(a) Non-DC STNPSU

A B

C D

b:2

−1

B:−4

d:2

−1

D:−4

(b) Distance Graph of the

STNPSU in (a)

Fig. 2 Non-DC STNPSU and corresponding distance graph.

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

= (

T,E

derived from the upper and lower bound constraints [

][

]. In the distance

graph (cf. Fig. 2b), each link between a pair of timepoints

and

is represented

as two ordinary edges in

AyB

, representing constraint

B≤A

, and

A−xB

for representing constraint

B≥A

x, y ∈R

. Moreover, for each

guarded link between a pair of timepoints

and

contains two other labeled

edges, called lower and upper case labeled values. A lower case labeled value,

Ac:x0C

, expresses that

cannot be forced to be executed at a time greater

than

after

, i.e., it is not possible to add a constraint

A−x00 C, x0< x00

the network. In turn, an upper case labeled value,

AC:−y0C

, expresses that

cannot be forced to be executed at a time less than

after

, i.e., it is not

possible to add a constraint Ay00 C, y00 < y0to the network.

Managing Time-Awareness in Modularized Processes 17

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:= AllMax-Projection of D;

4if (D0has a negative cycle) then return false;

5Generate new edges in Dusing edge-generation rules from Tab. 2;

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

must not be increased beyond its lower guard

and the upper bound

must

not be decreased below its upper guard y0[18].

In [

], it was shown how one can adapt and extend the edge-generation rules

and algorithm proposed by Morris et al. for checking the dynamic controllability

(DC) of STNU [

] in order to check the DC of an STNPSU in polynomial

time (cf. Alg. 1).

18 Roberto Posenato et al.

Table 2

Edge-generation rules of the STNPSU-DC-Check algorithm. Dashed edges are the

generated ones.

No Case:

u+v

Upper Case:

uR:v

R:u+v

Lower Case: QT

s:uv

u+v

Applicable if: v < 0∨(v= 0 ∧S6≡ T)

Cross Case: QT

s:uR:v

R:u+v

Applicable if: R6≡S∧(v <0∨(v= 0 ∧S6≡ T))

Label Removal:

S T R

R:v r :l

Applicable if: R6≡ S∧v≥x, where xis the negated value of

the lower bound of the guarded link from Tto R, i.e., x≤0

The checking algorithm works by recursively generating new edges in the

STNPSU distance graph according to the rules from Tab. 2 and by checking

whether newly added edges result in so called negative semi-reducible cycles

in the graph [

]. For each rule, existing edges are represented as solid arrows

and newly added ones as dashed arrows. Each of the first four rules takes

two existing edges as input and generates a single edge as output. Finally,

notation

R6≡ S

expresses that

and

must be distinct time-point variables,

but does not represent a constraint on the values of those variables. A path in

an STNPSU distance graph is called semi-reducible if, through the subsequent

application of the edge generation rules (cf. Tab. 2), it can be transformed into

a path solely consisting of ordinary or upper-case edges [

]. A semi-reducible

cycle with negative unlabeled length is called a negative semi-reducible cycle.

Managing Time-Awareness in Modularized Processes 19

To detect negative semi-reducible cycles Alg. 1 uses the AllMax-Projection of

the STNPSU. The AllMax-Projection is the distance matrix for the Simple

Temporal Network (STN) [

] formed by all of the original and generated

ordinary and upper-case edges (without their alphabetic labels) and represents

the occurrence when all guarded links in the original network assume their

upper guard value.

Example 1

(Negative Semi-Reducible Cycle) Consider the distance graph de-

picted in Fig. 2b corresponding to the STNPSU from Fig. 2a. It is a matter of

applying the edge generation rules from Tab. 2 to verify that Fig. 3 depicts

the derived distance graph of Fig. 2b (dashed lines are the generated ones)

containing the semi-reducible cycle

A−C−A

. Moreover, as the unlabeled

length of this semi-reducible cycle is negative, the respective STNPSU cannot

be dynamically controllable. In particular, let us consider the scenario where

is executed 4time units after

and

is executed 2time units after

. Then,

due to the fact that

may be executed at most 2time units after B,

has to

be executed at most 0time units after

(i.e., at the same item as

). In turn,

in the scenario where

is executed 2time units after

and

is executed 4

time units after A,Chas to be executed at least 1time unit after Ain order

to be able to satisfy the requirement link between

and

. However, it is not

possible to satisfy both conditions at the same time. Thus, the STNPSU is not

DC.

We observe that the edge-generation rules from Tab. 2 only generate

ordinary or upper-case edges. The upper-case edges generated by respective

20 Roberto Posenato et al.

A B

C D

b:2

B:−4

d:2

D:−4

D:−2

B:−3

B:−1

Fig. 3 New Generated Edges in Distance Graph of Fig. 2b

rules represent conditional constraints, called waits [

]. In particular, an upper-

case edge

BC:−vA

represents the following constraint: as long as contingent

timepoint

remains unexecuted, timepoint

must wait at least

units after

the execution of

, the activation timepoint for

. Note that [

] and [

]

presented two optimizations of the original algorithm, which are not further

discussed in this paper.

5 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

with a single start

and a single end node. In this paper we do not consider the choices pattern,

but we are currently extending STNPSU to support choices as well. However,

our preliminary analysis has shown that the results presented in this paper

will be also applicable to this extended kind of STNPSU.

First, we show how to verify the dynamic controllability (DC) of process

schema

and, if

is DC, how to derive its minimal constraints. Second,

we discuss how to determine the guards for a guarded link representing the

Managing Time-Awareness in Modularized Processes 21

Table 3 STNPSU transformation rules (adopted from [19]).

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

[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,∞]

A B

E[t, u]E

end-end

ASAEBSBE

[0,∞]

[t, u]

ANDjoin

[1,1]

+S+E

[0,∞]

[1,1] [0,∞]

A B

S[t, u]E

start-end ASAEBSBE

[0,∞]

[t, u]

Control Edge

A B ASAEBSBE

[0,∞]

duration of a process. Finally, we propose to extend the concept of guarded

range in order to completely represent the overall temporal properties of a

process.

5.1 STNPSU Representation of a Process Schema

In order to verify the dynamic controllability of a process schema

, it is

transformed into an STNPSU

using the transformation rules depicted in

Tab. 3. The resulting STNPSU has a single initial timepoint that occurs

before any other one—called

—and a single ending timepoint—called

—

that occurs after any other timepoint. This STNPSU is then checked for DC

by applying the standard algorithm for DC checking [

] to it. Given the above

transformation, one can easily show that the original process is DC if and

22 Roberto Posenato et al.

only if the corresponding STNPSU is DC. In turn, this results in the following

theorem.

Theorem 1

Given a time-aware process schema

, which uses the process

modeling elements from Tab. 3, there exists an STNPSU

such that

dynamically controllable if and only if SPis DC.

Proof

Tab. 3 depicts the mapping of the elements available for modeling a

time-aware process (i.e., tasks, control edges, AND gateways, and temporal

constraints) to the associated STNPSU fragments.

–

Task

. Given a process schema, each task node

is transformed into two

STNPSU timepoints,

and

, representing its start and end instants.

The duration attribute of

,[[

x, x0

][

y0, y

]], is converted to the guarded link

AS[x, x0][y0, y]AE.

–

ANDjoin/ANDsplit

gateways. The conversion process is analogous to the one

of a task. However, duration attribute [

x, y

]is converted to a requirement link

[x, y]AE

as control connectors are executed by the process engine of the

PAIS.

–

Control Edge

. A control edge from task

to task

is converted to a

requirement link

[0,∞]BS

with duration range [0

,∞

]in order to guarantee

the correct execution order of the original process.

–

Time Lags

. Consider a time lag

hIFi[t,u]hISi

, where

and

represent the

kind of instants to be considered, i.e., ’S’ for the start instant and ’E’ for the

end instant. If the considered time lag is between tasks

and

, it is converted

to a requirement link between the timepoints associated to instants

AIF

and

Managing Time-Awareness in Modularized Processes 23

BIS

of the two tasks

and

. The resulting requirement link then has the

same duration range [t, u]as the time lag.

Let

be a time-aware process schema. Applying the above transformation

and to the possible time lags, one can simply verify that the obtained

STNPSU represents all precedence relations and temporal constraints of the

original process schema P.

As introduced in Sect. 1, a time-aware process schema is dynamically

controllable if it is possible to execute it for all required durations of all

activities, while still satisfying all temporal constraints. Furthermore, recall

that an STNPSU is dynamically controllable if it is possible to execute it in a

way such that, no matter how the execution of any guarded link turns out, for

any other guarded link

A[x, x0][y0, y]C

, the lower bound

must never be increased

beyond its guard

and the upper bound

must never be decreased below its

guard y0in order to ensure controllability of the network.

Therefore, it is a matter of definition to verify that the dynamic controlla-

bility of a process schema implies dynamic controllability of the corresponding

STNPSU and vice versa. ut

5.2 Lower and Upper Guard

Assuming that the process is DC, it is noteworthy that the DC checking

algorithm also derives the minimum and maximum duration between timepoints

and

, i.e., the minimum and maximum durations of the process. However,

these bounds are not sufficient for characterizing the temporal behavior of the

24 Roberto Posenato et al.

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,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]

Fig. 4 STNPSUs corresponding to subprocesses P0, P1and P2from Fig. 1.

process as they do not represent its possible non-restrictable duration ranges.

As an example consider the STNPSU depicted in Fig. 4c, which corresponds to

process

of Fig. 1. One can easily show that the duration range between

and

corresponds to [5

19]. However, this range cannot be reduced to [5

10],

for example, since internal task

has a contingent duration of 1to 7, which

cannot be controlled (i.e., restricted) by the PAIS. In particular, if

lasts

exactly 7time units, process

will last at least 11 time units. On the other

hand, representing a subprocess by considering the duration range between

and

to be contingent, 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

determine the lower and upper guard of such a guarded range based on the

Managing Time-Awareness in Modularized Processes 25

STNPSU representation of the process schema. In this context, the upper guard

for the duration range of a process

represents the lowest value the maximum

duration of the process may be decreased to. In other words, considering the

STNPSU

corresponding to

, the upper guard corresponds to the lowest

value the upper bound of the requirement link, which is derived between

and

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 Ex. 2.

Example 2

(Upper Guard) Consider the STNPSU depicted in Fig. 4c. 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=

, 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

represents

the greatest value the minimum duration of the process may be increased

to. Regarding the STNPSU

, therefore, the lower guard corresponds to the

greatest value the lower bound of the requirement link between

and

may

be increased to.

If there are several paths leading from

, it becomes necessary to

consider the maximum/minimum value considering all paths. Therefore, Defi-

26 Roberto Posenato et al.

nitions 1 and 2 specify the concept of lower/upper guard for any timepoint of

an STNPSU.

Definition 1 (Upper Guard)

Let

be a dynamically controllable STNPSU

with distance graph

= (

T,E

)and let

be a timepoint. Then: The minimum

value that may be set for the upper bound

of a requirement link

Z[u, v]C

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)

Let

be a dynamically controllable STNPSU

with distance graph

= (

T,E

)and let

be a timepoint. Then: The maximum

value that may be set for the lower bound

of a requirement link

Z[u, v]C

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

Considering Defs. 1 and 2 it is easy to verify that

–

when there is a requirement link

Z[x, y]C

in STNPSU

, the

upperGuard

of Cis ≥x;

–

when there is a guarded link

Z[x, x0][y0, y]C

in STNPSU

, the

upperGuard

of Cis in [y0, y];

Managing Time-Awareness in Modularized Processes 27

–

when there is a requirement link

Z[x, y]C

in STNPSU

, the

lowerGuard

of Cis ≤y;

–

when there is a guarded link

Z[x, x0][y0, y]C

in STNPSU

, the

lowerGuard

of Cis in [x, x0];

–

in general, for any timepoints

and

with

Z[a, b]A[c, d]C

derived by the

DC checking algorithm, it holds

upperGuard

(

)

≥upperGuard

(

) +

and

lowerGuard(C)≤lowerGuard(A) + d.

Example 3

Regarding the STNPSUs from Fig. 4, one can verify that the values

of lowerGuard and upperGuard between Zand Ecorrespond to

–lowerGuardP0(E) = 15 and upperGuardP0(E) = 15,

–lowerGuardP1(E) = 13 and upperGuardP1(E) = 11, and

–lowerGuardP2(E) = 10 and upperGuardP2(E) = 14.

Definitions 1 and 2 allow determining to which extent the upper/lower

bound of the derived requirement link between

and a timepoint

in an

STNPSU

may be reduced/increased without affecting the DC of

(cf.

Lemmas 1 and 2).

Lemma 1 (Upper Guard)

Let

be a dynamically controllable STNPSU,

be the initial timepoint, and

be a timepoint in

. Then: The upper

bound

of the distance

Z[u, v]C

between

and

may be reduced to at most

upperGuardS(C), preserving the DC of S.

Proof

First, we show that if

is set to a value less than

upperGuardS

(

), the

network cannot be DC. Let

B1. . . Bk

be the path from

in the distance

28 Roberto Posenato et al.

graph Dthat determines the value for upperGuard(C), i.e.,

Zα0B1α1. . . αk−1BkαkC

where

αi

is either an ordinary or upper case edge and

−Pi∈{0,...,k}˜αi

upperGuard

(

)with

˜αi

corresponding to the value of

αi

ignoring any label.

Given such path, in the AllMax-Projection

, any upper case edge

αi

{Di

−y0

is replaced by

˜αi

−y0

. Thus, it is easy to verify that by the

standard STN propagation rules in the AllMax-Projection an ordinary edge

ZP˜αiC

is derived. At the same time, if we add a requirement edge

Zv∗C

with

v∗<upperGuard

(

)to the distance graph

of the original STNPSU

the same edge will also be added to the AllMax-Projection

, resulting in a

negative cycle ZP˜αiCv∗Z, i.e., the STNPSU cannot be DC.

Second, we show that if

is DC and

is reduced to a value

v0≥

upperGuardS

(

cannot be part of any negative semi-reducible cycle, i.e.,

the resulting network must be DC as well. Let us assume that

Z[u, v]C

restricted to

Z[u, v0]C

with

upperGuard

(

)

≤v0≤v

and that the resulting

network is not DC. This implies that there exists a negative semi-reducible

cycle

Zα0E1α1. . . αl−1ElαlCv∗Z

in the distance graph

consisting

only of ordinary or upper case edges

αi

such that

Pi∈{0,...,l}˜αi

v∗<

i.e.,

v∗<−Pi∈{0,...,l}˜αi

. Based on Def. 1, it follows that for any such path

E1, . . . , El

from

it holds

upperGuard

(

)

≥ − Pi∈{0,...,l}˜αi

and, thus,

upperGuard

(

)

≤v∗<−Pi∈{0,...,l}˜αi≤upperGuard

(

). This, in turn, con-

tradicts the assumption. ut

Managing Time-Awareness in Modularized Processes 29

Lemma 2 (Lower Guard)

Let

be a dynamically controllable STNPSU,

be the initial timepoint, and

be a timepoint in

. Then: The lower bound

distance

Z[u, v]C

between

and

may be increased to at most

lowerGuardS

(

preserving the DC of S.

Proof

The proof is analogous to the one of Lemma 1 using the AllMin-Projection

and applying a similar reasoning. The AllMin-Projection is similar to the

AllMax-Projection, but considers solely ordinary and lower-case edges. ut

Using Defs 1 and 2, it 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. This is illustrated by Example 4.

Example 4

The minimum and maximum durations of the processes from Fig. 1

are determined by the DC checking algorithm as

:[10

20],

:[5

19], and

:[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

may be restricted to

lowerGuardP0

(

) =

most, whereas its maximum duration may be restricted to

upperGuardP0

(

) =

15;

–

the duration of

may be restricted to

lowerGuardP1

(

) =

and

upperGuardP1(E) = 11, respectively, and

–

the duration of

may be restricted to

lowerGuardP2

(

) =

and

upperGuardP2(E) = 14, respectively.

30 Roberto Posenato et al.

Therefore, the guarded range representing the duration of the three subpro-

cesses

P0, P1,

and

are



[10

,15

][

15,

20]





,13

][

11,

19]



, and



,10

][

14,

19]



respectively.

Based on the definitions of

lowerGuard

and

upperGuard

, one can easily

verify that their value is always non-negative. Moreover, it becomes easy to show

that the

upperGuard

(

)value is given by value

of edge

Z−uC

in the AllMax-

Projection graph of the network, whereas the

lowerGuard

(

)value is given

by value

of edge

ZvC

in the AllMin-Projection graph. Using standard STN

algorithms [

], therefore, the computational cost of determining

lowerGuard

(

)

and

upperGuard

(

)is at most

(

), with

being the number of timepoints

in the considered STNPSU.

5.3 Contingency Span

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

(

)or

lowerGuard

(

)) 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 5.

Example 5

Consider the STNPSU from Fig. 4c, which corresponds to

subprocess

. One can easily show that

lowerGuardP2

(

) =

and

upperGuardP2

(

) =

hold. Moreover, the duration range of the process

corresponds to [5

19] as determined by the DC checking algorithm. Considering

Managing Time-Awareness in Modularized Processes 31

Lemmas 1 and 2, it then can be easily shown that the minimum duration of

the process may be increased to

or its maximum duration may be restricted

. However, for process

it is not possible to increase the minimum

duration to

while, at the same time, restricting the maximum duration

. In particular, if the minimum duration is increased to

, due to the

partially contingent guarded link between timepoints

T7S

and

T7E

(representing

task

), the maximum duration must not be decreased below 16 to further

guarantee DC of the process. On the other hand, the maximum duration may

be decreased to

. In this case, 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 con-

sidering 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.

For a guarded link

A[a, a0][b0, b]B

, the link contingency span

∆AB

is defined

as ∆AB =b0−a0.

32 Roberto Posenato et al.

For a requirement link

A[a, b]B

, the link contingency span

∆AB

is defined

as ∆AB =a−b.

Taking Def. 3 it is easy to verify that, respectively

–

the link contingency span of a requirement link is less than or equal to zero,

i.e., A[a, b]B⇒∆AB ≤0;

–

the link contingency span of a partially shrinkable guarded link is less than

or equal to zero, i.e., A[a, a0][b0, b]B∧a0≥b0⇒∆AB ≤0;

–

the link contingency span of a partially contingent guarded link is greater

than zero, i.e., A[a, a0][b0, b]B∧a0< b0⇒∆AB >0.

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

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

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

Managing Time-Awareness in Modularized Processes 33

contingency span of the path from

is again given by

∆AB

∆BC

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 initial timepoint

. 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

be a dynamically control-

lable STNPSU and let

be its initial timepoint. By definition, the path

contingency span of

contS

(

)=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 al-

ways greater or equal to zero, i.e.,

contS

(

)

≥

0. Moreover, the problem of

determining the value of

contS

(

), i.e., the maximum contingency span among

all possible paths from

, can be reduced to the problem of finding

the minimal distance between

and

in a suitable weighted graph whose

construction considered the link contingency spans as edge values.

Definition 5 (Contingency Graph)

Let

(T,C,G)

be an STNPSU to

which the DC-checking algorithm has been applied (cf. Alg. 1). The corre-

34 Roberto Posenato et al.

sponding contingency graph for

has the form

= (

T,ECO

). Thereby, each

timepoint in Tserves as a node in the graph; ECO is a set of weighted edges:

For each guarded link

A[x, x0][y0, y]B∈ G

, there exists a single edge

A−∆AB B∈

ECO.

For each requirement link

A[x, y]B∈ C

, there exist two edges

A−∆AB B

B−∆AB A∈ ECO.

c) For each timepoint T∈ T , there exists an edge Z0T∈ ECO.

Based on Def. 4, one can easily verify that the path contingency span of any

timepoint

C∈ T

corresponds to the negative value of the shortest path from

initial timepoint Zto Cin the corresponding contingency graph (cf. Def. 5).

Two comments are noteworthy with respect to Def. 4 and Def. 5. First,

as a requirement link may connect two-non sequential timepoints, its link

contingency span can be used in combination with the contingency coming from

any of its endpoints. Def. 5 considers these two mutually-exclusive options by

adding two edges

A−∆AB B, B −∆AB A∈ ECO

. Second, edges

Z0T∈ ECO, T ∈ T

added by Step c) in Def. 5 guarantee that the length of any path in the graph

starting at timepoint

is always less than or equal to 0, i.e., the corresponding

path contingency is always positive as requested by the definition.

Moreover, as

is DC, the contingency graph

cannot contain any negative

cycles. In particular, the only edges with a negative edge value are the ones

resulting from a partially contingent guarded link

A[x, x0][y0, y]B

. Then, for any

path

E0, . . . , Ek

it must hold

−Pi=1...k−1∆EiEi+1 ≥∆AB

, otherwise

cannot be DC. Using the Bellman–Ford algorithm, the computational cost of

Managing Time-Awareness in Modularized Processes 35

Z+1S+1E

T1ST1ET2ST2E

T3ST3E

+2S+2EE

−1

1−1

−6

0[−1] 0

0[−1]

0[−6] 0[−2] 0[−2] 0[−2]

Fig. 5

Contingency Graph of the STNPSU in Fig. 4a showing values determined by the

Bellman-Ford algorithm (grayed bracketed values).

determining

contS

(

)is at most

(

), with

being the number of timepoints

in the STNPSU.

Example 6

The path contingency graph corresponding to the STNPSU depicted

in Fig. 4a is shown in Fig. 5. Note that insignificant edges determined by the

DC checking algorithm have been omitted for the sake of readability. Applying

the Bellman-Ford algorithm to this graph, the grayed values in bracket are

determined (insignificant edges are re-omitted). In particular, edge

derived as

Z−2E

. Moreover, by applying Def. 4 to Fig. 4a it can be easily

verified that contP0(E)=2holds.

Regarding the other STNPSUs from Fig. 4, the path contingency span of

timepoints Eare as follows:

–contP1(E)=2, and

–contP2(E)=6.

36 Roberto Posenato et al.

Based on Def. 4, it becomes possible to describe the admissible duration

ranges between two timepoints in an STNPSU.

Lemma 3

Let

be a dynamically controllable STNPSU,

be its initial

timepoint, and

be any other timepoint. Then: In order to preserve the DC

, any restriction

Z[u∗, v∗]C

(

u≤u∗≤lowerGuardS

(

upperGuardS

(

)

≤v∗≤v

) of the distance between

and

must be set in such a way that

v∗−u∗≥contS(C)holds.

Proof

We solely consider timepoints

with a positive path contingency span

contS

(

)

0and

upperGuardS

(

)

−lowerGuardS

(

)

<contS

(

); otherwise

it is already ensured that

v∗−u∗≥contS

(

)holds (either by the fact that

v∗−u∗≥0holds or by the guards).

First of all, let us consider the definition of

contS

(

). Note that a positive

path contingency span can only occur when there is at least one partially

contingent guarded link inside

. Moreover, taking the definition of

contS

(), it

is always possible to find a sequence of timepoints

B0, . . . , Bk

with

Bk≡C

for

which it holds

contS(C) = contS(B0) + ∆B0,B1+. . . +∆Bk−1,Bk

with

1. contS(B0)=0,

2. ∀j∈ {1, . . . , k}Pi∈{1,...,j}∆Bi−1,Bi>0,

i.e., ∀j∈ {1, . . . , k}contS(Bj)>0

Managing Time-Awareness in Modularized Processes 37

Then, by definition, link

B0B1

is a partially contingent guarded link:

B0[x1, x0

1][y0

1, y1]B1.

If path

B0, . . . , Bk

contains a sequence of requirement links

Bi−1[xi, yi]Bi

[xi+1, yi+1]Bi+1

, there also exists an equivalent single requirement

link

Bi−1[xi+xi+1, yi+yi+1]Bi+1

resulting in the same value of

contS

(

Bi+1

Moreover, if path

B0, . . . , Bk

contains a sequence of guarded links

Bi−1[xi, x0

i][y0

i, yi]Bi[xi+1, x0

i+1][y0

i+1, yi+1]Bi+1

, it is always possible to split time-

point

into two timepoints

and

B00

connected by a requirement

link with value [0

0] without changing the properties of the network

(particularly

contS

(

Bi+1

)), i.e.,

Bi−1[xi, x0

i][y0

i, yi]Bi[xi+1, x0

i+1][y0

i+1, yi+1]Bi+1 ≡

Bi−1[xi, x0

i][y0

i, yi]B0

[0,0] B00

i[xi+1, x0

i+1][y0

i+1, yi+1]Bi+1.

In summary, without loss of generality we can assume that the sequence of

timepoints B0, . . . , Bkalways has the following pattern:

Z[a, b]B0[x1, x0

1][y0

1, y1]B1[x2, y2]B2[x3, x0

3][y0

3, y3]B3[x4, y4]B4. . .

. . . [xk−1, x0

k−1][y0

k−1, yk−1]Bk−1[xk, yk]Bk≡C

where

Z[a, b]B0

is the requirement link derived by the DC checking algorithm.

We can now show by induction that it is not possible to restrict

Z[u, v]Bk

to [

u∗, v∗

]such that

v∗−u∗<contS

(

)holds. Particularly, assuming that

v∗−u∗

contS

(

)

−

 >

0holds, we show that at least one link inside

path Z, B0, . . . , Bkhas to be restricted beyond its bounds/guards.

First, consider a path consisting of 3 timepoints

B0, B1

, and

, i.e.,

Z[a, b]B0[x1, x0

1][y0

1, y1]B1[x2, y2]B2

(Note that the case of two timepoints follows

38 Roberto Posenato et al.

by assuming

= 0 and the case of one timepoints is given by defini-

tion as

b−a≤contS

(

)

−

0holds then). In this case

contS

(

)is

given by

contS

(

) =

contS

(

) + (

1−x0

) + (

x2−y2

)with

contS

(

)=0.

Assume

Z[u, v]B2

is restricted to

Z[u∗, v∗]B2

with

v∗−u∗

contS

(

)

−

(

1−x0

)+(

x2−y2

)

−

 >

0. Then, by applying the No-Case Rule (cf. Tab. 2),

a requirement link

Z[u∗−y2, v∗−x2]B1

between

and

is derived. Moreover,

the Lower Case Rule (cf. Tab. 2) derives an ordinary edge

1−(u∗−y2)Z

In turn, the Upper Case Rule (cf. Tab. 2) derives a wait

B1:(v∗−x2)−y0

This wait is then transformed into the ordinary edge

B0(v∗−x2)−y0

by the

Label Removal Rule (cf. Tab. 2). Note that (

v∗−x2

)

−y0

1≥ −x0

holds as

v∗≥y0

x2≥y0

1−x0

must hold for the original network to be DC.

In summary, a requirement link

Z[(u∗−y2)−x0

1,(v∗−x2)−y0

1]B0

is derived. Hence, it

must hold

b≤

(

v∗−x2

)

−y0

and

a≥

(

u∗−y2

)

−x0

and, therefore, it must

also hold:

b−a≤(v∗−x2)−y0

1−((u∗−y2)−x0

=v∗−u∗+y2−x2+x0

1−y0

= (y0

1−x0

1)+(x2−y2)−+y2−x2+x0

1−y0

1v∗−u∗=contS(B2)−

=− < 0

which shows that the network can no longer be DC as the requirement link

ZB0is restricted too much.

Now let us consider a path consisting of

+ 3 timepoints

B0, . . . , Bk+2

as depicted below (Again, the case of

+ 2 timepoints follows by assuming

yk+2 =xk+2 = 0).

Managing Time-Awareness in Modularized Processes 39

ZB0BkBk+1 Bk+2

[a, b][xk+1 , x0

k+1][y0

k+1, yk+1][xk+2, yk+2]

[u∗, v∗]

[u∗−yk+2, v∗−xk+2]

[(u∗−yk+2)−x0

k+1,(v∗−xk+2)−y0

k+1]

Let us assume that

Z[u, v]Bk+2

is restricted to

Z[u∗, v∗]Bk+2

with

v∗−u∗

contS

(

Bk+2

)

−

 >

0. Then by the No-Case Rule (cf. Tab. 2) a require-

ment link

Z[u∗−yk+2, v∗−xk+2]Bk+1

is derived. Moreover, the Lower Case Rule

derives an ordinary edge

k+1 −(u∗−yk+2)Z

. In turn, the Upper Case Rule

derives a wait

Bk+1 :(v∗−xk+2)−y0

k+1 Z

. This wait is transformed into ordinary

edge

(v∗−xk+2)−y0

k+1 Z

by the Label Removal Rule because (

v∗−xk+2

)

−

k+1 ≥ −x0

k+1

holds, as

v∗≥y0

k+1

xk+2 ≥y0

k+1 −x0

k+1

xk+2

must

hold for the original network to be DC. In summary a requirement link

Z[(u∗−yk+2)−x0

k+1,(v∗−xk+2)−y0

k+1]Bkis derived.

Thus for the span of the requirement link

Z[p, q]Bk

between

and

derived by the DC checking algorithm it holds:

q−p≤(v∗−xk+2)−y0

k+1 −((u∗−yk+2)−x0

k+1)

= (v∗−u∗)−(y0

k+1 −x0

k+1)−(xk+2 −yk+2)

= contS(Bk+2)−−∆BkBk+1 −∆Bk+1Bk+2 v∗−u∗=contS(Bk+2)−, Def. 3

= contS(Bk) + ∆BkBk+1 +∆Bk+1Bk+2 −

−∆BkBk+1 −∆Bk+1Bk+2 Def. 4

= contS(Bk)−

Hence, the range of the requirement link

Z[p, q]Bk

is restricted such that

q−p≤contS

(

)

− < contS

(

)holds. By subsequent application of the same

40 Roberto Posenato et al.

steps (i.e., by induction), it follows that for

Z[a, b]B2

it holds

b−a < contS

(

However, as previously shown, this implies that the network can no longer be

DC. ut

From the previous observations, we can derive important relationships

between lowerGuard(C),upperGuard(C), and cont(C)values:

Lemma 4

Let

be a dynamically controllable STNPSU,

be its initial

timepoint, and

be any other timepoint. If

is the network derived from

by restricting upper bound

of the distance

Z[u, v]C

between

and

v∗

with upperGuardS(C)≤v∗≤v, for Tit holds:

lowerGuardT(C) = min {lowerGuardS(C); v∗−contS(C)}

Lemma 5

Let

be a dynamically controllable STNPSU,

be its initial

timepoint, and

be any other timepoint. If

is the network derived from

by restricting the lower bound

of the distance

Z[u, v]C

between

and

u∗, with u≤u∗≤lowerGuardS(C), for Tit holds:

upperGuardT(C) = max {upperGuardS(C); u∗+ contS(C)}

Proof

The proofs of Lemmas 4 and 5 are very similar. For the sake of brevity,

we only prove Lemma 4.

First, let us assume that

lowerGuardT

(

)

> v∗−contS

(

)holds. When

applying Def. 2 and Lemma 2, we obtain that

may be increased to

u∗

lowerGuardT

(

)

> v∗−contS

(

). According to Lemma 3, however, then the

resulting network cannot be DC.

Managing Time-Awareness in Modularized Processes 41

Second, let us assume that

is increased to

u∗

v∗−contS

(

)with

u∗≤lowerGuardS

(

)in

and that the resulting network is not DC. This

implies that there exists a negative semi-reducible cycle

Zα0E1α1E2. . . αl−1ElαlC−(v∗−contS(C)) Z

in the distance graph

such that

Pi∈{1,...,l}˜αi−

(

v∗−contS

(

))

holds, i.e.,

contS

(

)

< v∗−Pi∈{1,...,l}˜αi

. Moreover, it holds that

v∗≤v≤

Pi∈{1,...,l}˜αi

and thus

contS

(

)

< v∗−Pi∈{1,...,l}˜αi≤

0, which contradicts

the basic property that contS(C)≥0holds.

Third, let us assume that

is increased to

u∗

lowerGuardS

(

)with

u∗≤v∗−contS

(

)and that the resulting network is not DC. Again, this

implies that there exists a negative semi-reducible cycle

Zα0E1α1E2. . . αl−1ElαlC−lowerGuardS(C)Z

in the distance graph

such that

Pi∈{1,...,l}˜αi−lowerGuardS

(

)

0holds, i.e.,

Pi∈{1,...,l}˜αi<lowerGuardS

(

). Consequently, it also holds

Pi∈{1,...,l}˜αi<lowerGuardS

(

)

≤v∗−contS

(

)

≤v∗≤v

, i.e.,

Pi∈{1,...,l}˜αi<

, which contradicts the basic assumption that

has been restricted to

v∗

5.4 Overall Temporal Properties of a Process

The previous results give rise to the following theorem that enables a complete

description of the overall temporal properties of a process.

Theorem 2 (Overall Temporal Properties of a Process)

Considering a process

and its corresponding STNPSU

, let

and

be the single start and

42 Roberto Posenato et al.

single end timepoints of

. Then: The overall temporal properties of

can be

described by a guarded range with contingency [x, x0][y0, y]lc, where

–x

and

are the bounds of the requirement link

Z[x, y]E

between initial

timepoint

and ending timepoint

, 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

(

) =

and

upperGuardS

(

) =

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

(

) =

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 2, it becomes possible to represent the overall temporal

properties of a process using a single guarded range with contingency. This is

illustrated by Example 7.

Example 7

First, consider process

(cf. Fig. 1) and its corresponding STNPSU

(cf. Fig. 4). The overall temporal properties of this process may be described by

guarded range with contingency



,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,

Managing Time-Awareness in Modularized Processes 43

the overall temporal properties of process

(cf. Figs. 1 and 4) can be described

by a guarded range with contingency



,10

][

14,

19]

l

6. For example, therefore,

the duration range of the process can be restricted to [6

,14

],[

10,

17], or [8

,14

However, due to the required contingency span of 6, it must not be restricted

to, for example, [10,14], or [10,15].

Such kind of compact representation of the overall temporal properties of a

process schema is crucial for reusing 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 now becomes possible to determine a proper duration range

for it, when adding it to the main process. Without any need to reanalyze

the subprocess schema, this duration range ensures that any restriction of the

duration of the subprocess task in the main (i.e., toplevel) process will be made

in such a way that the subprocess remains dynamically controllable.

6 Checking the Dynamic Controllability of Modularized

Time-Aware Processes

As shown in the previous section, for each time-aware process, one can derive

aguarded range with contingency that fully describes the overall temporal

properties of the process. In particular, this guarded range with contingency

specifies the possible durations of the process as well as the permissible restric-

tions that may be applied to its duration range without violating the DC of

44 Roberto Posenato et al.

the process. This section shows how such a knowledge can be utilized to enable

a sophisticated PAIS support for modularized time-aware processes.

In a PAIS, in general, the available process schemas are stored in a central

process model repository [

]. Based on the results presented in Sect. 5, it

now becomes possible to enhance the repository information about a process

schema with its overall temporal properties represented as a guarded range

with contingency. Such information can then be utilized when reusing 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

and reuse it as a subprocess task. Similar to an atomic task, the designer then

has to configure the subprocess task in the process schema; i.e., he must specify

the duration range of the particular subprocess task. In this context, it must be

ensured that the temporal constraints of the modularized process as well as the

ones of the subprocess can be satisfied. 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 can 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.

Managing Time-Awareness in Modularized Processes 45

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).

Example 8

Fig. 6 depicts the modularized process from Fig. 1. Proper duration

ranges have been selected for the three subprocess tasks

and

, which are

related to (sub

process schemas

NonPharmR

PhysEx

and

PharmR

. For example,

for subprocess task

, 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 the contingency value

determined for the process schema are observed. In turn, for subprocess task

the designer decides to further restrict the upper bound of the duration

range to 11 (thus also decreasing the lower guard to 9due to the contingency of

2). Note that this still guarantees the DC of subprocess schema

PhysEx

as the

new constraints comply with the respective guards and contingency. Finally,

for subprocess

, the designer increases the lower bound to 8and the upper

guard to 17, thus providing a possible contingency of 7instead of the required

contingency of 6.

46 Roberto Posenato et al.

:PatEv

[2,4][6,8]

[1,1]

[10,14][16,20]

[5,9][11,11]

[8,10][17,19]

:TrExp

[1,3][5,5]

[1,1]

E[1,4]S

E[1,1]S

E[1,4]SE[1,4]S

E[1,4]S

E[1,5]SE[1,5]S

E[1,1]S

S[30,45]S

Process Repository

...

PharmR

[5,10][14,19]l6

...

NonPharmR

[10,15][15,20]l2

...

PhysEx

[5,13][11,19]l2

...

Fig. 6 Modularized process.

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. 5.

Finally, the modularized process itself may be added to the process reposi-

tory. It may then be reused as a subprocess in the context of another modular-

Managing Time-Awareness in Modularized Processes 47

ized process. This enables the definition of hierarchically structured modularized

time-aware process schemas comprising multiple levels.

7 Architecture and Implementation of the Proof-of-Concept

Prototype

The presented approach was implemented as a proof-of-concept prototype in

the ATAPIS Toolset [

][

], which, in turn, is based on the AristaFlow BPM

Suite [31].

Due to its Open API as well as its strict modular and service-oriented

design, AristaFlow can be easily applied and adapted to different application

domains. This way, it allows for the integration of advanced process support

functions into domain-specific PAIS as well as the provision of domain-specific

client, service and activity implementations.

In our case, we extended the original AristaFlow architecture by modifying

the time-aware modules, Design Toolset,ChangeOperations, and ProcessMan-

ager, to consider temporal aspects of tasks and (sub

processes. Moreover, we

introduced a new module, called TimeManager, that provides the run-time

support for all the temporal features discussed in this paper. We denoted this

extended framework as ATAPIS Toolset. Fig. 7 depicts the architecture of the

ATAPIS Toolset, where the extended/new modules are displayed with a gray

background. ATAPIS Toolset supports the designer in specifying a time-aware

process, verifying its properties, and enacting it.

48 Roberto Posenato et al.

Persistence (DBMS)

LogManager

ProcessManager

DataManager

WorklistManager

OrgModelManager

ExecutionManager RuntimeManager ChangeOperations

Application / Design Toolset

Execution layer

User/Designer interaction layer

Basic services layer

Low-level services layer

TimeManager

Fig. 7 ATAPIS Toolset: AristaFlow Temporally-Extended Architecture.

In particular, the design toolset, called Process Template Editor, and the

underlying modules enable designers to create time-aware process schemas and

to automatically transform them to a corresponding STNPSU. The STNPSU,

in turn, can then be checked for dynamic controllability. Moreover, the overall

temporal properties of the process can be determined. The screenshot from

Fig. 8 shows the Process Template Editor1.

At the top of Fig. 8, frame A depicts the common options available for

opening, editing and viewing time-aware process schemas. Moreover, there

are the main options for creating the corresponding STNPSU of the loaded

process schema, checking the temporal features of the STNPSU, and enacting

the time-aware process schema. Frame B, in turn, depicts the panel where

the process schema is designed. In Fig. 8, the process schema from Fig. 1c is

shown. At the bottom, the automatically generated STNPSU, frame E, and

the STNPSU after the DC check, frame D, are depicted. Finally, the dialog

1A screencast demonstrating the toolset is available at http://dbis.info/atapis

Managing Time-Awareness in Modularized Processes 49

Fig. 8 Determining Process Overall Temporal Properties in ATAPIS Toolset.

in the middle, frame C, shows the overall temporal properties of the process

schema, which have been determined based on the STNPSU.

Using the ATAPIS prototype, it becomes possible to create modularized

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

determined. It is then possible to reuse this modularized time-aware process

schema for any subprocess task in another modularized process.

First simulations based on the ATAPIS prototype show a significantly

improved performance of our modularization-based approach compared to the

50 Roberto Posenato et al.

“classical approach”, where each subprocess task has to be replaced by its

respective (temporal) components. Overall, the prototype demonstrates the

applicability of our approach.

8 Summary and Outlook

Time and modular design constitute two fundamental aspects for properly

supporting business processes by PAIS. So far, these aspects have only been

considered in isolation, although the overall temporal behavior 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 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.

Finally, we would like to explore the concept of modularization in the context

of temporal networks in order to improve the performance of controllability

checking of such network.

Managing Time-Awareness in Modularized Processes 51

References

Bettini C., Wang X.S., Jajodia S.: Temporal reasoning in workflow systems. Distributed

and Parallel Databases 11(3), 269–306 (2002). doi:10.1023/A:1014048800604

Combi C., Gambini M., Migliorini S., Posenato R.: Representing business processes

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 (2014). doi:10.1109/TSMC.2014.2300055

Combi C., Gozzi M., Posenato R., Pozzi G.: Conceptual modeling of flexible temporal

workflows. ACM Transactions on Autonomous and Adaptive Systems (TAAS)

(2),

19:1–19:29 (2012). doi:10.1145/2240166.2240169

Combi C., Hunsberger L., Posenato R.: An algorithm for checking the dynamic control-

lability of a conditional simple temporal network with uncertainty. In: ICAART 2013

- Proc of the 5th Int. Conf. on Agents and Artificial Intelligence, Vol. 2, pp. 144–156.

SciTePress (2013). doi:10.5220/0004256101440156

Combi C., Hunsberger L., Posenato R.: An algorithm for checking the dynamic con-

trollability of a conditional simple temporal network with uncertainty - revisited. In:

J. Filipe, A.L.N. Fred (eds.) Agents and Artificial Intelligence - 5th International Confer-

ence, ICAART 2013, Barcelona, Spain, February 15-18, 2013. Revised Selected Papers,

Communications in Computer and Information Science, vol. 449, pp. 314–331. Springer

(2013). doi:10.1007/978-3-662-44440-5_19

Combi C., Posenato R.: Controllability in temporal conceptual workflow schemata. In:

Business Process Management, 7th International Conference, BPM 2009, Ulm, Germany,

September 8-10, 2009. Proceedings, LNCS, vol. 5701, pp. 64–79. Springer (2009). doi:

10.1007/978-3-642-03848-8_6

Combi C., Posenato R.: Towards temporal controllabilities for workflow schemata. In:

N. Markey, J. Wijsen (eds.) 17th International Symposium on Temporal Representation

and Reasoning (TIME 2010), pp. 129–136. IEEE Computer Society (2010). doi:10.1109/

TIME.2010.17

52 Roberto Posenato et al.

Cruz-Jentoft A., Baeyens J., Bauer J., et al.: Sarcopenia: European consensus on definition

and diagnosis. Age and Ageing 39(4), 412–423 (2010). doi:10.1093/ageing/afq034

Dechter R., Meiri I., Pearl J.: Temporal constraint networks. Artificial Intelligence

49(1-3), 61–95 (1991)

10.

Eder J., Gruber W., Panagos E.: Temporal modeling of workflows with conditional

execution paths. In: Proc. DEXA’00, pp. 243–253. Springer (2000)

11.

Eder J., Panagos E., Rabinovich M.: Time Constraints in Workflow Systems, pp. 191–205.

Springer Berlin Heidelberg (2013). doi:10.1007/978-3-642-36926-1_15

12.

Eder J., Panagos E., Rabinovich M.: Workflow Time Management Revisited. In: Sem-

inal Contributions to Information Systems Engineering, pp. 207–213. Springer Berlin

Heidelberg, Berlin, Heidelberg (2013). doi:10.1007/978-3-642-36926-1_16

13.

Eder J., Pichler H.: Duration histograms for workflow systems. In: C. Rolland,

S. Brinkkemper, M. Saeki (eds.) Proceedings of the Working Conference on Engineering

Information Systems in the Internet Context (IFIP TC8/WG8.1), IFIP Conference

Proceedings, vol. 231, pp. 239–253. Kluwer, B.V. (2002)

14.

Eder J., Pichler H., Gruber W., Ninaus M.: Personal schedules for workflow systems.

In: W.M.P. van der Aalst, A.H.M. ter Hofstede, M. Weske (eds.) Proceedings of the 1st

International Conference on Business Process Management (BPM’03), Lecture Notes in

Computer Science, vol. 2678, pp. 216–231. Springer (2003). doi:10.1007/3-540-44895-0

15.

Haselkorn J., Hughes C., Rae-Grant A., et al.: Summary of comprehensive systematic

review: Rehabilitation in multiple sclerosis. Neurology

(21), 1896–1903 (2015). doi:

10.1212/WNL.0000000000002146

16.

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)

17.

Lanz A., Posenato R., Combi C., Reichert M.: Controllability of time-aware processes at

run time. In: R. Meersman, H. Panetto, T.S. Dillon, J. Eder, Z. Bellahsene, N. Ritter,

P.D. Leenheer, D. Dou (eds.) On the Move to Meaningful Internet Systems: OTM 2013

Conf.-Confed. Int. Conf.: CoopIS, DOA-Trusted Cloud, and ODBASE, Lecture Notes in

Managing Time-Awareness in Modularized Processes 53

Computer Science, vol. 8185, pp. 39–56. Springer (2013). doi:10.1007/978-3-642-41030-7_

18.

Lanz A., Posenato R., Combi C., Reichert M.: Simple temporal networks with partially

shrinkable uncertainty. In: S. Loiseau, J. Filipe, B. Duval, H.J. van den Herik (eds.)

ICAART 2015 - Proceedings of the International Conference on Agents and Artificial

Intelligence, Volume 2, Lisbon, Portugal, 10-12 January, 2015., pp. 370–381. SciTePress

(2015). doi:10.5220/0005200903700381

19.

Lanz A., Posenato R., Combi C., Reichert M.: Controlling Time-Awareness in Modular-

ized Processes. In: Enterprise, Business-Process and Information Systems Modeling -

International Conference, BPMDS 2016, 21

International Conference, EMMSAD

2016, Lecture Notes in Business Information Processing, vol. 248, pp. 157–172 (2016).

doi:10.1007/978-3-319-39429-9_11

20.

Lanz A., Reichert M.: Dealing with changes of time-aware processes. In: Proc BPM’14,

LNCS, vol. 8659, pp. 217–233 (2014)

21.

Lanz A., Reichert M.: Enabling time-aware process support with the atapis toolset. In:

Proc. BPM’14 Demo Track (2014)

22.

Lanz A., Reichert M., Weber B.: A formal semantics of time patterns for process-aware

information systems. Tech. Rep. UIB-2013-02, University of Ulm (2013)

23.

Lanz A., Reichert M., Weber B.: Process time patterns: A formal foundation. Information

Systems 57, 38–68 (2016). doi:10.1016/j.is.2015.10.002

24. Lanz A., Weber B., Reichert M.: Time patterns for process-aware information systems.

Requirements Engineering 19(2), 113–141 (2014). doi:10.1007/s00766-012-0162-3

25.

Marjanovic O., Orlowska M.E.: On modeling and verification of temporal constraints in

production workflows. Knowl. and Inf. Syst. 1(2), 157–192 (1999)

26.

Monti E., Mottes M., Fraschini P., Brunelli P., Forlino A., Venturi G., Doro F., Perlini

S., Cavarzere P., Antoniazzi F.: Current and emerging treatments for the management

of osteogenesis imperfecta. Therapeutics and clinical risk management 6, 367 (2010)

27.

Morris P.: A structural characterization of temporal dynamic controllability. In: F. Ben-

hamou (ed.) Intl Conf on Principles and Practices of Constraint Programming (CP’06),

pp. 375–389. Springer (2006)

54 Roberto Posenato et al.

28.

Morris P.: Dynamic controllability and dispatchability relationships. In: H. Simonis

(ed.) Intl Conf on Integration of AI and OR Techniques in Constraint Programming

(CPAIOR’14), LNCS, vol. 8451, pp. 464–479. Springer (2014)

29.

Morris P.H., Muscettola N.: Temporal dynamic controllability revisited. In: National

Conf on Artificial Intelligence (AAAI’05), pp. 1193–1198 (2005)

30.

Morris P.H., Muscettola N., Vidal T.: Dynamic control of plans with temporal uncertainty.

In: Intl Joint Conf on Artificial Intelligence (IJCAI’01), pp. 494–502. Morgan Kaufmann

(2001)

31.

Reichert M., Weber B.: Enabling Flexibility in Process-Aware Information Systems -

Challenges, Methods, Technologies. Springer (2012). doi:10.1007/978-3-642-30409-5

32. Reijers H.A.: Design and Control of Workflow Processes. Springer (2003)

33.

Vanhatalo J., Völzer H., Koehler J.: The refined process structure tree. Data & Knowledge

Engineering 68(9), 793–818 (2009). doi:10.1016/j.datak.2009.02.015

34.

Weber B., Reichert M., Mendling J., Reijers H.A.: Refactoring large process model

repositories. Computers in Industry

(5), 467 – 486 (2011). doi:10.1016/j.compind.

2010.12.012

35.

Zhang Y., Perry D.E.: A Data-Centric Approach to Optimize Time in Workflow-Based

Business Process. In: 2014 IEEE International Conference on Services Computing, pp.

709–716. IEEE (2014). doi:10.1109/SCC.2014.129