Dealing with Changes of Time-Aware Processes [original]

Dealing with Changes of Time-Aware Processes?

Andreas Lanz and Manfred Reichert

Institute of Databases and Information Systems, Ulm University, Germany

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

Abstract.

The proper handling of temporal process constraints is crucial

in many application domains. Contemporary process-aware information

systems (PAIS), however, lack a sophisticated support of time-aware pro-

cesses. As a particular challenge, the execution of time-aware processes

needs to be flexible as time can neither be slowed down nor stopped.

Hence, it should be possible to dynamically adapt time-aware process

instances to cope with unforeseen events. In turn, when applying such dy-

namic changes, it must be re-ensured that the resulting process instances

are temporally consistent; i.e., they still can be completed without violat-

ing any of their temporal constraints. This paper presents the ATAPIS

framework which extends well established process change operations with

temporal constraints. In particular, it provides pre- and post-conditions

for these operations that guarantee for the temporal consistency of the

changed process instances. Furthermore, we analyze the effects a change

has on the temporal properties of a process instance. In this context, we

provide a means to significantly reduce the complexity when applying

multiple change operations. Respective optimizations will be crucial to

properly support the temporal perspective in adaptive PAIS.

1 Introduction

Time is a crucial factor regarding the proper support of business processes [

Moreover, in many application areas (e.g., patient treatment, automotive engi-

neering), the handling of temporal constraints is vital in order to successfully

execute and complete processes [

]. However, contemporary process-aware

information systems (PAIS) lack a comprehensive support of such time-aware

processes [

]. To remedy this drawback, the proper integration of temporal

constraints with both the design and run-time components of a PAIS has been

identified as a key challenge [

]. Our ATAPIS framework aims to provide com-

prehensive support for the specification, execution and monitoring of time-aware

processes in adaptive PAIS.

As a prerequisite for robust process execution in PAISs, the executable process

models must be sound [

]. Moreover, in the context of time-aware process models,

i.e., process models enriched with temporal constraints, the consistency of the

temporal constraints must be ensured [

]. Checking consistency of time-aware

A more complete and formally rigor version of this work is described in a technical

report [8]

2 Andreas Lanz and Manfred Reichert

process models at design time has been extensively studied in literature [

By contrast, only little attention has been paid to the proper run-time support

of time-aware processes [

]. During run time, the temporal consistency of process

instances needs to be continuously monitored and re-checked to avoid constraint

violations. Particularly, note that activity durations and deadlines are specific to

the executed process instance and only become known at run time [7].

As a particular challenge, temporal constraints cannot be considered in isola-

tion, but might interact with each other. Hence, complex algorithms are required

for checking the temporal consistency of a process model [

]. At run time,

however, respective calculations should be reduced to a minimum to ensure scal-

ability of the PAIS [

]. Otherwise, no run-time support of time-aware processes

will be possible at the presence of a large number of process instances.

As another challenge, time can neither be slowed down nor stopped. Accord-

ingly, time-aware processes need to be flexible to cope with unforeseen events

or delays during run time [

]. For example, it is common that deadlines are

re-scheduled or temporal constraints are dynamically modified in order to success-

fully complete a process instance being in trouble. Moreover, in certain scenarios

the instances of time-aware processes must be structurally changed (e.g., by

moving, deleting or inserting activities) to be able to meet a particular deadline.

In the context of such dynamic process changes, we must re-ensure that the

resulting process instances are sound and temporally consistent. While soundness

has been extensively studied in literature [

], this work shows how temporal

consistency of a time-aware process instance can be efficiently ensured in the

context of dynamic changes. Furthermore, we analyse the effects, changes have

on the temporal constraints of the respective process instance. In particular, we

show how the results of this analysis can be utilized to significantly reduce the

complexity when applying multiple change operations. For example, the latter

becomes crucial in the context of process evolution, where a possibly large set of

process instances needs to be migrated on-the-fly to a changed process model [

The remainder of the paper is organized as follows: Sect. 2 considers existing

proposals relevant for our work. Sect. 3 provides background information on

time-aware processes and defines the notion of temporal consistency. Sect. 4 first

introduces the set of change operations we consider, followed by an in-depth

discussion on how these change operations work in the context of time-aware

processes. Sect. 5 analyzes the impact a change has on the temporal constraints

of a process and proposes useful optimizations. Sect. 6 evaluates the proposed

approach. Finally, Sect. 7 concludes with a summary and outlook.

2 Related Work

In literature, there exists considerable work on managing temporal constraints for

business processes [

]. The focus of these approaches is on design-time

issues like the modeling and verification of time-aware processes. By contrast,

only few approaches consider run-time issues of time-aware processes [

]. In

particular, none of the latter considers dynamic changes in this context.

Dealing with Changes of Time-Aware Processes 3

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 TP1 – TP10 [10]

Most approaches dealing with the verification of time-aware processes use a

specifically tailored time model to check for the temporal consistency of process

models. This becomes necessary since the interdependencies between the various

temporal constraints of a process model can be quite complex and cannot be

suitably captured in the respective process model. A specific conceptual model

for temporal constraints is defined in [

]. In turn, [

] use an extended version

of the Critical Path Method known from project planning. Simple Temporal

Networks (STN) are used as basic formalism in [

], whereas [

] uses Conditional

Simple Temporal Networks with Uncertainty for checking the controllability of

process models, i.e., a more restrictive form of temporal consistency. This paper

relies on Conditional Simple Temporal Networks (CSTN), an extension of STN

that allows for the proper handling of exclusive choices [15].

In [

], we presented 10 empirically evidenced time patterns (TP), that repre-

sent temporal 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 [

]. Moreover, [

] elaborated the need

for a proper run-time support of time-aware processes.

Dynamic process changes were extensively studied in the past. Particularly,

there exists considerable work on ensuring structural and behavioural soundness

in the context of dynamic process changes [

]. A survey of approaches enabling

dynamic changes is provided in [

]. To the best of our knowledge, [

] is the

only work considering dynamic changes in the context of time-aware processes.

As opposed to our work, however, [

] only provides a high level discussion of the

different aspects to be considered when changing time-aware process instances,

temporal consistency being one of them.

3 Basic Notions

This section provides basic notions. First, it defines a set of elements for modeling

time-aware processes. Second, it introduces the notion of temporal consistency.

3.1 Time-aware Processes

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

cess schema needs to be defined (cf. Fig. 1). In our work, a process schema

corresponds to a process model; i.e., a directed graph, that comprises a set of

nodes—representing activities and control connectors (e.g., Start-/End-nodes,

XORsplits, or ANDjoins)—as well as a set of control edges linking these nodes and

specifying precedence relations between them. We assume that process models

4 Andreas Lanz and Manfred Reichert

Activity

Data object

AND-Block

XOR-Block

Control Edge

Data Edge

Process Schema S

[5, 25]

S [30, 120] S

E [5, 60] S

[5, 25]

[5, 40] [10, 25]

[10, 25] [60, 120]

Process Duration: [90, 200]

Fixed Date Element

Activity Duration

Date value for

Fixed Date Element G

Time Lag between two Activities

Fig. 1. Core Concepts of a Time-Aware Process Model

are well structured [

], e.g., sequences and branchings are specified in terms of

nested single-entry single-exit (SESE) blocks. Fig. 1 depicts an example of a well

structured process model with the grey areas indicating respective blocks. Each

process model contains a unique start and end node, and may be composed of

control flow patterns like sequence, parallel split (ANDsplit), synchronization

(ANDjoin), exclusive choice (XORsplit), and simple merge (XORjoin) (cf. Fig. 1).

At run time, process instances may be created and executed according to the

defined process model. We assume that a process instance is logically represented

by a clone of the respective process model augmented with instance-specific

information. If a process model contains XOR-blocks, uncertainty is introduced

since not all instances perform exactly the same set of activities. The concept of

execution path allows us to identify which activities and control connectors are

actually performed during the execution of a particular process instance.

We base our ATAPIS framework on the time patterns (TP) (cf. Sect. 2).

Specifically, we focus on the patterns being most relevant in practice [

In detail:

activity duration

(TP2) defines the minimum and maximum time span

[

dmin, dmax

](0

≤dmin ≤dmax

) allowed for executing a particular activity (or

node, in general). We assume that each activity has an assigned duration. Since

control connectors are automatically executed, we may assume a fixed duration

for them (e.g., [0

1]). In turn, a

process duration

[

dmin, dmax

]represents the

time span allowed for executing a process instance.

Time lags between two activities

(TP1) restrict the time span allowed

between the starting and/or ending instants of two arbitrary activities of a process

model [

]. In Fig. 1, a time lag is visualized through a dashed edge between

the source and target activity. The label of the edge specifies the constraint ac-

cording to the following template:

hISi

[

tmin, tmax

]

hITi

(

−∞≤tmin ≤tmax ≤∞

);

hISi,hITi∈{S, E}

mark the instant (i.e., starting or ending) of the source and

target activity the time lag applies to. In turn, [

tmin, tmax

]represents the range

allowed for the time span between instants

hISi

and

hITi

. Finally, note that a

control edge implicitly represents an

,∞

]

time lag between the two activities.

Fixed date elements

(TP4) allow restricting activity execution in relation

to a specific date (e.g., a deadline). Generally, the value of a fixed date element

is specific to a process instance. Fig. 1 visualizes a fixed date element through

a clock symbol attached to the activity. Thereby, label

hDi ∈ {ES, LS, EE, LE}

represents the activity’s earliest start date (

), latest start date (

), earliest

completion date (EE), or latest completion date (LE).

Fig. 1 shows an example of a process model exhibiting temporal constraints.

Note that, although some of the symbols used for visualizing the temporal con-

Dealing with Changes of Time-Aware Processes 5

straints resemble BPMN timer events, their semantics is quite different and

should not be mixed up.

3.2 Temporal Consistency of Time-Aware Processes

A time-aware process model is executed by performing its activities and control

connectors, while obeying a set of temporal constraints. We denote a process

model as temporally consistent if it is possible to perform all execution paths

without violating the temporal constraints involved. Temporal consistency of

a time-aware process model (and its instances) constitutes a fundamental pre-

requisite for its robust and error-free execution [

]. For any PAIS supporting

time-aware processes, therefore, a crucial task is to check temporal consistency of

the process model at design time as well as to monitor and re-check corresponding

instances during run time. This is particularly challenging since temporal con-

straints might interact with each other resulting in complex interdependcies (e.g.,

a future deadline might restrict the duration of some or all preceding activities).

Whether a time-aware process model is temporally consistent can be checked

by mapping it to a conditional simple temporal network (CSTN)—a problem

known from artificial intelligence [

]. In ATAPIS, we use CSTN since it allows us

to exploit and reuse checking algorithms for a well founded model representing

temporal constraints. Finally, CSTN allows capturing the complex interdepen-

dencies between constraints, which cannot be captured in process models.

Definition 1 (Conditional Simple Temporal Network).

A Conditional

Simple Temporal Network (CSTN) is a 6-tuple hT ,C, L, OT ,O, P i, where:

–Tis a set of real-valued variables, called time-points;

–Pis a finite set of propositional letters (or propositions);

–L

T → P∗

is a function assigning a label to each time-point in

; a label is

any (possibly empty) conjunction of (positive or negative) letters from P.1

–C

is a set of labeled simple temporal constraints (constraint in the following);

each constraint

cXY ∈ C

has the form

cXY

[

x, y

]

XY , βi

, where

X, Y ∈ T

−∞ ≤ x≤y≤ ∞, and β∈P∗is a label.

–OT ⊆ T is a set of observation time-points;

–O

P→ OT

is a bijection that associates a unique observation time-point to

each propositional letter from P.

Time-points represent instantaneous events that may be, for example, associated

with the start / end of activities. In turn, at observation time-points a decision

regarding possible execution paths is made. More formally, when executing obser-

vation time-point

, the truth-value of the associated proposition (i.e.,

O−1

(

))

is determined. A constraint

cXY

[

x, y

]

XY , βi

expresses that the time span be-

tween time-points

and

must be at least

and at most

, i.e.,

Y−X∈

[

x, y

The label attached to each time-point (constraint) indicates possible executions

of the CSTN, i.e., a particular time-point (constraint) will be only considered if

In the following we use small Greek letters

α, β, . . .

to denote arbitrary labels. The

empty label is denoted by .

6 Andreas Lanz and Manfred Reichert

ASAE

FSFE

GSGE

DSDE

HSHE

ESEE

BSBE

CSCE

PSPE

Time Model M

ANDsplit G HA

CANDjoin

XORsplit p? XORjoin D

‹[5, 25], □›

‹[5, 40], □› ‹[10, 25], □›

‹[0, 1], □› ‹[0, 1], □›‹[60, 120], □›

‹[10, 25], □›

‹[0, 1], □›

‹[5, 25], p›

‹[5, 25],

p›

‹[0, 1], □› ‹[5, 25], □›

‹[0, 1], p›

‹[0, 1],

p›

‹[5, 60], □›

‹[90, 200], ◊›

‹[0, ∞], □›

‹[30, 120], p›

‹[0, ∞], p›

‹[0, ∞],

p›

E F

Time-Point

Observation

Time-Point

Activity Mapping

Temporal Constraint

Fig. 2. CSTN Representation of the Process Model from Fig. 1

the corresponding label is satisfiable in the respective instance. Fig. 2 depicts the

CSTN corresponding to the process model from Fig. 1.

The solution to a CSTN can be defined as follows [6]:

Definition 2 (Scenario and Solution).

Given a CSTN

hT ,C, L, OT ,O, P i

a scenario over set

is a function

P→ {true, false}

that assigns a truth-

value to each proposition in P.

A solution for CSTN

under scenario

then corresponds to a complete set

of assignments to all time-points

X∈ T

with

(

)) =

true

, which satisfies

all constraints h[x, y]XY , βi∈Cfor which sP(β) = true holds.

We denote the CSTN corresponding to a time-aware process model as its time

model. The required mapping can roughly be described as follows [

]: First, the

control flow of the process model is mapped to a CSTN. Particularly, each control

flow element implicitly represents a temporal constraint. Each activity, ANDsplit,

ANDjoin, and XORjoin

is represented as a pair of time-points

NiS

and

NiE

corresponding to the starting / ending instant of the respective node. In turn,

for an XORsplit, the ending instant (i.e.,

NiE

) is represented by an observation

time-point. Next, a constraint

[

dmin, dmax

]

NiS NiE ,i

is added between

NiS

and

NiE

representing the duration [

dmin, dmax

]of the node. Further, for any control

edge between nodes

and

, a constraint

,∞

]

NiE NjS ,i

is added between

the time-points representing the ending instant of

and starting instant of

If the source of the edge is an XORsplit, in addition, the label of the constraint is

augmented by proposition

O−1

(

). The latter represents the decision made

at the corresponding observation time-point

, i.e., the label of the constraint

,∞

]

NiE NjS , βi

belonging to the “

true

”-branch is set to

βp

and the one of the

“

false

”-branch to

β¬p

Further, the labels of all constraints and time-points

corresponding to activities, connectors and control edges in the XOR-block are

augmented by either por ¬pdepending on the branch they belong to.

Next, temporal constraints are mapped to the CSTN. A time lag

hISi

[

tmin,

tmax

]

hITi

corresponds to a constraint

[

tmin, tmax

]

NihISiNjhITi,L(NihISi)∧L(NjhITi)i

between the two time-points representing the respective instants of nodes

and

. In turn, a fixed date element is initially represented as a constraint

∞

]

ZNhDi,L(NhDi)i

with

being a special time-point representing time “0”. During

run time, value [0,∞]of the constraint will be updated according to the actual

Note that this can be easily extended to consider more than two branches, but for

the sake of simplicity, we only consider two branches in this paper.

Dealing with Changes of Time-Aware Processes 7

fixed date chosen. Finally, process duration [

dmin, dmax

]is represented as con-

straint

[

dmin, dmax

]

N0SNkE ,i

between the time-points representing the starting

instant

N0S

of the first and the ending instant

NkE

of the last

node of the process

As example consider Fig. 2. Note that the labels of the constraints represent-

ing the XOR-block are either set to

¬p

. For the sake of readability, all edges

without annotation are assumed to have bounds h[0,∞],i.

Based on Def. 2, we formally define the notion of temporal consistency for

time-aware process models.

Definition 3 (Temporal Consistency).

A CSTN

hT ,C, L, OT ,O, P i

is called

weakly consistent iff for each scenario sPat least one solution exists [15].

A time-aware process model is denoted as temporally consistent iff the corre-

sponding time model (i.e., its CSTN representation) is weakly consistent.

When executing a time-aware process model, temporal consistency of the re-

spective instances needs to be continuously monitored and re-checked. For this

purpose, the minimal network of a CSTN must be determined.

Definition 4 (Minimal Network).

The minimal network of a CSTN

hT ,C, L, OT ,O, P i

is the unique CSTN

hT ,C0, L, OT ,O, P i

having the

same set of solutions as

and each value allowed by any constraint

c∈ C0

being

part of at least one solution of S.

For any CSTN

a minimal network exists iff

is weakly consistent. In particular,

such a minimal network provides a restricted set of constraints: As long as the

value of each time-point is consistent with all constraints referring to it, we can

guarantee that the entire CSTN is weakly consistent. Besides explicit constraints

c∈ C

we obtain when mapping the process model to the CSTN, the minimal

network contains implicit constraints between any pair of time-points that may

occur in the same execution path. Note that these implicit constraints represent

the effects the explicit constraints have on the overall CSTN (i.e., they represent

interdependencies between explicit constraints). The implicit constraints are

derived from the explicit ones when determining the minimal network. How to

determine the minimal network is described in [15].

When executing a process instance, the minimal network of the time model

created at design time is cloned. This instance time model is then kept up-to-date

with the actual temporal state of the process instance (e.g., deadline, activity

start and completion times). Further, it is used to monitor and re-check temporal

consistency of the instance [

]. Cloning the time model becomes necessary as

the temporal state of each process instance is unique; i.e., no two instances have

exactly the same instance time model.

4 Change Operations for Time-aware Processes

Standard change patterns adapting process instances without temporal con-

straints have been extensively studied in literature [

]. This section discusses how

respective change operations may be transferred to time-aware processes. Sect. 4.1

8 Andreas Lanz and Manfred Reichert

Operation Informal Description

Control Flow Changes

InsertSerial(n1, n2, nnew,

[dmin, dmax])

Inserts node nnew with duration [dmin, dmax]between directly

succeeding nodes n1and n2.

InsertP ar(n1, n2, nnew,

[dmin, dmax])

Inserts node nnew with duration [dmin, dmax]in parallel to the

SESE block defined by n1and n2.

InsertCond(n1, n2, nnew ,

[dmin, dmax], c)

Inserts node nnew with duration [dmin, dmax]and condition cas

well as an XOR block between succeeding nodes n1and n2.

DeleteActivity(n)Deletes activity n.†

Temporal Constraints Changes

InsertT imeLag(n1, n2, typetl,

[tmin, tmax])

Inserts a time lag [tmin, tmax]between nodes n1and n2. Thereby,

typetl ∈ {start-start,start-end,end-start,end-end}describes

whether the time lag is inserted between the start of the two ac-

tivities, the start of n1and the end of n2, the end of n1and the

start of n2, or the end of the two activities.

InsertF DE(n, typefde)Adds a fixed date element of type typefde ∈ {ES, LS, EE, LE}

to node n.

DeleteT imeLag(n1, n2, typetl)Deletes the time lag of type typetl between nodes n1and n2.†

DeleteF DE(n, typef de)Deletes a fixed date element of type typefde from node n.†

†Delete operations are not considered in this paper, but are discussed in a technical report [8].

Table 2. Basic Change Operations

presents the change operations applicable to time-aware processes. Sect. 4.2 then

provides an in-depth discussion of these operations and shows how they can be

extended to ensure temporal consistency of a changed process instance.

4.1 Basic Change Operations

When changing a process instance or—more generally—its process model, sound-

ness must be ensured. To achieve this, ATAPIS abstracts from low-level change

primitives (e.g., adding an edge or node) to higher-level change operations with

well-defined pre- and post-conditions (e.g., inserting a node serially between

two succeeding nodes) [

]. Applied to a sound process model, such a high-level

change operation guarantees that the modified process model is structurally

and behaviourally sound as well [

]. The upper part of Tab. 2 shows selected

change operations required for structurally modifying a process instance. Note

that respective operations may be combined to realize more complex change

patterns [

] (e.g., move activity). ATAPIS extends the set of structural change

operations by change operations that allow modifying the temporal constraints of

a process model, e.g., inserting a time lag (see the bottom of Tab. 2). Altogether,

the operations allow changing a time-aware process instance, while guaranteeing

soundness of the corresponding process model. Due to lack of space, this paper

restricts itself to insert operations. A detailed presentation of delete operations

is provided in a technical report [8].

4.2 Applying Change Operations to Time-aware Processes

When modifying the model of a time-aware process instance, it must be ensured

that the resulting process instance is temporally consistent. This section defines

basic criteria ensuring that the application of a change operation does not result

in a temporally inconsistent process instance. We further analyze the local impact

Dealing with Changes of Time-Aware Processes 9

<[max{cmin,dmin}, cmax], β>

<[dmin,dmax], β>

<[0, cmax-dmin], β> <[0, cmax-dmin], β>

ASAEXSXEBSBE

<..., β> <..., β>

<[cmin, cmax], β>

<..., β> <..., β>

ASAEBSBE

dmin ≤ tmax

[dmin,dmax]BA

[dmin,dmax]

E [tmin, tmax] S E [tmin, tmax] S

[dmin,dmax]

InsertSerial(A, B, X,

[dmin,dmax])

E [tmin, tmax] S

Process Model

Time Model

Fig. 3. Change Operation Insert Serial

InsertSerial(n1,n2,nnew,[dmin,dmax])*

Pre succ(n1) = n2,∀h[cmin, cmax]N1EN2S, βi∈C:cmax ≥dmin

Init γ=L(N1E)∧L(N2S)

Post // Update process model:

. . .

// Add mapping to instance time model:

AddT imeP oint(NnewS , γ),AddT imeP oint(NnewE , γ),

AddConstraint(NnewS , NnewE ,[dmin, dmax], γ),

AddConstraint(N1E, NnewS ,[0,∞], γ),AddConstraint(NnewE , N2S,[0,∞], γ),

// Adapt instance time model:

∀h[cmin, cmax]N1EN2S, βi∈C:UpdateConstraint(N1E, NnewS ,[0, cmax −dmin], β),

UpdateConstraint(NnewE , N2S,[0, cmax −dmin], β),

UpdateConstraint(N1E, N2S,[max{cmin, dmin}, cmax)], β)

*The complete version of the algorithm is provided in [8].

Algorithm 1: InsertSerial

a particular change operation has on the temporal properties of the respective

process model, i.e., its temporal constraints.

When applying a change operation to a process instance, state-specific pre-

and post-conditions must be met [

]. Although these are not explicitly consid-

ered in this paper, they apply to time-aware processes as well. Furthermore, any

time-related, instance-specific data (e.g., activity start and completion times) is

maintained in the corresponding instance time model (cf. Sect. 3.2), i.e., it is

sufficient to only consider the current instance time model of the process instance.

Inserting an Activity Serially.

InsertSerial(

n1, n2, nnew,

[

dmin, dmax

]) is the

first change operation we consider. It allows inserting node

nnew

with duration

[

dmin, dmax

]between directly succeeding nodes

and

(cf. Fig. 3). Regarding

the temporal properties of the resulting process model, the insertion of

nnew

might first and foremost increase the minimum time distance between

and

dmin

. By contrast, the maximum distance between the two nodes is not

affected by the change as the newly added control connectors do not constrain it.

Accordingly, if for the instance time model the minimum duration

dmin

is compli-

ant with any implicit or explicit constraint

[

cmin, cmax

]

N1EN2S, βi

between the

ending instant of

and the starting instant of

(i.e.,

dmin ≤cmax

), the node

insertion will not affect temporal consistency of the process instance.

Remember

that each value of each constraint in the instance time model is part of at least one

solution (cf. Def. 4), i.e., one viable execution of the process model. After adding

the node to the process instance, the mapping of this node and the control edges

must be added to the instance time model as well. Further, the instance time

model must be locally adapted to properly reflect the changes. In particular, the

constraint between the ending instant of

and the starting instant of

must

be updated to [

max{cmin, dmin}, cmax

]in order to consider the new minimum

Note that any implicit constraint

[

cmin, cmax

]

N1EN2S, βi

is always at least as restric-

tive as any explicit time lag E[tmin, tmax]Sbetween n1and n2.

10 Andreas Lanz and Manfred Reichert

<[max{cmin,dmin}, tmax], β c>

<[cmin, cmax], β

<[dmin,dmax], β c>

<[0, cmax-dmin], β c> <[0, cmax-dmin], β c>

ASAE

XSXE

BSBE

GsS GsE GjS GjE

<[cmin, cmax], β>

ASAEBSBE

dmin ≤ tmax

[dmin,dmax]

E [tmin, tmax] S

GsGj

[dmin,dmax]

InsertCond(A, B, X, [dmin,dmax])

E [tmin, tmax] S

Process Model

Time Model

Fig. 4. Change Operation Insert Conditional

InsertCond(n1,n2,nnew,[dmin,dmax],c)*

Pre succ(n1) = n2,∀h[cmin, cmax]N1EN2S, βi∈C:cmax ≥dmin

Init γ=L(N1E)∧L(N2S)

Post // Update process model:

. . .

// Add mapping to instance time model:

AddT imeP oint(GsS , γ),AddObservationT imeP oint(GsE , c, γ),

AddConstraint(GsS , GsE ,[0,1], γ),

AddT imeP oint(NnewS , γ),AddT imeP oint(NnewE , γc),

AddConstraint(NnewS , NnewE ,[dmin, dmax], γc),

. . .

AddConstraint(GsE , GjS ,[0,∞], γ¬c),

// Adapt instance time model:

. . .

∀h[cmin, cmax]N1EN2S, βi∈C:UpdateConstraint(N1E, N2S,[cmin, cmax], β¬c),

AddConstraint(N1E, N2S,[max{cmin, dmin}, cmax], βc)

*The complete version of the algorithm is provided in [8].

Algorithm 2: InsertCond

distance between the two nodes (cf. Fig. 3), i.e., certain values permitted by the

old constraint might no longer be part of any solution. It further becomes evident

that the constraints corresponding to the two newly added control edges must

be initialized to [0

, cmax −dmin

](cf. Fig. 3). Algorithm 1 defines the pre- and

post-conditions for applying change operation InsertSerial to a process instance.

The changes applied to the instance time model need to be propagated to all

other constraints in order to remove values no longer contributing to any solution.

Note that this must be accomplished before performing any other change or

resuming the execution of the process instance. Practically, this means that the

minimality of the changed instance time model needs to be restored. This may be

achieved by applying the same algorithm as the one initially used for determining

the minimal time model (cf. Sect. 3.2).

Inserting an Activity in Parallel.

From a temporal point of view, change

operation InsertPar (cf. Tab. 2) is similar to InsertSerial. Node

nnew

(together

with ANDsplit and ANDjoin nodes) is inserted “serially” between nodes

and

—the temporal effects of the enclosed SESE block are already considered in the

implicit constraint between n1and n2. A detailed discussion is provided in [8].

Inserting an Activity Conditionally.

Change operation InsertCond(

n1, n2,

nnew,[dmin, dmax], c)inserts node nnew conditionally between succeeding nodes

and

. This change is accomplished by first inserting XORsplit

and XOR-

join

sequentially between

and

and then

nnew

conditionally between

and

(cf. Fig. 4). The transition conditions of the control edges linking

and its successors are set to

and

¬c

, respectively. When adding XORsplit

and condition

¬c

to the process model, a set of additional execution paths

results; i.e., each execution path of the old process model, which contains

and

, can now be mapped to two execution paths: one with

false

(i.e.,

¬c

)

Dealing with Changes of Time-Aware Processes 11

<[max(cmin,tmin), min(cmax,tmax)], β>

ASAEBSBE

<[cmin, cmax], β>

ASAEBSBE

tmin ≤ cmax

tmax ≥ cmin

A B

E [tmin, tmax] S

InsertTimeLag(A, B, start-start,

[tmin,tmax])

A B

E [tmin, tmax] S

Process Model

Time Model

Fig. 5. Change Operation Insert Time Lag

InsertTimeLag(n1,n2,typetl,[tmin,tmax])

Pre hISi=S typetl =start-*

E typetl =end-* ,hITi=S typetl =*-start

E typetl =*-end

(L(N1hISi)∧L(N2hITi)) is satisfiable

∀h[cmin, cmax]N1hISiN2hITi, βi∈C:cmin ≤tmax ∧tmin ≤cmax

Post // Update process model:

AddT imeLag(n1, n2,hISi[tmin, tmax]hITi)

// Add mapping to instance time model:

AddConstraint(N1hISi, N2hITi,[tmin, tmax], L(N1E)∧L(N2S))

// Adapt instance time model:

∀h[cmin, cmax]N1EN2S, βi∈C:

UpdateConstraint(N1hISi, N2hITi,[max{cmin, tmin},min{cmax, tmax}], β)

Algorithm 3: InsertTimeLag

representing the previous execution path and one with

true

representing

the new path containing

nnew

between

and

. Hence, for any execution

path containing

nnew

,InsertCond has similar effects as InsertSerial. In turn, any

execution path not containing

nnew

remains unchanged (except for the added

XORsplit and XORjoin, that constitute silent nodes). Altogether, for InsertCond

similar pre-conditions as for InsertSerial hold (cf. Algorithm 1).

In the context of a process instance change, the corresponding instance time

model needs to be adapted by adding the mappings of the inserted elements

as shown in Fig. 4. Note that this results in a new observation time-point

GsE

and proposition

to the instance time model (cf. Sect. 3.2). Accordingly, the

labels of the temporal constraints representing

nnew

and the two control edges

connecting it with

and

must be set to

βc

with

being the label of the

original constraint between

N1E

and

N2S

. In turn, the label of the constraint

corresponding to the control edge between

and

must be set to

β¬c

. Fi-

nally, the constraint between the ending instant of

and the starting one of

needs to be updated: The label of the original constraint must be augmented by

proposition

¬c

resulting in constraint

[

cmin, cmax

]

N1EN2S, β¬ci

. Further, another

constraint

[

max{cmin, dmin}, cmax

]

N1EN2S, βci

containing proposition

must be

added between the two time-points. The latter corresponds to the case

nnew

executed between the two nodes. Algorithm 2 defines the pre- and post-conditions

of InsertCond. When applying this operation, again the minimality of the adapted

instance time model must be restored. This is required before performing any

other change or resuming the execution of the process instance.

Inserting a Time Lag.

Operation InsertTimeLag(

n1, n2, typetl,

[

tmin, tmax

])

allows adding a time lag between activities

and

. The instants the time lag

refers to are specified by parameter

typetl

. Adding a time lag is only possible if

there exists at least one execution path containing both nodes [

]. The instance

time model is then adapted by adding a constraint

[

tmin, tmax

]

N1hISiN2hITi, βi

be-

tween the time-points representing the respective instants (start vs. end) of the two

nodes. Basically, this updates each implicit constraint

[

cmin, cmax

]

N1hISiN2hITi,

βi

. Note that this is only possible if the resulting constraint [

max{cmin, tmin},

12 Andreas Lanz and Manfred Reichert

min{cmax, tmax}

]in the adapted instance time model still permits at least one

value, i.e., it allows for at least one possible solution. Accordingly, in order to

apply the operation it must hold

cmin ≤tmax ∧tmin ≤cmax

. Algorithm 3 defines

the pre- and post-conditions. After updating the temporal constraints, minimality

of the adapted instance time model must be restored.

Inserting a Fixed Date Element.

Inserting a fixed date element (i.e., opera-

tion InsertFDE) is equivalent to adding a time lag between the special time-point

(indicating time “0”) and the respective instant of the node (cf. Sect. 3.2) [

5 Analyzing the Effects of Change Operations

When changing a time-aware process instance both the process model and the

instance time model must be updated. In this context, the minimality of the

instance time model must be restored after each change operation. Only then it

can be ensured that another change within the same change transaction may be

applied without violating temporal consistency of the process instance. However,

calculating the minimal network of a CSTN is expensive regarding computation

time, i.e., its complexity is

(

)with

being the number of time-points and

the number of observation time-points in the CSTN. Consequently, there might be

significant delays when applying multiple change operations to large time-aware

process instances. This becomes even more pressing in the context of process

schema evolution [

] when migrating a potentially large set of process instances

to a new schema version (i.e., process model). Hence, the maximum effect a par-

ticular change has on the instance time model must be estimated. Based on this

estimation, it becomes possible to decide whether another change operation may

be applied without need to restore minimality of the instance time model first.

When applying the change operations from Sect. 4.2 to the respective instance

time model, two types of changes result: adding a temporal constraint or making

an existing one more restrictive. Hence, it is sufficient to consider the effects a

basic change has on a minimal time model. Regarding changes that make an

existing constraint more restrictive, Theorem 1 shows how their maximum effects

can be estimated.

Theorem 1 (Restricting a constraint in a minimal network).

Let

hT ,CM, L, OT ,O, P i

be a minimal CSTN and

M∗

hT ,CM∗, L, OT ,O, P i

the CSTN derived from

by replacing constraint

cAB

[

x, y

]

AB, βi ∈ CM

with the more restrictive constraint

c∗

[

σ, y −ρ

]

AB, βi

;

σ, ρ ≥

0; i.e.,

C∗

M=CM\cAB ∪ {c∗

AB}.

Then: For the minimal network

hT ,CN, L, OT ,O, P i

M∗

it holds:

for any constraint

[

x0, y0

]

XY , γi∈CN

the lower bound is increased by at

most

max{σ, ρ}

and the upper bound is decreased by at most

compared to

the original constraint cXY =h[x, y]XY , γi∈CM. Formally:

∀h[x, y]XY , γi∈CM,h[x0, y0]XY , γi∈CN: (x≤x0≤x+δ)∧(y≥y0≥y−δ)

A proof of Theorem 1 can be found in [

]. Assume that due to a change a con-

straint

[x, y]XY

in the time model is restricted to

[x∗, y∗]XY

[x+ρ, y −σ]XY

Dealing with Changes of Time-Aware Processes 13

and afterwards minimality of the time model is restored. Theorem 1 now states

that any constraint

[u, v]UV

in the original time model is restricted to at most

[u0, v0]UV = [u+δ, v −δ]UV with δ= max{ρ, σ}in the new time model.

Reconsider operation InsertSerial. Assume that the instance time model is

adapted as described by Algorithm 1. The next step would be to restore minimal-

ity of this instance time model. First of all, note that the constraints introduced

by the newly added activity and control edges do not affect the other constraints

when restoring minimality. By construction, their effects are already incorporated

in the constraint between time-points

N1E

and

N2S

, which is updated in the

context of the operation (cf. Algorithm 1; see [

] for details). The only change

having an effect on the resulting instance time model is the one restricting con-

straint

[cmin, cmax]

between

N1E

and

N2S

[max{cmin, dmin}, cmax]

. Note that

if the constraint is not changed (i.e.,

dmin ≤cmin

), the existing constraints of

the instance time model also need not be changed. Otherwise, the lower bound of

the constraint is increased by

dmin −cmin

. Theorem 1 implies that the upper

and lower bound of any other constraint in the new instance time model will be

restricted by at most δas well. Thus we are able to approximate the maximum

difference between the new instance time model and the original one.

From this we can conclude that when applying another insert operation, it will

be sufficient to verify that any precondition referring to a constraint

[

x, y

]

XY , βi

of the instance time model is satisfied for the respective approximated constraint

[

δ, y −δ

]

XY , βi

as well. In this case, the insert operation may be applied

without violating the temporal consistency of the process instance. In particular,

and this is a fundamental advantage of ATAPIS, we need not restore minimality

of the modified instance time model prior to the application of the operation. By

contrast, if the precondition is not met for the approximated constraint, it might

still be possible to apply the change without violating temporal consistency. In

this case, however, minimality of the modified instance time model must be first

restored before deciding whether the change may be applied.

Similar rules apply to all other insert operations. Regarding InsertCond (cf.

Algorithm 2), in particular, the change relevant to the instance time model

is the one restricting the constraint between time-points

N1E

and

N2S

[max{cmin, dmin}, cmax]

, i.e., the impact on the other constraints is at most

max{

, dmin −cmin}

. Finally, for InsertTimeLag, the maximum impact

corresponds to δ= max{0, tmin −cmin, tmax −cmax}(cf. Algorithm 3).

Based on these observations it becomes possible to apply a sequence of change

operations to a process instance within the same transaction without need to

restore minimality of the instance time model after each change. If a sequence

of change operations

op1, . . . , opn

with impacts

δ1, . . . , δn

shall be applied to

a process instance, it will be sufficient to consider the aggregated impact of

the previously applied operations. Practically speaking, for operation

opi

, ap-

proximated constraint [

Pi−1

j=1 δj, y −Pi−1

j=1 δj

]

needs to be considered to

determine whether the operation may be applied. Note that this will significantly

reduce complexity when applying multiple change operations. However, the actual

savings depend on the strictness of the constraints of the time-aware process

14 Andreas Lanz and Manfred Reichert

Process Instance

Instance Time Model

Process Instance

Instance Time Model

[11, 20]

[0, 7]

[6, 8]

[3, 5]

ASAE

BSBE

[10, 15]

DSDE

[7, 14]

[3, 5]

CSCE

[5, 7]

FSFE

[0, 10]

[0, 7]

[0, 10]

[0, 7]

[6, 8]

[4, 9] B

[3, 5]

[10, 15]

[3, 5] F

[5, 7]

InsertSerial(A, ANDsplit, X, [4, 9])

E [10, 20] S

ANDsplit ANDjoin

E [7, 15] S

δ = 0

[11, 20]

[4, 7]

[6, 8]

[3, 7]

ASAE[4, 7]

XSXE

BSBE

[10, 15]

DSDE

[7, 14]

[3, 5]

CSCE

[5, 7]

FSFE

[0, 10]

[0, 7]

[0, 10]

[0, 7][0, 3] [0, 3]

[6, 8]

[3, 5]

[10, 15]

[3, 5] F

[5, 7]

[9, 15] InsertSerial(B, C, Y, [9, 15])

E [10, 20] S

E [7, 15] S

ANDsplit ANDjoin

[4, 9]

4 ≤ 7

δ = 4

9 ≤ 14 - δ = 10

[11, 20]

[4, 7]

[6, 8]

[3, 5]

ASAE[4, 7]

XSXE

BSBE

[10, 15]

DSDE

[9, 14]

[3, 5]

CSCE

[5, 7]

FSFE

[0, 10]

[0, 7]

[0, 10]

[0, 9][0, 3] [0, 3] [9, 15]

YSYE

[0, 5] [0, 5]

[19, 20]

[4, 5]

[6, 8]

[3, 4]

ASAE[4, 5]

XSXE

BSBE

[10, 15]

DSDE

[9, 10]

[3, 4]

CSCE

[5, 7]

FSFE

[0, 6]

[0, 1]

[0, 6]

[0, 1][0, 1] [0, 1] [9, 10]

YSYE

[0, 1] [0, 1]

[6, 8]

[3, 5]

[10, 15]

[3, 5] F

[5, 7]

[5, 8] InsertSerial(D, ANDjoin, Z, [5, 8])

E [10, 20] S

E [7, 15] S

ANDsplit ANDjoin

[4, 9]

[9, 15]

δ = 4+2

δ = 0 restore minimality

[19, 20]

[4, 5]

[6, 8]

[3, 4]

ASAE[4, 5]

XSXE

BSBE

[10, 15]

DSDE[5, 8]

ZSZE

[9, 10]

[3, 4]

CSCE

[5, 7]

FSFE

[0, 6]

[0, 1]

[0, 1][0, 1] [0, 1] [9, 10]

YSYE

[0, 1] [0, 1]

[0, 1]

[5, 6]

restore minimality

done!

[6, 8]

[3, 5]

[10, 15]

[3, 5] F

[5, 7]

E [10, 20] S

E [7, 15] S

ANDsplit ANDjoin

[4, 9]

[9, 15]

[5, 8]

5 ≤ 10 - δ = 4 δ = 5

5 ≤ 6

9 ≤ 10

*Note that for sake of compactness only relevant constraints and no labels are shown for the instance time models.

Fig. 6. Applying Multiple Change Operations to a Process Model

model; if the latter is “heavily” constrained, only few change operations can be

applied without need to restore minimality of the instance time model. In turn,

if the constraints are “weak”, multiple change operations may be applied at once,

without having to restore minimality of the instance time model

between changes

We illustrate our approach along the example from Fig. 6. It depicts a process

instance and corresponding instance time model to which a series of three change

operations



shall be applied. First, activity

with duration

[4,9]

shall be

inserted between

and

ANDsplit

(Fig. 6



). This is possible without violating

the temporal consistency of the process instance since the minimum duration of

is lower than the maximum time distance between

and

ANDsplit

(i.e., 4

≤

7).

After performing the change, the value used for approximating the instance time

model becomes

= 4

−

0 = 4. Next,

shall be inserted between

and

(Fig. 6



Again this is possible since the minimum duration is lower than the approximated

maximum time distance (i.e., 9

≤

−δ

= 10). Afterwards

is increased to

= 4 + (9

−

7) = 6. However, inserting

with duration

[5,8]

between

and

ANDjoin

(Fig. 6



) is then not possible based on the approximated instance

time model as the precondition of the respective change operation cannot be

met (i.e., 5

6≤

−δ

= 4). Hence, minimality of the instance time model must

be restored (Fig. 6



). Afterwards, inserting

becomes possible as for the new

instance time model the precondition of the operation is met. Finally, minimality

of the last instance time model must be restored (Fig. 6 e

).

6 Proof of Concept

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

our ATAPIS Toolset, which is based on the AristaFlow BPM Suite [

]. This

prototype enables users to create time-aware process models and to automatically

Dealing with Changes of Time-Aware Processes 15

Fig. 7. Screenshot of the Prototype (based on the AristaFlow BPM Suite)

generate respective time models based on CSTN. Further, the presented change

operations may be applied to both process models and corresponding instances.

Particularly, they are based on AristaFlow’s well-founded set of change opera-

tions [

]. Overall, the prototype demonstrates the applicability of our approach.

The screenshot from Fig. 7 shows the ATAPIS Toolset

: at the top, a process

model from the healthcare domain comprising several temporal constraints is

shown. At the bottom, the automatically generated time model and its minimal

network are depicted. Finally, the right side displays the available set of change

operations. Whether a particular change operation may be applied is decided by

checking both structural and temporal preconditions. When applying an opera-

tion to the process model (i.e., schema or instance) all three models are updated

simultaneously as described in Sect. 4.1. A first simulation based on our prototype

shows a significantly improved performance of our approximation-based approach

for applying multiple change operations compared to the

“classical approach” [8].

7 Conclusion

Time constitutes a fundamental concept for the operational support of business

processes in PAISs. In business, where missed deadlines and violations of temporal

constraints might cause significant problems, it is crucial for enterprises to be

able to efficiently control and monitor these temporal constraints during run

time. Since process execution does not always stick to the plan, enterprises must

be further able to flexibly react to deviations in a time-aware process instance

without affecting other properties of the instance. This paper considered dynamic

changes of time-aware process instances. First, we defined change operations for

time-aware processes. Second, we specified pre- and post-conditions for these

4A screencast demonstrating the toolset is available at dbis.info/atapis

16 Andreas Lanz and Manfred Reichert

operations, which ensure that changed process instances remain temporally con-

sistent. Third, we analyzed the effects respective change operations have on

the temporal constraints of the process instance. Fourth, we approximated the

resulting temporal properties of the entire process instance. In particular, this

allows us to significantly reduce the complexity of the required time calculations

in the context of subsequent changes. In order to demonstrate the feasibility of

the presented approach, a powerful proof-of-concept prototype was implemented.

We are currently investigating the pre- and post-conditions as well as the

impact of more complex change patterns (e.g., move). We further will examine

how the presented results can be applied to evolve time-aware processes and

migrate a large set of process instances to a new process model. Finally, we are

integrating advanced time-management capabilities into the AristaFlow BPM

Suite to obtain a fully-fledged time- and process-aware information system.

References

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

Distrib Para Dat 11(3), 269–306 (2002)

Chen, J., Yang, Y.: Temporal dependency based checkpoint selection for dynamic

verification of temporal constraints in scientific workflow systems. ACM Trans on

Soft Eng and Methodol 20(3), 9:1–9:23 (2011)

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

temporal workflows. TAAS 7(2), 19:1–19:29 (2012)

Eder, J., Euthimios, P., Pozewaunig, H., Rabinovich, M.: Time management in

workflow systems. In: Proc BIS’99. pp. 265–280 (1999)

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

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

Hunsberger, L., Posenato, R., Combi, C.: The dynamic controllability of conditional

STNs with uncertainty. In: Proc PlanEx’12 (2012)

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

processes at run time. In: Proc CoopIS’13. pp. 39–56 (2013)

Lanz, A., Reichert, M.: Process change operations for time-aware processes. Tech.

Rep. UIB-2014-01, University of Ulm (2014), dbis.eprints.uni-ulm.de/1027/

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)

10.

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

systems. Req Eng 19(2), 113–141 (2014)

11.

Marjanovic, O., Orlowska, M.E.: On modeling and verification of temporal con-

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

12.

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

Challenges, Methods, Technologies. Springer (2012)

13.

Rinderle, S., Reichert, M., Dadam, P.: Correctness criteria for dynamic changes in

workflow systems: A survey. Data & Knowl Eng 50(1), 9–34 (2004)

14.

Sadiq, S.W., Marjanovic, O., Orlowska, M.E.: Managing change and time in dynamic

workflow processes. Int’l J Coop Inf Syst 9(1-2), 93–116 (2000)

15.

Tsamardinos, I., Vidal, T., Pollack, M.: CTP: A new constraint-based formalism

for conditional, temporal planning. Constraints 8(4), 365–388 (2003)