Dealing with Forward and Backward Jumps in Workflow Management Systems [original]

Digital Object Identiﬁer (DOI) 10.1007/s00450-004-0157-5

Informatik Forsch. Entw. (2004) 18: 132–151

Dealing with forward and backward jumps

in workﬂow management systems

Manfred Reichert1, Peter Dadam1, Thomas Bauer2

1University of Ulm, Dept. Databases and Information Systems, 89069 Ulm, Germany;

E-mail: {reichert,dadam}@informatik.uni-ulm.de

2DaimlerChrysler Research and Technology Ulm, Dept. RIC/ED, Postfach 2360, 89013 Ulm, Germany;

E-mail: thomas.tb.bauer@daimlerchrysler.com

Received: 6 October 2002 / Accepted: 8 January 2003

Abstract. Workﬂow management systems (WfMS) offer a

promising technology for the realization of process-centered

application systems.A deﬁciency of existing WfMS is their in-

adequate support for dealing with exceptional deviations from

the standard procedure. In the ADEPT project, therefore, we

have developed advanced concepts for workﬂow modeling and

execution, which aim at the increase of ﬂexibility in WfMS.

On the one hand we allow workﬂow designers to model excep-

tional execution paths already at buildtime provided that these

deviations are known in advance. On the other hand authorized

users may dynamically deviate from the pre-modeled work-

ﬂow at runtime as well in order to deal with unforeseen events.

In this paper, we focus on forward and backward jumps needed

in this context. We describe sophisticated modeling concepts

for capturing deviations in workﬂow models already at build-

time, and we show how forward and backward jumps (of dif-

ferent semantics) can be correctly applied in an ad-hoc manner

during runtime as well. We work out basic requirements, facil-

ities, and limitations arising in this context. Our experiences

with applications from different domains have shown that the

developed concepts will form a key part of process ﬂexibility

in process-centered information systems.

Key words: Workﬂow management – Adaptive workﬂow –

Exception handling – Forward/backward jump

1 Introduction

E-Business has signiﬁcantly increased the competitive pres-

sure companies must face [4]. To meet this challenge enter-

prises are developing a growing interest in supporting their

business processes more effectively and in streamlining their

application systems such that they behave “process-oriented”;

i.e., to offer the right tasks at the right point in time to the

This paper is a revised and extended version of [40]. The described

work was partially performed in the research project “Scalability in

Adaptive Workﬂow Management Systems” funded by the Deutsche

Forschungsgemeinschaft (DFG).

right persons along with the information and application func-

tions needed. Workﬂow management systems (WfMS) like

MQSeries Workﬂow, Staffware, or INCOME Workﬂow offer

a promising technology for this [33,58]. Designed for a dis-

tributed environment they increase the number of work pro-

cesses (workﬂow; abbr. WF) that can pass through an elec-

tronic workplace. For this purpose, the business process logic

is extracted from application code. So, instead of a large,

monolithic program package we obtain a set of WF activi-

ties which represent the application functions. The process

logic between them (i.e, control and data ﬂow) is speciﬁed

in a separate WF schema. Usually, for WF modeling graphi-

cal formalisms like Petri Nets [1,38,58], Statecharts [32,60],

UML Activity Diagrams [16], or block-structured description

languages [13,36, 41] are used. They allow the WF designer

to quickly deﬁne and modify WF schemes at a high seman-

tic level, and enable the buildtime components of the WfMS

to detect behavioral inconsistencies and errors in a very early

implementation stage [46,47,52,58].

Long regarded as technology for the automation of well-

structured, repetitive processes, showing only little varia-

tions in their possible execution sequences, WF management

is in the throes of transformation as more and more non-

traditional applications require comprehensive process sup-

port as well. In many domains, like hospitals, engineering

environments, or E-Commerce, however, process-oriented in-

formation systems will not be accepted if rigidity comes with

them [4,8,14,18,26]. Instead users must be able to ﬂexibly de-

viate from the standard process (e.g., by skippingWF activities

or by working on a WF activity ahead of the normal sched-

ule), in particular to handle exceptional situations [45, 50].

(In this paper exceptions constitute events which may occur

during WF execution and which require deviations from the

standard business process.) In doing so, it is very important

that the use of the WfMS is not more cumbersome and time-

consuming than simply handling the exception by a telephone

call to the right person. As reported by several groups, insuf-

ﬁcient ﬂexibility and adaptability have been primary reasons

why many WfMS failed in process automation projects in the

past [17,19,41].

Generally, we have to differ between deviations that can

be pre-planned and deviations for which this is not possible.

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 133

Concerning pre-planned deviations, their context as well as

the actions necessary to handle them are known beforehand.

They, therefore, can be already considered at buildtime in or-

der to achieve a ﬂexible WF execution behavior. As opposed

to this, deviations that cannot be pre-planned may become

necessary to deal with unforeseen events and must be dynam-

ically handled during WF execution. In practice, both kinds of

deviations frequently occur and must therefore be adequately

supported by WfMS.

The present work is embedded in the ADEPT project

which aims at the ﬂexible support of enterprise-wide business

processes [5,14,41]. We have developed and implemented ad-

vanced concepts for the modeling, execution, and monitoring

of workﬂows as well as for the dynamic change of in-progress

WF instances. Our work is based on ﬁrst-hand knowledge with

clinical as well as engineering workﬂows [8,14]. We have ob-

served that many exceptions are known in advance and can

therefore be considered already at buildtime, which decreases

the necessity of “expensive” ad-hoc interventions during run-

time. To enable users to cope with unforeseen exceptions as

well, additionally, we offer advanced concepts for dynamic

WF changes.They are based on theADEPTﬂex calculus which

enables authorized users to dynamically change the structure,

the state, and the attributes of in-progress WF instances in a

consistent manner and at a high semantic level [41].

In this paper we develop advanced concepts for both, the

increase of ﬂexibility at buildtime and its enhancement dur-

ing runtime. Thereby, we focus on the support of forward and

backward jumps, which are indispensable to ﬂexibly deal with

exceptions in WfMS [14]. While the former enable deviations

in forward direction (e.g., to skip unnecessary activities or to

work on a particular activity ahead of the normal schedule),

backward jumps make it possible to partially roll back the ﬂow

to a previous execution state and to re-continue work in this

state (e.g., when activity execution fails). We present concepts

for both, the pre-modeling of jumps at buildtime and their dy-

namic application during runtime. To better understand related

issues and problems, we consider the viewpoint of the WF de-

signer as well as of the end user. In some respects forward and

backward jumps bear resemblance to GOTO statements in pro-

gramming languages. However, deviations from standard pro-

cedures concern exception handling at a higher semantic level,

which is indispensable for WfMS to cover a broad spectrum

of processes. (Note that the need for supporting jump opera-

tions has been approved by several other research groups as

well [1,27,36,42,50].) Nevertheless, jumps must not be com-

plicated for users or lead to an undeﬁned execution behavior.

For this reason, ADEPT imposes several restrictions for their

use, which either have to be checked at buildtime (pre-planned

jumps) or must be ensured when applying the jump during

runtime (ad-hoc jumps). Backward jumps, for example, must

always result in a former state of the WF instance in order to

guarantee a consistent execution behavior. Forward jumps, in

turn, must not lead to activity program invocations with miss-

ing input data or to skipping of imperative activities. Finally,

jump operations must be properly integrated with respect to

authorization and documentation.

Although very important for realizing and adaptive work-

ﬂows, forward and backward jumps do not cover all excep-

tion handling procedures needed in practice. As we have re-

ported in earlier papers [14,41], ADEPT provides other facil-

ities as well. Examples include the ad-hoc insertion or dele-

tion of WF activities, the late modeling of sub-workﬂows,

and the dynamic change of WF attributes (e.g., activity work

assignments). In addition, several research groups have used

the ADEPT WfMS for implementing sophisticated exception

handling procedures on top of it, like the automatic adapta-

tion of workﬂows or the dynamic creation of WF instances as

response to occurring exceptions [4,53]. In this context, ECA

rules (Event – Condition – Action) can be used to describe the

conditions leading to an exception and the actions necessary

to handle them [11,36]. Other exception handling approaches

are discussed in Sect. 5.

The outline of this paper is as follows: Sect. 2 furnishes ba-

sic information about WF modeling and execution in ADEPT

– background information which is necessary for a further un-

derstanding of this paper. Section Sect. ??forward describes

how pre-planned as well as ad-hoc forward jumps can be ﬂex-

ibly realized in WfMS. In Sect. 4 we set out how backward

jumps have to be handled. We discuss related work in Sect. 5

and conclude with a summary in Sect. 6.

2 Background information

For each business process type to be supported, a correspond-

ing WF schema has to be deﬁned and stored in the WfMS.

An example is depicted in Fig. 1. Among other things, the

diagrammed WF schema deﬁnes WF activities as well as the

control and data ﬂow between them. The work presented in this

paper uses the ADEPT formalism [39, 41] for WF modeling

and execution. On the one hand this WF meta model is expres-

sive enough to adequately model real-world processes [14], on

the other hand, the resulting WF models are easy to understand

for WF designers as well as for end users. ADEPT allows to

model aspects like control and data ﬂow, work assignments,

or time constraints. Furthermore it has proven itself by en-

abling correctness saving rules (e.g., no deadlocks, no data

losses, no temporal inconsistencies, no undeﬁned work as-

signments), ad-hoc changes of in-progress WF instances [41],

and distributed WF execution [5,6]. By implementing these

concepts in a powerful prototype [29], we have demonstrated

that they work in conjunction with each other as well. In the

meantime, the ADEPT prototype is used by research groups

from different application domains for the implementation of

ﬂexible, process-centered information systems [4,53].

2.1 Control ﬂow modeling and execution

The control ﬂow schema of a WF is represented by an at-

tributed WF graph with distinguishable node and edge types.

As shown in [41] this enables efﬁcient correctness checks (see

below) and eases the handling of loop backs. Formally, a con-

trol ﬂow schema Scorresponds to a tuple S=(N, E, ...)

with node set Nand edge set E. To each control ﬂow edge

e∈Ean edge type ET(e)from the set EdgeTypes =

{CONTROL E,SYNC E,LOOP E}is assigned: CONTROL E

denotes “normal” order relations between activities, SYNC E

“wait-for” relations between activities of parallel branches,

and LOOP Eloop backs. Similarly, each node n∈

Nhas a node type NT(n)∈NodeTypes (with

134 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

Table 1. Predecessor and successor functions deﬁned on WF graphs

c succ(n)/c pred(n) set of all direct successors/predecessors of activity n

considering control edges with type CONTROL E

c succ∗(n)/c pred∗(n) set of all direct or indirect successors / predecessors of activity n

considering control edges with type CONTROL E(transitive closure)

succ(n)/pred(n) set of all direct successors/predecessors of activity n

referring to control edges with type CONTROL Eor SYNC E

succ∗(n)/pred∗(n) set of all direct and indirect successors/predecessors of activity n

referring to control edges with type CONTROL Eor SYNC E

perform

examination

prepare

atient

make

ointment

inform

atient

order medical

examination

generate

ort

validate

report

patientId

report

data element

AND join

data flow control flow

yes

role = doctor

role = radiologist

Actor =

Actor("peform examination")

STARTLOOP

AND split

ENDLOOP

write data edge

read data edge

loop backward edge

(ET =LOOP_E)

normal control edge

(ET =CONTROL_E)

Fig. 1. Workﬂow modeling in ADEPT

NodeTypes := {STARTFLOW,ENDFLOW,ACTIVITY,

STARTLOOP,ENDLOOP,AND Split,XOR Split,AND

Join,XOR Join}). Based on these ingredients, sequences,

parallel branchings (AND split,AND join), conditional

branchings (AND/XOR split,XOR join), and loops

(STARTLOOP,ENDLOOP) can be easily modeled. For this we

have adopted concepts from block-structured process descrip-

tion languages [15] and enriched them by additional control

structures. Branchings as well as loops have exactly one entry

and one exit node. Control blocks may be nested but are not

allowed to overlap. As this limits expressive power, in addi-

tion, the already mentioned synchronization edges are offered

to WF designers, which allows them to describe more com-

plex control structures if required. We have selected this block

structure because it is rather quickly understood by users, it

allows the provision of user-friendly, syntax-driven model edi-

tors, and it makes it possible to implement efﬁcient algorithms

for control and data ﬂow analyses. – Table 1 informally sum-

marizes predecessor and successor functions on WF graphs

which are needed for the following considerations.

Based on a given WF schema Snew WF instances can

be created and started. To determine which activities are to

be executed next, for each WF instance we maintain infor-

mation about its current state by assigning markings NS(n)

and ES(e)to each activity node nand to each control edge

e. Corresponding to this, a WF graph with associated mark-

ings is denoted as a WF instance graph.1An example is de-

picted in Fig. 2. It shows two WF instances created from the

WF schema from Fig. 1. Similar to Petri Nets [58], markings

are determined by well deﬁned ﬁring rules [41]. In doing so,

markings of already passed regions are maintained (except

loop backs). Furthermore nodes and edges belonging to non-

selected branches of a conditional branching will be explicitly

marked as SKIPPED and FALSE SIGNALED, respectively.

ADEPT ensures well-deﬁned dynamic properties, including

the absence of deadlocks, the proper termination of the ﬂow,

and the reachability of markings which enable activity execu-

tion (for details see [39,41]). The described block structuring

as well as the used node and edge types help us to accomplish

this in an efﬁcient manner. Deadlocks, for example, can be

excluded if the WF graph does not contain cycles over control

and synchronization edges (see [39] for details).

State transitions of a single activity instance are depicted in

Fig. 3. Initially, the activity status is set to NOT ACTIVATED.

It is changed to ACTIVATED when all pre-conditions for ex-

ecuting this activity are met. In this case corresponding work

items are inserted into the worklists of authorized users (deter-

mined by role-based work assignments). If one of them selects

the respective item from his worklist, activity status changes to

RUNNING and respective work items are removed from other

worklists. Furthermore, an application component associated

with the activity is started. At successful termination, activity

status passes to COMPLETED.

2.2 Data ﬂow modeling and data context management

Data exchange between activities is realized by the use of

global process variables (called data elements in the follow-

ing). Data elements are connected with input and output pa-

rameters of WF activities. Each activity input parameter is

mapped to exactly one data element by a read data edge and

each activity output parameter is connected to a data element

1Note that this must not mean that for each WF instance a separate

WF graph is maintained. A WF instance graph represents a logical

view on a WF instance, and does not give any hint concerning its

physical representation.

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 135

perform

examination

prepare

atient

make

ointment

inform

atient

order medical

examination

generate

ort

validate

report

patientID

report

LOOP_E

true

false

user = "Dr. Quincy"

role = radiologist

WF instance graph I1

patientId = "Smith"

current value: "Smith"

NS=NodeState,

NS = ACTIVATED

NS = RUNNING

NS = COMPLETED

ES = EdgeState

ES = TRUE_SIGNALED

perform

examination

prepare

atient

make

ointment

inform

atient

order medical

examination

generate

ort

validate

report

patientID

report

LOOP_E

true

false

Actor = "Dr. Bond"

Actor = "Dr. Kitchen"

WF instance graph I2

patientID = "Major"

current value: "Major"

Actor = "Dr. Kitchen"

report = Id4763

patientID = "Major"

report = Id4763

Fig. 2. WF instance graphs (with different marking)

by a write data edge.An example is depicted in Fig. 1.Activity

“order medical examination” writes the data element “patien-

tID” which is read by the subsequent activity “perform exam-

ination”. The total collection of data elements and data edges

is called the data ﬂow schema. For its modeling, a number

of correctness properties must be satisﬁed. The most impor-

tant one ensures that all data elements read by an activity X

must have been written by preceding activities before Xcan

be started, independently from the execution path leading to

activation of X. Note that this property is crucial for the proper

invocation of external activity programs during WF execution.

In particular, it must be ensured in conjunction with forward

jumps as well (cf. Sect. 3). Other correctness constraints con-

cern the avoidance of lost updates due to parallel or subsequent

write operations on data elements (see [39]). At runtime, if re-

quired, ADEPT stores different versions of a data object for

each data element. In more detail, for each write access to a

data element, always a new version of the data object is cre-

ated and stored in the WfMS database; i.e., data objects are

not physically overwritten. This allows us, for example, to use

different versions of a data element within different branches

of an AND-/XOR-branching (cf. Sect. 3). As we will see in

Sect. 4, however, maintaining data object versions is not only

important for the context-dependent reading of data elements

but also for the correct rollback of WF instances in case of

failures.

3 Forward jumps

In this section we present both, pre-planned and ad-hoc for-

ward jumps for exception handling. While the former are

known at buildtime and can therefore be captured in the WF

schema, ad-hoc jumps become necessary to deal with unfore-

seen events. That means they cannot be pre-modeled and must

therefore be deﬁned by users at runtime. We motivate the need

for both kinds of forward jumps, discuss general issues related

finish

start

select

disable

deselect

NOT_A CTIVATED ACTIVATED

WAITI NG

SUSPENDED STARTED

RUNNING

suspend

FAILE D COMPLE TE D

SKIPPED

SELECTED

TE RM I NA TED

enable

resume

abort

skip

disable

skip

super state

(sub-) state

state transition

Fig. 3. Statechart for activity state transitions

to them, and show how forward jumps of different semantics

have been realized in ADEPT.

3.1 Motivation

During WF execution it may be required to omit unnecessary

activities or to immediately execute activities though not all

steps normally preceding them in the ﬂow of control have been

ﬁnished yet.

Example 1 ((Forward jumps in a ﬂow):). The processing of

a medical examination for an inpatient normally comprises

several steps: The examination must be ordered, an appoint-

ment with the examination unit be made, the patient be pre-

pared and notiﬁed about potential risks, the intervention be

performed, and medical reports be generated, obtained and

136 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

validated. Even for this simple process chain, it must be pos-

sible for physicians and nurses to ﬂexibly deviate from the

standard procedure, in particular to handle exceptional situ-

ations (e.g., if the patient’s state of health gets worse during

the process or the physician ﬁnds out that some preparatory

steps are unnecessary for the respective patient). In such cases

it must be possible to skip steps or to immediately perform the

examination; i.e., without making an appointment or waiting

until all preparatory steps (required in the normal case) have

been ﬁnished. Note that corresponding situations may occur

at any time during process execution. (A presentation of more

sophisticated examples is given in [49].)

Our experiences with clinical as well as engineering pro-

cesses [8,14,49] have shown that very often deviations from

standard processes can be pre-planned. If exceptional situa-

tions, in which a particular activity or a set of activities is to

be processed ahead of the normal schedule, are known in ad-

vance, it must be possible to capture them at buildtime. This, in

turn, enables the WfMS to offer respective activities as excep-

tional steps to users though the pre-conditions for their regular

execution have not been fully met; i.e., users may work “un-

timely” on these pre-scheduled activities, but the WfMS indi-

cates them that activity execution constitutes a deviation from

the preferred execution path in the current WF state. How this

can be accomplished is described in the following subsection.

3.2 Deﬁning and changing execution priorities

for WF activities

In this section we introduce simple, but useful extensions of

the ADEPT base model, which allow the WF designer to dif-

ferentiate between normal and exceptional execution paths.

3.2.1 Deﬁning activity priorities at build-time

To enable WF designers to express whether a scheduled ac-

tivity is to be offered as a “normal” or as an “exceptional”

step within worklists, we allow them to associate execution

priorities with activities. If an activity is to be treated as an

exceptional step when it is activated, priority EXCEPTIONAL

will have to be assigned to it at buildtime; otherwise the setting

REGULAR will be chosen as priority for this activity (default

setting). Internally, the WF engine schedules activities inde-

pendently from their execution priority; i.e., execution of an

activity with priority EXCEPTIONAL follows the same rules

(with respect to activation and termination) as execution of reg-

ular activities. The way how activities are offered in user work-

lists, however, may depend on the priority assigned to them

and is left to WF client applications. Possible worklist visual-

izations include the fade-in/fade-out of exceptional activities,

the use of different colors for activities with different priori-

ties, or the display of the work items related to these activities

within different windows. Combined with AND-split/XOR-

join branchings – calledAND-/XOR-branching for short – ac-

tivity priorities turn out to be very useful: When the AND-split

node of such a branching completes, its outgoing branches

are activated and can be worked on concurrently. As opposed

to parallel branchings (with AND-split/AND-join), however,

⇓ Completion of D (lower branch

)

Activate E

Rollback upper branch

AND split XOR join

... and mark its nodes as SKIPPED

COMPLETED

ACTIVATED

RUNNING

TRUE_SIGNALED

SKIPPED

FALSE_SIGNALED

⇓

Fig. 4. Operational semantics of an AND-/XOR-branching

the workﬂow may proceed at the XOR-join as soon as one

of its incoming branches is terminated.2In ADEPT, in such

a case activities from other branches are removed from user

worklists, aborted or compensated 3depending on their cur-

rent state. An example showing the operational semantics of

an AND-/XOR-branching is depicted in Fig. 4.

Based on this, WF designers are able to differentiate be-

tween preferred execution paths and exceptional ones. A sim-

ple example is given in Fig. 5. In the depicted WF instance

graph activities Band Xare concurrently active. Due to the as-

signed priorities Bis offered as regular step in user worklists

whereas Xis treated as exceptional activity. According to this,

2Synchronization of incoming branches at an XOR-join is seri-

alized, i.e., there will be always one branch that terminates ﬁrst. By

default, this branch is selected as “winner” and the other branches

are rolled back. Alternatively, ADEPT allows more than one incom-

ing branch to be completed such that the user can explicitly select

the most suited one (e.g., depending on the output data generated by

related activities).

3Whether a completed activity can be compensated or not may

depend on the kind of activity as well as on the current state of the

WF.

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 137

Fig. 5. Activity priorities

the preferred activity sequence is deﬁned by A,B,C, and D(in

the given order) whereas the sequence A,X, and Dconstitutes

an exceptional path (indicated by priority EXCEPTIONAL of

activity X); i.e., instead of Band Cactivity Xmay be executed.

3.2.2 Pre-planned changes of activity priorities

during run-time

Depending on the state of a WF instance it must be possible to

treat a particular activity differently with respect to its priori-

tization. Under certain circumstances its execution may con-

stitute a deviation whereas in other WF states it can be treated

as normal step. As an example, take an activity Xwhich nor-

mally is to be executed after some preceding steps have been

ﬁnished. Due to exceptional situations, however, it may be-

come necessary to work on Xahead of the normal schedule.

In this case, execution of Xconstitutes a deviation from the

preferred activity sequence which must be indicated to users;

i.e., this exceptional state must be preserved as long as not all

activities normally preceding Xin the ﬂow have been com-

pleted. If the latter case occurs, however, priority of Xis to be

changed accordingly.

Static priorities are not sufﬁcient for modeling such cases.

In addition, it must be possible to dynamically modify pri-

orities during WF execution. In order to be able to capture

such priority changes in the WF model we introduce pri-

oritization edges as an additional modeling concept. A pri-

oritization edge ep=src →dst links two activities src

and dst, but without enforcing an execution order between

them. Each prioritization edge epis associated with a prior-

ity eppriority ∈{REGULAR,EXCEPTIONAL}which has the

following semantics: When the source node src is completed,

edge epis signaled as TRUE and the priority of its destination

node dst is modiﬁed to eppriority. As an example take an ac-

tivity Ywith (static) priority EXCEPTIONAL. If an incoming

prioritization edge (with priority REGULAR) of this activity is

signaled as TRUE during runtime, the priority of Ywill be set

to REGULAR as well; i.e., from this point in time the execution

of Yno longer constitutes an exception.

Figure 6 shows an example for the combined use of pri-

oritization edges and activity priorities. In the WF instance

graph depicted in Fig. 6a, activities Cand Dare concurrently

active whereas Cis treated as normal step and the execution

of Dis considered as an exception (corresponding to the static

priorities assigned to Cand D). After completion of Cits out-

going prioritization edge C→D(with priority REGULAR)is

signaled as TRUE. According to this, priority of activity Dis

changed from EXCEPTIONAL to REGULAR such that Dcan

Fig. 6. Changing priorities during the execution of a WF instance

be offered as normal step in user worklists (cf. Fig. 6b). Re-

capitulating this, the preferred activity sequence is A,B,C,D,

E, though Dmay be executed directly after completion of A.

3.3 Modeling forward jumps at buildtime

As motivated, it often becomes necessary to give priority to

execution of activities though the steps normally preceding

them have not been completely ﬁnished yet. ADEPT provides

the needed ﬂexibility by allowing users to jump forward to

selected activities and, therefore, to bring forward their execu-

tion. To better understand the problems arising in this context,

we must consider both, the viewpoint of the designer and of the

end user. For the designer it must be possible to differentiate

between the normal course a workﬂow shall take and excep-

tional deviations. Furthermore, by incorporating pre-planned

jumps the clarity of the WF model must not suffer and the

complexity for its creation must not be signiﬁcantly increased.

From the viewpoint of end users, it is very important that they

are able to differ between activities scheduled along the nor-

mal ﬂow and activities whose execution (currently) constitutes

a deviation.

138 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

Fig. 7. Modeling shortcuts (viewpoint of the WF designer)

3.3.1 General issues

When deviating from the preferred activity sequence, one has

to decide how bypassed activities are to be treated. Generally,

they may either be skipped or be continued and ﬁnished con-

currently to the untimely executed activities.ADEPT supports

both variants as well as mixtures of them. In the following,

we show how the modeling concepts from Sect. 3.2 can be

used to deﬁne pre-planned forward jumps at buildtime. As a

prerequisite the WF states in which the forward jump shall

be applicable and the activities of which the execution shall

be brought forward due to the jump must be known in ad-

vance. Pre-planned jumps can be deﬁned at a high semantic

level. For this, a graphical WF description language is offered

which comprises the elements of the ADEPT base model (cf.

Sect. 2) as well as modeling elements for deﬁning jumps. For

the deﬁnition of forward jumps a special edge type – called

shortcut – can be used. Internally, a shortcut nSC

s→nSC

dis

transformed into a representation of the ADEPT base model

whereby a precise operational semantics can be guaranteed.

A simple example is depicted in Fig. 7. The diagrammed

shortcut A→Freﬂects a forward jump as it is modeled by

the designer. It has the following semantics: After successful

completion of source activity nSC

s(activity Ain our example),

both, direct successors of nSC

sover normal control edges (ac-

tivity Bin our example) and the target activity nSC

dof the

shortcut (activity Fin our example) are activated. While B

is treated as a normal step (with priority REGULAR), the “un-

timely” execution of activity Fis considered as an exceptional

case. This exceptional status is preserved as long as Fis not

scheduled along the “normal” control ﬂow. In our example, F

is offered as exceptional step (with priority EXCEPTIONAL)

in worklists until it will either be ﬁnished or its direct prede-

cessor Ewill be completed.

Independent of the semantics of a shortcut nSC

s→nSC

its transformation into an executable representation of the

ADEPT base model requires the following conditions:

•The source node nSC

sof the shortcut must be a predecessor

of its target node nSC

dover normal control edges (with edge

type CONTROL E). Formally: nSC

d∈c succ∗(nSC

•The shortcut must not partially overlap with a loop control

block (LoopStart, LoopEnd), but loop control blocks and

shortcuts may contain each other:4

nSC

s∈Lbody ⇔nSC

d∈Lbody(with

Lbody := c succ∗(LoopStart)∩c pred∗(LoopEnd))

4Concerning the schema from Fig. 1, for example, shortcut “order

medical examination” →“perform examination” would be allowed.

As opposed to this, it would not be possible to model a shortcut

leading from activity “order medical examination” to an activity suc-

ceeding the end node of the depicted loop.

Fig. 8. Forward jump (with skipping bypassed activities)

Assume that a user wants to follow shortcut nSC

s→nSC

i.e., he wants to jump forward to activity nSC

dand work on it

though not all steps normally preceding nSC

dhave been ﬁn-

ished yet. When deviating from the preferred execution order,

it must be clear how to deal with bypassed activities from the

jump region; i.e., with activities located between the source

and the target node of the shortcut (nodes B,Cor D,Ein our

example). We present two alternative approaches which either

allow to skip bypassed activities or to ﬁnish them concurrently

to activity nSC

3.3.2 Skipping bypassed activities

One possibility to deal with bypassed activities is to undo,

abort, or abandon their execution depending on their current

state; i.e., if a user deviates from the preferred execution path

by following a shortcut nSC

s→nSC

d, all activities located

between the source and the target activity of the shortcut will

be compensated, aborted, or abandoned – these activities form

the jump region of the shortcut and are deﬁned by the set

Nbypass := c succ∗(nSC

s)∩c pred∗(nSC

d)(nodes B,C,D, and

Ein our example from Fig. 8). Afterwards, the execution of

the ﬂow will proceed with node nSC

d(node Fin our example).

The WF graph Wmod in Fig. 8a contains a shortcut (A

→F) as it is modeled by the WF designer. The WF graph

Wtransform in Fig. 8b shows the transformation of this short-

cut into a representation of the ADEPT base model. As one

can easily see, this transformation is based on the combined

use of an AND-/XOR-branching (deﬁned by nodes Aand F

in our example) and activity priorities. In more detail, the up-

per branch of the created AND-/XOR-branching consists of

a single jump activity with priority EXCEPTIONAL and with

label <“Jump to ” + target node>(“Jump to F” in our exam-

ple). The lower branch, in turn, constitutes the jump region

and corresponds to that subgraph of Wmod induced by nodes

from the set Nbypass ({B,C,D,E}in our example). According

to Wtransform the jump activity (“Jump to F”) is selectable

(with priority EXCEPTIONAL) as soon as the source activity

of the shortcut (activity Ain our example) is completed. If

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 139

the jump activity is executed the upper branch of the AND-

/XOR-branching will be immediately completed. According

to the speciﬁed operational semantics, the lower branch (i.e.,

the jump region) will then be aborted and rolled back. After-

wards the ﬂow can proceed at the target activity of the shortcut

(node Fin our example). As opposed to this, if activities from

the lower branch (B,Cor D,Ein our example) are ﬁnished,

activation of the jump activity will be cancelled and corre-

sponding work items be removed from worklists.

Mapping the shortcut into a representation of the ADEPT

base model at buildtime. Generally, the mapping of a short-

cut nSC

s→nSC

d(with the described semantics) into a repre-

sentation of the ADEPT base model can be accomplished by

applying Algorithm 1 (which has complexity O(n)where n

denotes the number of activity nodes of theWF graph; the same

complexity results from the algorithms necessary to check the

conditions described in Sect. 3.3.1).

Algorithm 1. Transforming a shortcut nSC

s→nSC

d(with

skipping of bypassed activities) into ADEPT base model:

1. If nSC

scorresponds to a split node, insert a null activity

n1(i.e., an activity without associated action) which takes

over the output ﬁring behavior and outgoing control edges

of nSC

s. Set the output ﬁring behavior of activity nSC

sto

ONE Of ONE (i.e., nSC

sis no split node anymore) and add

control edge nSC

s→n1(cf. Fig. 9a)

2. Set the output ﬁring behavior of activity nSC

sto

ALL Of ALL; i.e., nSC

sis converted into an AND split

node (cf. Fig. 9b).

3. If nSC

dcorresponds to a join node, insert a null activity

n2which takes over the input ﬁring behavior and incom-

ing control edges of nSC

d. Set the input ﬁring behavior of

activity nSC

dto ONE Of ONE (i.e., nSC

dis no join node

anymore) and add control edge n2→nSC

d(cf. Fig. 9c).

4. Set the input ﬁring behavior of nSC

dto ONE Of ALL; i.e.,

nSC

dis converted into an XOR join node (cf. Fig. 9d).

5. Insert an additional branch between nSC

sand nSC

dwhich

contains a jump activity (with priority EXCEPTIONAL)

labeled as <“Jump to” + nSC

d>. The other branch, in

turn, corresponds to that sub-graph of Wmod induced by

the nodes of the jump region (cf. Fig. 9e).

Formal pre-conditions and required checks at buildtime. Ob-

viously, when transforming a shortcut with the described se-

mantics into a representation of ADEPT base (cf. Algorithm

1), steps 1–5 generate an AND-/XOR-branching with two

branches: One corresponds to the jump activity (with excep-

tional priority) and the other to the jump region. In order to

ensure structural correctness (i.e., a proper block structuring

of the WF graph and the absence of cycles; cf. Sect. 2) and a

correct dynamic behavior of the ﬂow (e.g., no deadlocks), in

addition to the already mentioned pre-conditions (see above),

the following restrictions must be met for the use of a shortcut

nSC

s→nSC

•The subgraph induced by the node set Nskip := Nbypass ∪

{nSC

s,n

d}must constitute a regular control block; i.e.,

nodes from branchings and loops are either not contained

within Nskip or they are completely covered by nodes from

this set.

Fig. 9. Shortcut transformation

•Different shortcuts nSC

s→nSC

dand mSC

s→mSC

dmust

not overlap but may contain each other. Formally: nSC

s∈

Mskip ⇔nSC

d∈Mskip (with Mskip := c succ∗(mSC

s)∩

cpred∗(mSC

d))

Both conditions can be easily checked. If the shortcut is

applied to a correct control ﬂow schema (i.e., proper block

structure, no cycles except loop backs) and if the above con-

ditions are satisﬁed, steps 1–5 of Algorithm 1 will result in

a correct control ﬂow schema again; i.e., structural and dy-

namic properties as required by the ADEPT base model will

be further valid (for a formal treatment see [39]).

When transforming a shortcut into a representation of the

ADEPT base model, in addition, we have to check whether

the related data ﬂow schema remains correct. As described in

Sect. 2, the most important correctness property requires that

all data elements read by an (arbitrary) activity Xmust have

been written by at least one preceding activity before Xcan be

started; in particular, this condition must hold independently

of the execution path leading to activation of X. This property

is ensured by corresponding data ﬂow analyses at buildtime,

which make use of the presented block structure and which

have complexity O(n2). The presentation of algorithms, how-

ever, is outside the scope of this paper (see [39]).

Necessary data ﬂow analyses can be reduced if the data

ﬂow schema statisﬁes the above correctness property already

before the shortcut is deﬁned. It is then sufﬁcient to check

whether there are successors of nSC

d(incl. nSC

d) which are

data-dependent on (skipped) activities from the jump region.

Only for this case there may be missing input data due to the

deﬁned shortcut. As an example take the scenario depcited in

Fig. 10a). The upper WF schema for which shortcut A→Dis

deﬁned contains data dependencies between Aand C(Creads

the data element d1written by A) as well as between Dand E(E

reads the data element d2written by A). As shown in the lower

140 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

Fig. 10. Checking data ﬂow correctness when transforming a shortcut

WF schema, these dependencies persist when the shortcut is

transformed into an ADEPT representation. Furthermore, the

data ﬂow schema remains correct since d1(d2) will always

be written before C(E) is activated. This does not apply, for

example, with respect to the scenario from Fig. 10b). It is very

similar to the one shown in Fig. 10a) but takes Eas target

activity of the shortcut instead of D. Since Dis now contained

within the jump region it will be compensated, aborted or

skipped when applying the forward jump (“Jump to E”). This,

in turn, will lead to invocation of Eor – more precisely – of

its associated activity program with missing input data, which

may cause inconsistencies (e.g., wrong outputs) or errors (e.g.,

program crashes). In ADEPT, therefore, the shortcut from A

to Ewill be either not allowed or the designer will have to

restore correctness of the data ﬂow; e.g., by re-linking the

corresponding input parameter of Eto another data element.

3.3.3 Finishing bypassed activities

When a user wants to apply a jump in order to bring forward

the execution of a certain activity, it is not always required to

skip activities of the jump region. Instead, it may be desired

to continue and ﬁnish them concurrently to the pre-scheduled

activities. With respect to activities from the jump region, this

means that the effects of already completed activities are to be

preserved, the execution of already started activities be contin-

ued, and activities not yet activated be scheduled as planned.

ADEPT allows the modeling of such forward jumps as well.

For this, the designer has to specify a shortcut nSC

s→nSC

and an activity nSC

nfor synchronizing bypassed steps. At run-

time, authorized users may then bring forward the execution

of nSC

das soon as nSC

sis completed. As opposed to the short-

cut semantics described above, activities from the jump region

are further processed in case the shortcut is followed. In do-

ing so, it is important to synchronize their execution with the

overall ﬂow. As mentioned, for this a synchronizing activity

nSC

nhas to be speciﬁed which then may be only activated if

its normal preconditions hold and – additionally to this – all

Fig. 11. Forward jump (with ﬁnishing bypassed activities)

activities from the jump region are completed. A simple ex-

ample is depicted in Fig. 11a). The WF graph Wmod contains

a shortcut A→Fas it is modeled by the designer. In addition,

activity node nSC

s=Hserves for synchronizing the execution

of bypassed activities. According to this, F(and its successor

G) may be executed ahead of the normal schedule (i.e., before

activity Eis completed) as soon as Ais ﬁnished. In case this

forward jump is followed, however, the processing of activi-

ties from the jump region (B,Cor D,Ein our example) must

be continued and ﬁnished before Hcan be activated.

The transformation of this shortcut is shown in Fig. 11

b). Activity Anow represents an AND-split and Hthe cor-

responding AND-join. The execution behavior is as follows:

After completing Aits successor Bcan be executed as ac-

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 141

tivity with priority REGULAR and the shortcut’s target Fas

activity with priority EXCEPTIONAL. If no deviation from

the preferred execution order occurs during runtime (i.e., only

activities with priority REGULAR are processed), the lower

branch will be completed before Fis started. For this case, the

outgoing prioritization edges of Eare signaled as TRUE such

that the priorities of Fand Gare changed to REGULAR. As op-

posed to this, if a user starts Fbefore Eis completed this will

correspond to a deviation from the preferred activity sequence

(indicated by priority EXCEPTIONAL of activity F).

Mapping the shortcut into a representation of the ADEPT base

model at buildtime. Assume that shortcut nSC

s→nSC

dis to

be applied to a correct WF schema and bypassed activities are

to be ﬁnished before the (synchronizing) activity nSC

nmay

be activated. This semantics can be realized by the combined

use the modeling concepts of the ADEPT base model and its

extensions as described in Sect. 3.2. To transform a shortcut

speciﬁcation into an executable representation of the ADEPT

base model, Algorithm 2 (which has complexity O(n)) must

be applied (for an example see Fig. 12):

Algorithm 2. Transforming a Forward Jump (with Finishing

Bypassed Steps) into ADEPT base model:

1. Determine the minimal control block (nstart,nend) that

contains activities nSC

s,nSC

d, and nSC

2. Create anAND split n1which represents a null activity and

takes over the input ﬁring behavior as well as the incoming

control edges (of type CONTROL E)ofnstart. Link nstart

as a direct successor to n1.

3. Create anAND join node n2corresponding to n1;n2shall

represent a null activity and take over the output ﬁring

behavior as well as the outgoing control edges of nend.

Link nend as a direct predecessor to n2.

4. Detach the subgraph induced by

Npreschedule := nSC

d∪c succ∗(nSC

d)∩c pred∗(nSC

from its current graph context, and insert it as additional

branch to the branching deﬁned by (n1,n2). Let xstart:=

nSC

dbe the start and xend be the end node of this subgraph

or branch.

5. Add two synchronization edges from nSC

sto xstart and

from xend to nSC

6. Assign priority EXCEPTIONAL to each node from

Npreschedule and add prioritization edges (with edge pri-

ority REGULAR) from the end node of the jump region to

each node of this set.

7. Apply ADEPT reduction rules to eliminate unnecessary

nodes and edges (for details see [39,41]).

Formal pre-conditions and required checks at buildtime. For

the correct use of a shortcut nSC

s→nSC

dwith described se-

mantics and its transformation into an executable representa-

tion of the ADEPT base model the following conditions must

be checked (corresponding algorithms make use of the block

structuring and have complexity O(n)):

•If nSC

dis contained within a branch of an XOR-branching,

node nSC

smust be contained within the same branch; i.e.,

it is not allowed to model a forward jump from an activ-

ity preceding an XOR-branching to an activity contained

within one of its branches.

•Let Npreschedule := {nSC

d}∪c succ∗(nSC

d)∩

cpred∗(nSC

n)comprise activities that may be executed

ahead of the normal schedule according to the de-

ﬁned shortcut (cf. Fig. 12). In order to obtain a proper

block structure we require that the subgraph induced by

Npreschedule itself constitutes a block (as it is the case in

Fig. 12 where the respective subgraph corresponds to a

sequence).

•Let N∗

preschedule be another set of activities that may be ex-

ecuted ahead of the normal schedule according to another

deﬁned shortcut. Then Npreschedule and N∗

preschedule

must not partially overlap. Formally:

(Npreschedule ⊆N∗

preschedule)∨

(Npreschedule ⊃N∗

preschedule)∨

(Npreschedule ∩N∗

preschedule =∅)

For shortcuts with same target we require that these sets

are identical. This may be relevant for forward jumps from

different branches of an XOR-branching to the same target

activity.

If these restrictions are satisﬁed the structural and dynamic

properties of the WF graph (proper block structure, no cycles

except loop backs, no deadlocks, etc.) can be guaranteed for

the resulting control ﬂow schema as well. Formal proofs can

be found in [39]. Concerning the data ﬂow schema, we must

check whether the described transformations may lead to in-

vocation of activities with missing input data or may cause

data losses (due to lost updates). If the data ﬂow schema is

correct before applying Algorithm 2 the following checks will

be sufﬁcient:

•Checks for avoiding missing input data: Due to

the described transformations, activities from the sets

Npreschedule and Nbypass may now be executed concur-

rently to each other. For each activity x∈Npreschedule,

therefore, we must check whether data elements read by

x are further written by preceding steps. Obviously, if this

is the case before introducing the shortcut, it will be sufﬁ-

cient to restrict these checks to those data elements written

by activities from Nbypass. Note that only order relations

of activities from this set are rearranged with respect to

nodes from Npreschedule.

•Checks for avoiding data losses due to lost updates:

Let Dbypass/Dpreschedule denote the set of data elements

to which activities from Nbypass/Npreschedule have write

access. Parallel write operations on data elements (and

data loss due to lost updates) will not arise, if Dbypass ∩

Dpreschedule =∅holds. If this does not apply, however,

the shortcut edge must either be removed or additional

synchronization edges between nodes from Nbypass and

Npreschedule have to be inserted.

3.3.4 Concluding remarks

The presented modeling concepts can be generalized. ADEPT

also allows the deﬁnition of hybrid forms of shortcuts. With

respect to nodes from the jump region, for each activity the de-

signer has the choice whether its execution is to be skipped or

continued when the jump is applied. Though the graph trans-

formations needed in this context are more complex, from the

142 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

Fig. 12. Transforming a shortcut into ADEPT base representation

conceptual point of view no new issues arise. We, therefore,

omit a more detailed presentation. In summary, pre-planned

deviations as described above form a key part of process ﬂex-

ibility in WfMS. In addition, they do not require expensive

user interactions as it is the case for ad-hoc changes. Unfor-

tunately, it will not always be possible to capture all jumps

in the WF schema at buildtime. For this reason, we require

additional techniques that allow authorized users to perform

forward jumps in an ad-hoc manner as well if need be.

3.4 Performing dynamic forward jumps during runtime

Our experience with clinical workﬂows has shown that the WF

designer is generally not capable to predict all possible devia-

tions in advance and to capture them in theWF schema [14].To

adequately cope with such unforeseen exceptions, in addition

to the described concepts, ADEPT supports ad-hoc deviations

from the pre-modeled WF schema at the instance level as well

(e.g., to insert, to delete, or to shift activities). In the following,

we restrict our considerations to dynamic forward jumps (e.g.,

skipping of a set of activities or immediate execution of an ac-

tivity though not all predecessors have been completed yet).

In this context, it is very important that change deﬁnition is

not complicated for users; i.e., all complexity associated with

missing activity input data (e.g., due to skipping of activities),

data losses (e.g., due to lost updates), deadlocks (e.g., due to

cyclic waits of activities), or state adaptations must be hidden

to a large degree from users. Instead, they must be able to de-

ﬁne a dynamic forward jump at a high semantic level without

requiring that they are familiar with the used WF description

formalism.

3.4.1 Dynamic forward jumps in ADEPT

Generally, dynamic jumps make only sense if there is no risk

of activity program crashes, data losses, or any other obscure

system behavior. We have spent much effort on the design

of high-level change operations that allow users to adapt in-

progress WF instances while preserving the mentioned cor-

rectness properties (cf. Sect. 2). As response to a dynamic

change request, ADEPT, in essence, ﬁrst checks data depen-

dencies and ordering constraints to detect whether the problem

of missing input values, lost updates, or cyclic waits (dead-

locks) may occur in the modiﬁed WF instance graph. In case

of missing input values, we offer the possibility to generate

an electronic form and to prompt users for these values (either

immediately or when needed). Only if no consistency problem

occur or if it is explicitly tolerated by the user the change re-

quest will be accepted and the necessary graph transformations

be performed. In addition, the markings of nodes and edges are

automatically adapted when the change is applied. In ADEPT,

users are not burdened with this. They may express a jump re-

quest in a rather declarative way and at a high semantic level

(e.g., “work immediately on X”, “skip X1,X2, ..., Xn”). For

this, high-level modiﬁcation operators are offered which are

based on the combined use of basic change operations.

Move operation: The move operation constitutes a basic

change operation for the (dynamic) rearrangement of activi-

ties. In more detail, it allows to shift an activity (or a whole

block) from its current position in the WF instance graph to

another place provided that the actual state of the instance does

not prohibit this. The restructuring of the instance graph, nec-

essary in this context, may be more or less complex depending

on the target position the activity is to be re-inserted. For ex-

ample, an activity detached from its current position may be

re-inserted between two succeeding activities, between two

sets of succeeding activities, or parallel to a certain activity

or control block. A simple example for the use of the move

operation is depicted in Fig. 13. Assume that for the WF in-

stance from Fig. 13a) a user wants to work immediately on

activity Cthough Bhas not yet been ﬁnished. In principle,

this is possible since Cis not data-dependent on B. Depending

on the concrete change scenario the user may desire to skip

execution of B, ﬁrst execute Cand then work on B(i.e., to

swap Band C), or continue the processing of Bconcurrently

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 143

A B C D

A BA C B D

a) b) c)

TRUE_SIGNALEDCOMPLETED ACTIVATED AND split AND join

Fig. 13. a Original WF instance graph and WF instance graph resulting after moving C from its current position to the position, b... located

between A and B, c... located parallel to B

to C. While the skipping of Bis internally based on the delete

operation [39] the other two changes can be realized by us-

ing the move operation. Figure 13b) shows the WF instance

graph after detaching activity Cfrom its current position and

re-inserting it between Aand B. Note that the re-evaluation of

the WF state, which is automatically done in ADEPT, results

in activation of Cand deactivation of B. Figure 13c) shows the

WF instance graph as it results when Cis moved to a position

parallel to B.

Concerning this example certain pre-conditions must be

met in order to correctly apply the move operation. For in-

stance, it would not be possible to move Cto a position before

Asince Aand its predecessors have been already ﬁnished and

therefore an undeﬁned marking would result. But even if ac-

tivity Ahad not yet been started, the desired operation would

be prohibited by ADEPT, since Cwould then be invoked with

missing input data.

Jump forward operation: Based on the sketched move

operation we have realized several high-level operations for

dynamic forward jumps. Generally, these jump operations

enable authorized users to pass the control or to jump for-

ward to an activity ntarget which has not yet been acti-

vated by the WfMS. When applying such a dynamic jump

different policies are offered to users in order to deal with

uncompleted activities from the jump region (i.e., uncom-

pleted activities preceding the node ntarget in the ﬂow

of control): Nbypass := {n∈pred∗(ntarget)|NS(n)∈

{NOT ACTIVATED,ACTIVATED,RUNNING}}.

Activities from this set may be aborted, skipped, or pro-

cessed anyway depending on what the user desires. In the

latter case, their execution must be synchronized with a dy-

namically speciﬁed activity nsync ∈c succ∗(ntarget)similar

to the static case described in Sect. 3.3. In any case the applied

transformation steps lead to a proper block structure again in

which additional synchronization edges may be used if nec-

essary (see below). Since the structural constraints as well as

the graph transformations necessary to realize dynamic for-

ward jumps are very similar to the static case, we omit further

details at this point (a more comprehensive treatment can be

found in [39]). Instead, in the following subsection we present

an example working out important issues related to dynamic

forward jumps.

3.4.2 Example

Let us assume that at a certain point in time an instance graph

looks like as the one depicted in Fig. 14: Aand Bare com-

pleted and Cis currently executed. Let us further assume that

an exceptional situation occurs which makes it necessary to

AND

oin

d1 d2 data elements

TRUE_SIGNALED COMPLETED RUNNING ACTIVATED

Fig. 14. WF instance graph (for which a user wants to jump forward

to D)

Fig. 15. Dynamic forward jump – intermediate WF instance graph

immediately perform D(i.e., to jump forward to D) but to

maintain the order relationship between all other activities (E

after D;Gafter Eand F, etc.).

At ﬁrst, data dependencies for activity Dare checked: D

is executable, in principle, because it receives its input data

from the already completed activity Band it does not produce

any output data such that no problem of lost updates occurs.

Thus the restructuring of the instance graph can be started. In

order to make it possible that Dcan be immediately activated,

Dmust no longer be a successor of C. Instead, Dhas to be

placed in a branch parallel to E. This means that the control

edge from Cto Dhas to be removed and replaced by a control

edge from Bto D.

Figure 15 illustrates how the (intermediate) WF instance

graph looks like at this point in time. Dhas become a parallel

step with respect to C, its direct predecessor now is B. This

transformation alone would not be correct, however, because

not all of the previously existing constraints are obeyed any

longer. It would be possible, for example, that Eis being started

(once Chas been completed) in parallel or even before D.

To enforce the correct execution sequence, a synchronization

edge from Dto Eis introduced which enforces that Ecannot

be started until Dhas been completed (cf. Fig. 15). Finally, the

WF state is reevaluated. In particular, the control edge from B

to Dis marked with TRUE SIGNALED which means that D

can be immediately executed. The ﬁnal WF instance graph is

depicted in Fig. 16.

144 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

Fig. 16. Dynamic forward jump – ﬁnal WF instance graph

It is important to mention that, in general, the applicability

of a dynamic change depends on the current state of the WF

instance graph as well. Concerning a dynamic forward jump,

we require that its target activity has not yet been activated;

otherwise the application of this operation would not make

sense. With respect to other change operations, the required

state constraints may be more or less complex, depending on

the kind of change. For example, a new activity must not be in-

serted as a predecessor of an already running or completed step

and a completed step must not be deleted. This would cause

an inconsistent marking and therefore an undeﬁned execution

behavior of the WF instance graph. It is therefore prohibited in

ADEPT. Generally, for each basic change operation ADEPT

deﬁnes formal and easy to check compliance rules with (com-

plexity O(n)) to decide whether the intended change can be

applied in the current WF state or not.

Also very challenging is the question how to adapt the

markings of a WF instance graph when a dynamic forward

jump or, more general, a dynamic change is applied. ADEPT

uses a sophisticated approach for setting markings of activity

nodes and edges, and for adapting them in a consistent man-

ner when a dynamic change is applied (an algorithm for this

with complexity O(n)is described in [43]). The correspond-

ing rules are independent from the kind of change, which en-

ables the WfMS to efﬁciently and automatically adapt mark-

ings even in case of complex changes. Taking our example

from Figs. 15 and 16, for instance, the newly inserted con-

trol edge B→Dis evaluated to TRUE SIGNALED since B

has been already marked as COMPLETED. This, in turn, leads

to re-evaluation of activity Dof which the marking is set to

ACTIVATED, such that users can now work on D. Note that

this is exactly the desired result. Generally, when introducing

a dynamic change, already activated activities may have to be

deactivated or vice versa. In doing so, ADEPT updates user

worklists accordingly.

3.5 Discussion

We have discussed general issues related to the support of

pre-planned as well as dynamic forward jumps. In particular,

we have shown how corresponding facilities can be offered to

users. Our most important goal was to ease the use of corre-

sponding facilities and to hide the complexity associated with

them from users. By allowing designers to describe deviations

already at buildtime, the ﬂexibility of WF-based applications

can be signiﬁcantly increased. In order to enable users to ad-

equately deal with unforeseeable events, in addition, ADEPT

provides support for dynamic changes and dynamic forward

jumps. Corresponding changes will be only allowed if they do

not violate the correctness properties set out by the ADEPT

base model. Furthermore, in the implemented ADEPT WfMS

all changes and deviations are properly integrated with respect

to authorization and documentation.

4 Backward jumps

In practice, it is very important to allow authorized users to

perform backward jumps to former execution states if need

be. In ADEPT, WF designers can model normal loop backs

as well as failure backward jumps (called backward jumps for

short). While loop backs specify iterative executions, back-

ward jumps can be used to partially roll back the ﬂow as re-

sponse to semantic failures (cf. Example 2). More precisely,

a rollback operation (partially) resets the effects of previous

activity executions. Among other things this includes the re-

setting of markings, the undoing of write operations on data

elements, and the compensation of external effects if possible

and reasonable (e.g., by invoking compensating activities).

ADEPT allows the modeling of different kinds of backward

jumps. Additionally, to deal with unforeseen situations that

cannot be pre-planned at buildtime, it enables users to per-

form ad-hoc backward jumps.

Example 2. (Semantic Failure of an Activity Execution): We

refer to Example 1. Regarding the described workﬂow, a med-

ical examination may fail due to several reasons. For instance,

it may not be possible to examine the patient if preparatory

measures have been omitted or the patient does not agree with

the intervention. Depending on the concrete reason of a se-

mantic failure, the actions necessary for exception handling

may vary. For example, the workﬂow may have to be aborted

or it may be sufﬁcient to suspend its execution, to roll back the

ﬂow to a former state, and then to resume work in this state.

4.1 Semantic failures and failure backward edges

For handling (semantic) activity failures (cf. Example 2) and

for the modeling of related backward jumps, we introduce two

additional concepts: failure codes and failure backward edges.

To each activity the WF designer may assign an ar-

bitrary number of failure codes provided that correspond-

ing semantic failures are known at buildtime. In our ex-

ample, activity “perform examination” may be associated

with the two failure codes OMITTED PREPARATIONS and

MISSING AGREEMENT. Generally, a failure code corre-

sponds to a semantic failure that may occur during activity ex-

ecution and that makes it impossible to successfully complete

this activity. The task of the WF designer is to identify these

semantic failures and to deﬁne adequate exception handling

actions for them. Possible reactions supported by ADEPT in-

clude the repetitive execution of failed activities, the execu-

tion of alternative steps, the skipping of the failed activity, the

(partial) rollback of the ﬂow, or its controlled abortion. In the

following we concentrate on issues related to partial rollback.

For the deﬁnition of rollback operations, failure back-

ward edges (called failure edges for short) are offered. A

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 145

start D

J K end

failure edge

E G

failure edge

ec1

XOR split XOR join/

AND split

AND join

Fig. 17. Modeling backward jumps with failure edges

failure edge f=nfail →nbwd links two activities nbwd

and nfail together (in backward direction) and is associated

with a failure code ec of the source activity nfail. If this

activity fails and returns ec as failure code, the processing

of the WF instance will be (partially) suspended, the fail-

ure edge fbe signaled, and the ﬂow be rolled back to the

state that had been valid before the execution of nbwd was

started. In doing so, the scope of the rollback is limited to

activities from the backward region which corresponds to

that subgraph induced by the nodes from the set Nbwd with

Nbwd := (c succ∗(nbwd)∩c pred∗(nfail)) ∪{nbwd,n

fail}.

Examples for the use of failure edges are depicted in

Fig. 17:

•I→Hdescribes a partial rollback whose scope is re-

stricted to a branch of the parallel branching (D,I); i.e.,

Nbwd ={I,H}. The signaling of I→Hdoes not affect

the processing of other branches.

•K→Fdeﬁnes a partial rollback from an activity outside

a parallel branching (Kin our example) back to activity F,

which is located within a branch of this branching (Nbwd =

{F,G,J,K}). If K→Fis signaled at runtime, activities

J,G, and Fwill be reset and the ﬂow will continue with

F. Note that activities from the lower branch (Hand I) are

not affected by this partial rollback.

•A special semantics is captured by the failure edge B→

start. It links a failure code of Bwith a rollback oper-

ation to the start activity of the ﬂow (Nbwd ={start,

A,B}). When signaling this edge the ﬂow will be aborted

and its execution be completely rolled back.

How the state markings and data elements of aWF instance

graph are reset when a failure edge is signaled is shown in

Fig. 18. To ensure a correctWF execution behavior afterwards,

the use of a failure edge nfail →nbwd must meet the following

restrictions:

•The target activity nbwd of the backward jump must pre-

cede the source node nfail in the (normal) ﬂow.

•If nbwd is contained within a branch of an XOR-branching

nfail must be contained within the same branch. Other-

wise the backward jump may refer to an activity that was

not previously executed and therefore lead to an unde-

ﬁned state. Formally: Let jbe the XOR-join of an XOR-

branching with corresponding split node s. Then we re-

quire:

nbwd ∈Z:= c succ∗(s)∩c pred∗(j)⇒nfail ∈Z

•If nbwd is contained within a loop body we require that

nfail must be contained within the same subgraph. Other-

wise it remains unclear to which iteration of the loop the

WF is to be rolled back.

These conditions can be easily checked; algorithms with

complexity O(n)are presented in [39].

4.2 Automatic backward jumps

Automatic backward jumps can be linked to semantic fail-

ures of WF activities. They can be simply modeled by the use

of failure edges and codes. When performing the backward

jump at runtime, markings of nodes from the backward region

(i.e., nodes from the set Nbwd) will be reset. This becomes

necessary in order to correctly proceed with the ﬂow after-

wards. Furthermore, for all completed or running activities

from the backward region, write operations on data elements

will be undone. In addition, external effects of these activi-

ties (e.g., modiﬁcations of application data) may have to be

undone as well by invoking corresponding compensation pro-

grams. However, whether compensation is possible or not is

highly dependend on the respective application. Concerning

compensation and data context management, ADEPT follows

an approach similar to Sagas [21] and Contracts [42]. In the

following, however, we put the focus on modeling aspects; a

treatment of transactional properties and other runtime issues

is outside the scope of this paper.

An example for a pre-planned, automatic backward jump

is depicted in Fig. 18. Let us assume that during the execution

of Ka semantic failure (with failure code ec1) occurs. This,

in turn, leads to the signaling of the failure edge K→F,

which causes a partial rollback of the ﬂow. In more detail,

activity Kis aborted and activities J,G, and Fare undone (by

invoking associated compensation steps). In doing so, their

effects on state markings as well as on data elements are reset.

For example, the write operation of activity Fon dis undone

and the old value of d(written by activity D) is restored. Note

that the rollback deﬁned by K→Fonly concerns nodes from

the backward region (Nbwd ={F,G,J,K}) and therefore

does not affect activities from the lower branch of the parallel

branching (Hand Iin our example).

4.3 User-initiated backward jumps

Up to now, we have only dealt with automatic backward jumps

which are applied when an activity execution fails. In excep-

tional situations, for authorized users it must be also possible

to directly intervene in the control of a ﬂow by aborting the WF

instance or by jumping back to already passed regions. Since

corresponding jumps are very often performed as response to

external events they can be more or less determined with re-

spect to context and predictability. Depending on this, we have

to differentiate between (user) backward jumps, which can be

pre-planned and therefore be captured in the WF schema at

buildtime, and ad-hoc backward jumps.

Example 3. (User-initiated Backward Jumps):We refer to Ex-

ample 1. Assume that the patient’s state of health gets worse

or the physician wants to revise previous decisions concerning

patient treatment. In such cases it must be possible for him or

her to regain control and to jump back to previously executed

steps. (This should at least be possible as long as the medical

examination has not taken place.) This, in turn, may require

that running activities (e.g., “preparation of the patient”) may

have to be aborted or completed ones (e.g., “making an ap-

pointment”) may have to be undone. In many cases, the context

for the application of such user initiated backward jumps is

146 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

Fig. 18. Partial rollback of a ﬂow

due to the signaling of a failure

edge. aAdaptation of state mark-

ings and breset of write operations

on data elements

known in advance such that they can be considered at build-

time.

4.3.1 Pre-planned user backward jumps

Similar to shortcuts, ADEPT offers a special edge type to de-

signers – called regainControl – for the modeling of user-

initiated backward jumps.A regainControl nRC

s→nRC

dlinks

an activity nRC

swith a preceding activity nRC

d∈pred∗(nRC

and has the following semantics: After completing nRC

dand

before activating nRC

s, users may initiate a rollback of the ﬂow

to the state which had been valid before nRC

dwas started. An

example is depicted in Fig. 19a). Comparable to the model-

ing of shortcuts it shows the viewpoint of the WF designer. A

backward jump from Cto Ais deﬁned by the regainControl

edge C→A. It is selectable after completing Aand before ac-

tivating C. If the backward jump is chosen by a user, the ﬂow

will be rolled back to the state that had been valid before A

was started. Similar to a shortcut, a regainControl is internally

transformed into a representation of the ADEPT base model

in order to guarantee a precise and correct execution behavior

(cf. Fig. 19b). Since the basic principles of such a transforma-

tion have been already discussed in conjunction with shortcuts,

we omit a more detailed presentation at this point. The same

applies with respect to pre-conditions that must hold for the

correct applicability of a regainControl.

4.3.2 Ad-hoc backward jumps

Generally, it will not always be possible to foresee and to

pre-model all semantic failures that might occur during WF

execution. Furthermore there are backward jumps for which a

pre-modeling is not possible or is too complex.As an example

take a backward jump to an activity that is contained within

a branch of an XOR-branching. Since at buildtime it is not

known whether the corresponding branch will be selected for

execution, the pre-modeling of such a backward jump does

Fig. 19. RegainControl (modeler view) and its internal realization in

ADEPT

not make sense. To adequately deal with such cases as well,

ADEPT allows authorized users to perform ad-hoc backward

jumps in order to roll back theWF to a previous execution state

if need be. Basic to such an ad-hoc deviation (in backward

direction) are the WF instance graph, the execution history,

and the data element history of the respective WF instance.

The execution history, for example, logs data about start and

completion of activity executions, which can be used when a

rollback has to be performed (cf. Fig. 20). To initiate an ad-

hoc backward jump the user may dynamically select a target

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 147

activity from the list of already completed or running activities.

Afterwards the ﬂow can be rolled back to the state that had

been valid before this activity instance was started. It is also

possible to roll back the WF instance to earlier iterations of

a loop, i.e., the scope of the rollback may comprise activity

executions from different loop iterations. A simple example

illustrating this is depicted in Fig. 20. Note that markings have

to be adapted in case of a backward jump as well.

4.4 Discussion

The presented concepts allow us to capture a broad spectrum

of pre-planned as well as dynamic backward jumps. Concern-

ing transactional guarantees in combination with backward

jumps, usually, for long-running workﬂows we cannot ensure

full ACID properties (and we also do not need this in most

cases in practice). We, therefore, have adopted concepts from

the ﬁeld of extended transaction models [21, 42] by allow-

ing the WF designer to (optionally) associate activities with

compensation programs, which are then invoked in case these

activities have to be undone due to a rollback. Currently, we are

working on several other issues arising in this context. They

include the handling of backward jumps in modiﬁed WF in-

stance graphs (e.g., backward jump to a previously inserted

activity), the undoing of temporary changes (e.g. modiﬁca-

tions caused by a dynamic forward jump) in connection with

rollback operations, and the deﬁnition of compensation scopes

in order to ﬂexibly adapt the compensation behavior of WF

instances depending on their state.

5 Related work

A widespread formalism for WF modeling is offered by Petri

Nets [38,58]. Petri Nets have proven themselves as very useful

if structural and dynamic properties of WF models have to be

analyzed and veriﬁed (e.g., liveness, reachability of marking

situations, net invariances). Concerning exception handling,

many approaches assume that all exceptions which might oc-

cur during WF execution are known in advance and can there-

fore be captured in the Petri Net model [37]. Most of them,

however, do not offer special modeling elements for this. In

particular, backward jumps as described in this paper have not

been addressed at all. Instead, exceptions and deviations have

to be described with the same language elements that are used

for modeling the “standard” token ﬂow. Very often this leads

to complex net structures, which are difﬁcult to understand

and to maintain for users [19]. The adaptation of nets is addi-

tionally aggravated by the fact that Petri Nets formalisms very

often lack a clear separation between control and data ﬂow

and do not provide concepts for the explicit modeling of loop

backs. Recent work from the ﬁeld of Petri Nets has picked up

this criticism and has offered more ﬂexible concepts for ex-

ception handling. In detail, these approaches support the late

binding and modeling of WF subnets [24, 25], the dynamic

adaptation of net markings during WF execution [1,20], the

ad-hoc migration of a WF instance between two net conﬁg-

urations [3,55], or the dynamic change of the net structure

during runtime [18,19,56,57].

Simple, but useful approaches are offered by HOON [25]

and MOVE [24]. HOON uses high-level Petri Nets for WF

modeling and execution. In particular, late binding of activity

components or subnets is supported to increase ﬂexibility. De-

viations from the pre-modeled net or dynamic changes, how-

ever, are not possible once a subnet is bound to an activity. A

more advanced approach is offered by MOVE, which supports

late modeling of subnets [24]. At buildtime, the designer may

specify activity nodes for which a subnet may be dynamically

deﬁned or modiﬁed during runtime as long as the correspond-

ing activity is not activated. While this approach is sufﬁcient

for supporting dynamically evolving workﬂow structures, it

does not provide the necessary ﬂexibility to deal with excep-

tional situations. MOBILE [28] follows a descriptive approach

for WF modeling. In particular, the WF designer may omit

those aspects of a WF model (e.g., the order of tasks), which

have to be deﬁned by end users during run-time. Although

this approach allows to combine activities in a very ﬂexible

way, it is only applicable as long as the activity programs are

encapsulated and autonomous such that they may be executed

in arbitrary order.

One of the ﬁrst approaches for the dynamic adaptation

of net markings has been offered by MWMS [1,2]. MWMS

uses a simple Petri Net formalism. In particular, MWMS al-

lows users to apply backward and forward jumps within a

net instance during runtime. Such “roll forwards” and “roll

backs” [1] can be applied without violating the consistency

of the ﬂow (e.g., no deadlocks). This is achieved, however,

by abandoning important elements needed for WF modeling

in practice (e.g., no loops, no conditional branchings, no data

ﬂow tokens). Though this approach is interesting from a the-

oretical point of view, due to its restrictive WF meta model it

will not work in real-world environments.

One of the ﬁrst frameworks for dynamic WF changes has

come from the Petri Net community [19] as well. For WF

modeling so-called ﬂow nets are used. A dynamic change is

accomplished by substituting a marked subnet (old change re-

gion) by another marked net (new change region). The most

interesting issues arising in this context are how to adapt net

markings at all and how to accomplish this in a consistent man-

ner; i.e., without causing an undesired dynamic behavior (e.g.,

deadlocks) in the sequel (cf. Fig. 21). Many of the proposals

made in this context assume that users are familiar with Petri

Nets or that they are able to manually shift tokens from the old

to the new net or to add new tokens, if required [20]. Concern-

ing clinical workﬂows, for example, such an approach does not

work in practice. Apart from this, correctness and consistency

checks necessary in this context require expensive reachabil-

ity analyses for each WF instance. To avoid “dynamic change

bugs” [54,57], several proposals have been made: In [54], for

example, the authors require that instances of a given net may

be only changed if they are not currently executed on modiﬁca-

tion hit regions. To correctly adapt net markings, in addition,

it is proposed to introduce functions that map markings be-

tween the old and the new net [55]. Corresponding mapping

functions either have to be speciﬁed by the designer or are

limited to special kinds of changes (i.e., completeness is not

ensured). In our experience this is not realistic when looking

at real-world processes.

As opposed to these approaches, ADEPT automatically

preserves the consistency of markings when a jump operation

148 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

Fig. 20. Dynamic backward jump and concomitant adaptation of state markings

C D E

Old Change Region

Token

activity

New Change

Region

DEADLOCK!

arrange B and C as

parallel steps!

Fig. 21. Dynamic structural changes in Petri nets and the problem of

adapting markings

is applied. In particular, node and edge markings are auto-

matically adapted in an efﬁcient and consistent way. Basic

to this are the described execution properties of the ADEPT

base model and the chosen marking rules. When compared

to existing approaches, ADEPT covers a broader spectrum of

deviations. In addition, we have dealt with many challenging

issues that have not been systematically addressed in the WF

literature so far (e.g., concerning the modeling of backward

and forward jumps, the correct application of jump operations

in connection with loops and conditional branchings, the sup-

port of jump operations with different semantics, or the use of

automatic jumps).

Several approaches use State- and Activity-Charts for WF

modeling [22,51,60]. HieraStates [51], for example, tries to

increase ﬂexibility by allowing users to dynamically add new

states or state transitions during runtime. Furthermore, simple

forward jumps can be modeled by the use of a special tran-

sition type. As opposed to ADEPT, backward jumps cannot

be expressed in a direct way, and dynamic jumps are not sup-

ported at all. Another interesting approach has been presented

in [22]. It uses Statecharts for WF modeling and deals with

issues related to semantic preserving changes. This may be

of interest, for example, when more complex modiﬁcations

become necessary.

Other approaches from the literature combine graphical

WF description formalisms with ECA rules in order to increase

ﬂexibility [11,12,30,36]. AgentWork [36], for example, uses

global rules to enable the WfMS to dynamically restructure

the control ﬂow of a WF instance at the occurrence of logi-

cal exceptions. The implementation of AgentWork has been

partially based on the ADEPT prototype [29, 53]. Hence the

two approaches complement one another. In MOKASSIN [30]

rules serve as the basis for extending the WF meta model by

user-deﬁned constructs, if need be. In addition, WF designers

may conﬁgure the WF behavior (e.g., with respect to dynamic

changes) in a very ﬂexible manner. Although this approach

provides a great ﬂexibility for WF designers, it will be not

applicable in many application domains, since no correctness

or consistency guarantees can be made.

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 149

In the WF community, several other work on is-

sues related to dynamic WF changes has been done

(e.g., [9,10,17,26,31,35,48,59]). WIDE [10], TRAM [31],

WASA2[59] and BREEZE [48], for example, focus on WF

schema evolution and on the migration of in-progress WF in-

stances to the new schema, if possible and desired. In Obli-

gations [9] a WF instance graph is dynamically composed of

multiple process templates which reﬂect different views on

the WF instance. Exception handling is possible through the

dynamic addition or removal of templates. Correctness issues

are not discussed. Finally, in CONSENSUS [4] combined e-

negotiations are modeled and enacted using WF technology.

To support dynamism, runtime WF modiﬁcations are sup-

ported. Like AgentWork, CONSENSUS has used the ADEPT

WfMS for implementation purposes.

Finally, several other proposals for the support of adaptive

workﬂows have been made in the literature. They are based on

different formalisms, like graph grammars [9,27,44], process

grammars [23], planning techniques [7], inheritance mecha-

nisms [56], or transactional models [17,21,34].

6 Summary

We have presented a sophisticated approach for the ﬂexi-

ble support of pre-planned as well as dynamic deviations in

WfMS. For WF designers, high-level concepts are offered for

the modeling of forward and backward jumps. By transform-

ing them into an executable representation of the ADEPT base

model, a correct and efﬁcient execution by theADEPT WF en-

gine can be ensured. Furthermore, the separation of standard

process descriptions from exceptional paths contributes to a

better structuring of the WF models. We have shown that a

ﬂexible execution behavior can be achieved when capturing

deviations in WF models at buildtime provided that they are

known in advance.To increaseWfMS ﬂexibility at runtime and

to enable users to deal with unforeseen exceptions, in addition,

we offer high-level operations to dynamically intervene into

the control of in-progress workﬂows. Authorized users may

work on activities ahead of the normal schedule by jumping

forward to them or they may roll back the ﬂow to a former ex-

ecution state by applying a corresponding backward jump. In

any case,ADEPT ensures that the correctness and consistency

of the ﬂow is preserved when applying such a jump and that

the complexity arising from the support of dynamic changes

is hidden to a large degree from users.

In this paper we have concentrated on issues related to for-

ward and backward jumps in WfMS. How to deﬁne other kinds

of changes, how to “physically” perform them, how to adapt

state markings and user worklists in this context, or how to deal

with concurrent change deﬁnitions (and with synchronization

issues arising in this context) are other important questions

addressed by our research as well. Some of them have been

already reported in other papers of our group (e.g. [41, 43])

and been considered in our prototypical WfMS implementa-

tion as well [29]. Indeed, the ADEPT prototype proves that

one can really build a ﬂexible and robust WfMS which offers

the described functionality within one system.

Acknowledgements. We would like to thank the anonymous review-

ers and our colleague Stefanie Rinderle for their valuable suggestions.

References

1. Agostini, A., De Michelis, G.: Simple workﬂow models. In:

Proc. of the Workshop on Workﬂow-Management: Net-bases

Concepts, Models, Techniques, and Tools., Lissabon, Juni 1998,

pp. 146–163

2. Agostini, A., De Michelis, G.: Improving ﬂexibility of workﬂow

management systems. In: Proc. Business Process Management

(BPM’2000), LNCS 1806, Lissabon, June 2000, pp. 218–234

3. Badouel, E., Oliver, J.: Reconﬁgurable nets – a class of high level

petri nets supporting dynamic changes. In: Proc. of the Work-

shop on Workﬂow-Management: Net-bases Concepts, Models,

Techniques, and Tools, Lissabon, Juni 1998, pp. 129–145

4. Bassil, S., Benyoucef, M., Keller, R., Kropf, P.: Addressing dy-

namism in e-negotiations by workﬂow management systems. In:

Proc. DEXA Workshop, September 2002

5. Bauer, T., Dadam, P.: Efﬁcient distributed workﬂow manage-

ment based on variable server assignments. In: Proc. CAiSE

’00, Stockholm, June 2000, pp. 94–109

6. Bauer, T., Reichert, M.: Dynamic change of server assignments

in distributed workﬂow management systems. Datenbank Spek-

trum, 2(4): 59–67, 2002

7. Beckstein, C., Klausner, J.: A planning framework for workﬂow

management. In: Proc. Workshop on Intelligent Workﬂow and

Process Management., Stockholm, August 1999

8. Beuter, T., Dadam, P., Schneider, P.: The WEP model: Adequate

workﬂow-management for engineering processes. In: Proc. Eu-

rop. Concurrent Engineering Conf. 1998, Erlangen, April 1998

9. Bogia, D.: Supporting Flexible, Extensible Task Descriptions In

and Among Tasks. PhD Thesis, University of Urbana, Illinois,

1995

10. Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workﬂow evolution.

Data and Knowledge Engineering, 24(3): 211–238, 1998

11. Casati, F., Fugini, M., Mirbel, I.: An environment for designing

exceptions in workﬂows. Information Systems, 24(3): 255–273,

1999

12. Chiu, D., Li, Q., Karplapalem, K.: A meta modeling approach to

workﬂow management systems supporting exception handling.

Information Systems, 24(2): 159–184, 1999

13. Curbera, F., Goland,Y., Klein, J., Leymann, F., Roller, D., Thatte,

S., Werawarana, S.: Business Process Execution Language for

Web Services (V 1.0). Initial Public Draft Release, 2002, see

http:// www.ibm.com/developerworks/library/

ws-bpel, 2002

14. Dadam, P., Reichert, M., Kuhn, K.: Clinical workﬂows – the

killer application for process-oriented information systems? In:

Proc. 4th Int’l Conf. on Business Information Systems (BIS ’00),

Poznan, Poland, 2000, pp. 36–59

15. Dijkstra, E.: Cooperating sequential processes. In: Genuys, F.

(ed.) Programming Languages. Academic Press, 1968

16. Dumas, M., ter Hofstede, A.H.M.: UML activity diagrams as

a workﬂow speciﬁcation language. In: Proc. Int’l Conf. on the

Uniﬁed Modeling Language, Toronto, 2001

17. Eder, J., Liebhart, W.: Contributions to exception handling in

workﬂow-management. In: Proc. EDBT Workshop onWorkﬂow

Management Systems, Valencia, 1998, pp. 3–10

18. Ellis, C.A., Keddara, K.: A workﬂow change is a workﬂow. In:

Proc. Business Process Management (BPM’2000), LNCS 1806,

2000, pp. 201–217

19. Ellis, C.A., Keddara, K., Rozenberg, G.: Dynamic change within

workﬂow systems. In: Proc. Int’l Conf. on Org. Comp. Sys.,

Milpitas, CA, August 1995, pp. 10–21

20. Ellis, C.A., Maltzahn, C.: The Chautauqua workﬂow system. In:

Proc. 30th Int’l Conf. on System Science, Maui, 1997

150 M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems

21. Elmargarmid, A.K. (ed.): Database Transaction Models for Ad-

vanced Applications. Morgan Kaufmann Publ., 1992

22. Frank, H., Eder, J.: Equivalence transformations on statecharts.

In: Proc. 12th Int’l Conf. on Software and Knowledge Eng.,

Chicago, July 2000, pp. 150–158

23. Glance, N., Pagani, D., Pareschi, R.: Generalized process struc-

ture grammars (gpsg) for ﬂexible representations of work. In:

Proc. 7th Intl Conf. on Computer Supported Cooperative Work

(CSCW96), Boston, MA, 1996, pp. 180–189

24. Hagemeyer, J., Hermann, T., Just-Hahn, K., Striemer, B.: Flex-

ibility in workﬂow management systems. In: Proc. Software-

Ergonomie’97, Dresden, Germany, 1997, pp. 179–190 (in Ger-

man)

25. Han,Y.: Software Infrastructure for Conﬁgurable Workﬂow Sys-

tems. PhD Thesis, TU Berlin, 1997

26. Han, Y., Sheth, A.: On adaptive workﬂow modeling. In: Proc.

4th Int’l Conf. on Information System Analysis and Synthesis,

Orlando, 1998

27. Heimann, P., Joeris, G., Krapp, C., Westfechtel, B.: DYNA-

MITE: Dynamic task nets for software process management.

In: Proc. 18th Int’l Conf. Software Engineering, Berlin, 1996, p.

331341

28. Heinl, P., Schuster, H., Stein, K.: Support of ad-hoc workﬂows

in the mobile workﬂow model. In: Proc. Softwaretechnik in Au-

tomation und Kommunikation, Munich, March 1996, pp. 229–

242

29. Hensinger, C., Reichert, M., Bauer, T., Strzeletz, T., Dadam,

P.: ADEPTworkflow – advanced workﬂow technology for the

efﬁcient support of adaptive, enterprise-wide processes. In: Proc.

Software Demonstration Track (EDBT ’00), Konstanz, March

2000

30. Joeris, G.: Deﬁning ﬂexible workﬂow execution behaviors.

In: Proc. GI-Workshop, Enterprise-wide and Cross-enterprise

Workﬂow-Management (Informatik ’99), October 1999, pp. 49–

31. Kradolfer, M., Geppert, A.: Dynamic workﬂow schema evolu-

tion based on workﬂow type versioning and workﬂow migration.

In: Proc. CoopIS ’99, Edinburgh, September 1999, pp. 104–114

32. Lei, Y., Singh, M.P.: A comparison of workﬂow metamodels.

In: Proc. ER’97 Workshop on Behavioral Models and Design

Transformations, Los Angeles, 1997

33. Leymann, F., Roller, D.: Production Workﬂow. Prentice Hall,

2000

34. Liu, L., Pu, C.: Methodical restructuring of complex work-

ﬂow activities. In: Proc. 14th Int’l Conf. On Data Engineering

(ICDE98), Orlando, Florida, 1998, pp. 342–350

35. Luo, Z., Sheth,A.: Defeasible workﬂow, its computation and ex-

ception handling. In: Proc. CSCW’98 Workshop Towards Adap-

tive Workﬂow Systems, Seattle, WA, November 1998

36. M¨uller, R., Rahm, E.: Dealing with logical failures for collabo-

rating workﬂows. In: Proc. Int’l 5th Conf. on Cooperative Infor-

mation Systems, Eilat, 2000, pp. 210–223

37. Oberweis, A.: Speciﬁcation of techniques for handling excep-

tions with petri nets.Automatisierungstechnik – at, 40(1): 21–30,

1992 (in German)

38. Oberweis, A.: Modeling and Execution of Workﬂows Based on

Petri Nets. Teubner, 1996 (in German)

39. Reichert, M.: Dynamic Changes in Workﬂow-Management-

Systemen. PhD thesis, University of Ulm, 2000 (in German)

40. Reichert, M., Bauer, T., Fries, T., Dadam, P.: On modeling pre-

dictable deviations in workﬂow management systems. In: Proc.

Modellierung ’02, pp. 183–194, Tutzing, March 2002 (in Ger-

man)

41. Reichert, M., Dadam, P.: ADEPTflex – supporting dynamic

changes of workﬂows without losing control. JIIS, Special Issue

on Workﬂow Management Systems, 10(2): 93–129, 1998

42. Reuter, A., Schwenkreis, F.: Contracts–alow-level mechanism

for building general-purpose workﬂow management systems.

IEEE Bulletin of the Technical Committee on Data Engineering,

18: 4–10, 1995

43. Rinderle, S., Reichert, M., Dadam, P.: Efﬁcient compliance

checks and automatic migration of workﬂow instances to sup-

port workﬂow schema evolution. Informatik, Forschung und En-

twicklung, 17(4): 177–197, 2002 (in German)

44. Rozenberg, G.: Handbook of Graph Grammars and Computing

by Graph Transformation – Volume 1: Foundations. 1997

45. Saastamoinen, H.: On the Handling of Exceptions in Information

Systems. PhD thesis, University of Jyvaskyla, Finland, 1995

46. Sadiq, S.: On Veriﬁcation Issues on Conceptual Modeling of

Workﬂow Processes. PhD thesis, University of Queensland,Aus-

tralia, 2001

47. Sadiq, S., Orlowska, M.: Analyzing process models using graph

reduction techniques. Information Systems, 25(2): 117–134,

2000

48. Sadiq, S., Orlowska, M.: On capturing exceptions in workﬂow

process models. In: Proc. 4th Int’l Conf. on Business Information

Systems (BIS ’00), Poznan, Poland, April 2000

49. Schultheiss, B., Meyer, J., Mangold, R., Zemmler, T., Reichert,

M.: Process design for therapeutic treatment of inpatients. DBIS-

5, University of Ulm, November 1995 (in German)

50. Strong, D., Miller, S.: Exceptions and exception handling in com-

puterized information processes. ACM ToIS, 13(2): 206–233,

1995

51. Teege, G.: Flexible workﬂows. In: Proc. Workshop Flexibilit¨at

und Kooperation in Workﬂow-Management-Systemen, p. 1321,

1998 (in German)

52. ter Hofstede, A.H.M., Orlowska, M., Rajapakse, J.: Veriﬁcation

problems in conceptual workﬂow speciﬁcations. Data & Knowl-

ege Engineering, 24(3): 239–256, 1998

53. Rahm, E., Greiner, U.: Webﬂow: A system for the ﬂexible exe-

cution of web-based, cooperative workﬂows. In: Proc. Database

Systems For Business, Technology and Web (BTW’2003),

Leipzig, February 2003 (in German)

54. van der Aalst, W.M.P.: Exterminating the dynamic change bug:

A concrete approach to support workﬂow change. Information

Systems Frontiers, 3(3): 297–317, 2001

55. van der Aalst, W.M.P.: How to handle dynamic change and cap-

ture management information: An approach based on generic

workﬂow models. Int’l Journal of Computer Systems, Science,

and Engineering, 16(5): 295–318, 2001

56. van der Aalst, W.M.P., Basten, T.: Inheritance of workﬂows: An

approach to tackling problems related to change. Theoretical

Computer Science, 270(1–2): 125–203, 2002

57. van der Aalst, W.M.P., Jablonski, S.: Dealing with workﬂow

change: Identiﬁcation of issues an solutions. Int’l Journal of

Comp. Systems, Science and Engineering, 15(5): 267–276, 2000

58. van derAalst,W.M.P., van Hee, K.: Workﬂow Management. MIT

Press, 2002

59. Weske, M.: Flexible modeling and execution of workﬂow ac-

tivities. In: Proc. 31st Int’l Conf. on System Sciences, Hawaii,

1998, pp. 713–722

60. Wodtke, D., Weikum, G.: A formal foundation for distributed

workﬂow execution based on state charts. In: Proc. Int’l Conf.

on Database Theory (ICDT’97), Delphi, Greece, 1997

M. Reichert et al.: Dealing with forward and backward jumps in workﬂow management systems 151

Manfred Reichert is assistant professor

in the Department Databases and Infor-

mation Systems at the University of Ulm,

Germany. He ﬁnished his PhD thesis on

ﬂexible workﬂow management in May

2000. He is author and co-author of many

articles and conference papers on hospital

information systems and workﬂow man-

agement. Current research topics include

enterprise-wide and cross-organizational

workﬂows, enterprise application integration and workﬂow, and dif-

ferent aspects related to workﬂow technology.

Peter Dadam has been full professor at the

University of Ulm and director of the De-

partment Databases and Information Sys-

tems since 1990. Before he came to the

University he had been director of the re-

search department for Advanced Informa-

tion Management (AIM) at the IBM Hei-

delberg Science Center (HDSC). At the

HDSC he managed the AIM-P project on

advanced database technology and appli-

cations. Current research areas include distributed, cooperative in-

formation systems, workﬂow management, and database technology

and its use in advanced application areas.

Thomas Bauer is a researcher at the

DaimlerChrysler Research Centre in Ulm

where he is working in the area of en-

gineering process management. Before,

he was a member of the Department

Databases and Information Systems at the

University of Ulm where he ﬁnished his

PhD thesis on the efﬁcient management of

enterprise-wide workﬂows in 2001. Cur-

rent research areas include engineering

processes, workﬂow management, and enterprise application inte-

gration.