CCBR–Driven Business Process Evolution
Barbara Weber1, Stefanie Rinderle2, Werner Wild3, and Manfred Reichert4
1Quality Engineering Research Group, Institute of Computer Science,
University of Innsbruck – Technikerstrasse 21a, 6020 Innsbruck, Austria
2Dept. Databases and Information Systems, University of Ulm, Germany
3Evolution Consulting, Innsbruck, Austria
4Information Systems Group, University of Twente, The Netherlands
Abstract. Process-aware information systems (PAIS) allow coordinat-
ing the execution of business processes by providing the right tasks to the
right people at the right time. In order to support a broad spectrum of
business processes, PAIS must be flexible at run-time. Ad-hoc deviations
from the predefined process schema as well as the quick adaptation of the
process schema itself due to changes of the underlying business processes
must be supported. This paper presents an integrated approach com-
bining the concepts and methods provided by the process management
systems ADEPT and CBRFlow. Integrating these two systems enables
ad-hoc modifications of single process instances, the memorization of
these modifications using conversational case-based reasoning, and their
reuse in similar future situations. In addition, potential process type
changes can be derived from cases when similar ad-hoc modifications at
the process instance level occur frequently.
1 Introduction
For a variety of reasons companies are developing a growing interest in aligning
their information systems in a process-oriented way to provide the right tasks to
the right people at the right point in time. However, when automating business
processes it is extremely important not to restrict users. Early attempts to real-
ize process-aware information systems (PAIS) have been unsuccessful whenever
rigidity came with them [1,2]. Therefore, a flexible PAIS must allow authorized
users to deviate from the pre-modeled process schema if needed (e.g., by dynam-
ically inserting, deleting or moving process steps). In addition, the PAIS must
be quickly adaptable to changes of the underlying business processes, e.g., due
to business process reengineering efforts or the introduction of new laws [3,4,5].
In the ADEPT project we have developed a next generation process man-
agement system (PMS) that satisfies these needs. On the one hand, the ADEPT
PMS offers full functionality with respect to the modeling, analysis, execution,
H. Mu˜noz-Avila and F. Ricci (Eds.): ICCBR 2005, LNCS 3620, pp. 610–624, 2005.
c
Springer-Verlag Berlin Heidelberg 2005
Proc. 6th Int'l Conf. on Case-Based Reasoning (ICCBR'05), Chicago, August 2005 (to appear)
CCBR–Driven Business Process Evolution 611
and monitoring of business processes [1,3,6]. On the other hand, it provides sup-
port for adaptive processes at both the process instance and the process type
level. Changes at the instance level may affect single process instances and be
performed in an ad-hoc manner, e.g., to deal with exceptional or unanticipated
situations [1]. Process type changes, in turn, can be applied to adapt the PAIS
to business process changes. In this context, concurrent migration of hundreds
up to thousands of process instances to the new process schema may become
necessary. ADEPT allows to perform the respective migrations on-the-fly while
preserving process consistency and system robustness [3,6,7].
In practice, process type changes are often driven by previous ad-hoc adap-
tations of individual process instances. Usually, similar or equivalent changes of
a larger number of process instances indicate the need for adapting the process
type (i.e., the process template) itself [8]. For example, in a patient treatment
process an additional lab test activity has been inserted for a significant number
of process instances; in order to better reflect the real-world process, a process
schema evolution should then be initiated to create a new process template ver-
sion which includes this additional activity (cf. Fig. 2). So far, ADEPT has not
adequately dealt with this fact and has not considered the reuse of information
about previous ad-hoc changes. In particular, it has not maintained semantic in-
formation about these changes (e.g., their reason and context). Thus, it has been
the responsibility of the process designer to identify frequently applied changes
and to adapt process types accordingly.
By contrast, CBRFlow [9] enables users to apply process instance changes in a
more intelligent way. Particularly, it allows to document the reasons for a process
instance change and to reuse information about previously performed ad–hoc
changes when defining new ones. For this conversational case-based reasoning
(CCBR) [10] is used. So far, focus has been put on ad–hoc changes of single
process instances whereas process type changes have not yet been considered. In
order to provide comprehensive change support a PAIS must capture the whole
process life cycle and all kinds of changes in an integrated way.
In this paper we provide such an integrated approach, which combines the
concepts and methods offered by ADEPT and CBRFlow: On the one hand, the
combined system provides a powerful process engine, which supports all kinds
of changes in one system. On the other hand, it enables the intelligent reuse of
process instance changes and the derivation of process type changes from the
collected information. The added value offered by this integration is shown in
Table 1.
Table 1. Benefits from Integrating ADEPT and CBRFlow
ADEPT CBRFlow ADEPT+CBRFlow
process instance changes + + +
reuse of process instance changes + +
process type changes + +
deriving process type changes +
612 B. Weber et al.
Section 2 provides background information, Section 3 discusses issues that
arise when trying to derive process type changes from cases. In addition to the
resulting evolution of the business processes the corresponding case-bases evolve
over time as well. This important issue is covered in Section 4. Section 5 discusses
related work and Section 6 closes with a summary and an outlook on future work.
2 Background
In this section we provide background information regarding process manage-
ment and case-based reasoning (CBR) as used in our approach.
2.1 Process Management
For each business process supported (e.g., booking of a business trip or handling
a medical order) a process type Thas to be defined. Formally, such a type is
represented by a process schema Sof which different versions may exist. In
Fig. 1, for example, Sand Scorrespond to different schema versions of the
same process type T(thus reflecting the evolution of T).
In the following, a process schema is represented by a directed graph, which
defines a set of activities – the process steps – and the control flow between
them.1In Fig. 1 process schema Sconsists of 6 activities: for example, activity
Admit patient is followed by activity Make appointment in the flow of control
whereas Prepare Patient and Inform Patient can be processed in parallel.
Formally:
Definition 1 (Process Schema). A process schema Sis defined by a tuple
(N,E)where Ndenotes the set of activities and Ethe set of control edges (i.e.,
precedence relations) between these activities.
At runtime new process instances can be created and executed based on
schema S. Similar to Petri Nets, the execution state of a particular process in-
stance is captured by a marking function M=(NS,ES). It assigns to each
activity nits current status NS(n)∈{NOT ACTIVATED, ACTIVATED, FIN-
ISHED}and to each control edge its marking ES(e)∈{NOT SIGNALED, SIG-
NALED}. For the top most process instance I(1)
νin Fig. 1, for example, activity
Admit patient has already been finished and therefore its outgoing edge is
marked as SIGNALED. Activity Make appointment, in turn, is currently acti-
vated, i.e., offered to users for execution in their worklists.
Usually, a process instance Iis executed according to the control flow de-
fined by its original schema S. As motivated in Section 1, however, users may
have to deviate from the original schema (e.g., by adding new activities or by
1In this paper we restrict our considerations to schemes with sequential and parallel
activities. Our approach, however, considers more complex control structures as well
(e.g., conditional branchings, loops, and synchronizations between parallel execution
branches). Details of the process meta model used can be found in [1,6,7].
CCBR–Driven Business Process Evolution 613
IQ(Q= 1...n)
Admit
patient
Inform patient
Prepare patient
Examine
patient
Deliver
report
Schema Version S:
Make
appointment
Lab
test
Schema Version S‘:
Migrate compliant
instances
Admit
patient
Make
appointment
Prepare
patient
Examine
patient
Deliver
report
IQ‘(Q‘{1, ..., n})
Lab
test
Iµ(µ = 1...m)
IZ(Z= 1...l)
Migrate compliant
instances
IP‘(P‘{1, ..., m})
IZ‘(Z‘{1, ..., l})
Lab
test
Migrate compliant
instances
Process Type
Change 'T
Process Instance Level:
Activity finished
Activity activated
Process Type Level:
(1)
(2)
(3)
(1)
(2)
(3)
Fig. 1. Migration of Process Instances – Clinical Example
deleting existing ones). For this reason, we must distinguish between two ba-
sic classes of process instances, those that still follow their original schema and
those that have been individually modified during runtime. In the following, we
call instances of the former class unbiased and those of the latter one biased.
Correspondingly, a biased instance Icannot solely be characterized by its orig-
inal schema Sand marking M, but must also capture the sequence of ad-hoc
changes ∆I=(a1,...,a
k) applied to it so far. Generally, several ad-hoc changes
may have been applied to a biased instance Iat different points in time.
For example, consider Fig. 1: Process instances I(1)
ν,ν =1...nare unbiased.
By contrast, process instances I(2)
µ,µ=1...m and I(3)
ω,ω=1...l are biased
since their current execution schema deviates from their original schema S.In-
stances I(3)
ω,ω=1...l, for example, are biased due to the dynamic deletion of
activity Deliver report. Formally:
Definition 2 (Process Instance).
A process instance I is defined by a tuple (S, ∆I,M)where
–S=(N,E)denotes the process schema I was originally created on.
–∆I=(a1,...,a
k) comprises the instance–specific sequence of ad–hoc modi-
fications which have been applied to I so far (i.e., changes transforming the
process schema S, instance I was created from, into the current execution
schema SI=S+∆I=(N,E)).Thereby ai= (op, s, paramList) denotes
an operation op ∈OP which operates on a schema subject s (i.e., activities
614 B. Weber et al.
Table 2. A Selection of ADEPT Change Operations∗
Change Operation op Effects on Schema S
applied to Schema S
Additive Change Operations
serialInsert(S, X, A, B) insert activity X into schema S between
the two directly connected activities A and B
parallelInsert(S, X, (A)) insert activity X into schema S parallel to activity A
Subtractive Change Operations
deleteActivity(S, X) delete activity X from schema S
∗A detailed description of all change operations supported by ADEPT can be found in [11,12].
or edges) using parameters paramList. OP is the set of change operations
provided by ADEPT, a subset of these operations is given in Table 2.
–M =(NS, ES) reflects the current marking of I. It assigns to each activity
n∈Nits current status NS(n) and to each edge e∈Eits marking ES(e).
2.2 Case-Based Reasoning and Learning Processes
Case-based reasoning is a contemporary approach to problem solving and learn-
ing. New problems are dealt with by applying past experiences – described as
cases – and by adapting their solutions to the new problem situation [13]. Thus,
CBR contributes to incremental and sustained learning: Every time a new prob-
lem is solved, information about it and its solution is retained and therefore
immediately made available for solving future problems [14].
Conversational CBR is an extension to the CBR paradigm, which actively
involves users in the inference process [15]. A CCBR system can be character-
ized as an interactive system that, via a mixed-initiative dialogue, guides users
through a question-answering sequence in a case retrieval context. Unlike tra-
ditional CBR, CCBR does not require the user to provide a complete a priori
problem specification for case retrieval, nor requires him to provide knowledge
about the relevance of each feature for problem solving. Instead, the system as-
sists the user in finding relevant cases by presenting a set of questions to assess
the given situation. Furthermore, it guides users who may supply already known
information on their initiative. Therefore, CCBR is especially suitable for han-
dling exceptional or unanticipated situations that cannot be dealt with in a fully
automated way.
In our approach a case crepresents a concrete ad-hoc modification of a pro-
cess instance Iwhich can be reused by other instances. It consists of a textual
problem description, a set of question-answer pairs, and a solution part (i.e.,
the action list). The question–answer pairs describe the reasons for the ad-hoc
change and the action list comprises the change operations (and related context
information) applied to I.
CCBR–Driven Business Process Evolution 615
Definition 3 (Case, Case–Base).
A case c is a tuple (pd, {q1an1, ..., qnann}, sol, freq) where
–pd is a textual problem description
–{q1an1, ..., qnann}denotes a set of question-answer pairs
–sol = {aj|aj=(opj,s
j, paramListj), j = 1, ..., k}is the solution part
of the case denoting a list of actions (i.e., a set of changes that have been
applied to one or more process instances; see also Def. 2)
–freq ∈Ndenotes the reuse frequency of case c
Acase–baseCB={c1,...,c
m}is defined as a set of cases.
3 Deriving Evolutionary Process Changes from Cases
Fig. 2 illustrates our approach: it shows how CCBR is used to perform ad-hoc
changes of single process instances (cf. Section 3.1) and how it triggers process
type changes if the same or similar ad-hoc changes happen over and over again
(with respect to instances of a given process type; cf. Section 3.2). Fig. 2 also
indicates that the evolution of a process schema may require the concurrent
migration of the associated case-base (cf. Section 4).
As already mentioned, new instances canbecreatedbasedonagivenprocess
schemaandthenbeexecutedaccordingto that schema. If required, authorized
users may deviate from the pre-modeled process schema during runtime at the
level of single process instances. They apply CCBR to retrieve knowledge about
previous ad-hoc changes. In addition, they document the new change and collect
information about the reasons which required the respective ad-hoc deviation.
This information is then immediately available for future reuse in similar sit-
uations. Finally, if a case is frequently reused (i.e., the same ad-hoc change is
often applied to instances of a particular process type), case usage may exceed a
predefined threshold. In this situation, the knowledge engineer is notified about
the potential need of a process type change. He can then take action, e.g., by
adapting the process type and migrating the case-base.
3.1 Performing Ad-Hoc Changes Using CCBR
Integrating ADEPT and CBRFlow offers promising perspectives: It allows for
ad-hoc modifications at the process instance level in a correct and consistent
manner, it facilitates the memorization of these modifications using CBR tech-
niques, and it provides for reusing respective cases in similar, future situations.
The underlying CBR cycle [14] can be described as follows:
Adding a New Case. Whenever a user wants to apply an ad-hoc change at the
process instance level and no similar cases can be found in the CCBR system,
she adds a new case c=(pd, {q1an1,...,}, sol, 1) to the case-base. The user
enters this case by briefly describing the current problem, by entering a set of
question-answer pairs describing the reasons for the ad-hoc deviation, and by
specifying the actions to be taken from the list of available change operations.
616 B. Weber et al.
Lab
test
Add / Reuse
Case LabTest
IQ(Q= 1...n)
IQ(Q= 1...n)
Changed Process
Instances
Lab
test
CCBR
Instantiation
ProcessTypeChange
Process Instance Change
Notification
Thresholdexceeded
Process Instances
Workflow User
Knowledge Engineer
Knowledge
Engineer
Migrate
case-base
Prepare
Patient
Examine
patient
Make
appointment
Schema S‘:
Enter
order Inform
patient
Lab
Test
Make
appointment
Deliver
report
Prepare
Patient
Schema
S:
Enter
order Inform
patient
Prepare
Patient
Examine
patient
Deliver
report
Make
appointment
Fig. 2. Deriving Evolutionary Process Changes from Cases
Question-answer pairs can be entered by either selecting the question from a list
of previously entered questions (i.e., reusing questions from existing cases) or,
when no suitable question is already in the system, by defining a new question
and giving the appropriate answer. Depending on the permissions of the user
and the current state of the process instance (i.e., which activities are currently
performed) only a subset of the ADEPT operations may be applicable. The user
selects the desired change operations op1,...,op
pand the subjects s1,...,s
p
they operate on (e.g., activities and control edges). In addition, she provides the
parameters for each selected operation. Finally, the case is retained and thus
immediately made available for future reuse.
Retaining a Case. Unlike CBRFlow [9], our approach stores cases not relative
to the location in the process graph where the ad-hoc modification occurred (e.g.,
relative to an activity), but in reference to the process schema itself. There is one
case-base version for each process schema version S, as they might be relevant
at different locations in the process. For example, the insertion of a particular
activity (e.g., order lab test) might become necessary at different points in time
during process execution.
Case Retrieval. For case retrieval the CCBR approach as described in [10]
has been adapted. When deviations from the predefined process schema become
necessary the user initiates case retrieval in the CCBR component. The system
then assists her in finding already stored, similar cases by presenting a set of
questions. Users can directly answer any of the displayed questions (in arbitrary
order) or additionally apply a filter to the case-base by specifying an operation op
CCBR–Driven Business Process Evolution 617
as well as the subject son which the operation is supposed to operate. Filtering
is done by selecting values from predefined lists and by ignoring those cases that
do no match the filter criteria (i.e., that do not have the selected operation and
subject in the actions list); only the remaining cases are presented. Formally:
Definition 4 (Filtered Case–Base). Let CB = {c1,...,c
k}be a case–base
with ci=(...,sol
i,...)(i=1, .., k)andsoli={(opj,s
j,...)}(j=1, .., m)(cf.
Def. 3). Then the filtered case-base CBfilter can be determined as follows:
CBfilter =⎧
⎨
⎩
{ci∈CB |∃(opj,s
j,...)∈soli:opj=op ∧sj=s}ifA
{ci∈CB |∃(opj,s
j,...)∈soli:opj=op}ifB
CB otherwise
whereby
•A: user has specified change operation op ∈OP and subject s
•B: user has specified change operation op ∈OP
The system then searches for similar cases by calculating the similarity for
each case in the case-base CBfilter. It then displays the top nranked cases
(ordered by decreasing similarity) and their reputation score, which indicates
how successfully each case has been applied in the past. Similarity is calculated
by dividing the number of correctly answered questions minus the number of
incorrectly answered questions by the total number of questions in the case.
Formally:
Definition 5 (Similarity). Let c = (pdc,QAc={qc
1anc
1,...,qc
nanc
n},...)be
a case of case–base CB and Q = {qQ
1anQ
1,...,qQ
manQ
m}be a query against CB.
Then sim(Q, c) denotes the similarity between Q and c. Formally:
sim(Q,c) = same(Q,c)−diff(Q,c)
|QAc|
whereby
•same(Q, c) = |QAc∩Q|
•diff(Q, c) = |{qc
ianc
i∈QAc|∃qQ
janQ
j∈Qwith
qc
i=qQ
j∧anc
i=anQ
j; i = 1,..,n; j = 1,.., m}|
Case Reuse. ADEPT supports different kinds of ad-hoc changes which, for ex-
ample, allow users to skip activities, to change activity orders, or to insert new
activities [1]. In particular, the system ensures that ad-hoc changes do not lead
to unstable system behavior2or to inconsistent instance states. When an excep-
tional or unexpected situation occurs, the user is assisted in selecting the desired
change operations and in setting the change context (e.g., the predecessors and
successors of an activity to be inserted) accordingly.
Generally, change definition requires user experience, in particular if the in-
tended change requires concurrent adaptations (e.g., when deleting a particular
2None of the guarantees (e.g., absence of deadlocks, correctness of data flow) which
have been achieved by formal checks at buildtime are violated due to the change.
618 B. Weber et al.
activity, data-dependent activities may have to be deleted as well). Therefore,
the reuse of existing knowledge about previous ad-hoc changes is highly desir-
able. When a user decides to reuse an existing case, the actions specified in the
solution part of the case are forwarded to and carried out by the ADEPT change
engine. The reuse counter is increased and a work item is created for evaluating
the ad-hoc change later on to maintain the quality of the case-base.
When the reuse counter exceeds a certain configurable threshold the knowl-
edge engineer is notified about the potential need to perform a schema evolution
(cf. Section 3.2). Altogether, the reuse of existing ad-hoc changes contributes to
hide as much complexity from users as possible.
Ensuring Quality Through Case Evaluation. The accuracy of the cases in
the case-base is crucial for the overall performance of a CBR system and conse-
quently for the trust users have in it. When cases are not added by the knowledge
engineer but by end users, evaluation mechanisms are needed to ensure quality
of the cases in the case-base.
Therefore, similar to Cheetham and Price [16], we propose to augment the
CBR cycle with the ability to determine the confidence in the accuracy of indi-
vidual solutions. However, for CCBR systems the accuracy cannot be determined
automatically as the semantics of the question-answer pairs are, unlike in tra-
ditional CBR systems, unknown to the system. For this purpose we apply the
concept of reputation from e-commerce where such systems are used to build
trust among strangers like, for instance, in eBay’s feedback forum [17]. There,
each positive feedback on a transaction increases the reputation score of a seller,
while each negative feedback results in a decrease. In our approach, we use the
concept of reputation to indicate how successfully a case has been reused in the
past, i.e., how much it has contributed to the performance of the case-base, thus
indicating the degree of confidence regarding the accuracy of this case. Like in
eBay, users are encouraged to provide feedback when adding or reusing a case.
For this purpose, a new work item representing an optional feedback task is
automatically created and inserted into the worklist of the user who entered or
applied the case. She can then rate the performance of the case either with 1
(positive), 0 (neutral) or −1 (negative), and may optionally specify an addi-
tional comment. The reputation score of a case is then calculated as the number
of distinct users who gave a positive feedback minus the number of those who
gave a negative feedback. Negative feedback usually results in a notification of
the knowledge engineer (see below).
During case retrieval the CCBR system displays the overall reputation score
together with a table of the totals of each rating in the past 7 days, the past
month, and the past 6 months to the user. Upon request the user can read all
comments provided in the past and decide whether the reputation of the case is
high enough for her to have confidence in its accuracy.
Case Revision. Negative feedback results in a notification of the knowledge
engineer who can then revise the case or decide to deactivate it (no deletion is
allowed to foster traceability).
CCBR–Driven Business Process Evolution 619
Workflow User
Title: Perform Lab Test
Description: Additional lab test is needed
Question-Answer Pairs: Patient has diabetes? Yes
Patient has overweight? Yes
Patient is older than 35? Yes
Blood pressure? High
Actions: Insert (LabTest, PreparePatient, ExaminePatient)
Process
Instance I:
Enter
order Inform
patient
Prepare
Patient
Examine
patient
Deliver
report
Make
appointment
Lab
test
Add Case
Insert (LabTest, Prepare Patient, Examine Patient)
Fig. 3. Adding a New Case to Insert a Process Step
Select Operation
Patient has diabetes?
Patient has overweight?
Patient is older than 35?
Blood pressure?
Question Answer
Yes
Yes
Yes
High
Select Activity/Edge
Insert
LabTest
Case ID
1
Score
100%
Title
Lab test required
Reputation Score
25
positive
Past 7
Days
25
Past
Month
30
Reputation Score: 25
Positive Feedback: 83%
Positive: 30
Negative: 5
Recent Ratings for Case 1:
Past 6
Months
0
neutral 1 1 0
negative 2 5 0
Overall Ratings for Case 1:
Fig. 4. Retrieving Similar Cases
Example. To illustrate the above concepts we provide a simplified medical ex-
ample. As depicted in Fig. 1 the examination of a patient usually takes place
after a preparation step. During the examination the physician recognizes that
the patient suffers from diabetes and he detects several other important risk
factors. Therefore, the physician decides to request an additional lab test for
the patient to be performed after activity Prepare patient and before activ-
ity Examine Patient. As the system contains no similar cases, the physician
enters a new case describing the situation and the action to be taken (Fig. 3).
ADEPT then checks whether the insertion of activity Lab Test is possible for
the respective process instance, and - if so - applies the specified insert operation
to that instance. The latter includes updating the instance markings and user
worklists. If, for example, Prepare patient is completed and Examine Patient
620 B. Weber et al.
is activated, this activation will be undone (i.e., respective work items are re-
moved from user worklists) and the newly inserted activity Lab test becomes
immediately activated. In any case, the newly inserted activity is treated like
the other process steps, i.e., the same scheduling and monitoring facilities exist.
When talking with another diabetic patient some time later, the physician
remembers that there has been a similar situation before and initiates the CCBR
sub-system to retrieve similar cases. As he still remembers that he had performed
an additional lab test, he selects the Insert operation as well as the Lab Test
activity to filter the case-base. He then answers the questions presented by the
system, finds the previously added case, and reuses it (Fig. 4). Of course, the
physician could also directly answer any of the presented questions without se-
lecting an operation or an activity first (e.g., when he doesn’t remember a similar
previous situation).
3.2 Deriving Process Type Changes
When the usage of a particular case exceeds the specified threshold value (i.e.,
based on the frequency the case was reused, cf. Def. 3), the system sends a
notification to the knowledge engineer. He may then initiate a process type
change in order to derive a new version of the process schema. For this purpose
he may directly apply the change operations captured by the respective case;
alternatively, he can adapt the case’s operation set (e.g., by only considering a
subset of it).
When a new process schema is released future instances can be created from
it. However, the challenging question is how to treat already running process
instances, i.e., instances that have been derived from the old process schema
version. Particularly for long-running processes, it is crucial that respective in-
stances can be migrated to the new process schema version if desired (cf. Fig. 1).
In this context ADEPT first checks whether these instances are compliant with
the new process schema or not. Compliant means that the process schema change
can be applied to the instance in its current state so that it can be smoothly
re–linked to the new schema, i.e., migrated to it without causing inconsistencies
or errors (e.g., deadlocks). Then the set of compliant process instances is divided
into unbiased and biased instances. The former can be directly re–linked to the
new schema. For each instance its marking with respect to the new schema
version is automatically determined. For biased process instances further cor-
rectness checks are necessary, e.g., regarding structural correctness (for details
see [12]). Finally, all compliant process instances are running according to the
new schema version whereas non compliant process instances remain running on
the old schema. An example is given in Section 4.
4 Migrating the Case-Base
Assume that the frequencies for reusing certain cases exceed specified thresholds
(cf. Section 3.2). For instance, as illustrated in Fig. 5 the specified thresholds for
reusing case c1 (freq = 51) and c5 (freq = 60) are exceeded, thus triggering a
CCBR–Driven Business Process Evolution 621
Schema Version S: Schema Version S‘:
Process Type
Change 'T1
CCBR:
Process Type Level:
X
D
X
Process Type
Change 'T2
F
FX
Schema Version S‘':
CB:
c1: (..., {sInsert(S, X, C, E)}, 51)
c2: (..., {sInsert(S, X, C, E)}, 1)
c3: (..., {pInsert(S, B, ...)}, ...)
c4: (..., {deleteAct(S, D)}, 60)
c5: (..., {deleteAct(S, D),
sInsert(S, X, C, E)}, 2)
c6: (..., {pInsert(S, C)}, ...)
Migration
CB':
c3: (..., {pInsert(S, B, ...)}, ...)
c6: (..., {pInsert(S, C)}, ...)
c7: (..., {deleteAct(S‘, F)}, 55)
c8: (..., {sInsert(S‘, K, ...)}, ...)
c9: (..., {deleteAct(S‘, F)}, 1)
CB'':
c3: (..., {pInsert(S, B, ...)}, ...)
c6: (..., {pInsert(S, C)}, ...)
c8: (..., {sInsert(S‘, K, ...)}, ...)
c10: (..., {sInsert(S‘‘, U, ...)}, ...)
Migration
new cases added for process instances
based on schema version S'
Case-Base Migration
Filter all cj= (…, solj, …) from CB with solj'
T1
AB
C
EB
ACEB
ACE
'T1 = {sInsert(S, X, C, E), deleteAct(S, D)} 'T2 = {deleteAct(S‘, F)}
Case-Base Migration
Filter all ck= (…, solk, …) from CB‘ with solk'
T2
new cases added for process instances
based on schema version S‘'
Fig. 5. Migrating the Case-Base
process type change. The knowledge engineer is informed and decides that the
respective instance changes serialInsert(S,X,C,E) (sInsert(S,X,C,E) for short)
and deleteActivity(S,D) (deleteAct(S,D) for short) should be pulled up to the
process type level. He derives a new process schema version S’ by applying
process type change ∆T1={sInsert(S,X,C,E), deleteAct(S,D)}.
This process type change is accompanied by the migration of compliant pro-
cess instances to the new schema version S’, whereas non-compliant process
instances remain running on the old schema version (cf. Section 3.2). In addi-
tion, the challenging question is, which cases of the previous case-base CB (on
S) shall be valid for process instances of S’ as well. This consideration becomes
necessary as the solution part of certain cases may be covered by a process type
change ∆T. Therefore the respective cases are no longer needed. In our approach,
only cases whose solution part is not reflected in the process type change ∆T
are migrated to CB’. By contrast, cases whose solution part is a subset of ∆T
are omitted. Formally:
Definition 6 (Case-Base Migration). Let CB = (c1,...,c
k)beacase-base
stored for process instances running according to process schema S. If then pro-
cess type change ∆Ttransforms S into another process schema S’ the new version
CB’ of CB can determined as follows:
CB’ = CB \{ci=(...,sol
j,...)∈CB |solj⊆∆T(j = 1,..,m)}
In the example depicted by Fig. 5, cases c1 and c4 that initiated the process
type change, as well as case c2 and c5 are already covered by the new schema
version S’. Consequently, the new version CB’ of case-base CB is built by mi-
622 B. Weber et al.
grating only cases c3 and c6. Of course, new cases may be added to CB’ due to
ongoing ad-hoc changes of instances based on S’. Again, the migration of this
case-base will become necessary if another process schema migration takes place
later on. In our example, type change ∆T2={deleteAct(S’,F)}is triggered by
case c7 which exceeds a certain frequency freq (55). The resulting case-base
CB” is shown in Fig. 5.
5 Related Work
This paper is based on the idea of integrating PMS and CCBR. In related work
CBR has been applied to support process modeling [18,19], to the configuration
of complex core processes [20], to the handling of exceptions [21] and for the
composition of Web Services [22]. All of these approaches apply traditional CBR,
to our knowledge there are no other approaches relying on CCBR.
Related work also includes adaptive process management. Existing approaches
either support ad-hoc changes at the process instance level or schema modifica-
tions at the process type level (for an overview see [3]). Except for ADEPT [12]
none of these approaches considers both kinds of changes in an integrated man-
ner. In particular the full life cycle support using CCBR techniques has not been
addressed so far. Though CBRFlow [9] fosters the reuse of ad-hoc changes, it has
not yet considered process type changes. This gap is closed by the integration of
ADEPT and CBRFlow.
AI planning, especially mixed-initiative case-based planning (e.g., NaCo-
DAE/HTN [23], MI-CBP [24], SiN [25] and HICAP [26]) can be seen as com-
plementary to our approach as we primarily focus on the execution of processes
and not on modeling or planning. Process management approaches rely on a pre-
defined process schema (i.e., plan) that is instantiated during run-time in high
numbers. In contrast, in AI planning the user is supported in generating a new
plan for every new problem situation, which prevents the problem of having to
change other running instances of the same plan. Other than in AI planning our
meta-model supports complex control flow constructs (e.g., conditional branch-
ing, loop backs, and synchronizations between parallel execution branches).
Process-based knowledge management systems are suitable for knowledge
intensive workflows and are often used to provide additional process informa-
tion to the user in order to support them during the execution of activities
(e.g., DECOR [27], FRODO TaskMan [28], KnowMore [29]). FRODO TaskMan
extends the approach taken in KnowMore by supporting integrated modeling
and enactment of weak workflows. Like our approach, FRODO TaskMan allows
instance level modifications of the workflow during run-time, but does not sup-
port process type changes. Additionally it supports working with an incomplete
process schema due to its late modeling capabilities.
6 Summary and Outlook
The integration of ADEPT and CBRFlow offers promising perspectives. It re-
sults in a new generation of adaptive process technology, which facilitates and
CCBR–Driven Business Process Evolution 623
speeds up the implementation of new as well as the adaptation of existing pro-
cesses. Both, the capability to quickly and correctly propagate type changes to
in-progress process instances as well as the intelligent support of ad-hoc adapta-
tions will be key ingredients in next generation PMS, resulting in highly adap-
tive PAIS. Currently, we are working on the implementation of a prototype that
combines the methods and concepts provided by ADEPT and CBRFlow. Fu-
ture research will include the evaluation of this approach in different application
settings, like healthcare processes and emergent workflows (e.g., in the automo-
tive domain). Our future research will include the extension of the presented
approach towards agile process mining, i.e., fostering to start with a simple, in-
complete process schema and then learn from the living processes to evolve the
schema over time.
References
1. Reichert, M., Dadam, P.: ADEPTflex - supporting dynamic changes of workflows
without losing control. JIIS 10 (1998) 93–129
2. Jørgensen, H.D.: Interactive Process Models. PhD thesis, Norwegian University of
Science and Technology, Trondheim, Norway (2004)
3. Rinderle, S., Reichert, M., Dadam, P.: Correctness criteria for dynamic changes in
workflow systems – a survey. Data and Knowledge Engineering 50 (2004) 9–34
4. Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workflow evolution. Data and Knowledge
Engineering 24 (1998) 211–238
5. v.d. Aalst, W., Basten, T.: Inheritance of workflows: An approach to tackling
problems related to change. Theoret. Comp. Science 270 (2002) 125–203
6. Rinderle, S., Reichert, M., Dadam, P.: Flexible support of team processes by
adaptive workflow systems. Distributed and Parallel Databases 16 (2004) 91–116
7. Rinderle, S., Reichert, M., Dadam, P.: On dealing with structural conflicts between
process type and instance changes. In: Proc. BPM’04. (2004) 274–289
8. Rinderle, S., Reichert, M., Dadam, P.: Disjoint and overlapping process changes:
Challenges, solutions, applications. In: Proc. Int’l Conf. on Cooperative Informa-
tion Systems (CoopIS’04). LNCS 3290, Larnaca, Cyprus (2004) 101–120
9. Weber, B., Wild, W., Breu, R.: CBRFlow: Enabling adaptive workflow manage-
ment through conversational case-based reasoning. In: Proc. European Conf. on
Cased based Reasoning (ECCBR’04), Madrid (2004) 434–448
10. Aha, D.W., Breslow, L., Mu˜noz-Avila, H.: Conversational case-based reasoning.
Applied Intelligence 14 (2001) 9–32
11. Reichert, M.: Dynamic Changes in Workflow-Management-Systems. PhD thesis,
University of Ulm, Computer Science Faculty (2000) (in German).
12. Rinderle, S.: Schema Evolution in Process Management Systems. PhD thesis,
University of Ulm, Computer Science Faculty (2004)
13. Kolodner, J.L.: Case-Based Reasoning. Morgan Kaufmann (1993)
14. A. Aamodt, E.P.: Case-based reasoning: Foundational issues, methodological vari-
ations and system approaches. AI Communications 7(1994) 39–59
15. Aha, D.W., Mu˜noz-Avila, H.: Introduction: Interactive case-based reasoning. Ap-
plied Intelligence 14 (2001) 7–8
16. Cheetham, W., Price, J.: Measures of solution accuracy in case-based reasoning
systems. In: Proc. European Conf. on Case-Based Reasoning (ECCBR’04). LNCS
3155, Madrid (2004) 106–118
624 B. Weber et al.
17. eBAY: Feedback Forum. (2005)
http://pages.ebay.com/services/forum/feedback.html.
18. Kim, J., Suh, W., Lee, H.: Document-based workflow modeling: a case-based
reasoning approach. Expert Systems with Applications 23 (2002) 77–93
19. Madhusudan, T., Zhao, J.: A case-based framework for workflow model man-
agement. In: Proc. 1st Int’l Conf. on Business Process Management (BPM’03),
Eindhoven (2003) 354–369
20. Wargitsch, C.: Ein Beitrag zur Integration von Workflow- und Wissensmanagement
unter besonderer Ber¨ucksichtigung komplexer Gesch¨aftsprozesse. PhD thesis, Er-
langen (1998)
21. Luo, Z., Sheth, A., amd J. Miller, K.K.: Exception handling in workflow systems.
Applied Intelligence 13 (2000) 125–147
22. Limthanmaphon, B., Zhang, Y.: Web service composition with case-based reason-
ing. In: Proc. of 15th Australasian Database Conf. (ADC’02), Australia (2002)
23. Mu˜noz-Avila, H., McFarlane, D., Aha, D., Ballas, J., Breslow, L., Nau, D.: Using
guidelines to constrain interactive case-based htn planning. In: Proceedings of the
Third International Conference on Case-Based Reasoning, Munich (1999) 288–302
24. Veloso, M., Mulvehill, A., Cox, M.: Rationale-supported mixed-initiative case-
based planning. In: Proceedings of the Ninth conference on Innovative Applications
of Artificial Intelligence, Providence, Rhode Island (1997) 1072–1077
25. Mu˜noz-Avila, H., Aha, D., Nau, D., Breslow, L., Weber, R., Yamal, F.: Sin: In-
tegrating case-based reasoning with task decomposition. In: Proc. IJCAI-2001,
Seattle (2001) 99–104
26. Mu˜noz-Avila, H., Gupta, K., Aha, D., Nau, D.: Knowledge Based Project Plan-
ning. In: Knowledge Management and Organizational Memories. Kluwer Academic
Publishers (2002)
27. Abecker, A., et al.: Enabling workflow-embedded OM access with the DECOR
toolkit. In Dieng-Kuntz, R., Matta, N., eds.: Knowledge Management and Orga-
nizational Memories. Kluwer Academic Publishers (2002)
28. Elst, L., Aschoff, F., Bernardi, A., Maus, H., Schwarz, S.: Weakly-structured work-
flows for knowledge-intensive tasks: An experimental evaluation. In: Proc. 12th Int’l
Workshop on Enabling Technologies. (2003) 340–345
29. Abecker, A., Bernardi, A., Hinkelmann, K., O. K¨uhn, O., Sintek, M.: Context-
aware, proactive delivery of task-specific knowledge: The KnowMore project. Int.
Journal on Information Systems Frontiers 2(2000) 139–162
