Providing Integrated Life Cycle Support in Process-Aware Information Systems [original]

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

International Journal of Cooperative Information Systems

World Scientific Publishing Company

PROVIDING INTEGRATED LIFE CYCLE SUPPORT IN

PROCESS-AWARE INFORMATION SYSTEMS

BARBARA WEBER

Department of Computer Science, University of Innsbruck,

Technikerstraße 21a, 6020 Innsbruck, Austria

barbara.web[email protected]

MANFRED REICHERT, STEFANIE RINDERLE-MA

Dept. Databases and Information Systems, University of Ulm,

Oberer Eselsberg, 89069 Ulm, Germany

{manfred.reichert,stefanie.rinderle}@uni-ulm.de

WERNER WILD

Evolution Consulting,

Jahnstraße 26, 6020 Innsbruck, Austria

[email protected]

The need for more flexiblity of process-aware information systems (PAISs) has been

discussed for several years and different approaches for adaptive process management

have emerged. However, only few of them provide support for both changes of individual

process instances and the propagation of process type changes to a collection of related

process instances. Furthermore, knowledge about process changes has not yet been ex-

ploited by any of these systems. This paper presents the ProCycle approach which over-

comes this practical limitation by capturing the whole process life cycle and all kinds of

changes in an integrated way. Users are not only allowed to deviate from the predefined

process in exceptional situations, but are also assisted in retrieving and reusing knowl-

edge about previously performed changes in this context. If similar instance deviations

occur frequently, process engineers will be supported in deriving improved process models

from them. This, in turn, allows engineers to evolve the PAIS (including the knowledge

about the changes) over time. Feasability of the ProCycle approach is demonstrated by

a proof-of-concept prototype which combines adaptive process management technology

with concepts and methods provided by case-based reasoning (CBR) technology.

Keywords: Adaptive Process, Process-Aware Information System, Process Flexibility,

Learning and Evolving Systems, Exception Handling

1. Introduction

The economic success of enterprises increasingly depends on their ability to react to

changes in their environment in a quick and flexible way.1Examples for such changes

include regulatory adaptations (like the introduction of Sarbanes-Oxley2or Basel

II3), market evolution, changes in customer behavior, process improvement and

strategy shifts. Companies have therefore identified business agility as a competitive

B. Weber, M. Reichert, W. Wild, S. Rinderle-Ma (2009): Providing integrated

life cycle support in process-aware information systems. World Scientific

Publishing Company, Int'l Journal of Cooperative Information Systems

(IJCIS) , Vol. 18, No. 1, pp. 115-165.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

2B. Weber et al.

advantage required for coping with business trends like increasing product and

service variability, faster time-to-market4, and increasing division of labor along

the supply chain of goods and services.5

Nowadays needed business agility is often hindered by the lacking flexibility of

contemporary enterprise information systems. Recently, a new generation of process-

aware information systems (PAISs) has emerged to overcome this rigidity.6,7To

allow for more flexibility, PAISs introduce an additional layer when compared to

traditional information systems, which provides an explicit description of the pro-

cess logic. The core of a PAIS is built on top of a process management system,

which provides generic functionality for the modeling, enactment, and monitoring

of (business) processes.6In general, process logic is represented as process models

(also called process schemes) within the PAIS. Such a model represents a particular

process type and consists of the activities (i.e., the tasks) to be executed, their con-

trol and data dependencies, organizational entities performing the activities, and

the business objects manipulated by them. Based on a process model, new process

instances can be created, each representing a concrete business case. At run-time,

the PAIS is responsible for enacting these process instances and for coordinating

corresponding activities as specified in the process model. In this context, process

monitoring and process intelligence tools provide real-time status information about

running processes, and can be used for process analysis and diagnosis.8

Though PAISs allow to reduce maintenance costs when compared to contem-

porary enterprise information systems1,9, their development is still costly and time

consuming. One major reason for this is the missing run-time flexibility of contem-

porary PAISs. Once a process has been implemented, its logic cannot be adapted

anymore during run-time, which often freezes already modeled business processes.10

However, to allow for the required business agility and to support business processes

effectively, PAISs must be flexible at run-time and enable users to quickly adapt the

supported processes to environmental changes or exceptional situations. In response

to these needs adaptive PAISs have emerged to support changes at the process in-

stance and/or process type level.11,12,13,14,15

Instance-specific changes affect a single process instance (i.e., one business case)

and are required to handle (unexpected) exceptions.10 For example, consider a cru-

ciate rupture treatment process for patients, which usually includes a magnetic res-

onance tomography (MRT), an X-ray, and a sonography. For a particular patient

the MRT may have to be skipped as he has a cardiac pacemaker. The respective

change is instance-specific and must not affect any other process instances. Process

type changes, in turn, are applied to adapt the PAIS to changes of the underlying

business processes. This is done by creating a new process schema version. Due to

new legal regulations, for example, it might become necessary to inform patients

about alternative treatment methods before applying one of them. This newly in-

troduced duty requires the modification of the process schema (e.g., inserting an

activity Inform Patient). For ongoing treatments it must then be decided whether

corresponding problems shall be completed according to the old process schema or

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 3

be migrated to the new process schema version. In the former case only newly ad-

mitted patients are informed about potential risks. By contrast, when using PAISs

supporting instance migration (e.g., ADEPT216 and WASA217) patients with an

already ongoing treatment process can be informed as well.

1.1. Problem Statement

The need for more flexible PAISs has been recognized for several years. Existing

approaches support instance-specific changes as well as the evolution of the process

schema at the type level.

Regarding instance changes, same or similar exceptions can occur more than

once, making the reuse of existing exception handling procedures desirable.13,18 The

definition of instance changes from scratch, however, requires user experience, es-

pecially when secondary adaptations become necessary. For example, when deleting

a particular activity in a process schema, data-dependent activities might have to

be deleted as well, requiring complex user interactions.10 Therefore, a PAIS should

not only allow for deviations from the predefined process, but also support users in

reusing knowledge about previous deviations (incl. the process adaptations associ-

ated with them). For example, the knowledge that an MRT could not be performed

for a patient with cardiac pacemaker is highly relevant when treating other patients

with the same or similar problem.

To be able to reuse knowledge about similar deviations, respective process

changes must be annotated with contextual information (e.g., information about

the reasons for the deviation) and be memorized by the PAIS. This contextual in-

formation is needed to ensure that only knowledge about those changes is presented

to the user, which are relevant in the current situation. For example, an MRT must

not be skipped for patients in general, but only for those with cardiac pacemaker.

Another challenge concerns process evolution. When similar exceptions occur

frequently, this often indicates a gap between the modeled and the real-world busi-

ness processes. This misalignment can stem from errors in the design of a process

model or be the result of changing requirements. Therefore, adaptive PAISs should

continuously monitor deviations between a predefined process model and actual

process enactment in order to detect discrepancies between modeled and observed

process behavior. If a particular deviation occurs frequently, the process engineer

will have to be informed and the PAIS will have to support her to evolve the pro-

cess model as needed. Assume, for example, that the activity performing an MRT is

skipped frequently. Then it can be beneficial to include this situation directly in the

process model to reduce cost of change later. In addition, not only process models

evolve over time, but also the knowledge about process changes. In particular, if

frequent instance changes trigger a process evolution and are consequently pulled

up to the process schema, knowledge about these past instance deviations becomes

obsolete. The challenge thereby is to determine, which changes are still relevant and

therefore should be kept in the knowledge base and which ones are outdated and

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

4B. Weber et al.

therefore can be dropped.

The high practical relevance of this problem has been confirmed by the ap-

plication projects performed with ADEPT110 in domains like healthcare19, e-

Negotiation20, and transportation.21 All these projects have shown that similar

exceptions often occur in practice and therefore have to be repeatetly handled. In

addition, all these projects have revealed that certain exceptions, which occured

frequently could be avoided through a redesign of the process schema.

1.2. Contribution

In this paper we present our ProCycle approach, which supports all phases of the

process life cycle in an integrated way. It allows for the modeling, the execution and

the monitoring of business processes in a flexible way, and enables process changes

at the instance as well as the type level. In particular, ProCycle facilitates instance

changes during run-time by supporting the retention and reuse of process deviations.

Further, it allows for the automated derivation of process type changes to evolve

business processes over time and to reduce cost of change. Regarding process type

changes ProCycle does not only support the co-existence of process instances of dif-

ferent schema versions, but also enables the migration of ongoing process instances

to a new schema version. In addition to process evolution, ProCycle provides system

support for evolving knowledge about changes over time. This allows to support the

entire process lifecycle seamlessly. To demonstrate the feasability of the ProCycle

approach a powerful proof-of-concept prototype, based on the ADEPT210,16,22 and

CBRFlow18 technologies, has been implemented. However, most of the concepts

described in this paper could be realized on top of other adaptive PAISs (e.g.,

WASA217 or METEOR23) as well. ADEPT2 offers full functionality with respect

to the modeling, analysis, execution, and monitoring of business processes.10,14,16,24

In addition, it provides support for adaptive processes at both process instance and

process type level. CBRFlow on the other hand supports the reuse of instance

changes. Our proof-of-concept implementation builds upon this functionality and

extends it such that integrated process life cycle support can be achieved.

Note that the focus of this paper is on control-flow changes. Changes of the

resource perspective (e.g., actor assignments) or data perspective are out of the

scope of this paper. However, the proposed approach, in principle, is not limited to

control-flow changes and could be extended to cover other perspectives as well.

This paper provides a significant extension of our previous work25,26, which

made several simplifications. We provide an in-depth description of all phases of

the process life cycle. For example, in our previous work retrieval of similar devia-

tions was an entirely manual process, which solely considered free text for describ-

ing the reasons of a deviation.25 By contrast, this paper partially automates the

retrieval process by considering structured information about the process context

(e.g., reasons for a deviation and status of the process instance to be modified) as

well. Further, if similar deviations can be retrieved, but cannot be reused directly

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 5

(e.g., if the process instance has progressed too far such that the change cannot

be applied directly), user support for adapting the respective change definition to

the current situation will be enabled. This paper further provides substantial ex-

tensions regarding process learning and the derivation of process type changes. In

particular, we discuss strategies for deriving process type changes and suggest meth-

ods for evolving not only process schemes, but also the knowledge about instance

deviations.

Section 2 provides background information needed for understanding this paper.

Section 3 explains how ProCycle supports retention and reuse of instance changes.

In Section 4 we show how quality of the knowledge on instance changes can be

ensured. Section 5 focuses on issues relevant for process learning and evolution.

Section 6 describes the implementation of ProCycle. Finally, Section 7 discusses

related work and Section 8 concludes with a summary and an outlook.

2. Backgrounds

2.1. Basic Concepts

A process-aware information system (PAIS) is a specific type of information system

which enables process support and allows for separating process logic and appli-

cation code. At build-time, process logic has to be explicitly defined based on the

constructs provided by a process meta model. At run-time the PAIS orchestrates

the processes according to the defined logic. Workflow systems like Staffware, Web-

sphere Process Server, Ultimus, ADEPT210, and YAWL27 as well as Case-Handling

Systems (e.g., Flower6,28) are PAIS-enabling technologies.

For each business process to be supported (e.g., handling a customer request or

processing an insurance claim), a process type Trepresented by a process schema S

has to be defined. For a particular process type several process schemes may exist,

representing the different versions and the evolution of this type over time. In the

following, a single process schema corresponds to a directed graph, which comprises

a set of nodes – representing process activities or control connectors (e.g., XOR-

Split, AND-Join) – and a set of control edges between them. Control edges specify

precedence relations between the different nodes. In addition, a process schema

comprises a set of data elements and a set of data edges. A data edge links an

activity with a data element and represents a read or write access of this activity

to the respective data element.

Fig. 1a shows a simplified version of the control-flow perspective of a cruciate

rupture treatment process. The respective process schema consists of ten activ-

ities and six control connectors: Activity Patient Admission is followed by ac-

tivity Anamnesis & Clinical Examination in the flow of control, whereas activ-

ities X-ray,MRT and Sonography can be processed in parallel (i.e., in arbitrary

order). Activities Initial Treatment & Operation Planning and Operative

Treatment will be conditionally executed if the preceding medical examinations

show that the patient is suffering from a cruciate rupture and non-operative treat-

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

6B. Weber et al.

++xx x

Activated

a) Process Type Level

b) Process Instance Level

Process Schema S

Completed Skipped

Execution Trace:

σ1 = < „Patient Admission“, „Anamnesis & Clinical Examination“, „X-ray“> Execution Trace:

σ2= < „Patient Admission“>

Execution Trace:

σ4= < „Patient Admission“, „Anamnesis & Clinical Examination“, „Non Operative

Therapy“>

Process Instance I1

Execution Trace:

σ3 = < „Patient Admission“, „Anamnesis & Clinical Examination“, „MRT“,

„X-ray“, „Sonography“>

Process Instance I2

Process Instance I3

Process Instance I4

Activity

XOR-Split/Join

AND-Split/Join

Activity States:

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

++ x xx

++xx x

clinicalSuspicionOf

CruciateRupture = „Yes“

cruciateRupture = „Yes“ and

operationIndicated = „Yes“

Fig. 1. Core Concepts (Control-Flow Perspective)

ment does not constitute a viable option.

Based on process schema Sdepicted in Fig. 1a, at run-time corresponding

process instances can be created and executed (cf. Fig. 1b). Regarding process

instance I1in Fig. 1b, for example, activities Patient Admission,Anamnesis

& Clinical Examination and X-ray are completed, activity Non Operative

Therapy is skipped, and MRT and Sonography are concurrently activated. Com-

pletion events of activities of an instance are recorded in the instance trace.

Definition 2.1. (Execution Trace) Let InstSbe the set of all process instances

derived from process schema S. The trace σof a process instance I∈InstSis given

by σ=<t1, . . . , tk>where the temporal order of tiin σreflects the order in which

activities tiwere completed over S. The set of all traces for all instances I∈InstS

is denoted as execution log.

The traces for instances I1to I4only contain completed activities and are illus-

trated in Fig. 1b. Generally, a large number of instances being in different states

might run on a particular process schema.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 7

2.2. Process Change

Adaptive PAISs are characterized by their ability to correctly and efficiently deal

with process changes. Before discussing different levels of change, we give a definition

on the topology of change.

Definition 2.2. (Change in Process Schemas) Let Pbe the set of all process

schemas and let S,S0∈ P. Let further ∆=<op1, ..., opn>denote a process change,

which applies change operations opi, i=1,. . . ,n sequentially.

(1) S[∆>if and only if change ∆is applicable to S

(2) S[∆> S0if and only if ∆is applicable to S(i.e., S[∆>) and S0is the process

schema resulting from the application of ∆to S(also: S0=S+ ∆)

(3) S[∆> S0if and only if there are process schemes S1, S2,. . . ,Sn+1 ∈ P with

S=S1, S0=Sn+1 and for 1 ≤i≤n: Si[∆i> Si+1 with ∆i= (opi)

In general, changes can be triggered and performed at two levels – the process

type and the process instance level.

Changes to a process type Tmay become necessary to cover the evolution of

real-world business processes captured by the process schema of this type.14,17,29

Generally, process engineers can accomplish type changes of a process schema by

applying a set of change operations (i.e., change primitives or change patterns) to the

current schema version Sof type T.30 This results in the creation of a new schema

version S0of the same type (cf. Fig. 2a). Execution of future process instances is

then based on S0. In addition, for long-running process instances it is often desired to

migrate them to the new schema version S0in a controlled and efficient manner.24,30

For example, in Fig. 2a process schema Shas evolved to new schema version S0

by inserting activities Xand Y. Changes can be propagated to running instances

as well, if these instances are compliant with the new schema version (i.e., their

traces can be produced on S0as well).24,31 For example, instances I1and I2from

Fig. 2a can be migrated to S0, while I3has already progressed too far and therefore

must be completed based on original schema version S. Due to the data dependency

between activities Xand Y, the uncontrolled migration of I3to S0would not only

lead to inconsistent states, but potentially introduce deadlocks or other errors.

By contrast, changes of individual process instances are usually performed by end

users. They become necessary to react to exceptional situations.10,18,23 In particular,

the effects of such changes must be kept local, i.e., they must not affect other process

instances of the same type. In Fig. 2b instance I5has been individually modified

by inserting activity Xand by deleting activity F.

Instance-specific changes applied to process instance Iare denoted as bias ∆I

of I, i.e., ∆I=<op1, ..., opn>comprises the change operations opi(i= 1, ..., n)

applied to I so far and making its schema different from S. Schema SI:= S+ ∆I,

which results from the application of ∆Ito S, is called instance–specific schema

of I. For example, in Fig. 2b the bias of I5is given by ∆I=<Delete(I5,F),

Insert(I5,X,AND-Split1,AND-Join1)>.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

8B. Weber et al.

Process Schema S‘

Schema Evolution

S[ΔS>S‘

Process Schema S

Process Instance I1

Migration

of compliant

process instances

to schema S’

Instance Change

SI[ΔI>SI‘

a) Process Type Change

Process Instance I2

Process Instance I3

Process Instance I1

Process Instance I2

Instance I5 on SI5

ΔS= <Insert(S,X,A,B),

Insert(S,Y,C,AND-Join1),

AddDataDependendcy(X,Y,d)>

AND-Split1 AND-Join1

b) Instance-Specific Change

Process Instance I3not compliant with S’

ΔI = <Delete(I5,F),

Insert(I5,X,AND-Split1,AND-Join1)>

AND-Split1 AND-Join1

++EFAB

++EF

++E

++EF

Data Element

Instance I5 on SI5’

Fig. 2. Process Type and Process Instance Changes

In ProCycle, both process type and process instance changes are based on

a set of high-level change operations (i.e., change patterns) with well-defined

semantics.30,32. Table 3 presents a selection of respective change patterns, which al-

low for structural modifications of process schemes at a high-level of abstraction. Ex-

amples are as shown in Fig. 2b the deletion of activity Ffrom process schema S(i.e.,

Delete(S,F)) or the insertion of activity Xinto schema Safter node AND-Split1

and before node AND-Join1 (i.e., Insert(S,X,AND-Split1,AND-Join1)). Formal

semantics of the listed patterns is described in.32

Note that respective changes can also be performed using change primitives like

add node,remove node,add edge and remove edge. Following this approach, the

realization of a particular adaptation (e.g., activity deletion or insertion) requires

the application of multiple change primitives. However, due to their lack of abstrac-

tion, changes based on change primitives are more complex and error-prone. In

addition, correctness of a process schema has to be explicitly checked after applying

the respective set of primitives (for details see Ref. 30);

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 9

Name Change Pattern Short Description of Pattern

Insert(S,f,A,B) Process fragment (*) f is inserted between activity sets A and B.

Insert Process

Fragment CondInsert(S,f,A,B,cond) A conditional branch with process fragment f will be inserted

between activity sets A and B.

Delete Process

Fragment Delete(S,f) Deletes process fragment f from schema S.

Move Process

Fragment Move(S,f,A,B) Process fragment f is moved from its current position and re-

inserted between activity sets A and B.

Replace Process

Fragment Replace(S,f,g) Process fragment f is replaced by fragment g in schema S.

Swap Process

Fragments Swap(S,f,g) Process fragments f and g are swapped.

(*) A process fragment can either be an atomic activity or a sub-graph with single entry and single exit nodes

Fig. 3. Examples of Process Change Patterns

2.2.1. Backgrounds on Case-Based Reasoning

Case-Based Reasoning (CBR) is a contemporary approach to problem solving and

learning.33 Problems and their solutions are described as cases and stored in case–

bases. New problems are dealt with by drawing on past experiences and by adapting

respective solutions to the new problem situation. Reasoning based on past experi-

ences is a powerful and frequently applied way to solve problems by humans.34 A

physician, for example, remembers previous cases to correctly diagnose the disease

of a newly admitted patient. A banker uses her experiences about previous cases in

order to decide whether to grant a loan or not. Generally, a case is a contextualized

piece of knowledge representing an experience33, which typically consists of a prob-

lem description and the corresponding solution. In particular, CBR uses specific

knowledge of past experiences to solve new problems. CBR also contributes to in-

cremental and sustained learning: every time a new problem is solved, information

about it and its solution is retained, and therefore immediately made available for

solving future problems.34

Our approach described in this paper relies on Conversational CBR (CCBR)

which constitutes an extension of the CBR paradigm. CCBR actively involves users

in the case retrieval process.35 A CCBR system can be characterized as interactive

system. Via a mixed-initiative dialogue it guides users through a question-answering

sequence in a case retrieval context. In contrast to traditional CBR, the user is not

required to provide a complete a-priori problem specification for case retrieval. He

does also not need to have a clear picture of what is relevant for problem solving.

Instead, CCBR guides users, who might only have a vague idea of what they are

searching for, to assess the given situation and to find relevant cases. Users can

provide already known information at any time. Therefore, CCBR is especially

suited to support inexperienced users in handling exceptional situations that cannot

be dealt with in a fully automated way.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

10 B. Weber et al.

2.3. Process Life Cycle Support in Adaptive PAISs

Adaptive PAISs extend traditional PAISs with the ability to deal with process

changes at different levels. This enables life cycle support as depicted in Fig. 4:

At build-time an initial representation of a business process is created either by

explicitly modeling the process (based on analysis results) or by discovering pro-

cess models through the mining of execution logs8(1). At run-time new process

instances can be derived from the predefined process schema (2). In general, pro-

cess instances are executed according to the process type schema they were derived

from, and (non-automated) activities are assigned to process participants to per-

form the respective activities (3). However, when exceptional situations occur during

run-time, process participants may deviate from the predefined schema (4). While

execution logs record information about the start and completion of activities as

well as their ordering, process changes are recorded in change logs (5). The analysis

of respective logs by a process engineer and process intelligence tools respectively

allows discovering malfunctions or bottlenecks.8,36 This information often results in

an evolution of the process schema (6). If desired, changes can be propagated to

running process instance (7).

Enter

order Make

appointme

Schema S‘:

++EC

Create Instances

Instance I1

Execution

Log

Process

participant

Arbeitsliste

Tätigkeit 1

Tätigkeit 2

Tätigkeit 3

Tätigkeit 4

Process

Execution

Process engineer /

Process administrator

Process

Monitoring

Change Log

I1(with instance-specific change)

Instance-

specific

Change

Exception:

Delete (I1, E)

CreateProcessSchema

Enter

order Make

appointme

Schema S:

EvolveProcessSchema

++EC

Change Propagation

Fig. 4. Process Life Cycle Support with Adaptive PAISs

3. Retention and Reuse of Instance Deviations

To deal with unexpected exceptions adaptive PAISs allow users to define instance

changes on-the-fly, e.g., to add, delete or move activities. In general, different meth-

ods for dealing with unanticipated exceptions exist. This includes structural modi-

fications of instance-specific process schemes as well as changes of their state (e.g.,

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 11

Redo activity or Rollback process). In this paper we focus on structural instance

changes. However, the ProCycle approach, in principle, is not restricted to structural

adaptations and can be extended to cover other exception handling procedures like

state changes as well (and ADEPT2 already provides basic support for this10,37).

Usually, instance changes are performed by end users requiring significant experi-

ence. This is particularly true when changes have to be defined from scratch. Change

complexity will become particularly evident if multiple adaptations are necessary

to handle an exception. For example, when deleting an activity during run-time,

(data-)dependent activities might have to be deleted as well (e.g., when deleting ac-

tivity Write Medical Report, the subsequent activity Validate Medical Report

is no longer required; or when inserting a new activity its inputs and outputs have

to be bound to process data elements10).

Adaptive PAISs like ADEPT210, WASA217, METEOR23, and CAKE213 support

the user in defining instance changes. In particular, changes can be expressed at a

high level of abstraction ensuring also their syntactical correctness. Furthermore, it

is checked whether the process instance is compliant with the new process schema

(cf. Section 2.2).10

Generally, user assistance going beyond syntax checks is needed to enable less

experienced users to perform instance changes as well. Instead of defining every

instance change from scratch existing knowledge about previously defined devia-

tions should be exploited, especially when similar deviations occur more than once.

However, pure syntactical information (i.e., information about the applied change

patterns), as provided by change logs in existing adaptive PAISs38, is not sufficient

to adequately support retrieval and reuse of corresponding change definitions later.

Additionally, information about the application context of the deviations is required

(like the deviation is due to an allergic reaction of the patient). Later this allows the

PAIS to present just those deviations to the user relevant in the given exceptional

situation. Regarding a cruciate rupture treatment process, for example, the context

information that the MRT was skipped for a patient with cardiac pacemaker is

useful for other physicians as well, particularly when treating other patients with

similar problems. Consequently, instance changes should be annotated with rele-

vant context information to foster their retrieval and reuse later on. Section 3.1

describes how process changes and their context can be captured. In Section 3.2 we

show how knowledge about instance changes can be retrieved, adapted and reused

when similar exceptional situations occur.

3.1. Memorizing Process Instance Deviations

ProCycle uses case-based reasoning (CBR) for memorizing process instance devia-

tions. Thereby, changes of individual process instances are annotated with relevant

context information (e.g., reasons for the deviation), which allows users to retrieve

and reuse this information when similar exceptional situations occur.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

12 B. Weber et al.

3.1.1. Representing Process Instance Deviations as Cases

We describe step-by-step how ProCycle represents process instance deviations as

cases to allow for their later retrieval, adaptation and reuse. In addition, we give

insights into our motivation and the criteria used for choosing this particular so-

lution. In its simplest form, in ProCycle, a case crepresents a process instance

deviation consisting of a textual problem description and a solution part. The tex-

tual problem description pdcbriefly describes the exceptional situation that made

the deviation necessary. The solution part ∆c, in turn, comprises the change oper-

ations which were applied to cope with the exception. In addition, for each case c

its reuse frequency freqcis maintained.

Definition 3.1. (Case) A case c is a tuple (pdc,∆c,freqc) where

•pdcis a textual problem descriptiona

•∆c=<op1, . . . , opk>, k ∈Nis the solution part of the case comprising a list

of change operations, which were sequentially applied to one or more process

instances in the given problem context

•freqcis the reuse frequency of the case

Example 3.1. (Case Representation) For our running example, Fig. 5 illus-

trates how an instance change deleting a process activity (i.e., Delete(I1, MRT))

can be represented as case and be annotated with context. The problem description

pdc1of this case c1briefly describes the reason for skipping the MRT in free text and

the solution part solc1contains the change operation needed to remove the MRT

from the process instance schema (i.e., Delete(SI, MRT)). In addition, freqc1= 1

expresses that case c1has been applied exactly once. To foster reuse and to allow

for the application of c1to other process instances as well, the parameter repre-

senting the instance schema to be modified, is generalized. For this, parameter I1

of operation Delete(I1, MRT) is replaced by a placeholder for an instance-specific

schema SI. Thus a case description absracts from a particular process instance.

ProCycle stores instance changes related to a process schema version Sas cases

in the case-base cbSassociated with S.

Definition 3.2. (Case–Base) Let Cbe the set of all cases representing instance

deviations in a PAIS. Then: A case–base cbS⊆ C corresponds to the set of all cases

associated with S(i.e., cases which were applied to at least one instance running on

S).

This simple representation with unstructured problem description (cf. Def. 3.1)

only allows for limited user guidance during case retrieval. It is thus up to the user

to formulate suitable queries. This works well for experienced users having a clear

idea of what they are searching for and therefore knowing which search terms to

aThe problem description might be free text or be based on a domain-specific ontology.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 13

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

Process Instance I1Delete(I1,MRT)

pdc1= The treatment of cruciate ruptures routinely includes a magnetic resonance

tomography (MRT), an X-ray and a sonography. However, for a particular

patient the MRT may have to be skipped as the respective patient has a

cardiac pacemaker.

solc1= <Delete(SI,MRT)>

freqc1= 1 Case c1

Fig. 5. Case Representation

use to achieve suitable results. Concerning inexperienced users, this lack of guid-

ance often results in either too broadly or too narrowly formulated queries. To

ease case retrieval for these users as well and to partially automate case retrieval,

ProCycle additionally captures application context information about instance de-

viations (e.g., the reasons for deviating from the original process schema version).

This context information can be used during case retrieval to filter out those cases

not relevant in the current exceptional situation. Regarding our running example, a

case skipping the MRT for a patient should be filtered out for all patients without

cardiac pacemaker.

3.1.2. Capturing Application Context of Instance Deviations

When capturing the application context of a process instance change, one major

challenge is to adequately represent this context information and to gather it on-the-

fly. The application context of process instance deviations usually cannot be defined

in a generic way, but is domain- or application-specific. ProCycle allows process

engineers to define an (application-specific) context model. The respective context

model defines what application context information might be relevant for reusing

deviations and thus should be collected. For example, patient information like age,

allergies and anamnesis should be part of a context model in the medical domain.

By contrast, a context model for the logistic industry might contain information

about customers, location of trucks, weather, and road conditions.

Definition 3.3. (Application Context Model) An application context model

Ctxt=(DataObjSet, AttrSet, Attrs) consists of a set of data objects DataObjSet,

a set of context attributes AttrSet, and a function Attrs: DataObjSet 7→ AttrSet.

The latter assigns to each data object d∈DataObjSet a set of context attributes

Attrs(d)⊆AttrSet. Each context attribute attr = (aName, aT ype, min, max)∈

Attrs has a name aName, a data type aT ype, a minimal occurrence min, and a

maximum occurrence max. The data type of a context attribute either is atomic

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

14 B. Weber et al.

(e.g., Boolean, Integer, String or Time) or complex (i.e., refers to already defined

data objects).

Example 3.2. (Application Context Model) Figure 6 shows a simplified ex-

ample of an application context model in the medical domain. It consists of the data

objects Diagnosis,Patient,ProblemList, and Therapy. Attributes problemList,

diagnoses and therapies are examples for context attributes with complex type

as they are composed of other data objects; age,weight and hasPaceMaker con-

stitute attributes with simple type. Attributes with a minimum occurrence greater

than one constitute collections (e.g., therapies and diagnoses).

Fig. 6. Sample Application Context Model

Regarding a particular instance deviation, usually only a subset of the data

objects and attributes from the application context model is relevant to describe

the reasons for this deviation. It is therefore inefficient and also not necessary to

memorize the full context model in the case–base.

Example 3.3. (Relevant Application Context) The application context

model from Fig. 6 describes a patient record including the complete patient history.

The decision to skip the MRT during the cruciate rupture treatment of a particular

patient, however, only has become necessary because the respective patient has a

cardiac pacemaker.

To effectively support users in reusing similar cases and to avoid storage of ir-

relevant context information, knowledge about the exact reasons of a deviation is

required. Automated discovery of relevant application context attributes using data

mining techniques (i.e., the analysis of historical data using statistics) is not appli-

cable in the given scenario. To statistically identify correlations between deviations

and context attributes, a large set of deviations is needed and deviations have to

occur frequently. As ProCycle wants to support users from the first deviation on-

wards, it cannot rely on a long learning process. In addition, user support should

be offered for rarely occurring deviations as well.

To overcome this problem, whenever an exception occurs, ProCycle encour-

ages users to state which parts of the context model are relevant for their decision

to deviate from the predefined process schema. Note that in many domains (e.g.,

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 15

healthcare5,39 or automotive engineering4) users have to give reasons when devi-

ating from the standard procedure anyway (e.g., to fulfill the legal obligation for

documentation in the medical domain39). Following this approach the reasons for

the change can be immediately captured. This allows for the reuse of changes al-

ready after the first case has been added to the system. In addition, memorizing

the whole process context as part of the case is not required, but the application

context of the deviation can be narrowed to the relevant context attributes. Com-

plementary to our approach a snapshot of the entire context model (or a predefined

part of it) could be automatically stored in the change log of the adaptive PAIS

whenever a process instance deviation is performed.

ProCycle adopts and extends the conversational case-based reasoning approach

of Ref. 40, and allows users to describe the reasons for a deviation in an intuitive

way as question-answer pairs qaSetc. Thereby each question-answer pair (q, a) char-

acterizes one particular condition making the deviation necessary. Question-answer

pairs are also used during case retrieval to assist users in finding similar cases (cf.

Section 3.2). The question qof such a pair (q, a) corresponds to free text and the

answer ais mapped to an answer expression, which can be automatically evaluated

by the PAIS. ProCycle internally uses OCL (Object Constraint Language) as lan-

guage for representing answer expressions.41 Note that end-users are not expected

to enter these expressions by hand, but are assisted in describing the reasons for the

deviation (cf. Section 4.1). For example, domain-specific user interfaces can be built

on top of the OCL representation. As an example consider the medical domain.5

Instead of requiring a phyisician to formulate the answer expression a form can be

presented to him with a list of symptoms: he then just has to select those symptoms

relevant for the deviation.

Example 3.4. (Question-Answer Pair) Consider Example 3.1 where a physi-

cian decides to skip the MRT activity for a particular patient and assume that the

decision to perform this deviation is triggered by the fact that the treated patient

has a cardiac pacemaker. To record the reasons for this instance deviation the physi-

cian enters the question Does the patient have a cardiac pacemaker? as free

text as well as an answer expression which either evaluates to true or falseb. For

example, Patient.problemList.hasPacemaker = ’Yes’ constitutes such answer

expression. It uses the hasPacemaker attribute of data object Patient from the

application context model shown in Fig. 6.

To include context information in the representation of a case, Definition 3.1

has to be extended by adding question-answer pairs.

Definition 3.4. (Case - Extended With Question-Answer Pairs) A case

c is a tuple (pdc,∆c,qaSetc,freqc) where

bThe entering of question-answer pairs can be interactively supported by a respective user interface

(cf. Section 4).

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

16 B. Weber et al.

•pdc,∆cand freqcare defined as in Def. 3.1

•qaSetc={(q1, a1), ..., (qn, an)},n∈Ndenotes a set of question-answer pairs

depicting the application context of the case (with qi∈ Q and ai∈ A where

Q/Adenotes the set of all possible quesions/answers.

Example 3.5. (Representing Deviations as Cases) Fig. 7 shows how case

c1from Fig. 5 can be enriched with application context information. In addition to

the textual problem description pdcand the solution part solc, case c1contains a

question-answer pair describing the application context of the applied change.

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

Process Instance I1Delete(I1,MRT)

pdc1= The treatment of cruciate ruptures routinely includes a magnetic resonance

tomography (MRT), an X-ray and a sonography. However, for a particular

patient the MRT may have to be skipped as the respective patient has a

cardiac pacemaker.

solc1= <Delete(SI,MRT)>

qaSetc1= {(Does the patient have a cardiac pacemaker?,

patient.problemList.hasPacemaker = ‘Yes‘)}

freqc1= 1

Case c1

Fig. 7. Annotating Instance-Specific Changes with Application Context

3.1.3. Going beyond Predefined Context Attributes

So far, we are able to annotate instance deviations with application context informa-

tion and to make statements about which context attributes are relevant depending

on the concrete deviation. In addition to the context attributes specified in the

context model there might be other criteria not (yet) known to the system, but

nevertheless contributing to the decision to deviate from the predefined process. In

such a situation the user should be able to record these criteria as reasons for the

deviation.

Example 3.6. (Additional Application Context) Assume that the planned

cruciate ligament operation for patient Miller has to be postponed – an emergency

surgery has to be performed for patient Smith and therefore Miller has to be trans-

ferred back to the ward in order to wait for his intervention. Under such circum-

stances it is unlikely that the reasons for the deviation can be captured automat-

ically. However, reuse of such cases is desirable as well and should therefore be

supported.

In such scenarios, formal answer expressions are not applicable as the reasons for

the deviation are outside the scope of the pre-specified context model. By contrast,

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 17

they must be manually entered by users. Instead of mapping answers to logical ex-

pressions on attributes from the application context model, free text can be used for

both the questions and the answers, thus allowing for the specification of arbitrary

reasons (even if they are not (yet) captured in the PAIS). Such free text answer

expressions can be further utilized to evolve the application context model and to

enable automation of the retrieval of previous instance deviations (cf. Section 4.3).

In particular, if cases with free text answers are frequently reused, extending the

application context model often will make sense.

3.2. Retrieving and Adapting Similar Process Instance Deviations

Once instance changes and their application context (i.e., reasons for the process

change) are stored by the PAIS, they can be retrieved, adapted and reused when

similar exceptional situations occur and thus similar deviations become necessary.

To effectively support users in handling exceptions only such cases should be pre-

sented to them which are relevant to resolve the given exception. For this purpose

the cases which occurred in an application context similar to the current exceptional

situation must be determined. In addition to the application context the current

state of the process instance for which a change should be performed (denoted as

control context) has to be taken into account as well since it restricts the appli-

cability of the adaptations defined by a particular case.10,12 We first describe how

similarity in respect to application context is calculated in ProCycle. We then show

how the instance status (i.e., control context) is considered to retrieve relecant cases.

Finally, we illustrate how knowledge about previous instance change can be reused.

3.2.1. Application Context Similarity

Application context similarity measures how well the question-answer pairs of a

stored case c(cf. Def. 3.4) match with query qu representing the application context

of the problem situation the user is confronted with. ProCycle uses conversational

case-based reasoning to assist users in formulating this query in an interactive and

incremental way. Fig. 12 gives an overview of the case retrieval process as supported

by ProCycle. When an exceptional situation occurs during execution of a process

instance I, case retrieval is initiated (1). ProCycle then creates a list of questions

and possible answers to guide the user in formulating the query capturing the excep-

tional situation (2). As next step, structured answer expressions are automatically

evaluated (3) and the answered questions are added to the query (4). Similarity is

then calculated and cases are ranked by decreasing similarity (5). The list of ranked

cases as well as the list of questions with possible answers is displayed to users (6),

who then can answer any of the not yet answered questions (7). This leads to a

query expansion and a re-ranking of the cases (5+6).

In the following the retrieval process is described step-by-step using an exam-

ple case–base cbS={c1,c2}(cf. Fig. 9a). After having initiated case retrieval an

empty query qu is created. To guide the user in incrementally expanding qu for cbS,

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

18 B. Weber et al.

Show Ranked Cases +

List of Question with Possible Answers

Answer Questions with

Answer Expressions

Process

participant

Arbeitsliste

Tätigkeit 1

Tätigkeit 2

Tätigkeit 3

Tätigkeit 4

Exception for

Instance I →

Create List of Questions

with Possible Answers

Calculate Similarity and

Rank Cases

Add answered questions to

query qu

cInitiate Case Retrieval

Answer Question

Fig. 8. Retrieving Similar Cases in ProCycle

ProCycle calculates the set of possible questions qSet(cbS). In addition, for each

question qthe set of all possible answers aSet(q) is determined. This also includes

an entry OTHERANSWER, which can be selected if none of the answer options applies.

Fig. 9b shows the list of questions with possible answers, as it can be created for

cbS. In total, this list comprises three questions. For example, question ’Does the

patient have fluid in the knee?’ has two possible answers: ’A significant

amount’ or OTHERANSWER (if the first answer ’A significant amount’ does not

apply).

qaSetc1= {(Does the patient have a

cardiac pacemaker?,

Patient.problemList.hasPacemaker

= 'Yes')}

{‚Yes‘, OTHERANSWER}

{‚A significant amount‘, OTHERANSWER}

{Patient.problemList.hasPacemaker = ‚Yes‘, OTHERANSWER}

Possible Answers

List of Questions with Possible Answers

Does the patient have an acute effusion of the knee?

Does the patient have fluid in the knee?

Does the patient have a cardiac pacemaker?

Question

qaSetc2= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Case c1Case c2

Query qu

OTHERANSWERDoes the patient have a cardiac pacemaker?

Given AnswerQuestion

Query qu‘

‚A significant amount‘Does the patient have fluid in the knee?

OTHERANSWER

Does the patient have a cardiac pacemaker?

Given AnswerQuestion

50%

Appl. Context Similarity

List of Retrieved Cases for Query qu

Case

75%

Appl. Context Similarity

List of Retrieved Cases for Query qu‘

Case

Fig. 9. List of Questions

As a next step ProCyle automatically evaluates all questions with associated

answer expression. It then adds the derived question-answer pairs (qi, ai) to query

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 19

qu. For example, as illustrated in Fig. 9c question q1=’Does the patient have

a cardiac pacemaker?’ has been evaluated to false (i.e., a1=OTHERANSWER) re-

sulting in the intermediate query qu ={(q1,a1)}. After this step, query qu is used

to determine cases c∈cbSwhose application context is most similar to the current

one represented by qu. To calculate application context similarity between query

qu and case c, the question-answer pairs in qaSetcand qu are matched.

Definition 3.5. (Application Context Similarity) Let c∈cbSbe a case and

qu be a query representing the present application context. Then: The application

context similarity sim(qu, c)between qu and ccorresponds to the number of ques-

tions with same answers same(qu, qaSetc)minus the number of questions with dif-

ferent answers diff(qu, qaSetc) divided by the total number of questions in the case.

To obtain similarity values between 0 and 1 we further normalize sim(qu, c)). For-

mally,

sim(qu, c) = 1

2∗(same(qu, qaSetc)−diff(qu, qaSetc)

|qaSetc|+ 1)

Taking query qu ={(q1,a1)}, for c1we obtain sim(c1, qu) = 0 as the question-

answer pair in case c1does not match with qu (cf. Fig. 9d). Regarding c2we obtain

sim(c2, qu) = 0.5, because none of the two questions of c2has been answered.

In summary, ProCycle displays the list of ranked cases as well as the list of

questions with possible answers to users, who then can answer any of the not yet

considered questions to further refine the query. Whenever an additional question

is answered or an answer is modified similarity is recalculated. Cases are displayed

to the user ordered by decreasing similarity (cf. Fig. 9d+f).

Consider the above example and assume that the user additionally answers

question q2=’Does the patient have fluid in the knee?’ with a2=’A

significant amount’. This results in new query qu0={(q1,a1), (q2,a2)}(cf.

Fig. 9e). Considering query qu0for c1we still obtain sim(c1, qu) = 0. However, for

case c2similarity sim(c2, qu) increases to 0.75 (cf. Fig. 9f).

3.2.2. Control Context

In addition to application context, ProCycle considers the state of a process instance

when retrieving similar cases. Generally, the state of a process instance restricts the

applicability of the adaptations defined by the solution part of a particular case.10,12

Example 3.7. (Applicability of a Case Depending on Control Context)

Consider case c1in Fig. 7, which skips activity MRT in a treatment process. Further,

consider further process instances I1,I2and I3from Fig. 1b as well as their execution

traces. While c1is applicable to I1and I2, it is not relevant for I3. Regarding I3

the MRT activity is completed and can therefore be not skipped anymore.24

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

20 B. Weber et al.

To determine whether a case cis applicable to a given process instance Ior not

we introduce the notion of case compliance.

Definition 3.6. (Case Compliance) Let c = (pdc,∆c,qaSetc,freqc) be a

case with solution part ∆c=<op1, .., opn>,n∈N. Then: Process instance Iwith

schema SIand execution trace σIis denoted as case compliant with ciff

(1) SI[∆c> SI0, i.e., ∆ccan be correctly applied to instance schema SIand the

application of ∆cto SIresults in instance schema SI0=SI+∆c(where change

operations are applied sequentially according to their order in ∆c).

(2) Execution trace σI(cmp. Def. 2.1) is producible on SI0as well.c

Example 3.8. (Case Compliance) Consider case c1from Fig. 7 with solution

part ∆c1=<Delete(SI, MRT)>. Let SIbe the schema according to which in-

stances I1,I2and I3are executed (cf. Fig. 10a) and assume that ∆c1is applied to

SI, resulting in new schema version SI0(cf. Fig. 10b). When considering the exe-

cution traces of instances I1,I2and I3(cf. Fig. 10c), I1and I2are case compliant

with c1as their traces are producible on SI0. Instance I3, in turn, does not comply

with case c1since its trace σ3cannot be produced on SI0.

Trace of instance I1: σ1= < „Patient Admission“, „Anamnesis & Clinical Examination“, „X-ray“>

Trace of instance I2: σ2= < „Patient Admission“>

Trace of instance I3: σ3= < „Patient Admission“, „Anamnesis & Clinical Examination“, „MRT“, „X-ray“, „Sonography“>

SI‘

SI[Δc1>SI‘with Δc1=

<Delete(SI,MRT)>

σ1is producible on SI‘

σ2is producible on SI‘

σ3is not producible on SI‘

Execution Traces:

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

XOR-Split1 XOR-Join1

Fig. 10. Case Compliance

Case compliance is a necessary prerequisite for a case to be directly applicable

to the respective process instance. It guarantees that no inconsistencies or errors

are introduced when applying the case (i.e., the operations of its solution part) to

this instance. As the following example shows, however, it is not sufficient to only

consider case compliance when retrieving relevant cases.

cThis notion could be relaxed in connection with loops. We omit a discussion of loop tolerant

adaptations in this paper and refer to Ref. 24 instead.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 21

Example 3.9. (Effect of Changes) Consider instance schema SIas depicted

in Fig. 11a and assume that the solution part of case c2shall be applied to SI.

The respective case inserts two activities Follow-Up Examination and Puncture

after activity Non Operative Therapy and before XOR-Join1, resulting in schema

SI0(cf. Fig. 11b). Further, consider the execution trace of instance Ias depicted

in Fig. 11c. As the events logged in this trace are re-producible on SI0,Iis case

compliant with c2. This guarantees that the application of c2to Idoes not introduce

any inconsistency. However, applying c2to Idoes not have any effect on instance

execution as the branch with activity Non Operative Therapy has been skipped

for Ibefore (and thus the newly inserted activities are skipped as well due to a

deadpath elimination).

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

Execution Trace of Instance I:

σ= < „Patient Admission“, „Anamnesis & Clinical Examination“, „MRT“, „X-ray“, „Sonography“>

SI‘

Change Δc2 remains without any effects for I

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

Follow-up Examination Puncture

XOR-Split1 XOR-Join1

Δc2 = <Insert(SI, Follow-Up Examination, Non Operative Therapy, XOR-Join1),

Insert(SI, Puncture, Follow-Up Examination, XOR-Join1)>

Fig. 11. Case Compliance and Changes Without Effects

Generally, changes within skipped parts of an instance schema have no effect on

instance execution except the instance loops back later. In the latter case the change

might affect execution of future loop iterations. To indicate whether a change has

an effect on a given instance we introduce function hasEffect(c, I).

Definition 3.7. (Effect of a Change) Let c∈cbSbe a case with solution part

∆cand I∈InstSbe a process instance on S. Then:

hasEffect(c, I) =











1if ∆chas an effect on the behavior of I

0.5if ∆cdoes not have an immediate effect on the be-

havior of I but might have one when I loops back

0if ∆cdoes not have any effect on the behavior of I

During case retrieval it makes sense to exclude cases, which neither would have

an effect on I(i.e., hasEffect(c, I) = 0) nor with whom Iis case compliant. How-

ever, in certain situations a case ccan be adjusted such that it becomes applicable

to I. We therefore introduce function isAdjustable(c, I) to indicate whether case c

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

22 B. Weber et al.

can be adjusted in such a way that Ibecomes case compliant with cand chas an

effect on I.

Definition 3.8. (Case Adjustability) Let c∈cbSbe a case with solution part

∆cand I∈InstSbe a process instance. Then:

isAdjustable(c, I) = 





1if ccan be adjusted such that chas an effect on I

(i.e., hasEffect(c,I)>0) and I becomes case compliant

0otherwise

Whether a case ccan be adjusted or not also highly depends on the change

patterns used in ∆c. For change patterns Delete Process Fragment,Replace

Process Fragment and Swap Process Fragment no adjustment is possible. This

applies for situations where case compliance is not met as well as for situations

in which an instance change does not have any effect. By contrast, regarding pat-

terns Insert Process Fragment and Move Process Fragment the solution part

of a case can be adjusted by changing the corresponding parameterization (e.g.,

adjusting the position at which the process fragment shall be (re-)inserted).

Example 3.10. (Case Adjustability) Consider instance schema SIas depicted

in Fig. 11a and assume that the solution part of case c2shall be applied to SI.

Inserting activities Follow-Up Examination and Puncture after Non Operative

Therapy and before XOR-Join1 would be without any effect on I1in its current

state. However, in the given example the parameterization of the change operations

can be adjusted in such a way that c2becomes applicable. For example, activities

Follow-Up Examination and Puncture can be inserted after activity Operative

Treatment. We obtain isAdjustable(c2, I1) = 1.

By contrast, for case c1and instance I3from Fig. 10c no adjustment is possible.

The MRT activity has already been completed for I3and cannot be skipped anymore,

i.e., c1cannot be adjusted in such a way that I3becomes case compliant with c1

(i.e., isAdjustable(c2, I3) = 0).

3.2.3. Retrieving Similar Cases

To determine those cases most relevant in a given exceptional situation all cases

are ranked by decreasing application context similarity and the top nranked cases

are displayed to the user (cf. Fig. 12). To better support the user during case reuse

the list of similar cases is further enriched with information regarding the control

context of the process instance Ito be modified. Cases which cannot be applied

directly (i.e., cases not compliant with Ior having no effect), but which can be

adjusted are highlighted (together with the specific change operations that need to

be adjusted). Finally, cases which cannot be adjusted are excluded from the list of

similar cases.

Example 3.11. (Case Retrieval) Consider case-base cbS={c1, c2}, process

instance I, and query qu as depicted in Fig. 12. For case c1we obtain sim(c1, qu) =

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 23

Case c1

qaSetc1= {(Does the patient have a

cardiac pacemaker?,

Patient.problemList.hasPacemaker

= 'Yes')}

Δc1= <Delete(SI,MRT)>

Case c2

qaSetc2 = {(Does the patient have fluid in the knee?, 'A

significant amount'), (Does the patient have an

acute effusion of the knee?, 'Yes')}

Δc2= < Insert(SI, Follow-Up Examination,

Non Operative Therapy, XOR-Join1),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join1>

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++xx

Process Instance I1

Query qu

‘A significant amount‘Does the patient have fluid in the knee?

OTHERANSWER

Does the patient have a cardiac pacemaker?

Given AnswerQuestion

c1is not case compliant and not adjustable

c2 does not have any effect, but is adjustable

75%

Appl. Context Similarity

List of Retrieved Cases

Case

Fig. 12. Similar Cases Displayed to the User

0. Furthermore, instance Iis not case compliant with c1. As c1cannot be adjusted, it

is eliminated from the list of similar cases. For case c2we obtain sim(c2, qu)=0.75.

As c2does not have any effect on Iand needs to be adjusted, the respective case is

highlighted for the user.

3.2.4. Case Reuse

If instance Iis case compliant with case c, the user may want to reuse cdirectly. The

actions specified in the solution part of the case are then forwarded to and carried

out by the PAIS. For this, in each change operation the placeholder for the instance-

specific schema SIneeds to be replaced by process instance I(cf. Section 3.1.2). As

the reuse of a case necessitates case compliance, correctness and consistency of the

instance after change application can be ensured by the PAIS.10 Finally, case reuse

leads to an increase of the case reuse counter freqcby 1.

Example 3.12. (Case Reuse) Assume that case c2from Fig. 9 shall be applied

to instance I. As Iis case compliant with c2, no case adjustment is needed and c2

can be applied directly.

If the instance to be modified is not compliant with cor this case does not have

any effect on Iit can be adjusted prior to its reuse. For this, a copy of the case is

created and modified. Afterwards the newly created case is added to the case–base.

4. Ensuring Quality of Cases

So far, we have described how instance changes can be represented, retrieved and

reused in ProCycle. To effectively provide support for reusing cases as well as for

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

24 B. Weber et al.

deriving process (model) optimizations based on them, the quality of the data main-

tained in the case-base is crucial. Poor PAIS performance, like long dialogues and

inaccurate case data, can limit user acceptance significantly.26 In ProCycle, cases

are added by end users and not by experienced process engineers. In addition, case-

bases evolve over time. New cases may be added to it when exceptional situations

occur, which have never been dealt with before. To ensure accuracy and to improve

overall performance, maintenance is becoming crucial when the case-base grows.

Fig. 13 summarizes characteristic quality problems that arise in this context and

shows how ProCycle deals with them.

Quality Issue Support by ProCycle

Q1: Inexperienced users have difficulties in entering cases Provide user assistance when entering cases

Q2: Case of poor quality are added to the case-base Evaluate performance of cases

Q3: Free text answer expressions require user interaction Support refactoring for question-answer pairs

Q4: Inter-case dependencies between cases exist Discover inter-case dependencies and merge

cases

Q5: Case-base contains similar cases which just differ regarding

the parameterization of their change operations (i.e., the position) Generalize cases

Fig. 13. Quality Issues and their Support in ProCycle

Section 4.1 describes how users are assisted when entering cases. To avoid reuse

of low quality cases, case performance is evaluated (cf. Section 4.2). Section 4.3

introduces refactoring strategies supported by ProCycle to foster full automation

of the case retrieval process. The discovery of inter-dependent cases is described

in Section 4.4; Section 4.5 deals with their merging. Finally, Section 4.6 proposes

generalization of cases with similar solution part.

4.1. User Assistance When Entering Cases

To assist users in defining question-answer pairs and to ensure data quality (Quality

Issue Q1) user guidance is provided (e.g., by avoiding spelling errors or the entering

of redundant data).

In the current version of ProCycle, question-answer pairs can be entered either

by selecting the question from a list of previously defined questions (i.e., reusing

questions from existing cases) or, if there is no suitable question in the system,

by defining a new one and by giving the appropriate answer. Through displaying

already existing question-answer pairs users are encouraged to reuse them to avoid

redundancies. In addition, it is recommended that engineers review the case-base

on a regular basis and refactor it if needed (e.g., by combining two question-answer

pairs with the same semantics to a single pair).

To further improve reuse of question-answer pairs ontologies can be integrated.

In many domains (e.g., healthcare) domain-specific vocabularies (e.g., ICD-9 for

diagnoses42) exist and are widely used. We omit a discussion here since ontology

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 25

issues are currently outside the scope of ProCycle.

The entering of answer expressions is guided by the system. This ensures that

users can only enter syntactically correct answers. In particular, user assistance

for selecting context attributes is provided. In addition, depending on the chosen

context attribute suitable operators are proposed to users.

4.2. Evaluating Case Performance

The accuracy of cases is crucial for overall PAIS performance, and consequently

for the trust users have in the PAIS (Quality Issue Q2). When cases are added by

end users, evaluation mechanisms are needed to ensure case-base quality. Similar

to Cheetham and Price43, we propose to augment the conversational case-based

reasoning (CCBR) component with the ability to determine the confidence in the

accuracy of individual solutions.26 ProCycle uses the concept of reputation to in-

dicate how successfully an instance change, represented by a case, was reused in

the past; i.e., how much it contributed to the performance of the case-base, thus

indicating the degree of confidence regarding the accuracy of the respective case.

To be able to evaluate case performance for each case cProCycle maintains a

history histc. Whenever cis applied to a process instance an entry eis added to the

case history. Each history entry erefers to the process instance to which the case

was applied. In addition, it contains a feedback score fScoree, which either can be

highly positive (2), positive (1), neutral (0), negative (-1), or highly negative (-2),

reflecting the performance of the respective case. Optionally, a comment comecan

be added to provide feedback on the performance of c.

Definition 4.1. (Case History) Let cbSbe a case-base and let further c∈cbS

be a case. Then: Case history histc=<e1, .., en>with n = freqccomprises a list

of history entries eifor case cin the order they were created. A history entry eiis

a tuple ei=(I, fScoreei, comei)where

•Idenotes the process instance to which cwas applied

•fScoreei∈ {−2,−1,0,1,2}corresponds to the feedback score

•comeiis a free text comment about the performance of case c

The overall reputation rScorecof case ccorresponds to the average feedback

score of the history entries from histc. While a high reputation score of a case is

an indicator for its semantical correctness, negative feedback probably results from

problems after performing the respective instance change. Negative feedback leads

to immediate notification of the process engineer who may deactivate the case to

prevent its further reuse. The case itself remains in the system to allow for learning

from failures and to ensure traceability. Definition 4.2 extends Definition 3.4 with

case history histcand reputation score rScorec.

Definition 4.2. (Case With History) A case c is a tuple (pdc,∆c,qaSetc,

freqc,histc,rScorec) where

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

26 B. Weber et al.

•pdc,∆c,qaSetcand freqcare defined as in Def. 3.1

•histc=<e1, .., en>is the history associated with c(cf. Def. 4.1)

•rScorec=Pn

i=1 fScoreei

|histc|denotes the reputation score. It is calculated as the

average feedback score in histc.

4.3. Refactoring Question-Answer Pairs

Question-answer pairs describe the reasons making a deviation at the process in-

stance level necessary. A question constitutes free text, an answer can either be a

structured expression or free text. In general, answer expressions should be used

instead of free text to increase problem solving efficiency. While answer expressions

can be automatically evaluated by the system (i.e., answer values are automati-

cally calculated from existing data), free text answers have to be provided by the

user (Quality Issue Q3). The ability to also give free text answers is crucial for

the success of the conversational case-based reasoning component since it is not

always possible to use structured answer expressions. In the following we describe

three scenarios where free text question-answer pairs are entered into the system.

In addition, maintenance policies for refactoring free text answers to formal answer

expressions are sketched (cf. Fig. 14).

Problem Maintenance Policy

Scenario 1: End user is not knowledgeable enough

to specify formal answer expressions Notify process engineer when answer frequency exceeds a predefined

threshold and support him in refactoring the free text answer to a

formal answer expression.

Scenario 2: End user is unaware of the application

context Notify process engineer when answer frequency exceeds a predefined

threshold and support him in refactoring the free text answer to a

formal answer expression.

Scenario 3: Needed context attributes are not

available within the system Notify process engineer when answer frequency exceeds a predefined

threshold and support him in refactoring the free text answer to a

formal answer expression and to extend the context model.

Fig. 14. Maintenance Policies for Question-Answer Pairs

Scenario 1 (Inexperienced User): The end user applies ProCycle to handle an

exception, but is not knowledgeable enough to specify formal answer expressions.

As the exception has to be resolved quickly the user enters free text question-answer

pairs to capture the reasons for the deviation, and he applies the case immediately.

To increase problem solving efficiency the question-answer pair will be refactored

to a formal answer expression later on, if feasible. Thus, a notification is sent to the

process engineer to accomplish this refactoring when a particular question-answer

pair is frequently applied by users in their queries.

Scenario 2 (Unawareness of Application Context): In this scenario the end user

is unaware of the application context and cannot find suitable context attributes

for specifying answer expressions even though they are available in the system.

Therefore, the user enters free text to capture the reasons for the deviation. In this

scenario, the process engineer is not informed immediately, but only when the re-

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 27

spective question-answer pair has been answered frequently enough, thus exceeding

a predefined threshold value. The process engineer can then refactor the free text

to an equivalent answer expression, which will be used during case retrieval instead

of the free text.

Scenario 3 (Missing Context Attributes): In certain situations no suitable context

attributes are available within the system to describe the concrete instance devi-

ation. In this scenario, the user must specify the question-answer pair using free

text. Like Scenario 2 the process engineer is informed when the question-answer

pair has been answered frequently enough. He can then decide whether to extend

the application context (cf. Section 3.1.2) by adding the required context attribute

to the context model.

4.4. Discovering Inter-dependent Cases

ProCycle does not only provide support for refactoring question-answer pairs, but

also for maintaining cases. In particular, it supports the discovery of correlations

between cases based on respective case histories (Quality Issue Q4).

Example 4.1. (Inter-Dependent Changes) Assume that for a particular

treatment process the MRT has to be skipped for a patient with cardiac pace-

maker and another imaging technique is applied instead, i.e., one activity is deleted

and another one inserted.

Since ad-hoc changes are applied in exceptional situations, we cannot expect that

such semantically related adaptations are always conducted at the same time; i.e.,

they might be not added as single case to the PAIS. This will particularly happen

if end users are inexperienced and do not consider all consequences of a change.

Further, if change dependencies are not known when adding a case, semantically

related adaptations will be stored in different cases as well.

To allow for better user assistance, ProCycle collects information about inter-

case dependencies. For each case cthe set of dependent cases interDepcis provided.

Whenever a user selects a case cto be applied to a process instance Iand Ihas not

yet been changed (i.e., |∆I|= 0), ProCycle presents her all cases from interDepc.

The user can then decide to additionally apply any of these cases, if they are relevant

for her current situation. If instance Ihas already been changed (i.e., |∆I|>0),

ProCycle does not only present the cases from interDepcto the user, but also

those cases cinot contained in interDepc, but previously been applied to I(i.e,

ci∈∆I). The user can then tag any of the cases ci∈∆Ias inter-dependent case.

As a consequence ciis added to interDepc.

4.5. Merging Inter-Dependent Cases

Two inter-dependent cases c1and c2can be merged into a single case cif they always

co-occur. For a given set of process instances the co-occurrence rate CoRate(c2|c1)

denotes the relative frequency of the application of case c2on condition that case

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

28 B. Weber et al.

c1has been applied as well. Consequently, two cases c1and c2are merged if

CoRate(c1|c2) = 1 and CoRate(c2|c1) = 1 hold. In this situation a new case is

added to the case-base and the original cases c1and c2are deactivatedd, i.e., a

refactoring of the case-base takes place. Problem descriptions as well as question-

answer pairs related to the two cases are manually merged by the process engineer,

who has the domain-specific knowledge needed for this; the corresponding solution

parts, in turn, can be automatically merged. In addition, different optimizations

for purging the resulting operation sets in case of redundancies can be applied.44

Finally, as both cases c1and c2always co-occur we can set freqcand histcaccord-

ingly.

Definition 4.3. (Conditional Co-Occurrence Rate) Let c1,c2∈cbSbe two

cases and let Instcdenote the set of all process instances I∈InstSto which cwas

applied. Then: The conditional co-occurence rate CoRate(c2|c1)denotes the relative

frequency of c2on condition that c1has been applied as well. Formally:

CoRate(c2|c1) = |Instc2∩Instc1|

|Instc1|

4.6. Generalizing Cases

As described in Section 3.2 cases are not always directly applicable, but might

have to be adjusted. Over time this can lead to similar cases with slightly different

solution parts, i.e., same list of change operations, but different parameterization

(Quality Issue Q5). To speed up case retrieval and to ensure maintainability of the

case–base such cases need to be generalized. In ProCycle, the process engineer is

notified when an existing case cis adjusted and memorized as new case c0. He then

can decide to create a generalized version cg. When generalizing two cases cand

c0the solution part of the generalized case ∆cgneeds to cover both the changes

defined by cand c0. In addition, the question-answer pairs of both cases need to

be merged. The reuse frequency of the generalized case is calculated as the sum of

freqcand freqc0. Finally, the history histcgis determined as the union of histcand

histc0. To ensure traceability cases cand c0are not deleted, but can be deactivated

by the process engineer.

Example 4.2. (Generalizing Cases) Consider schema SIand the solution

parts of cases c2and c3as depicted in Fig. 15. Both cases insert activities Follow-Up

Examination and Puncture, but at different positions. The process engineer creates

a generalized case cg, which covers the changes defined by c2as well as by c3. For ex-

ample, cgallows to insert Follow-Up Examination and Puncture after Anamnesis

& Clinical Examination and before Discharge & Documentation. Case cgcov-

ers the changes of c2and c3, but also allows for some additional behaviour by

dFor traceability reasons respective cases are not deleted, but only deactivated.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 29

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

XOR-Split2 XOR-Join2

XOR-Split1 XOR-Join1

Case c2Case c3

Merge

qaSetc2= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc2= <Insert(SI, Follow-Up Examination,

Non Operative Therapy, XOR-Join1),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join1>

freqc2 = 41

qaSetc3= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc3= <Insert(SI, Follow-Up Examination,

Non Operative Therapy1, XOR-Join2),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join2>

freqc3 = 35

qaSetcg= {(Does the patient have fluid in the knee?, 'A significant amount'),

(Does the patient have an acute effusion of the knee?, 'Yes')}

Δcg= <Insert(SI, Follow-Up Examination, Anamnesis & Clinical Examination,

Discharge & Documentation),

Insert(SI, Puncture, Follow-Up Examination, Discharge & Documentation}

freqcg= 76 Case cg

Fig. 15. Generalizing Similar Cases

inserting the activities in parallel to a larger schema region when compared to c2

and c3. The question-answer pairs of cgare the same than for c2and c3. As reuse

frequency we obtain freqcg= 76.

5. Process Learning and Process Evolution

In ProCycle, the knowledge about previous instance changes is not only used for as-

sisting users in exceptional situations, but also for process improvement. When same

or similar process instance changes occur frequently, this indicates a gap between

the used process schema and the real-world business process. This misalignment

often stems from errors in the design of the process schema or can be the result

of changing requirements. To discover such discrepancies, ProCycle continuously

monitors deviations between process schema and actual instance enactment. When

same or similar deviations occur frequently the process engineer is notified about

the potential need to evolve the process schema. He can then perform a process

type change by pulling up instance changes to the type level and migrating already

running instances to the new schema version.

5.1. Discovery of Process Type Changes

To derive suggestions for process type changes from a collection of process instances

and their associated changes, we need to monitor case reuse. Let Sbe a process

schema and InstS={I1, . . . , In},n∈Nbe the set of process instances created

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

30 B. Weber et al.

from S. Let further cbSbe the set of all cases capplied to at least one instance

I∈InstS.

A naive solution would be to suggest a process type change exactly when for a

particular case c∈cbSits reuse frequency freqcexceeds the predefined threshold

value thr:

freqc

|InstS|≥thr

As detailed in the following solely monitoring the reuse frequency for each case

c∈cbSis not sufficient. For example, cbSmight contain distinct cases with same

solution parts, but different question-answer pairs, i.e., the same instance change

was applied in different context. As another example consider cases, which do not

have the same, but similar solution parts, i.e., overlapping change operations or

same change operations with different parameterization. For example, in Fig. 16

cases c2and c3comprise the same list of change operations, which just differ in

their parameterization. To better support process engineers in deriving process type

changes ProCyle does not only monitor case reuse, but also the reuse frequency of

single change operations. Thereby, change operations, which just differ in their

parameterization are combined to abstract change operations abstOp. An abstract

change operation only consists of an operation type and the activity effected by the

change, while the insertion or move positions are neglected.

Case c3freqc3= 35

qaSetc3= {(Does the patient have fluid in the

knee?, 'A significant amount'),

Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc3= <Insert(SI, Follow-Up Examination,

Non Operative Therapy1, XOR-Join2),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join2>

Case c1freqc1 = 51

qaSetc1= {(Does the patient have a cardiac

pacemaker?,

Patient.problemList.hasPacemaker

= 'Yes')}

Δc1= <Delete(SI,MRT)>

Case c2freqc2= 41

qaSetc2= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc2= <Insert(SI, Follow-Up Examination,

Non Operative Therapy, XOR-Join1),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join1>

Process Schema S

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

XOR-Split2 XOR-Join2

XOR-Split1 XOR-Join1

clinicalSuspicionOf

CruciateRupture = „Yes“

cruciateRupture = „Yes“ and

operationIndicated = „Yes“

Fig. 16. Discovery of Process Type Changes

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 31

Example 5.1. (Abstract Change Operations) Consider schema Sand re-

lated case-base cbS={c1, c2, c3}as depicted in Fig. 16. As abstract change opera-

tions applied on instances from Swe obtain abstOP1= Delete(SI,MRT),abstOP2

= Insert(SI,Follow-Up Examination), and abstOp3= Insert(SI,Puncture).

ProCycle suggests a process type change when the reuse frequency of an abstract

change operation exceeds the predefined threshold value thr:

freqabstOp

|InstS|≥thr

Example 5.2. (Reuse Frequency of Change Operations) Consider process

schema Sand cbS={c1, c2, c3}as depicted in Fig. 16. We obtain freqabstOp1=

0.051, freqabstOp2= 0.076, and freqabstOp3= 0.076. With threshold thr = 0.075

this suggests to pull abstOp2and abstOp3up to the type level.

To inform the process engineer about the potential need of a process type change

a notification with information about the abstract change operation abstOp exceed-

ing the threshold value is sent to him. In addition, for each abstract change operation

abstOp all cases c∈cbSwith a matching change operation in their solution part

are listed. The process engineer can then decide whether and how to perform the

process type change (i.e., to create a new schema version S0by applying a list of

change operations ∆Sto S). In most situations the change operations as defined

in the solution part of respective cases cannot be directly applied to the process

schema as the change operations have been only performed in a particular context.

Examining the question-answer pairs additionally enables the process engineer to

gain valuable insights into the context of a previously applied change operation as

each question-answer pair represents a condition under which the corresponding

case was applied. For example, activities Follow-up Examination and Puncture

from Fig. 16 should not be performed for all future process instances, but only if

certain conditions hold (e.g., there is fluid in the knee and an acute effusion of the

knee exists). Therefore, the solution part of the case is not directly pulled up to

the process type level, but the process engineer inserts the corresponding activity

only conditionally (cf. Fig. 17). In addition, pulling changes up to the type level

often necessitates the generalization of the change operations through parameter

adjustments (cf. Sect. 4.6). In particular, this can happen if for an abstract change

operation abstOp several matching cases exist.

Example 5.3. (Deriving a Process Type Change) Consider process schema

Sand cases {c2, c3}as depicted in Fig. 17. Based on this information the process

engineer decides to insert activities Follow-up Examination and Puncture at the

type level resulting in a new schema version S0. Considering the question-answer

pairs of c2and c3he decides to insert the respective activities only on condition

that the patient has a significant amount of fluid in the knee and an acute ef-

fusion of the knee. In addition, the process engineer generalizes the insert posi-

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

32 B. Weber et al.

Process Schema S

Process Schema S‘

Case c2freqc2 = 41

qaSetc2= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc2= <Insert(SI, Follow-Up Examination,

Non Operative Therapy, XOR-Join1),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join1>

Case c3freqc3 = 35

qaSetc3= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc3= <Insert(SI, Follow-Up Examination,

Non Operative Therapy1, XOR-Join2),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join2>

ΔS= <Insert(SI, Follow-Up Examination, Anamnesis & Clinical Examination, Discharge & Documentation),

Insert(SI, Puncture, Follow-Up Examination, Discharge & Documentation>

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

XOR-Split2 XOR-Join2

XOR-Split1 XOR-Join1

clinicalSuspicionOf

CruciateRupture = „Yes“

cruciateRupture = „Yes“ and

operationIndicated = „Yes“

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

XOR-Split2 XOR-Join2

XOR-Split1 XOR-Join1

clinicalSuspicionOf

CruciateRupture = „Yes“

cruciateRupture = „Yes“ and

operationIndicated = „Yes“

Follow-Up Examination

Puncture

Significant amount of fluid in knee and

acute effusion

Fig. 17. Deriving Process Type Changes

tion of activities Follow-up Examination and Puncture. He decides to insert the

two activities after Anamnesis & Clinical Examination and before Discharge

& Documentation. The list of change operations the process engineer applies to

transform Sinto S0is denotes as ∆S.

5.2. Process Schema Evolution and Process Instance Migration

Assume that the process engineer decides to perform a process type change, i.e.,

to transform process schema Sinto a new version S0by applying a list of change

operations ∆S. For example, schema Sin Fig. 17 has been modified by insert-

ing activities Follow-up Examination and Puncture after Anamnesis & Clinical

Examination and before Discharge & Documentation on condition that a signifi-

cant amount of fluid is in the knee and an acute effusion of the knee exists. When a

process type change takes place ongoing process instances can either be completed

based on original schema version Sor be migrated to the new schema version S0.30

The latter will be only possible if the respective instances have not progressed too

far. Migration to the new schema version then is accompanied by state adaptations

of the compliant instances.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 33

When migrating process instances to a new type schema version it has to be

considered whether respective instances are still running according to their original

schema (unbiased instances) or have already been individually modified due to ex-

ceptional situations (biased instances). The deviation of a process instance Ifrom

its original schema Sis thereby denoted as bias ∆I. Fig. 18 depicts four process

instances derived from process schema Sas depicted in Fig. 17a. Instance I1is

still running according to the original schema and is therefore denoted as unbiased

(i.e., |∆I1|= 0). By contrast, instances I2,I3and I4were individually modified

before, i.e., they constitute examples of biased instances. For biased instances it

has to be further considered whether the instance-specific change ∆Ioverlaps with

the process type change ∆S(e.g., I3and I4) or whether these changes are disjoint

(e.g., I2inf Fig. 18). Obviously, instances for which ∆Iand ∆Soverlap require a

different migration policy than instances for which ∆Iand ∆Sare disjoint (see Ref.

45 for details). Fig. 19 summarizes the different migration strategies supported by

ProCycle depending on the degree of overlap between ∆Sand ∆I.

9Migration

Policy 1

Adapt

Markings

++ x xx

I1on S I1on S‘

x++ x xx

xBA

ΔI1(on S) = τ(empty bias) ΔI1(on S‘) = = τ(empty bias)

unbiased

Migration

Policy 2

Adapt

Markings,

keep

Δon S‘

++ x xx

I2on S I2on S‘

x++ x xx

xBA

ΔI2(on S) = <Delete(SI2, C)> ΔI2(on S‘) = <Delete(SI2‘, C)>

disjoint

I3on S

x++ x xx

I3on S‘

x++ x xx

xBA

Migration

Policy 3

Adapt

Markings

reduce

Δon S‘

ΔI3(on S) = < Insert(SI3,A,D,E), Insert(SI3,B,A,E),

Delete(SI3, C)>

Migration

Policy 4

default

strategy

++ x xx

I4on S I4on S‘

x++ x xx

xBA

ΔI4(on S) = < Insert(SI4,A,F,J), Insert(SI4,B,A,J) >

partially equivalent

ΔI4(on S‘) = < Move(SI4‘,A,F,J), Move(SI4‘,B,A,J) >

xBA

subsumption equivalent

ΔI3 (on S‘) = <Delete(SI3‘,C)>

A .. Follow-up Examination, B .. Puncture, C .. MRT, D .. Anamnesis & Clinical Examination, E .. Discharge & Documentation, F .. Non Operative Therapy

Fig. 18. Instance Migrations after the Process Type Change Depicted in Fig. 17 (Instance-specific

modification are grey shaded)

For unbiased process instances, state–related compliance with the new schema

version has to be checked24 (cf. Def. 2.2). Compliant instances can be migrated

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

34 B. Weber et al.

to the new schema version S0(i.e., S[∆S> S0) by re-linking them to S0and by

adapting their state markings accordingly (e.g., instance I1from Fig. 18).

Process instances for which ∆Iand ∆Sare disjoint can migrate to the new

schema version S0on condition that they are compliant regarding their state as

well as their structure.46 Regarding Fig. 18, for example, ∆I2and ∆Sare disjoint;

i.e., they affect different activities and regions of the process schema. In addition,

I2is compliant with S0. Therefore, I2can be migrated to the new schema version

S0by adapting its markings and by keeping its bias ∆I2unchanged on S0, i.e., (S

+ ∆I2) [∆S>(S0+ ∆I2) (cf. Fig. 19).

Instances which have ’anticipated’ the process change completely (i.e., ∆Iand

∆Sare equivalent) can automatically migrate to new schema S0if they are compliant

with it. In this scenario, bias ∆Ibecomes empty after migration as the effects of

the instance change are entirely covered by S0.

An instance where ∆Isubsumes ∆Scan automatically migrate to S0if it is

compliant with S0.46 In Fig. 18, for example, ∆I3captures all effects of ∆Son

S, but has additional ones. In our example, both ∆Iand ∆Sconditionally insert

activities Aand B. However, ∆Iadditionally deletes activity C. As I3is compliant

with S0it can be migrated to S0by adapting instance markings. In addition, bias

∆Iis re-calculated, i.e., only those changes from ∆Inot covered by ∆Sare kept.

For process instances, which have partially anticipated the process type change

(resulting in an overlap of process type and instance changes), no default migration

policy can be provided and user interaction is required. The migration policy to

be applied to such instances depends on the particular degree of overlap between

process and instance change. To determine an appropriate migration policy it is not

sufficient to only check the parameterization of change operations. In addition, the

order in which the operations are applied may have an effect on change comparison

(e.g., when inserting activities in a sequence). We therefore compare the effects

of change operations. This is accomplished by a hybrid approach, which compares

change operations on the one side, but also the resulting process schema on the

other side (for details see Refs. 45 and 47). Fig. 18 shows an example of partially

equivalent changes. Both ∆Sand ∆I4insert the same activities, but at different

insert positions. To migrate instance I4to S0, in addition to adapting markings,

bias ∆I4needs to be re-calculated on S0. This is accomplished by replacing the

insert operations by move operations.

5.3. Case–Base Evolution

ProCycle does not only support the evolution of business processes and the migra-

tion of running instances to a new schema version, but additionally provides system

support for evolving the knowledge about process changes. This is crucial for any

approach on learning processes. Given a case-base cbSand a process type change

∆Swith S[∆S> S0, parts of cbSmight become obsolete on S0, because a subset of

the knowledge encoded in the cases of cbSis captured by S0afterwards. This will

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 35

Let S be a process schema and let ΔS be a type change transforming S into S’ (i.e., S’ = S + ΔS). Let

further I be an instance created from S with schema SI and bias ΔI (i.e., SI = S + ΔI).

Degree of overlap

between ΔS and ΔI Description Migration Policy

Category 1

ΔS and ΔI are

disjoint

ΔS and ΔI have different effects on S, i.e., ΔS and

ΔI concern different schema regions and different

activities. ΔS and ΔI are commutative.

Migrate I to S’

ΔI‘:= ΔI

SI’:= S’ + ΔI‘

Category 2

ΔS and ΔI are

equivalent

ΔS and ΔI have the same effects on S, i.e., changes

ΔS and ΔI effect the same activities, the same

schema regions, and apply the same change

operations in same order.

Migrate I to S’

ΔI‘:= τ (i.e., bias of I on

S’ becomes empty)

SI’:= S’

Category 3

ΔS subsumes ΔI

ΔS subsumes the effects of ΔI; i.e., ΔI captures the

effects of ΔS, but has additional ones as well.

Example:

• ΔS is a sub-list of ΔI

Migrate I to S’

ΔI‘:=ΔI – ΔS

SI’:= S’ + ΔI‘

Category 4

ΔI subsumes ΔS

ΔI subsumes the effects of ΔS; i.e., ΔS captures the

effects of ΔI, but has additional ones as well.

Example:

• ΔI is a sub-list of ΔS

Migrate I to S’

ΔI‘:= τ (i.e., bias of I on

S’ becomes empty)

SI’:= S’

Category 5

ΔS and ΔI are

partially equivalent

ΔS and ΔI are overlapping, i.e., they have

(partially) overlapping effects.

Examples:

• ΔS and ΔI insert different activities at the same

position of S

• ΔS and ΔI insert the same activities at different

positions of S

• ΔI moves an activity which is deleted by ΔS

(i.e., different operations, same activity)

• ΔI inserts an activity, which is only

conditionally inserted by ΔS

No “standard” migration

policies can be provided.

Fig. 19. Degrees of Overlap Between Changes and Related Migration Policies

particularly apply if the type change is triggered by the PAIS itself when case reuse

exceeds a given threshold (cf. Section 5.1). The challenge is to decide which cases

of cbSshall be transferred to cbS0, which cases have to be adapted before being

migrated to cbS0, and which ones are already covered by the new schema version S0

and can therefore be dropped. Note that this has to be done independently from

instance migrations as decribed in the previous section. Furthermore, we have to

consider that same or similar changes might have been applied in different applica-

tion context.

To determine suitable migration policies for a case c∈cbSthe relationship

between type change ∆Sand solution part ∆c(representing an instance change)

has to be analyzed. Depending on the degree of overlap between ∆Sand ∆cthree

major migration policies exist (cf. Fig. 20).

Cases for which ∆Sand ∆care disjoint can be automatically added to cbS0

without need for adaptation since ∆cdoes not contain any change already reflected

by S0. Regarding Fig. 21, for example, ∆c1and ∆Sare disjoint, i.e., they affect

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

36 B. Weber et al.

Let S be a process schema and ΔS be a type change transforming S into S’ (i.e., S’ = S + ΔS). Let

cbS’ be the set of cases applied to instances on S and cbS’ be the case-base associated with the new

schema version S’. Let further be c a case with solution part Δc.

Degree of overlap

between ΔS and Δc Description Migration Policy

ΔS and Δc are disjoint As Δc is not yet covered by ΔS case c

is still relevant

Keep case c unchanged and migrate

it to cbS’

Drop c if question-answer pairs are

reflected by ΔS

Migrate c to cbS’ if question-answer

pairs are not reflected by ΔS

Δc and ΔS are

equivalent

Δc subsumes ΔS

All changes in Δc are covered by ΔS.

However, ΔS and Δc might have

been applied in different application

context, i.e., be performed due to

different reasons. Consequently, it

has to be analyzed whether the set of

question-answer pairs qaSetc is

reflected by ΔS as well.

Migrate c to cbS’ and manually adapt

set qaSetc if question-answer pairs

are only partially reflected by ΔS

ΔS subsumes Δc

ΔS and Δc are

partially equivalent

As Δc has additional effects than ΔS

parts of change Δc are still relevant.

Migrate c to cbS’

Adapt solution part Δc as well as

qaSetc if question-answer pairs are

already partially reflected

Fig. 20. Evolution Policies for Cases

different regions of the process schema. Therefore c1is automatically added to cbS0.

If ∆cand ∆Sare equivalent or ∆csubsumes ∆S, migrating cto S0will not pro-

vide any additional information regarding the solution part. However, the question–

answer pairs qaSetcof cwill differ if ∆Sand ∆chave been performed under different

conditions (i.e., different application context). Consequently, question answer pairs

qaSetchave to be analyzed in order to decide on the migration of c. Case cwill not

be migrated to S0if all question-answer pairs are reflected by the conditions inserted

by ∆Sat type level. Case cwill be added to cbS0without adaptation if none of the

question-answer pairs is reflected by ∆S. If the question-answer pairs are partially

reflected by ∆S,qaSetcwill have to be adapted. The solution part of case c2in Fig.

21 is subsumption equivalent with ∆S. All changes of ∆c2are covered by ∆S. In

addition, the question-answer pairs of c2are reflected by the process type change

as well, as activities Follow-up Examination and Puncture are inserted under the

same conditions. Therefore, case c2is not migrated to cbS0.

If ∆csubsumes ∆S, or ∆Sand ∆care partially equivalent, case adaptation will

become necessary before adding the respective case to cbS0. In this situation ∆c

has additional effects when compared to ∆S, and consequently parts of ∆care

still relevant. Therefore, case cmust be added to cbS0after adapting ∆c. Question-

answer pairs might also have to be adapted if they are already partially reflected by

∆S. Case c3and ∆Sas depicted in Fig. 21 are partially equivalent. Consequently,

c3is migrated after adapting its solution part ∆c3. The question-answer pairs can

remain unchanged.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 37

Case-Base cbSon S:

Process Schema S‘

ΔS= <CondInsert(SI, Follow-Up Examination, Anamnesis & Clinical Examination, Discharge &

Documentation, cond), Insert(SI, Puncture, Follow-Up Examination, Discharge & Documentation>

Patient

Admission x

Anamnesis &

Clinical Examination

Non Operative Therapy

Sonography

MRT

X-ray

Initial Treatment &

Operation Planning

Non Operative Therapy 1

Operative Treatment

Discharge &

Documentation

++ x x

XOR-Split2 XOR-Join2

XOR-Split1 XOR-Join1

Follow-Up Examination

Puncture

qaSetc1= {(Does the patient have a cardiac

pacemaker?,

Patient.problemList.hasPacemaker =

'Yes')}

Δc1= <Delete(SI,MRT)>

qaSetc2= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc2= <Insert(SI, Follow-Up Examination,

Non Operative Therapy, XOR-Join1),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join1>

subsumption

equivalent

qaSetc3= {(Does the patient have fluid in the

knee?, 'A significant amount'),

(Does the patient have an acute

effusion of the knee?, 'Yes')}

Δc3= <Insert(SI, Follow-Up Examination,

Non Operative Therapy1, XOR-Join2),

Insert(SI, Puncture, Follow-Up

Examination, XOR-Join2>

partially

equivalent

c1qaSetc1= {(Does the patient have a cardiac

pacemaker?,

Patient.problemList.hasPacemaker =

'Yes')}

Δc1= <Delete(SI,MRT)>

disjoint

Case-Base cbS‘ on S‘:

migrate

c3qaSetc3= {(Does the patient have fluid in

the knee?, 'A significant

amount'), (Does the patient have

an acute effusion of the knee?,

'Yes')}

Δc3= <Move(SI, Follow-up Examination,

Non Operative Therapy, XOR-

Join1), Insert(SI, Puncture,

Follow-Up Examination, XOR-Join1)>

migrate

not migrated

change ΔS

Fig. 21. Case–Base Evolution

6. Architecture and Implementation

To demonstrate the feasibility of our ProCycle approach an integrated prototype

was implemented. It combines ADEPT210 and the conversational-case based rea-

soning (CCBR) component CCBR-Tool18,48 (cf. Fig. 24). This section gives an

overview of how our proof-of-concept prototype supports the process life cycle (cf.

Section 2.3). Thereby, we focus on the integration of the ADEPT2 and CCBR-Tool

as well as the extensions made in this context. Detailed descriptions of ADEPT2

and its architecture can be found in Ref. 49.

The prototype consists of two components ADEPT2 and CCBR-Tool. The

ADEPT2 technology16 supports the modeling, execution, and monitoring of busi-

ness processes. In addition, ADEPT2 enables process changes at both the process

type and the process instance level (for details see Ref. 49). Particularly, ADEPT2

provides functionality for migrating running process instances to the new schema

version. In this context, CCBR-Tool allows annotating instance changes with con-

text information. The resulting cases are memorized in a case-base and can be later

reused when applying CCBR-Tool.

In the following we describe the interplay between ADEPT2 and CCBR-Tool.

ADEPT2 is used for modeling, executing and monitoring processes (cf. Fig. 23).

During run-time users are working with worklists generated by the ADEPT2 system.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

38 B. Weber et al.

ADEPT2 Server Interface

CCBR-Tool Client ADEPT2 Client

Execution Manager Change Operations

Process Manager

Database Access

Process

CCBR-Tool Server

Case Base

ADEPT2 Server

Fig. 22. Architecture of the Integrated Prototype

If for a particular process instance an instance change becomes necessary, the user

will initiate the CCBR-Tool component for retrieving similar cases.

Fig. 23. Modeling the Process from Fig. 1a with the ADEPT2 Process Composer

Fig. 24 illustrates the interplay of ADEPT2 and CCBR-Tool during case re-

trieval. The ADEPT2 Client sends a request containing the instance to be modified

to the ADEPT2 Server (1). This server then determines the schema from which

this instance was derived and the case-base associated with this schema (2). It

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 39

then forwards the request to the CCBR-Tool Server and the CCBR-Tool Client (3).

CCBR-Tool is then started with the respective case–base and the graphical user

interface is opened (cf. Fig. 25), which assists users in finding similar cases (4). To

reuse a particular case the user needs to select and execute it. Following this, the

change operations from the solution part of the case are forwarded to the ADEPT2

system and applied to the respective instance (5). As a next step the reuse counter

of the case is increased by one (6). To ensure case quality the user has the option to

evaluate the case with a feedback form (7+8). The respective history entry is then

added to the case (9).

Fig. 24. Interplay of ADEPT2 and CCBR-Tool during Case Retrieval

Fig. 25 shows the graphical user interface for case retrieval. The upper part of

the screen shows the list of questions, which assists the user during case retrieval.

Questions can be answered in arbitrary order by selecting any of the available

answer options. On the lower part of the screen the most similar cases are displayed

ordered by decreasing similarity. When answering a question the list containing the

most similar cases is re-calculated. Cases, which need to be adjusted before reuse,

are highlighted in red, i.e., these cases cannot be directly applied to the respective

instance, but need adjustment. By clicking on the Show button users can access case

details, i.e., knowledge about problem description, question-answer pairs, change

operations, and full case history. If a case cannot be directly reused, the change

operations to be adjusted will be highlighted.

When adjusting a case, a copy is made, which can then be modified by the

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

40 B. Weber et al.

Fig. 25. Case Retrieval

user. This functionality can be used to quickly add cases to the case-base, if they

are similar to already existing ones (e.g., same problem description, but different

parameterization of change operations). To support later generalization, cases which

are the result of an adjustment contain a reference to the case they were derived

from.

If no similar case can be found the user will close the retrieval dialogue and

add a new case to the case–base. He first performs the desired change using the

process composer of ADEPT2. The changes are forwarded to CCBR-Tool to be

annotated with context information. For this, a textual problem description as well

as the reasons for the deviation in terms of question-answer pairs have to be entered.

Additional administrative attributes like creation date are automatically added by

the system. Finally, the case is stored in the case–base before ADEPT2 executes

the change operations.

A detailed description of the implementation can be found in Ref. 50.

7. Related Work

Adaptive PAISs are related to our approach. Most existing approaches either sup-

port process instance or process type changes (e.g., Refs. 11, 12, 13 and 29). Except

ADEPT210, WASA215 is the only adaptive PAIS, which has implemented both kinds

of changes in an integrated manner. While ADEPT2 provides high-level change

patterns, in WASA2 process changes have to be performed using change primitives

(e.g., add node, delete edge).30 ADEPT2 is the only adaptive PAIS, which allows

migrating biased instances to a new process schema version.

As change definition requires extensive user experience adaptive PAISs like

ADEPT2 or WASA2 support the user in the definition of instance changes by

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 41

Fig. 26. Add Case

ensuring that the resulting instance schemes are syntactically correct and the in-

stance is compliant with the new schema version.10 In addition, CBRFlow18 assists

users in exceptional situations by allowing for the reuse of previously defined in-

stance changes. However, no framework for integrated and seamless process lifecycle

support has been provided so far.

CAKE213,51 is an adaptive PAIS, which is related to our approach. It was re-

cently developed in the context of complex engineering processes in the domain

of digital chip design. Focus is on instance-specific changes and late modeling. In

contrast to ProCycle, CAKE2 does not support high-level change patterns. Instead

structural instance changes are based on a set of change primitives.30 Process type

changes have not been addressed by CAKE2, but each process instance has its own

process schema. Like ProCycle, CAKE2 provides authoring support for changes

using case-based reasoning techniques. Thereby, a case consists of a problem de-

scription (i.e., the process instance before the change including its context) and a

solution (i.e., the process instance after the change). Like in ProCycle the measure

used for retrieving similar cases considers context information and the status of the

process instance to be modified.51 The proposed similarity measure has turned out

to be appropriate for the chip design domain. However, it does not consider that

activities are often inserted at different positions in the process. In such situation,

the similarity measure used by CAKE2 will be too restrictive. In addition, case-base

evolution and quality issues are not addressed by CAKE2.

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

42 B. Weber et al.

The Pockets of Flexibility approach (PoF) is related to ProCycle as well.52 PoF

uses a combination of imperative and declarative process modeling. The process

itself is modeled in an imperative way, however, so called placeholder activities can

be specified in a declarative way based on constraints. During run-time the process

model is concretized by modeling the sub-processes for placeholder activities. In Ref.

53 a querying component for supporting the concretization of placeholder activities

is suggested. However, the feasibility of the proposed similarity measure has still to

be demonstrated through a proof-of-concept implementation. A similar approach

is provided by Worklets54, which addresses flexibility through the late binding of

placeholder activities. Using Worklets the need for structural process changes can

be reduced, but still is an issue. For these situations the Worklets approach only

provides very limited support.30 Basic support for change reuse is provided by

supporting the incremental evolution of selection rules for sub-process fragments.

Also related to our approach are declarative approaches for defining business

processes (e.g., DECLARE55 or MOBILE56). Instead of requiring process modelers

to specify how the process shall be executed, declarative models only specify what

shall be done by the process during run-time resulting in more flexibility. By using

declarative approaches the need for process changes can be reduced. However, run-

time modifications still can be an issue, e.g., a particular constraint might have to

be violated for a particular process instance due to an unforeseen situation. Fur-

thermore, constraints themselves may evolve over time, which raises the challenge

of propagating changes to ongoing instances. In Ref. 55 these issues are addressed

from a pure control-flow perspective, while data issues are not handled. In addition,

it still has to be evaluated how well maintenance issues of constraint-based process

models, particularly in case of large constraint sets, can be addressed. Furthermore,

performance issues might arise in the presence of larger constraint sets.

Process Mining techniques like Delta Analysis57,58,59, Conformance Testing59

and Change Mining38 can be used alternatively to our approach to improve the

quality of business processes. Using these techniques, discrepancies between the

modeled business process and the observed execution behavior can be discovered.

For this, Delta Analysis compares the present business process model with the

model derived from the execution log of the respective business process.59 By con-

trast, Conformance Testing directly compares the modeled business process with

its execution log. Though both techniques can be used to reveal malfunctions or

bottlenecks, they do not provide any semantics about the reasons for the observed

discrepancies. However, contextual knowledge about the reasons for these discrep-

ancies is needed by the process engineer in order to create an improved process

model.

Like ProCycle, change mining38 addresses the question what can be learnt from

the information about changes and suggests the use of adapted process mining

techniques to exploit the information gathered in change logs. A mining technique

is proposed, which reflects all changes applied to the instances of a particular process

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 43

type so far. The obtained change process can be used for optimizing and evolving

the process schema and is therefore complementary to our approach. For supporting

the user in reusing previously performed instance changes, the approach presented

in Ref. 38 is not yet suitable as the context of the change is not considered.

Orthogonal to this paper are security aspects. SecServ60 is a security service,

which can be used together with ProCycle to ensure that no uncontrolled changes

are performed and compliance rules are met. SecServ enforces the execution of

particular activities (e.g., due to legal requirements) and ensures that only activities

which are applicable in a specific context can be inserted into a process instance.

For a drug procurement process in a hospital, for example, the insertion of a patient

treatment step makes no sense and should thus not be allowed.

Existing research on versioning of process schemes is complementary to this

paper. While several commercial workflow products use an incremental numbering

system for versioning process schemes, Zhao et al. propose a version preserving

directed graph.61 The proposed approach is suitable to represent changes at both

the process type and process instance level. For a discussion on issues related to the

internal representation of versions we refer to Refs. 44 and 62.

8. Summary and Outlook

In this paper we have presented the ProCycle approach, which provides one of the

first implementations for integrated and seamless process life cycle support. As illus-

trated by Fig. 27, ProCycle extends existing life cycle support as offered in adaptive

PAISs (cf. Fig. 4). This includes advanced support for change reuse (see Item 4 in

Fig. 27) as well as intelligent support for deriving improved process models based

on knowledge about instance changes (see Item 8). In addition, ProCycle allows to

evolve knowledge on instance changes over time (see Item 9). These features are

fundamental for ensuring maintainability and up-to-date knowledge of the adaptive

PAIS.

We elaborated the need for the described kind of change support in several case

studies in which we applied the ADEPT1 technology.19,20,21 Furthermore, ProCycle

does not only provide a conceptual framework for flexible process life cycle support,

but also a powerful proof-of-concept implementation, which is based on two mature

research prototypes – ADEPT2 and CCBR-Tool. Our ambitious goal is to success-

fully transfer large parts of the described conceptual framework to practice later on.

On the one hand, a commercial product is currently built around the ADEPT2 tech-

nology. On the other hand, CCBR-Tool has been integrated into the Dynamic Logic

Engine (DLE)63. The DLE supports domain specialists in defining and executing

business processes in highly dynamic environments like the logistics industry. The

integration of CBR technologies into the DLE should foster continuous improvement

of business processes.

Future work includes the integration of ProCycle with our research on change

mining.38,64 In the MinAdept64,65 project, we are working on mining techniques for

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

44 B. Weber et al.

Case Base

Enter

order Make

appointme

Schema S‘:

++EC

Create Instances

Instance I1

Execution

Log

Process

participant

Arbeitsliste

Tätigkeit 1

Tätigkeit 2

Tätigkeit 3

Tätigkeit 4

Process

Execution

Process engineer /

Process administrator

Process

Monitoring

Change Log

I1(with instance-specific change)

Instance-

specific

Change

Exception:

Delete (I1, E)

CreateProcessSchema

Enter

order Make

appointme

Schema S:

EvolveProcessSchema

++EC

Change Propagation

fChange Reuse

Case Base

cbS

jDerive ProcessType Change

kEvolve Case-Base

Fig. 27. Process Life Cycle Support with ProCycle

exploiting the information gathered in process change logs. Respective techniques

can be used, for example, to provide more advanced support for the generalization of

instance changes. One of the themes we are currently working on are algorithms for

mining process variants and for merging these variants in a generic (i.e., improved)

process model.64,65 This is done in such a way that the average distance between

process instance and newly derived process type schema becomes minimal; i.e., the

number of high-level change operations required to derive an instance schema from

the new type schema.

Acknowledgements. Parts of this work was funded by the Tiroler Wissenschaftsfond.

We would like to thank Stefan Zugal and Jakob Pinggera for the implementation of the

CCBR-Tool component and Ulrich Kreher, Markus Lauer and Elisabeth Marini for their

help in integrating CCBR-Tool and ADEPT2. In addition, we would like to express our

appreciation to Peter Dadam for his feedback and the many valuable discussions on this

topic.

References

1. B. Mutschler and M. Reichert and J. Bumiller, “Unleashing the effectiveness of

process-oriented information systems: Problem analysis, critical success factors, im-

plications.” IEEE Trans. on Systems, Man and Cybernetics (Part C) 38(1) (2008)

280-291.

2. Sarbanes-Oxley Act of 2002, “Public Law 107-204 (116 Statute 745)”, (United States

Senate and House of Representatives in Congress, 2002).

3. Basel Committee on Banking Supervision, “International convergence of capital mea-

surement and capital standards (Basel II)” (2004).

4. D. M¨uller and J. Herbst and M. Hammori and M. Reichert, “IT support for release

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 45

management processes in the automotive industry.” Proc. BPM’06, Vienna (2006)

368-377.

5. R. Lenz and M. Reichert, “IT support for healthcare processes - premises, challenges,

perspectives.” Data and Knowledge Engineering 61 (2007) 39-58

6. M. Dumas and A. ter Hofstede and W. van der Aalst (eds.), “Process aware infor-

mation systems.” (Wiley Publishing, 2005).

7. M. Weske, “Business process management: concepts, methods, technology.” (Springer

2007).

8. W. van der Aalst and H. Reijers and A. Weijters and B. van Dongen and A.A.

de Medeiros and M. Song and H. Verbeek, “Business process mining: An industrial

application.” Information Systems 32 (2007) 713-732.

9. N. Kleiner, “Supporting usage-centered workflow design: Why and how?” Proc.

BPM’04, (2004) 227-243.

10. M. Reichert and P. Dadam, “ADEPTflex - Supporting dynamic changes of workflows

without losing control.” J. of Intelligent Information Systems 10 (1998) 93-129.

11. W. van der Aalst and T. Basten, “Inheritance of workflows: An approach to tackling

problems related to change.” Theoret. Comp. Science 270 (2002) 125-203.

12. C. Ellis and K. Keddara and G. Rozenberg, “Dynamic change within workflow sys-

tems.” Proc. COOCS’95 (1995) 10-21.

13. M. Minor and A. Tartakovski and D. Schmalen and R. Bergmann, “Agile work-

flow technology and case-based change reuse for long-term processes.” International

Journal of Intelligent Information Technologies 1(2008) 80-98.

14. S. Rinderle and M. Reichert and P. Dadam, “Correctness criteria for dynamic changes

in workflow systems - a survey.” Data and Knowledge Engineering 50 (2004) 9-34.

15. M. Weske, “Formal foundation and conceptual design of dynamic adaptations in a

workflow management system.” Proc. HICSS-34 (2001).

16. M. Reichert and S. Rinderle and U. Kreher and P. Dadam, “Adaptive process man-

agement with ADEPT2”, Proc. ICDE’05 (2005) 1113-1114.

17. M. Weske, “Workflow management systems: Formal foundation, conceptual design,

implementation aspects”, University of M¨unster, Germany (2000) Habil Thesis.

18. B. Weber and W. Wild and R. Breu, “CBRFlow: Enabling adaptive workflow man-

agement through conversational case-based reasoning.”, Proc. ECCBR’04 (2004) 434-

448

19. R. M¨uller, “Event-oriented dynamic adaptation of workflows.” PhD thesis, University

of Leipzig, Germany (2002)

20. S. Bassil and M. Benyoucef and R. Keller and P. Kropf, “Addressing dynamism in

e-negotiations by workflow management systems.” Proc. Workshop on Negotiations

in e-Markets - Beyond Price Discovery (DEXA’02) (2002).

21. S. Bassil and R. Keller and P. Kropf, “A workflow-oriented system architecture for

the management of container transportation.” Proc. BPM’04 (2004) 116-131.

22. M. Reichert and S. Rinderle and P. Dadam, “ADEPT workflow management system:

Flexible support for enterprise-wide business processes.” Proc. BPM’03 (2003) 370-

379.

23. Z. Luo and A. Sheth and K. Kochut and J. Miller, “Exception handling in workflow

systems.” Applied Intelligence 13 (2000) 125-147.

24. S. Rinderle and M. Reichert and P. Dadam, “Flexible support of team processes by

adaptive workflow systems.” Distributed and Parallel Databases 16 (2004) 91-116.

25. S. Rinderle and B. Weber and M. Reichert and W. Wild, “Integrating process learning

and process evolution - a semantics based approach.” Proc. BPM’05 (2005) 252-267.

26. B. Weber and M. Reichert and W. Wild, “Case-base maintenance for CCBR-based

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

46 B. Weber et al.

process evolution.” Proc. ECCBR’06 (2006) 106-120.

27. W. van der Aalst and A. ter Hofstede, “YAWL: Yet another work ow language.”

Information Systems 30 (2005) 245-275.

28. W. van der Aalst and M. Weske and D. Gr¨unbauer, “Case handling: A new paradigm

for business process support.” Data and Knowledge Engineering 53 (2005) 129-162.

29. F. Casati and S. Ceri and B. Pernici and G. Pozzi, “Workflow evolution.” Data and

Knowledge Engineering 24 (1998) 211-238.

30. B. Weber and M. Reichert and S. Rinderle-Ma, “Change patterns and change sup-

port features - enhancing flexibility in process-aware information systems. Data and

Knoweldge Engineering (accepted for publication).

31. S. Rinderle-Ma and M. Reichert and B. Weber, “Relaxed compliance notions in

adaptive process management systems.” Proc. ER’08 (2008).

32. S. Rinderle-Ma and M. Reichert and B. Weber, “On the formal semantics of change

patterns in process-aware information systems.” Proc. ER’08 (2008).

33. J.L. Kolodner, “Case-based reasoning.” (Morgan Kaufmann, 1993).

34. A. Aamodt and E. Plaza,”Case-based reasoning: Foundational issues, methodological

variations and system approaches.” AI Communications 7(1994) 39-59.

35. D.W. Aha and H. Mu˜noz-Avila, “Introduction: Interactive case-based reasoning.”

Applied Intelligence 14 (2001) 7-8.

36. S. Subramaniam and V. Kalogeraki and D. Gunopulos and F. Casati and M. Castel-

lanos and U. Dayal and M. Sayal, “Improving process models by discovering decision

points.” Information Systems 32 (2007) 1037-1055.

37. M. Reichert and P. Dadam and T. Bauer, “Dealing with forward and backward jumps

in workflow management systems.” Software and System Modeling 1(2003) 37-58.

38. C. Guenther, S. Rinderle-Ma and M. Reichert and W. van der Aalst and J. Recker,

“Using process mining to learn from process changes in evolutionary systems.” Int’l

Journal of Business Process Integration and Management, Special Issue on Business

Process Flexibility (accepted for publication) (2008).

39. A. Advani and M. Goldstein and Y. Shahar and M. Musen, “Developing quality

indicators and auditing protocols from formal guideline models.” AMIA’03 (2003)

11-15.

40. D.W. Aha and L. Breslow and H. Mu˜noz-Avila, “Conversational case-based reason-

ing.” Applied Intelligence 14 (2001) 9-32.

41. OMG: Object Constraint Language (OCL), www.omg.org/docs/ptc/03-10-14.pdf

(2003).

42. ICD-9: International classification of diseases,

http://www.cdc.gov/nchs/about/otheract/icd9/abticd9.htm (2003).

43. W. Cheetham and J. Price, “Measures of solution accuracy in case-based reasoning

systems.” Proc. ECCBR’04 (2004) 106-118.

44. S. Rinderle and M. Reichert and M. Jurisch and U. Kreher, “On representing, purg-

ing, and utilizing change logs in process management systems.” Proc. BPM’06 (2006)

241-256.

45. S. Rinderle and M. Reichert and P. Dadam, “Disjoint and overlapping process

changes: Challenges, solutions, applications.” Proc.On the Move to Meaningful In-

ternet Systems 2004: CoopIS, DOA, and ODBASE, LNCS 3290 (2004) 101-120.

46. S. Rinderle and M. Reichert and P. Dadam, “On dealing with structural conflicts

between process type and instance changes.” Proc. BPM’04, (2004) 274-289:

47. S. Rinderle, “Schema evolution in process management systems.” PhD thesis, Uni-

versity of Ulm (2004)

48. B. Weber and W. Wild, “Conversational case-based reasoning support for business

June 22, 2008 11:12 WSPC/INSTRUCTION FILE ijcis

Providing Integrated Life Cycle Support in Process-Aware Information Systems 47

process management.” Proc. Mixed-Initiative Problem-Solving Assistant - Papers

from the AAAI Fall Symposium. (AAAI Press, 2005).

49. M. Reichert and P. Dadam and U. Kreher and M. Jurisch and K. G¨oser, “Architec-

tural Design of Flexible Process Management Technology.” Proc. MKWI’08, (2008)

328-343.

50. J. Pinggera and S. Zugal and B. Weber and W. Wild and M. Reichert, “Integrating

case-based reasoning with adaptive process management.” Technical report, CTIT,

University of Twente, Enschede (2008).

51. M. Minor and A. Tartakovski and R. Bergmann, “Representation and structure-

based similarity assessment for agile workflows.” Proc. ICCBR’07 (2007) 224-238.

52. S. Sadiq and W. Sadiq and M. Orlowska, “A framework for constraint specification

and validation in flexible workflows.” Information Systems 30 (2005) 349-378.

53. R. Lu and S. Sadiq, “On the discovery of preferred work practice through business

process variants.” Proc. ER2007 (2007) 165-180.

54. M. Adams and A. ter Hofstede and D. Edmond and W. van der Aalst, “A service-

oriented implementation of dynamic flexibility in workflows.” Proc. On the Move

to Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE, LNCS

4275 (2006).

55. M. Pesic and M. Schonenberg and N. Sidorova and W. van der Aalst, “Constraint-

based workflow models: Change made easy.” Proc. On the Move to Meaningful In-

ternet Systems 2007: CoopIS, DOA, ODBASE, GADA, and IS, LNCS 4803 (2007)

77-94.

56. S. Jablonski and K. Stein and M. Teschke, “Experiences in workflow management

for scientific computing.” Proc. DEXA ’97 (1997) 56-61.

57. W. van der Aalst, “Inheritance of business processes: A journey visiting four notorious

problems.” Proc. Petri Net Technology for Communication Based Systems. (2003)

383-408.

58. V. Guth and A. Oberweis, “Delta analysis of petri net based models for business

processes.” Proc. Applied Informatics. (1997) 23-32.

59. W. van der Aalst, “Business alignment: Using process mining as a tool for delta

analysis and conformance testing.” Requirements Eng. Journal (2005) 198-211.

60. B. Weber and M. Reichert and W. Wild and S. Rinderle, “Balancing flexibility and

security in adaptive process management systems.” Proc. On the Move to Meaningful

Internet Systems 2005: CoopIS, DOA, and ODBASE, LNCS 3760 (2005) 59-76.

61. X. Zhao and C. Liu, “Version management in the business process change context.”

Proc. BPM’07 (2007) 198-213.

62. S. Rinderle-Ma and U. Kreher and M. Lauer and P. Dadam and M. Reichert, “On rep-

resenting instance changes in adaptive process management systems.” Proc. WET-

ICE’06 (2006) 297-302.

63. W. Wild and R. Wirtensohn and B. Weber, “Dynamic engines - a flexible approach

to the extension of legacy code and process-oriented application development.” Proc.

WETICE’06 (2006) 279-284.

64. C. Li and M. Reichert and A. Wombacher, “On measuring process model similarity

based on high-level change operations.” Proc. ER’08 (2008).

65. C. Li and M. Reichert and A. Wombacher, “Discovering reference process models by

mining process variants.” Proc. ICWS’08 (2008).