UNIVERSITY OF ULM
Faculty of Computer Science
Department of Database and Information Systems
U
N
I
V
E
R
S
I
T
Ä
T
U
L
M
·
S
C
I
E
N
D
O
·
D
O
C
E
N
D
O
·
C
U
R
A
N
D
O
·
Emergent Workow
Diplomarbeit
presented by
Florian Bertele
Thesis advisers: Prof. Dr. Manfred Reichert
Prof. Dr. Peter Dadam
April 2005
Abstract
Many elds of work require information systems that supp ort an organization in man-
aging its complex pro cess-aligned business. However, the exibility of pro cess creation
and enactment oered by current workow management systems is often insucient. As
a consequence these systems are not broadly used and suer from low acceptance. Agile
pro cesses that involve creative work are hardly supp orted as requirements changes and
exceptional situations o ccur frequently. Emergent Workow is an approach that tries to
overcome these deciencies by capturing the current pro cess instantly as it
emerges
out of work and oering immediate supp ort to workow participants. Its goals are
the retainment of organizational knowledge, improved reuse of individual work patterns
and a b etter transparency of the overall pro cess. This thesis rst motivates the sub-
ject by intro ducing a eld of application in automotive pro duct development. Typical
comp onents of an Emergent Workow Management System are identied and their re-
quirements as well as a pro cess mo del are sp ecied. Then related work is presented and
matched against these requirements. The thesis closes with a conceptual architectural
prop osal and discusses some issues of feature integration and implementation.
Contents
1. Intro duction 1
1.1. Motivation................................... 1
1.2. Vision of Emergent Workow . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3. Application example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Terminology.................................. 9
1.5. Organization of this thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2. Requirements 12
2.1. Usecases ................................... 12
2.2. Comp onent overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3. Comp onent-based requirements . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1. User interfaces/Client application . . . . . . . . . . . . . . . . . . 17
2.3.2. Server interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3. Dictionary............................... 20
2.3.4. Organizational mo del . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.5. Time management . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.6. Pro cess creation engine . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.7. Runtimeengine ............................ 33
2.3.8. Pro cess matching engine . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.9. Repository............................... 49
2.3.10. Requirements summary . . . . . . . . . . . . . . . . . . . . . . . . 51
2.4. Processmetamodel .............................. 53
2.4.1. Pro cess denitions . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4.2. Pro cess instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.4.3. Pro cess comp ositions . . . . . . . . . . . . . . . . . . . . . . . . . 62
3. Related approaches 66
3.1. Case-based reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.1.1. Fundamentals ............................. 66
3.1.2. Applications.............................. 70
3.1.3. Assessment of usefulness . . . . . . . . . . . . . . . . . . . . . . . 82
3.2. Processmining ................................ 83
3.2.1. Fundamentals ............................. 83
3.2.2. Multi-phase pro cess mining . . . . . . . . . . . . . . . . . . . . . 87
3.2.3. Assessment of usefulness . . . . . . . . . . . . . . . . . . . . . . . 88
i
Contents
3.3. Flexibility approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3.1. Schema evolution and propagation . . . . . . . . . . . . . . . . . 89
3.3.2. Ad-ho c instance change . . . . . . . . . . . . . . . . . . . . . . . . 92
3.3.3. Integration of schema evolution and ad-ho c instance mo dication 96
3.3.4. Assessment of usefulness . . . . . . . . . . . . . . . . . . . . . . . 98
4. Architectural prop osal 100
4.1. Stage 1 Basic functionality . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.2. Stage 2 Advanced functionality . . . . . . . . . . . . . . . . . . . . . . 103
4.3. Stage 3 Full functionality . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5. Discussion 110
6. Conclusion 115
6.1. Summary and conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.2. Omitted and future work . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
A. Supplementary Listings and Figures 117
A.1.CODAW.................................... 117
A.1.1. Pro cess data mo del . . . . . . . . . . . . . . . . . . . . . . . . . . 117
A.1.2. Instance level workow schema . . . . . . . . . . . . . . . . . . . 119
Bibliography 120
ii
1. Intro duction
1.1. Motivation
To day, entrepreneurial success is determined by b oth external and internal factors. As
the economic comp etition grows harder, companies face several external challenges. The
high innovation sp eed in research and pro duction leads to shorter pro duct life cycles and
less development time. Markets tend towards going global and oer more choice for cus-
tomers. Thus customers' exp ectations towards comp etitive pricing, quality, p erformance
and exibility of pro ducts rises as well. Internally, pro duction and development gets more
and more complex with each generation. To handle that complexity, sta b ecomes highly
diverse and develops sp ecic knowledge in each department. That makes it harder to
aggregate each individual's work and to communicate common goals. Obviously, com-
plicated pro ducts cause complicated corp orate structures. That is why companies have
come to extend their fo cus from a pro duct-oriented view to a more pro cess-oriented
view.
By aligning business in a
process-oriented
manner, inputs, outputs and relationships
b etween activities have to b e identied. Formalizing these elements helps to break down
the corp orate strategy into op erations and claries their relation. The pro cess itself of
creating explicit pro cess mo dels and visualizations fosters a more in-depth understanding
of collab oration and the ow of do cuments, pro ducts and work. A more transparent
p erception helps to sp ot chances to increase eciency such as eliminating redundant
work, defective pro ducts or reducing cycle times. According to Jablonski and Bussler
[JB96], the exp ected b enets are among others improved quality of service, improved
pro ductivity and cost reduction and reduced vulnerability of the work pro cess.
Workow management systems
have b een intro duced in order to give technological sup-
p ort to the idea of business pro cesses. They are software systems dedicated to manage
the steps involved when dealing with business pro cesses, such as mo deling or assigning
tasks. A workow management system is meant to encapsulate all pro cess logic within
a corp orate information technology system.
The classical mo del of a
business process life cycle
is depicted in Figure 1.1.
Process
design
is the task of distilling a pro cess mo del from a set of informal business require-
ments. It involves the denition and selection of appropriate tasks (p ossibly from a
task library), sequencing of the tasks to satisfy data and logical dep endencies, allo ca-
tion of resources consumed by tasks, allo cation of agents to execute tasks, scheduling
of tasks considering concurrency, and nally validation and verication of the mo del.
1
1. Intro duction
Diagnosis
Process
design
System configuration
Process
enactment
Figure 1.1.: The business pro cess life cycle (compare [Aal02] Figure 2)
During
system conguration
, an initial business pro cess is implemented and deployed in
the workow management system. In the following
enactment phase
instances of the
implemented mo dels are created and executed. A pro cess instance passes a numb er of
states by initiating its tasks. The conditions and sequence of task execution is stated in
the pro cess schema as well as a terminal state. After enactment, the pro cess instance
history is
diagnosed
for analysis and improvement. Conclusions drawn from that phase
inuence the next
process (re)design phase
.
However, workow management systems have not b een accepted widely in pracice b een
[HSW97]. Multiple reasons can b e found for that: Technology sometimes has not b een
proven to b e mature enough for corp orate-wide deployment. On a managerial level
p eople may b e not convinced of the p ositive eects a workow management system has
on eciency and see primarily high investments. As most activities of employees can
b e individually controlled and monitored by information systems, acceptance problems
b ecome apparent as well. People feel observed or are afraid of doing "oce assembly-line
work" due to the high degree of work assignment automatization. The most profound
deciency though is the lack of exibility in most commonly used workow management
systems.
Dep ending on the typ e of work and op erational business, it is quite common that, from
time to time, the pro duct or the pro duction pro cess needs to b e changed. Exceptional
situations o ccur that have to b e treated separately. These might b e caused due to
internal or external events, such as sp ecial arrangements with a customer or extra quality
checks due to legislative changes. Very often it is not p ossible to foresee all p ossible
exceptions during pro cess design, so the implemented workow mo del do es not cover
it. What happ ens most of the time is a treatment of such cases out of the system.
Activities are inserted, mo died or skipp ed manually without prop er do cumentation
the workow management system do es not know anything ab out the deviation from its
standard pro cedures. Such b ehavior leads into a situation where pro cesses (or what is
2
1. Intro duction
left of them) b ecome intransparent and the knowledge ab out them is incomplete or even
incorrect. Since this would practically reverse all eorts put into pro cess management,
exceptional situations need to b e taken care of dierently.
The correct resolution of an incomplete pro cess implementation is another reiteration
through the business pro cess cycle (see Figure 1.1): Let pro cess designers and sta diag-
nose the weaknesses, redesign their mo dels and get them implemented into the workow
management system. Furthermore running pro cess instances need to b e taken care of
separately to assure their conformance with the new mo del. That is a tedious and time-
consuming task that involves many rep orts, meetings and interviews. Design work and
communication b etween various groups of p eople leads to a certain degree of informa-
tion loss and p otential misunderstanding. If such changes app ear very frequently on
p otentially long-running pro cess instances, the eciency advantages of workow man-
agement system are mostly lost. Due to these shortcomings of conventional workow
management systems, we motivate the use of exible workow management.
A
exible workow management system
is able to adapt to changing requirements of its
users and their work items, particularly during pro cess enactment. That includes the
consideration of exceptional situations, ad-ho c changes to workow instances, activities
and resources and workow schema alteration. Knowing that not even the most care-
fully pre-built pro cess mo del suits all p ossible future situations and later alterations are
unavoidable, a exible workow management system rather fo cuses on oering means
to extend or mo dify its b ehavior for all involved parties in an acceptable way. It do es
not force users to circumvent its limited capabilities outside the system, but lets them
do cument a change op eration and its context as well as p ossible.
1.2. Vision of Emergent Workow
Emergent Workow
envisions a exible workow management system with the capabil-
ity of building small-scale workows during pro cess enactment without explicit pro cess
design.
There exist many elds of work which share characteristics such as b eing highly variable
and having low regularity patterns in their schema of activities. For instance, highly cre-
ative or knowledge intensive pro cesses like pro duct development fall into that category.
At the same time, those kind of pro cesses require close collab oration of many p eople from
several disciplines, each representing distinctive knowledge. There exist many dierent
views on one common pro ject, all of which need to b e integrated prop erly.
Intro ducing a workow management system into an environment like that is very promis-
ing due to the large amounts of implicit knowledge involved. Building an information
system that collects structured information ab out the pro cess and makes it available
for later reuse would yield the b enet of improving each individual's pro cess awareness
and pro ductivity. A higher work pace, work quality and learning curve are among the
3
1. Intro duction
p otential b enets.
However due to the nature of creative work, a small scale pro cess can hardly b e pre-
mo deled b ecause there do es not exist literally one single regular case of reasonable
complexity. Rather, there is a rough framework whose detailed structure is sub ject
to continuous adaption due to sp ontaneous requirement changes.
As the exact pro cess logic is unknown until pro cess enactment, it is the approach of
Emergent Workow to capture the pro cess as it
emerges
from sp ontaneous p erformance
of activities. An explicit mo deling approach is impractical as it is b oth to o complicated
and to o time-consuming to b e done by p eople who are not dedicated pro cess designers.
The user rather do cuments their advancement in a more convenient and less formal way,
e.g. supp orted by a dialogue-based software. A partial pro cess mo del is then supp osed
to b e derived from an audit trail that do cuments users' activities.
Interesting uses for that information include do cumentation, reuse and comp osition. As
for do cumentation, recurring situations including their context and decisions made up on
them can b e reviewed to gain insights for future work. If a very similar situation o ccurs
in the future, it is even p ossible to reuse a previously recorded situation as a template
to guideline up coming activities. Finally, the collected set of small-scale pro cess parts
contains all information necessary to comp ose a view on the overall current pro cess.
This is particularly interesting to compare with a theoretically develop ed target pro cess
in order to nd characteristic dierences and chances for improvements.
1.3. Application example
In order to get a taste of what a typical application environment could lo ok like, an initial
example is intro duced. It helps understanding the ma jor questions that have to b e asked
and answered when considering the intro duction of Emergent Workow. Furthermore
the application scenario is used throughout the thesis to illustrate prop osed ideas.
The example intro duces an outline of a
new product development process
in the auto-
motive engineering sector. Automotive development is a relevant application eld for
Emergent Workow for a numb er of reasons. Mo dern automobiles are
mechatronic sys-
tems
machines whose comp onents comprise mechanical, electronical and information
technology asp ects. Their correlation is visualized in Figure 1.2 and the meaning of
mechatronics is dened by VDI [Ver04] as follows:
[
Mechatronics
is]...the synergetic integration of mechanical engineering
with electronic and intel ligent computer control in the design and manufac-
turing of industrial products and processes.
4
1. Intro duction
mechatronics
information
technology
electrical
engineering
mechanical
engineering
Figure 1.2.: Mechatronics as the interaction of dierent disciplines (compare [Ver04] Fig-
ure 2-1)
It is crucial to notice that
synergetic eects
can not b e reached by indep endently op-
erating science groups but take their p ower from co op eration with each other. That
implies consequent synchronization b etween the disciplines to establish a common view,
language and understanding of development issues.
The driving force b ehind interests in mechatronic systems is the fast paced innovative
p otential in information technology. On the one hand it is due to the exp onential ad-
vancements of pro cessing p ower and memory with concurrently decreasing costs and size
at the same time. On the other hand the functional and spatial integration of technolo-
gies unleashes p otential improvements concerning functionality, absolute p erformance
and price-p erformance ratio as well as b etter b ehavior.
In an automobile, electronic and information pro cessing comp onents are built on top of a
mechanical structure. This structure would suggest a sequential development pro cedure
which is not practical in reality though b ecause of its very time-consuming nature. For
eciency reasons it is rather desirable to have a continuous, distributed development
and cross-domain co op eration at the same time. A
digital mock-up
is a widely used
to ol in pro duct development to achieve that ob jective. It is a virtual prototyp e used
by all involved disciplines to simulate and test the most imp ortant physical and other
functional asp ects.
As development pro cedures can not b e pinned down to one single b est mo del, the com-
bination of the following patterns oers more exibility:
5
1. Intro duction
•
General problem-solving as a micro cycle
•
V mo del styled macro cycle
Problem-solving as a micro cycle
The problem-solving cycle shown in Figure 1.3
applies to small-scale pro cedures and comprises several comp onents. The starting p oint
is either a
situation analysis
or the
adoption of a goal
, dep ending on whether a pre-
existing structure is adopted or new structures are built from scratch. After the situation
has b een analyzed with a given structure, a goal can b e formulated from given input.
In case an ideal concept is the starting p oint, these goals are adopted rst and situation
analysis starts from there.
During
analysis
and
synthesis
, a solution for the given problem is researched. Both
activities analysis and synthesis are alternating: The rst develops solution alternatives
which are then checked, improved or rejected during synthesis of the results. By iterating
these steps, improved solutions are eventually found.
The nal
analysis and assessment
step evaluates the solution alternatives found in more
detail. An assessment with regard to the initial goal formulation leads to either a pro-
p osal or a recommendation for one or more prop osed solutions.
During
decision
, one compares the overall success of pro cedures which have shown sat-
isfactory result so far. It either ends in a return to another goal formation if the results
were not convincing or a favorite solution is chosen.
Planning for further procedure
or
learning
makes sure that, at the end of one micro-
cycle, the eorts made so far are carefully reviewed and evaluated. Learning ab out the
go o d and bad p oints from the past cycle helps to improve further planning. That leads
to a systematic improvement of future pro cesses.
V mo del
The V mo del is a macro-cycle that formulates in contrast to a micro-
cycle a view on the overall development pro cess. In Figure 1.4 multiple iterations of
macro-cycles are shown.
The pro cess starts at the entry p oint of the innermost cycle on its left side. From there,
each iteration b egins with a formulation of its resp ective
requirements
. They sp ecify the
goals of the macro-cycle in detail and are used as a comparative measure for outcomes.
During
system design
, develop ers establish cross-domain concepts for solutions. That
is achieved by decomp osition of ma jor system functionalities, nding solution elements
and recomp osing these into an overall solution concept.
The
domain-specic design
phase is used by each discipline individually to elab orate
on solutions that had b een outlined during
system design
. Solutions are substantiated
in more detail which requires separate mo dels and views for mechanical, electrical and
information engineering each.
6
1. Intro duction
Synthesis
Analysis
Goal formation Situation analysis
Adoption of goalSituation analysis
Analysis and assessment
Decision
Planning for
further
procedure
Learning
- develop
alternatives for a
solution
- check, improve,
reject solutions
Procedure based
on actual state
(existing structure is
taken as a basis)
Procedure based
on desired state
(ideal concept is at
the forefront)
Figure 1.3.: Problem-solving as a micro-cycle (compare [Ver04] Figure 3-1)
7
1. Intro duction
Degree of maturity
Requirements Product
Entry
Degree of maturity
Assurance
of
properties
System design
System design
System design
System
integration
System integration
System integration
Mechanical engineering
Electrical engineering
Information engineering
Mechanical engineering
Electrical engineering
Information engineering
Mech. eng.
Electrical eng.
Inform. eng.
Quality gate
Figure 1.4.: V-mo del styled macro cycles with increasing pro duct maturity (compare
[Ver04] Figures 3-2 and 3-3)
8
1. Intro duction
System integration
nally consolidates all partial solutions and investigates their inter-
action. An imp ortant part of integration is the
assurance of properties
as indicated in
Figure 1.4 by arrows p ointing from right to left. As integration pro ceeds, its results
are continuously checked back with the solution concepts built during
system design
.
Furthermore, their compliance with the initial requirements has b e assured.
A macro-cycle iteration results in a
product
. This can b e either the nal pro duct which is
ready to b e released or just an intermediate pro duct such as a certain prototyp e stage. As
complex pro ducts require usually several macro-cycles for development, an intermediate
product
has to pass a
quality gate
to pro ceed to the next development cycle. A
quality
gate driven process
ensures the quality level of outcomes at a certain stage by dening
detailed requirements that have to b e met b efore entering the next stage. After passing
the quality gate, the next set of
requirements
gives the agenda for the next macro-cycle
and the next quality gate. With each additional macro-cycle, the
product maturity
in
terms of completeness and correctness increases until the last cycle outputs the nal
pro duct.
The
V model
and the
problem solving micro-cycle
indicate that Emergent Workow
is a promising approach in automotive development. On the one hand, the overall
pro cess has a coarse xed structured dened by iterating through
quality gates
. On the
other hand, small-scale problem solving app ears frequently, is individually determined
by the context and has little rep etitive structure. Still, there are exp ected b enets
from reusing previously applied pro cedures. Supp ose a construction detail such as an
advanced window p ower lifter. It may have already b een implemented in a premium
class mo del line successfully and is ab out to b e adopted for the next generation of a
compact car. The pro cesses and insights recorded while integrating the p ower lifter in
the premium car can save eorts by b eing reused for its integration in the compact car.
1.4. Terminology
While talking ab out a sp ecic eld of application, we have used a lot of terms without
exactly sp ecifying their meaning. This sections purp ose is to intro duce the terminology
that will b e used most commonly throughout the subsequent chapters. The following
denitions and explanations were established by the Workow Management Coalition
in "Terminology & Glossary" [Wor99] resp ectively taken from [AH02, WRWR05]. We
will adapt their interpretation in the following paragraphs.
A
business process
is a set of pro cedures and activities, which collectively realize a
business objective
such as the construction of a new car generation. These pro cedures
and activities are linked by various relations, e.g. temp oral or causal dep endencies.
A
workow
is the automation of a business pro cess, in whole or partially. A set of pro-
cedural rules manage the exchange and distribution of do cuments, information or tasks.
Strictly sp eaking, the term workow refers to the subset of pro cesses which are sup-
9
1. Intro duction
p orted by
information technology
. Since however the dierentiation of a pro cess versus
a workow is not crucial in the light of this thesis, I will mostly use b oth terminologies
synonymously.
The execution of workows is dened, created and managed by a
workow management
system
. By the use of software it runs on one or more
workow engines
. These are
able to interpret formal
process denitions
, interact with
workow participants
(also
called
workow users
) and, where required, invoke the use of applications and other
information technological to ols. A workow participant is a human or machine-based
agent that constitutes a resource which p erforms work represented by a workow activity
instance. A workow management system that meets the requirements discussed in
Chapter 2 will b e referred to as an
Emergent Workow Management System
.
The automation of a workow is dened within a
process denition
. It is the represen-
tation of a business pro cess in a form which is supp orted for automated manipulation,
such as mo deling or enactment by a workow management system. A pro cess denition
holds a certain
process type
. The typ e is sp ecied by a
process schema
which denes
the pro cess structure. The schema consists of a network of tasks and their relationships,
constraints to indicate the start and termination of the pro cess and information ab out
individual activities, such as participants, asso ciated applications and data, etc.
A business pro cess is structured by the identication of logical steps. Each atomic
step is referred to as a
task
. A task is p erformed by the execution of an instance-sp ecic
activity
. During execution, an activity passes a sequence of dened states. Activity state
traversal can b e either workow automated or manual without information technology
supp ort. A workow activity requires human and/or machine resources to supp ort
workow execution. Where human resources are required, an activity is allo cated to a
workow participant.
A
process instance
is a pro cess denition with individually allo cated resources and ac-
tivity states for all tasks it contains. The set of activity states denes the execution
state of a pro cess instance. During
process enactment
, a pro cess denition is b oth in-
stantiated and executed. That is, a pro cess denition with an individual pro cess state
and its resources are allo cated and an initial state transition is p erformed in order to
indicate the instance's readiness. In literature, pro cess instances are often referred to as
cases
1
. In this thesis, we will stick to the term pro cess instance in order not to confuse
it with the term case used in case-based reasoning (see Section 3.1).
Many individual
process instances
may b e op erational during pro cess enactment. Each
pro cess instance is the representation of one single enactment of a pro cess denition and
may b e controlled indep endently. It has its own internal state and externally visible
entity. A workow management system creates and manages a pro cess instance for each
separate invo cation of the pro cess denition.
A
worklist
is a list of
work items
which are asso ciated with a given workow participant.
1
e.g. by van der Aalst et al. in [AH02]
10
1. Intro duction
Each work item is a representation of a task which has b een scheduled for execution in
the context of an activity within a pro cess instance. The worklist represents a part of
the interface b etween a workow engine and the
worklist hand ler
, a software comp onent
that manages the interaction b etween the user and the worklist. It enables work items
to b e passed from the workow management system to users and forwards notications
of completion or other work status conditions.
1.5. Organization of this thesis
Up to now,
Chapter one
has motivated and intro duced the sub ject around Emergent
Workow. After a
motivation
of business pro cess management in conjunction with work-
ow management, the
vision
of Emergent Workow is presented. A characterization of
a p ossible eld of
application
follows. The Chapter closes with an intro duction and clar-
ication of the
terminology
most commonly used throughout the thesis.
Chapter two
presents the requirements on an Emergent Workow Management System in a struc-
tured manner. First, typical
use cases
are identifed, from which a
component overview
is
concluded. Then detailed
requirements on each individual component
are elab orated. A
tabular
requirements summary
gives a brief statement on the most noticeable p oints of
the comp onent's requirements. The Chapter closes with a sp ecication of characteristics
for a suitable pro cess metamo del.
Chapter three
presents related work approaches to
Emergent Workow.
Case-basd reasoning
,
process mining
and
exibility approaches
are
intro duced and assessed with resp ect to their usefulness for Emergent Workow.
Chap-
ter four
contains an
architectural proposal
for an Emergent Workow Management
System presented in
three stages
.
Chapter ve
discusses
functional issues of integra-
tion
. Finally,
Chapter six
contains a
summary
of the presented work, a
conclusion
and
mentions
future and omitted work
.
11
2. Requirements
In order to receive functionalities as describ ed in the vision of Emergent Workow,
certain requirements have to b e met. This Chapter attempts to explore these and lay
out some details ab out them. First, an overview of typical use cases identies user groups
and their interaction with system comp onents. That information is used as a starting
p oint for a more complete illustration of all generic comp onents of Emergent Workow.
From there, each mentioned comp onent is further elab orated concerning its interfaces,
functionalities and constraints. After a summary of comp onent-oriented requirements,
requirements on an underlying pro cess metamo del follow.
2.1. Use cases
Pro cess design
Although Emergent
Workow aims at a more sp ontaneous
creation of pro cess mo dels, pre-mo deled
pro cesses can not b e left out in practice: On
the one hand, they may b e still used as a
starting p oint for pro cess development and
on the other hand a coarse, big scale pro cess
mo del can b e used for exible workows as
well.
Example 1.
The
V model
depicted in
Figure 1.4 shows the common pro cedures
for automotive development. Although it
is a highly creative pro cess, there is a rigid
framework of steps to take during develop-
ment: There is a numb er of quality gates
to pass, each with a dedicated design phase,
discipline-sp ecic problem solving and a -
nal integration phase.
Before enactment, a dedicated pro cess de-
signer mo dels explicitly a more or less com-
plete pro cess mo del. It consists of the over-
all structure determined by a development
mo del and also generic pro cedures which
have standardized and rep etitive character.
This mo del is b eing formalized by the help
of a pro cess denition to ol and stored to the
rep ository.
Process
definition tool
Repository
Process
designer
stores process
model
Figure 2.1.: Use case: pro cess de-
sign
12
2. Requirements
Administration
A pro cess mo del is the
starting p oint for enactment of pro cess in-
stances. Instances may b e initialized by
users or an administrator using a
user in-
terface
to the
runtime engine
of the work-
ow management system. After the instance
is up and running, it is b eing managed by
the administrator until it reaches a termi-
nal state. Management includes observing
functions such as monitoring the progress
and state of instances, intervening in excep-
tional cases and overriding user interactions
as necessary.
User interface
Repository
Administrator
instantiates
process model
Runtime
engine
manages
instances
Figure 2.2.: Use case: administra-
tion
Usage & creation
A workow user is
someone whose work is co ordinated by a
workow management system. In Emergent
Workow, this p erson (or agent) do es not
only receive tasks from the runtime engine,
but is also involved in creation and adaption
of partial pro cesses. This is p ossible and
necessary as the exible approach of Emer-
gent Workow intends to give its users the
freedom for self-determining, thus creating
their own partial pro cess. So after the re-
ception of a task through a
user interface
or a
client application
, the participant p er-
forms the steps necessary to complete the
task. His actions are b eing formalized in an
interaction protocol
. This proto col contains
the information which is necessary to recon-
struct the user's individual pro cess fragment
in a
process creation engine
. Finally, this
fragment of a pro cess instance is stored to
the
repository
.
Repository
User &
Creator
Runtime
engine
creates
interaction
protocol
Process
creation
engine
assignment of
tasks
stores process
fragments
User interface/Client application
Figure 2.3.: Use case: usage & cre-
ation
13
2. Requirements
Comp osition
Having stored these pro cess
fragments, the pro cess designer can now go
ahead and comp ose these elements into big-
ger comp ositions. These foster the under-
standing of the coherence of collab orative
work and can b e used either for do cumen-
tation or as a template for big-scale pro cess
redesign. As there are probably many frag-
ments available in the
repository
, a designer
needs the supp ort of a
process matching en-
gine
comp onent which assists him nding
relevant fragments. These are comp osed in
a
process modeling tool
and resulting com-
p ositions are stored to the
repository
.
Process modeling tool
Repository
Modeling &
Composition
Process
matching
engine
stores
composition
queries
fragments and
models
specification of
model
properties
Figure 2.4.: Use case: comp osition
Usage & reuse
Once the
repository
is
lled with pro cess fragments, a workow
user may now cho ose to make use of them.
So when the
runtime engine
assigns him
with a task that turns out to b e similar to a
task which has b een pro cessed in the past,
the user may cho ose to follow similar pro-
cedures again. Thus, he will rely on the
process matching engine
to nd a template
in the form of a stored pro cess fragment.
That template guides him at a chosen level
of interactivity through the pro cedures. As
it is in creative pro cesses likely that sp onta-
neously formed pro cesses slightly dier from
each other, deviations from the templates
o ccur and are recorded again in an
interac-
tion protocol
. As b efore, the trail is trans-
formed by the
process creation engine
into a
new fragment and stored to the
repository
.
User interface/Client application
Repository
(Re-)User
Runtime
engine
creates
interaction
protocol
Process
creation
engine
assignment
of tasks
stores process
fragments
Process
matching
engine
searches
templates
queries
fragments
Figure 2.5.: Use case: (re-)usage
14
2. Requirements
Do cumentation
The last distinguished
use case is the role of do cumenting work.
Pro cess fragments can b e do cumented al-
ready at run time with annotations, how-
ever separate do cumentation may summa-
rize the most imp ortant insights from a p ost-
ho c p oint of view. These records may re-
quire references to pro cess fragments as they
were derived during the execution of the cur-
rent pro cess. Again, a
process matching en-
gine
is needed to sp ot the relevant fragments
and integrate them on the client side with
a
documentation tool
and store the results
back to the
repository
.
Documentation tool
Repository
Documentation
Process
matching
engine
stores
documentation
queries
fragments and
models
specification of
model
properties
Figure 2.6.: Use case: do cumenta-
tion
2.2. Comp onent overview
While enumerating use cases, basic comp onents of Emergent Workow were mentioned.
In order to receive a more complete understanding of all the comp onents involved, this
section gives a short overview of them. As the usefulness of a workow management
system is not only determined by its functions but also by its ability to interact with
external entities, a set of standardized interfaces has b een dened by the Workow
Management Coalition. Their Reference Mo del [Hol95] is shown in Figure 2.7.
The mo del generalizes the idea of a runtime engine to a
workow enactment service
, as
such could p otentially contain multiple workow engines. This service is encapsulated
by a Workow API and interchange formats which are the results of standardization
eorts by the Workow Managements Coalition.
It distinguishes ve interfaces in total:
Interface 1: Pro cess denition to ols
This is the interface used during pro cess design
phase by pro cess designers to transfer develop ed pro cess mo dels to the workow
management system.
Interface 2: Workow client applications
All workow-related user interaction is di-
rected over this interface. Typically this includes client applications that manage
assigned work items for users and up dates the system ab out work progress.
15
2. Requirements
Process definition
tools
Administration &
Monitoring tools
Invoked
applications
Workflow client
applications
Workflow API and interchange formats
Workflow enactment service
Workflow
engine(s)
Other workflow enactment
service(s)
Workflow
engine(s)
Interface 1
Interface 5
Interface 2 Interface 3
Interface 4
Figure 2.7.: Workow Reference Mo del (compare [Hol95] Figure 6)
Interface 3: Invoked application
This interface addresses third-party applications which
are invoked server-side by the workow enactment service such as Enterprise Re-
source Planning software.
Interface 4: Other workow enactment service(s)
Cross-organizational workow b e-
comes a hot issue when a combination of services oers additional b enets. This
interface serves the purp ose of enabling interop erability b etween various typ es of
workow management systems. They exchange use and control data, enable syn-
chronization and virtually merge indep endently created and executed pro cesses.
Interface 5: Administration & monitoring to ols
Administration and monitoring is a
default requirement for any workow management system. Therefore, a generic in-
terface is dened which allows the use of non legacy applications for administration
and monitoring.
Figure 2.8 gives an overview of all identied Emergent Workow comp onents. Three
groups of comp onents were identied and aligned in an interface, logic and data layer
each.
Interface
comp onents direct and format relevant input or output data. Comp o-
nents for the application
logic
pro cess data and forward outputs to the other two layers.
The
data
layer nally handles storage of data.
16
2. Requirements
Repository
Process
matching
engine
Runtime
engine
Process
creation
engine
Logic
Interfaces
Data
Dictionary
Organizational model
Time management
External applications
External WfMS
Client Server
User interfaces/
Client application
Figure 2.8.: Emergent Workow comp onents
2.3. Comp onent-based requirements
In the following Sections, the desired functionality of all mentioned comp onents is ex-
plained and functional as well as nonfunctional requirements are derived.
2.3.1. User interfaces/Client application
A user interface represents all users' access p oint to the Emergent Workow Manage-
ment System. Notice that we summarize interfaces 1, 2 and 5 from Figure 2.7 into
this generic Section ab out user interfaces/client application. Hence three dierent user
groups, workow participants, designers and administrators apply varying functional and
nonfunctional requirements on this interface. They have b een combined into this section
as a detailed sp ecication of functional requirement of applications used by designers
and administrators is not a p oint of emphasis in this thesis.
Functional requirements
Administrators
require applications that allow them to con-
trol the workow management system with sp ecial fo cus on the runtime engine. Asp ects
such as instantiation, execution, termination of instances as well as their p ermanent
placement in an archive are to b e monitored and inuenced as necessary.
Process de-
signers
analyze, create and comp ose pro cess mo dels. Hence their client applications are
to provide supp ort when retrieving running or archived pro cess instances and during
the creation or comp osition of pro cess mo dels.
Human workow participants
(from this
p oint on also referred to as "the" users) require client applications that receive incoming
work items representing tasks, manage this set of tasks using a worklist handler, help
them do cument their work and return status information to the system, such as when
the user has started or nished their job on one work item. Non-human workow par-
ticipants referred to as
agents
have sp ecial requirements regarding a machine-readable
interface, but b ehave generally very similar to human users and are therefore not further
17
2. Requirements
considered here.
A
user interface
is either referred to as a part of the
client application
or represents the
client application itself, commonly dep ending on whether there is enough application
logic present at the client: A to ol that graphically lists all incoming work items is usually
called an user interface, whereas a version of this to ol supplemented with functionality
for execution and manipulation is rather called an application. In b oth cases, their
app earance is critical to the acceptance of the whole workow management system.
That is, nonfunctional asp ects determine whether a software system is understo o d and
controlled by users to its fullest extent or its features are mostly ignored and worked
around.
Application integration levels
describ e the functional level on which client applications
can access a workow management system's functionality and vice versa. At a mini-
mum integration level, the runtime engine may receive the ability to start/stop a client
application up on the start/stop of an activity. In a second level, startup parameters
can additionally b e handed over to a client application which itself hands back a return
value up on its termination. At the next level, the ability to pass data ob jects as input or
output for the application may b e added. The highest level of integration of a workow
management system and a client application represents a mo dule or macro call typ e
of access directly through the client's resp ectively the workow management system's
API (Application Programming Interface). The implemented level of integration deter-
mines to a certain extent the ability to automatize a pro cess and thereby increase user
eciency.
Usability
User interfaces and usability in general are a wide eld of studies; this para-
graph do es not intend to claim completeness on this side asp ect of the thesis. It is rather
meant to provide a starting p oints and examples of ob jectives to consider. For a more
elab orate discussion of usability, appropriate literature exists
1
In order to help the novice or o ccasional user to make his rst steps with workow
management, an easy to use interface is substantial.
Intuitivity
and
simplicity
are two
very frequently mentioned nonfunctional requirements for any user interface. The rst
may b e describ ed as the ability of an interface to b ehave in all situations as exp ected by
its typical user. Simplicity is a very delicate issue, as it runs contrary to most functional
requirements: To give users a clear understanding of how they are supp osed to interact
and what their actions will infer. This goal is mostly reached by a low numb er of items
on the screen and predened screen sequences (such as "assistants" or "wizards") which
makes it hard to integrate a lot of functions in the interface. The simpler the interface,
the lower is the learning curve for its users to work at a high level of pro ductivity.
Additionally,
documentation
is an imp ortant asp ect in order to achieve acceptance for
1
For example Dix, Finley, Ab owd, Beale "Human-Computer Interaction" [DFAB98] or Shneiderman
"Designing the User Interface" [Shn98]
18
2. Requirements
a user interface. As a p ersistent and complete understanding of all asp ects of a user
interface is rather less likely for all p otential users, prop er do cumentation helps them to
answer raising questions on their own.
Conguration & customization
A system environment diers individually from client
to client: Invo cation of various third-party applications needs to b e
congured
individ-
ually on each system. Also, once a user b ecomes more advanced in using an interface,
he might want to mo dify its b ehavior in order to enhance his working sp eed. As there
is not one uniform user, there do es not exist one p erfect interface that meets all users'
needs as well. While an explanatory p op-up window is helpful for the novice user, it is
annoying and useless for the advanced user.
Customization
describ es those abilities of
an interface, e.g. to mo dify its lo ok-and-feel, toggle optional parameters, add keyb oard
shortcuts and adjust the level of interactivity.
Interaction proto col
Apart from user communication, the most imp ortant functional
requirement can b e seen from the use cases in Section 2.1. A user interface has to
propagate user interaction in the form of an
interaction protocol
back to the workow
management system. It is one of the key ideas of Emergent Workow to derive complete
or partial pro cess or instance mo dels from recordings of sp ontaneous ow of work. This
can only happ en if there exists sucient input which has b een generated on the client
interface layer. An adequate interaction proto col contain the sequence of actions of a
user including their context and mo died data ob jects. The more complete and con-
sistent user interaction can b e formalized, the more it is likely to come up with correct
conclusions regarding the current in-detail pro cess.
2.3.2. Server interfaces
Although this thesis do es not deal with server-side interfaces in-depth, for the sake of
completeness they are mentioned here shortly. Two interfaces assure the integration of
workow management systems into an existing and heterogeneous environment: One for
external workow management systems
, the other one for
external applications
.
Communication b etween workow management systems is motivated by a trend towards
closer collab oration b etween companies, such as along the value chain of a mo dular and
complex pro duct. The consequence is that companies using pro cess aligned information
technology start sharing certain p ortions of their internal pro cess in order to improve col-
lab oration. Cross-organizational workows are an example for the alignment of multiple
individual workows into one virtual big workow
2
.
2
Compare for example C. Bussler "The Role of B2B Protocols in Inter-Enterprise Pro cess Execution"
[Bus01] or Grefen et al. "CrossFlow: cross-organizational workow management in dynamic virtual
enterprises" [GAHL01]
19
2. Requirements
For interop erability, an XML based proto col Wf-XML has b een prop osed for run time
integration of pro cess engines
3
. Dierent levels of interop eration are separated dep end-
ing on the following scenarios: Co op eration may b e chained where output items are
passed on as input items for the next pro cess. A nested subpro cess can b e found where
a sub-task is p erformed by an external entity. A p eer-to-p eer organization describ es
indep endently acting entities that send work items as unsynchronized packets, whereas
in contrast to that a parallel synchronized top pro cess is established.
Non-workow external application integration of workow management is needed to put
the abstract view of pro cess instances into practice and execute them. Involved external
applications may b e as fundamental as a database system, an automotive pro duction
control system or as the classic example, enterprise resource planning software. There
exist applications which are "workow enabled" and those which are not; in the latter
case an intermediate "Application agent" is used, otherwise communication may function
directly. A standardized Workow Application Programming Interfacen (WAPI) for
synchronous/asynchronous access and data exchange has b een established
4
.
Analogue to the client interface, the creation of
interaction protocols
for all commu-
nication passing the server interfaces is a vital part for the functionality of Emergent
Workow. As user interaction is complemented by system reaction, b oth sides need to
b e recorded in order to draw a complete picture. Such systems do not only reside at
the client side, but primarily at the server side as the examples given in the paragraph
ab ove illustrate.
2.3.3. Dictionary
When many users do cument their work progress, their input is used to build formal
fragments of each individual's stake in the development pro cess inside the workow
management system. As dierent users may enter the same data redundantly or use
the same terminology in a dierent context, it is imp ortant to keep an eye on data
consistency. Without an explanation and knowledge of the eld of application, b enets
from having the pro cess do cumented are very limited. To avoid such ambiguities, it is
suggested to establish a common syntax for all terminology which is used to describ e
work and its outcomes. Otherwise it is not p ossible for the system to grasp commonalities
in related activities describ ed by dierent users, if they use heterogeneous terminology
for the same facts without sp ecifying the semantic contents of their vo cabulary.
Such confusion is avoided if all entered data is based on a previously or concurrently
dened common dictionary. It denes shared terminology and highlights relations b e-
tween terms like entities b eing synonyms, antonyms and homonyms. Authorized roles
should b e able to extend, mo dify and use this dictionary while do cumenting their work.
A well develop ed dictionary is very valuable as it b ears a formalization of various views
3
See Wf-XML 2.0 Current Draft: http://www.wfmc.org/standards/docs/WfXML20-200410c.pdf
4
See WAPI Version 2.0e Sp ecication: http://www.wfmc.org/standards/do cs/interface2-3.p df
20
2. Requirements
Keyword
Description
Author
Discipline
Project
group
Development
stage
used in
explained by
created by
has background in
is a member of
consists of
synonymous to
antonymous to
homonymous to
[custom relation]
Figure 2.9.: Dictionary entities
and references on the sub ject which is b eing worked on.
Figure 2.9 shows a exemplary view on entities which are most likely to b e chosen for a
dictionary in an automotive new pro duct development context. The core of a dictionary
is the set of keywords it contains. During any rather complex pro cess, it is very likely
that a large numb er of keywords is b eing used and thus the dictionary grows quite big.
In order to keep the dictionary still useful, it is essential to add supp ortive data in order
to categorize its content. If the context of a keyword is stored additionally, it is easy to
apply metho ds of data retrieval and mo dication just like in relational database systems.
The relevant context of a keyword is for example its description, which yields a textual
explanation of the key term. As the same word can b e used in several development
stages with dierent meanings, one keyword can have multiple descriptions. Moreover,
the author and his background regarding his discipline and role as well as the pro ject
group he is working in determines the usage and thereby the description of a keyword
as well.
Furthermore, relations b etween keywords themselves should b e expressed in a dictionary
as well. Common relations are "consists of", which sp ecies hierarchical dep endencies
b etween keywords, "is synonymous to" , "is antonymous to" and "is homonymous to".
Additionally, it is meaningful to allow pro cess designers to create custom relationships
21
2. Requirements
Window
power lifter
Group of components
which are involved in
opening/closing the
window of a door
ME
Designer
Bob
Sidedoor,
Integration
Stages >= 2
Side window
lifting gears
Side window
lifting toggle
button
Side window
lifting motor
ME
used in
explained by
created by
consists of consists of
has
background in
is a
member of
(a) Mechanical engineering view
Window
power lifter
Set of sensors and
actors that control the
movement of the side
window
EE
Designer
Jim
Sidedoor,
Integration
Stages >= 2
Sensor window
resistance
Sensor control
button
Actor window
motor control
Sensor window
position
EE
used in
explained by
created by
consists of consists of
has
background in
is a
member of
(b) Electrical engineering view
Figure 2.10.: Examplary views of disciplines on the keyword "window p ower lifter"
within the dictionary, e.g. "is called by mechanical engineers . . . " or "is named in the new
development generation . . . ". Extensibility is crucial to the adaptability of a dictionary
to changing requirements consequently users will only make use of the dictionary if it
supp orts their needs within their sp ecic environment.
Example 2.
Figure 2.10 shows an example of two dierent views on the comp onent
"window p ower lifter" within the automotive development pro cess. In a mechanical
context (Subgure 2.10(a)), the window p ower lifter is regarded as an assembly group of
gears, a motor and controls. An electrical engineer's view (Subgure 2.10(b)) however
fo cuses rather on the sensors and actors of that comp onent.
This idea is closely related to the eorts b eing made in the Semantic Web movement. Its
goal is to structure the contents of the World Wide Web in a way that allows b oth humans
and machines to capture the semantics of the information available. The approach is to
establish an ontology which is a conceptual schema that denes a data structure with
entities, relationships and rules for a given domain.
5
A dictionary as describ ed denes a corp orate-sp ecic ontology that yields information
ab out typ es of employees and their relations. That way, it is not only an information
5
Compare http://en.wikipedia.org/wiki/Semantic_web
22
2. Requirements
source to human users, but creates a machine-readable representation of domain-sp ecic
knowledge which builds the foundation for applications that supp ort e.g. semantic com-
p osition of pro cess fragments.
2.3.4. Organizational mo del
Employees p erform dierent tasks according to their resp onsibilities within an organiza-
tion. Consequently, a commonly used information system needs to adapt to each typ e
of user by the provision of individually tailored supp ort. That is why apart from secu-
rity reasons authentication systems are gatekeep ers to any kind of multi-user software
using p ersonalized applications or data.
A workow management system additionally controls work activities and assigns work
items to pro cess participants. In order to abstract from individual users, sets of skills
and resp onsibilities are subsumed to identify common
roles
within an organization. The
execution of tasks is usually b ound to a particular role, which means that the work item
can b e pro cessed by any user holding a matching role.
Abstracting roles from individuals helps to distribute work load automatically as equally
as p ossible within available p ersonnel. Another b enet is the handling of exceptional
situations like unavailability of a user. Dynamic rescheduling of work items to a work
list of a substitute pro cess participant makes it p ossible to avoid high variance in waiting
time for work items.
When role abstraction is enriched with hierarchy information and roles are put into re-
lations with each other, an
organizational model
is created. It represents the translation
of a corp orate p ersonnel structure into an workow mo del as seen from an organiza-
tional p ersp ective (see also Section 2.4). Obviously that includes the hierarchic order
and comp osition of organizational segments. Each individual has for example an edu-
cational background in a certain discipline, but can also have other resp onsibilities like
executive tasks. So the fact that one p erson acts within several roles has to b e formal-
ized. Relationships like b eing sub ordinate or sup erordinate can exist b etween p ersons or
only b etween certain roles of p ersons. Moreover, one p erson can participate with each
role in dierent pro jects or task forces with overlapping resp onsibilities. Figure 2.11
illustrates these basic relations.
23
2. Requirements
Person
Position
Discipline
Organizational
unit
Organizational
type has type is a composition of
is a composition of
has background in
is sub- /superordinate to
Project
group
is a
is lead by
participates
occupies
Figure 2.11.: Organizational Mo del
Example 3.
An example of a basic organizational mo del is given in Figure 2.12. It
refers to the running example of an automotive development environment. The au-
tomotive development unit has a typ e "development unit" and is lead by a head of
development which is supp orted by an assistant. The unit splits up in three depart-
ments, each dedicated to the three disciplines involved in mechatronics (see also Figure
1.2): Mechanical engineering, electrical engineering and software development. Each
department comprises a numb er of employees who p erform one (or more) of the listed
roles: A head of department with assistant, designers, engineers, quality assurance for
testing purp oses and p eople for do cumentation. That workforce is distributed over a
numb er of pro ject teams, where each individual gets assigned to pro jects according to
his role. As an example, pro jects "chassis" and "sidedo or" are shown. The third pro ject
"integration" in the schema indicates that pro jects are not indep endent from each other.
As comp onent integration is a complicated task in automotive development, a dedicated
pro ject "integration" fo cuses just on integration issues.
24
2. Requirements
Development
unit
Automotive
development
unit
Mechanical
engineering
(ME)
Software
development (SD)
Electronic/Electrical
engineering (EE)
has type
consists of
Head of Dept. Head of Dept. Head of Dept.
Dept. assistant Dept. assistant Dept. assistant
ME Designer EE Designer SD Designer
ME Engineer
ME
Quality ass.
ME
Documentation
SD Engineer
EE
Quality ass.
EE
Documentation
EE Engineer
SD
Quality ass.
SD
Documentation.
Head of
development
unit.
Assistant
leads
Project Team
Project
Integration
Project “Side
door”
Project “Chassis”
has type
consists of consists of consists of
integrated
by
integrated
by
project participation
supports
Figure 2.12.: Example: Organizational mo del
Creation of an organizational mo dels starts with identication of existing p ersonnel
relations. Its usability is determined by its completeness and level of detail. Only
roles that have b een explicitly identied exist in an information system. In real-life
organizations, employees hold ocial and unocial roles representing their primary and
secondary, often implicit tasks. On the one hand it is meaningful to capture roles as
detailed as p ossible, on the other hand generalization is necessary to establish groups of
individuals providing exchangeable capacities.
When existing p ersonnel relations in an organization are identied, it has to b e deter-
mined whether they are suitable for mapping one-by-one to an organizational mo del or
they turn out to b e to o inexible, ambiguous or incomplete. For example a statement
"most p eople who having spare time work on the integration pro ject" is not helpful if its
formalization yields the assignment of the whole development crew to that pro ject. So
25
2. Requirements
there has to b e found a trade o b etween adapting the workow management system's
organizational mo del to the real organization and vice versa.
Once a complete organizational mo del is built, it is b eing used throughout the whole
Emergent Workow pro cess: The originator of a new workow fragment uses his orga-
nizational status to narrow the dictionary down to a subset which is relevant for him.
A new pro cess fragment can b e assigned to its related pro cess phase, team and pro ject.
Such knowledge facilitates also the comp osition of fragments and their placement in
the current pro cess. Just like any conventional workow management system, an or-
ganizational mo del determines during run time which user is suitable to do a task and
places it into his worklist handler. Finally, the search for templates in the rep ository is
strongly supp orted by an organizational mo del analogous to the search for keywords in
the dictionary.
2.3.5. Time management
Pro cess denitions express control or data ow b etween activities and ob jects. They
yield relative temp oral dep endencies such as "activity A can run concurrently to activity
B" or "do cument D has to b e pro cessed b efore rep ort R can b e created". However, they
do not tell anything ab out quantitative temp oral constraints which are involved in any
kind of pro cess.
Example 4.
Quality gates (see Figure 1.4 on page 8) in the automotive development
pro cess are an example for quantitative temp oral constraints. They tell that a certain
stage of features and quality has to b e met until a certain deadline. All activities
preceding that quality gate have to b e completed until that deadline.
In general a maximum or minimum duration for a set of activities or the earliest and lat-
est start and end date for activities are common temp oral dep endencies within planning
a pro cess. Furthermore, during run time actual values for start, stop and duration are
b eing lled in. This is necessary for the integration with external applications managing
temp oral constraints, such as collective calendar systems or planning software. As so on
as activities have b een passed during enactment, temp oral alignment b etween real-life
activities and their planning counterpart can b e checked and stored.
Example 5.
Table 2.1 gives an overview of ctious temp oral constraints of an activity.
All typ es of constraints (start, stop, duration) can b e dened either relative to other
constraints or absolute in time. Each constraint has two planning values (earliest/latest
resp ectively max/min) and one value recording the real values after execution. Notice
that planned constraints are not mandatory and the information they provide can b e
incomplete, redundant or ambiguous. The earliest start time and the lastest stop time
do not have to describ e the same value as the planned maximum duration. Consistency
b etween them can only b e exp ected from recorded real values after execution.
26
2. Requirements
Constraint Absolute dep endency Relative dep endency
Start
earliest
latest
real
2004-01-13 12pm
2004-01-20 12pm
2004-01-14 1:32pm
after termination of activity A
1 day b efore quality gate Q
after termination of activity A
Stop
earliest
latest
real
2004-01-21 12pm
after start of activity C
b efore quality gate Q
Duration
minimum
maximum
real
1 day
7 days
1 day longer than activity A
Table 2.1.: Example for temp oral dep endencies of an activity
These demands motivate the integration of a central
time management component
in
the Emergent Workow approach. It handles all temp oral asp ects of pro cess mo dels
during mo deling, execution and evaluation.
Prerequisite for centralized time management is the availability of timing information.
This can b e assured if temp oral constraints b ecome an integral part of the pro cess
metamo del. Before or during execution, earliest/latest resp ectively minimum/maximum
timing dep endencies are created which need to b e checked during execution. These values
have to b e integrated with pro cess mo dels as well as with instances. While and after
execution, real execution values are derived either from the runtime engine itself or from
interaction proto cols. Hence running and archived pro cess instances have to integrated
execution timing for instances and activities.
Externalizing time management has b esides its b enets strong requirements concerning
synchronization and integration. After the initial transmission of timing constraints of
a pro cess mo del or an instance, constant synchronization is necessary to keep time man-
agement, pro cess creating engine and runtime engine up dated. While time management
propagates notications ab out the passage of dened time events, opp osite comp onents
keep time management up dated ab out status and schematic changes of running pro cess
instances. Notice that time management itself is not concerned with reactions initiated
by temp oral events. As a consequence, the time management comp onent can not inter-
act directly with users b ecause reactions to regular or exceptional temp oral events are
instance-sp ecic.
27
2. Requirements
Example 6.
What happ ens if the quality gate has b een reached, but one preceding
activity has not terminated yet? Let us assume that at the pro cess denition level a rule
has b een set up that, in case an activity missed a quality gate, the head of the resp onsible
department should b e notied. The time management comp onent though can not notify
the head of department directly, as it has to b e decided on the instance level who the
resp onsible department actually is. So time management noties the
runtime engine
ab out the exceptional event in an activity. The runtime engine has information ab out
the resp onsible user, nds his department and emails the head of department.
2.3.6. Pro cess creation engine
Conventional workow management systems come with a software to ol which is used
to design a workow explicitly. Before designing and enacting an instance, dedicated
pro cess designers either textually or graphically create a mo del in this software to ol and
transfer it to the workow engine.
This pro cedure is not entirely suitable for Emergent Workow as it do es not separate
mo deling and enactment time of pro cess denitions clearly from each other. According to
the use case in Figure 2.1, dedicated pro cess designer do still exist: They pro duce pro cess
mo dels which either initiate an emerging pro cess or provide a coarse framework for the
overall pro cess. Instances of these pro cess mo dels are then altered or completed ad-ho c
during run time. To supp ort this step, Emergent Workow has to provide functionalities
to do cument user interaction implicitly.
The idea of a
process creation engine
is to incrementally derive a pro cess denition
including instance-sp ecic data from user interaction
6
. These pro cess denitions are
formalized according to a chosen metamo del (see Chapter 2.4). The input is a collection
of interactions of the complete workow management system using its interfaces. Input
data is commonly styled in a textual and sequential manner. It is referred to as an
audit
trail
and originating from multiple interfaces comp osed by the runtime engine. The
audit trail describ es what all external instances that interact during run time intend to
do or have done.
It can b e further claried what the outcomes of a pro cess creation engine lo ok like if
one distinguishes when a certain piece of do cumentation was created: The ob jective for
do cumenting an event dep ends on when it has b een created relative to its execution: Any
do cumentation can b e either created
before
, in the
meanwhile
or
after
execution of the
according activity. The moment of do cumentation do es not only inuence its purp ose
but determines also how the start of pro cess creation is triggered. These relations are
listed in Table 2.2.
If a record was created
prior
to execution, planning supp ort as well as synchronization
of future activities are interesting asp ects for a user. Such would b e the estimation of
6
In literature, p ost-ho c process creation from log les is referred to as
process mining.
28
2. Requirements
Time Purp ose Trigger Example asp ects
b efore planning & explicitly start date
synchronization by user input data
while & do cumentation & implicitly by output data
after reuse runtime engine stop date
Table 2.2.: Do cumentation purp ose relative to its creation time
resource availability and the early detection of their shortage. In this case, the pro cess
creation engine is activated
explicitly
by user interaction. When a pro cess denition
is created for planning, that is, the preparation of future activities, there is no way
for any part of a workow management system to detect the correct startup time and
corresp onding planning audits automatically. If pro cess mo dels are created
while
or
after
the execution of according activities, they serve for purp oses such as do cumentation
and reuse. Unlike the former, the invo cation of the pro cess creation engine is here
likely to b e triggered
implicitly
. For do cumentation, any kind of activity records is
immediately relevant as throughout execution of activities, information such as start/end
date, involved data and resources is completed on-the-y.
Example 7.
Supp ose this example for a planned activity: An interdisciplinary meeting
is scheduled for 16pm in a conference ro om. The according memo is created in the morn-
ing and the Emergent Workow system has b een set up to inform all pro ject memb ers of
the up coming meeting. The system might also put a watch on requirements do cuments
and notify pro ject leader ab out eventual changes taking place b efore the meeting.
Both on-the-y and after the event do cumentation rather serve as a do cumentary basis
for later reuse or analysis. If do cumentation is created during execution of an activity
on-the-y, esp ecially temp oral asp ects of activities might b e of interest.
Example 8.
The activity start time of the interdisciplinary meeting was already xed
prior in the morning, but meetings in this ctitious organization are always op en-ended.
So the information ab out the meeting's ending time must to b e added after its termina-
tion.
These varying usage purp oses create dierent requirements regarding when to run the
pro cess creation engine on which data. In order to supp ort planning, a pro cess creation
engine needs to evaluate data which is indicating up coming activities, such as outputs
from schedules or pro ject planning to ols. That forms a coarse framework of work struc-
ture but contains usually no details b eyond the planned activity, starting time and du-
ration. As that picture changes throughout execution of activities, the pro cess creation
engine has to add sequentially more details to the pre-mo deled workow.
If do cumentation or later reuse asp ects are fo cused, then the creation of pro cess mo dels
is delayed until all addressed activities have terminated and complete information is
29
2. Requirements
available. That raises the question which data is relevant and if it is p ossible to manage
the invo cation of the pro cess creation engine automatically. The recognition of relevant
data for a certain usage purp ose needs supp ortive data. That comprises state information
of an activity as well as contextual data. Both tells whether due to the termination status
detailed information is available and what the overall task according to context such
as a pro duct numb er of the particular activity was. In order to determine the right
time to start a pro cess denition extraction, a continuously running pro cess creation
engine is required. Otherwise an explicit start/stop mechanism of the pro cess creation
engine would b e needed, which would turn the pro cess creation engine basically into
a cross-application macro recorder. Such solution would b e impractical as it reduces
usability drastically and it results eectively in explicit do cumentation of tasks. The
purp ose of a pro cess creation engine is to avoid exactly that requirement.
As already mentioned, the sole recording of events caused by activities is not a sucient
input for the pro cess creation engine to function prop erly. On the one hand, even
rep etitive tasks have dierences and cause instances of the same pro cess mo del to dier
from each other. On the other hand, in real life unforseeable things can happ en such that
the planned course of activities gets interrupted or changed. The key for the development
of an understanding for individual case variations is an extended view on an activity and
the following related factors:
•
Activity
•
Classication
•
Context
•
Reason
Activity
Do cumentation of an activity means to describ e all relevant parameters which
inuence its execution during run time and all parameters which are aected by the
execution. They can b e identied as the following ones:
•
Author
•
Data input/output/mo dication
•
Activity status
•
Activity start/end time/duration
In order to nd dep endencies within an audit trail, rst of all any record requires a note
who its
author
is. This information is needed to determine whether it was an individual
who created the entry or a whole group of either co op erating or indep endently acting
30
2. Requirements
users. Based on that assignment the engine can estimate how many instance fragments
can b e extracted and what piece of information ts into which fragment.
Most activities involve data pro cessing, creation or consumption. These external con-
tacts are a substantial part of a do cumentation, consequently any form of
data input,
output
or
modication
is vital to build a formal data ow representation. That in-
cludes ob jects such as pap er do cuments, electronic do cuments as well as data ob jects
b eing exchanged b etween applications, database queries or transactions within an ERP
system.
Example 9.
If in our automotive development example an activity "interdisciplinary
meeting" in pro ject integration (see Figure 2.12 on page 25) is scheduled by a pro ject
leader, the side do or and chassis requirements do cuments will b e used as a data input
and the output might b e new change requests.
As the audit trail is concurrently created with the execution of activities, the status of
a running pro cess instance has to b e found out. That is based on the status of each
single activity within the pro cess; consequently the
activity status
is an integral part
of an activity description. The status has to conform with the run time pro cess status
metamo del as shown in Figure 2.17 on page 61.
For planning and do cumentation purp oses, temp oral asp ects are highly imp ortant as
already motivated in Section 2.3.5. Thus,
start, end dates and activity duration
are
recorded and are used within the pro cess creation engine for pro cess mo del creation and
can b e forwarded to the
time managment component
as needed.
Classication
A classication of activity instances makes sense due to exp ected de-
viations of the regular case. Once recorded, the instances of an activity will lo ok all
alike if an annotation is missing on how the o ccurrence of an activity has to b e judged.
If an exception o ccurs only in 1 % of all activity records, a pro cess mo del that weights
an exceptional case equally likely to a regular case is misleading. A simple classication
to avoid that is to distinguish b etween regular and exceptional activities.
Additionally, an exception which leaves out parts of the control or data ow is to b e
considered separately. Namely, if an exceptions b ehavior is to step over a commonly
executed activity for some reason, then no trace in the audit trail would indicate its
existence. To avoid that lack of information, for example an additional typ e of activity
"replacement" might extend the exceptional classication. This relation can p oint to
left out activities and indicates what the exception's character.
Context
Contextual information describ es basically any condition which is crucial for
the execution of an activity. It can b e either a side note or a further sp ecication that
sub divides an activity into distinctive cases. When a workow user carries out tasks
31
2. Requirements
as a particular role, this can describ e a distinctive context as well as involved key data
which determines the typ e of work.
Example 10.
When a software tester p erforms the activity "basic mo dule unit testing"
in the context of a stage "rst generation", then the activity has other characteristics
than b eing executed in the context of "pre-release generation".
Reason
"Why did we do it that way?" A workow user might ask himself that question
when he lo oks at past executions of activities. The parameters mentioned ab ove already
give a detailed testimony of what happ ened. Actually the reason is a formalized causal
conclusion drawn from all other parameters. In order to make it easier to catch why
something happ ened exactly the way it did, it should b e mentioned explicitly in an audit
trail. This part makes most sense in sp ecial exceptional cases, where strong deviations
from more common pro cedures have o ccurred. In cases where the same path has b een
chosen as ten times b efore or the taken actions are made clear by contextual information
and common sense, a reason is not mandatory.
Advanced but imp ortant issues are selective pro cess creation and handling of erroneous
and incomplete audit trails. As a workow management system is in a central p osition
handling many users and b eing integrated in big scale information systems, only a small
subset of the information available at a time is relevant for creating a pro cess fragment.
Therefore the extraction pro cedure should oer parameters to control what record typ es
are to b e considered from a single logical workow. It should also b e able to comp ensate
with non-conform inputs such as erroneous or incomplete audit trails. Esp ecially having
incomplete input is a very likely scenario if parts of a workow are do cumented for
planning early, but many details are missing and are supplemented piece by piece later
on.
The
quality of pro cess denition fragments
is another factor determining require-
ments of a pro cess creation engine. All created fragments have to conform with a chosen
meta mo del (see Chapter 2.4). This implies that there must exist sp ecications as well
as metho ds to test the correctness of pro duced fragment. Dep endencies within the con-
trol ow and the data ow have to b e detected and mo deled accordingly. To maintain
robustness and a mo dular structure within the set of pro cess fragments, there should
not exist any implicit correlations or dep endencies b etween fragments.
When a fragment has b een created, it can b e stored in the rep ository. Notice that it
is vital to attach either manually or automatically a description of the pro cedure that
is represented by the fragment. As one do es not only want to save the fragment but
also needs to nd it later on within a p otentially large set of fragments, a fragment's
description is almost as imp ortant as its contents. A set of attributes like an identier,
a description, involved groups, asso ciated pro cess stages, numb er of activities and some
examples for relevant information which is combined into a descriptive tag.
32
2. Requirements
2.3.7. Runtime engine
The
runtime engine
is the central functional comp onent of a workow management sys-
tem. Its invo cation starts with the instantiation of pro cess denitions. During execution
of instances, they traverse state changes which trigger activities integrated in data and
control ow. These activities are distributed and p erformed by external entities. The
following asp ects of a runtime engine will b e considered in this Section:
•
Interfaces
•
Audit trail
•
Task assignment with role management
•
Instantiation
•
Flexibility
Change classication
Flexible execution
•
Annotations
•
Consistency and correctness
Interfaces
Lo oking at the inputs and output ob jects of a runtime engine in a black b ox
manner, one notices that interfaces 2 through 5 intro duced by the workow reference
mo del (Figure 2.7 on page 16) refer to the runtime engine: Client applications receive
work items (interface 2), applications are invoked during run time (interface 3), other
workow enactment services exchange ob jects during during pro cess execution (interface
4) and administrators monitor the progress of instances (interface 5).
Input ob jects for a runtime engine comprise pro cess mo dels from the rep ository, the
pro cess creation engine or an external pro cess mo deling to ol and interaction proto cols of
its interfaces to client applications, server applications and external pro cess enactment
services.
During run time, a runtime engine outputs task assignments to client applications, mon-
itoring information to administrators, and an audit trail for storage and reuse purp oses
(e.g. to the pro cess creation engine). Furthermore, it exchanges status up dates and
synchronization messages with external workow enactment services.
Audit trail
The term
audit trail
refers to a continuous stream of use data in a machine
pro cessable form. This stream can either originate from a workow management system
(inside-out) or is handed to it from external information sources (outside-in).
33
2. Requirements
Conventional uses of an "inside-out" audit stream are monitoring and controlling func-
tions for workow participants in order to extend their own scop e on the pro cesses they
work on. Monitoring and controlling may b e used also for comp ensation of the lack of
awareness inherent in workow implementations. An audit stream going outside-in helps
administration and management to monitor and control pro cedures and gives them a
b etter understanding of op erational dynamics. But also trading partners or customers
can use monitoring functionality for optimizing B2B collab oration (e.g. supply-chain
forecasting) or tracking of remote pro cesses (e.g. order tracking).
A sp ecial use of Emergent Workow for an audit trail is as an input for the pro cess cre-
ation engine. However, "raw" data entering the interfaces of Emergent Workow is not
yet suitable for it. First, as mentioned in Section 2.3.6, pro cess creation imp oses strong
formal requirements on its input as well as ltering abilities to receive an audit trail se-
lectively. Numerous input sources deliver massive amounts of proto col data consisting of
events, data actions, transaction information and others. All of them arrive in dierent
data formats. As all that information arrives at the runtime engine, its resp onsibility
is to lter incoming data, arrange it in a common format and deliver a selected stream
to the pro cess creation engine. The outputs of the pro cess creation engine in exchange
are planned for later reuse and are input for the runtime engine at a later p oint of time.
This pro cess is visualized in Figure 2.13.
Runtime
engine
Process
creation
engine
APIs (Interfaces 2 & 3 & 4)
Client
application
Invoked
application
mining of
interaction
protocols
Audit trail
(Interface 5)
Process
fragments
External
enactment
services
Figure 2.13.: Audit trail ow
External applications at the client and server side as well as external workow enactment
services communicate through dierent a layer of various application programming in-
terfaces (APIs) with the runtime engine. With resp ect to the workow reference mo del
(see Figure 2.7 on page 16) that layer represents the interfaces 2, 3 and 4. Besides
control data, use data is exchanged by that interface. Hereof proto cols of workow user
interaction are extracted, which is also called
mining
. After b eing forwarded to the
runtime engine, this information can b e pro cessed and spread to other comp onents such
34
2. Requirements
as the pro cess creation engine. Although outputs of the pro cess creation engine are not
directly passed back to the runtime engine, in the course of pro cess mo del reuse they
return to the runtime engine. Thus, the stream of pro cess fragments from the pro cess
creation engine back to the runtime engine can b e interpreted as a return value to the
audit trail, closing a cycle b etween these comp onents.
An interesting, requirements-related architectural question is to consider whether a
push
or
pul l
mechanism is realized b etween the runtime engine and the pro cess creation
engine. These patterns refer to how communication is initiated b etween data source and
destination. The answer to that question inuences where program logic for the assembly
of relevant audit trails and the initiation of pro cess fragment creation is settled. In
this case a
pushing
architecture means to have the runtime engine to decide on timing
and content of audit data sent to the pro cess creation engine. That case implies a
continuously running pro cess creation engine, which service-like awaits incoming audit
trails and answers these requests with the delivery of pro cess fragments. In a
pul l
architecture, the pro cess creation engine requests an audit trail from the runtime engine
by sp ecifying when and what typ e of audit data will b e transmitted. Obviously, here
the pro cess creation engine needs an external trigger which initiates the explicit query.
If one compares these two p ossible realizations with the listing of do cumentation time and
purp ose in Table 2.2 on page 29, one can detect a relation b etween the usefulness of either
the push or pull principle and the purp ose of do cumentation. If do cumentation is meant
to b e created
before
the execution of activities for planning & synchronization reasons,
fragment creation by the pro cess creation engine is explicitly triggered by workow
users. Hence, a
pul l
mechanism would make sense where the pro cess creation engine
comparable to SQL statements in relational database systems requests excerpts
of the overall incoming audit trail. In the contrary case of do cumentation during or
after the execution of activities, an implicit run by the runtime engine suggests a
push
architecture.
Task assignment with role management
Task assignment addresses an event during
execution of a pro cess instance and is in conjunction with the activation of activity in-
stances. Activation is an intermediate activity state b etween b eing
inactive
and
running
(activity states are intro duced in Section 2.4.2). Task assignment describ es the resolution
of an abstract role mo del into existing real individuals. Only interactive activities (e.g.
activities with asso ciated roles incorp orated by either human users or software agents)
are aected of this action as they have a role asso ciation. Automatic activities can b e
started immediately up on completion of all pre-constraints, thus they do not distinguish
b etween the states
activated
and
started
. When an interactive activity instance switches
from
not_activated
to
activated
and further to
started
, task assignment is done by the
runtime engine. In order to nd all p ersonications of a role within an organization, the
runtime engine relies to an organizational mo del as describ ed in Section 2.3.4.
Ma jor ob jectives of task assignment are
optimal work eciency
and
exible assignment
35
2. Requirements
of work load. Optimum eciency denotes a maximum average throughput of work items
using the available resources while minimizing erroneous pro cessing and administrative
overhead. Throughput can b e inuenced by exibility of assignment, such as automatic
rescheduling of tasks from busy participants to idle participants. The automation of
assignments supp osedly reduces overhead but reduces also exibility if realized without
p ossibility of manual interference.
Two queuing mo dels of task assignment are p ossible:
One virtual global queue
describ es
virtually one worklist shared by all workow users emb o dying a particular role. What
happ ens is that an activated activity shows up as a work item within the worklist handler
of each workow user with a corresp onding asso ciated role. As so on as a user cho oses to
pro cess a work item, the activity's state changes to
started
. At this p oint, an instance
of that role has b een assigned to the activity instance. Concurrently, the work item
is removed from the virtual queue and disapp ears from all other role p ersonications'
worklist handlers. This typ e can either oer a list to each user from which he can cho ose
a work item or all users can just request an anonymous "next" work item. Individu-
ally selectable items oer more exibility but b ear also the p ossibility of non-uniform
item prioritization. By implementing a virtual global queue, the workow management
system can inuence prioritization of activities by intro ducing priority levels into the
queue. If tasks are assigned to users by an anonymous "get next" retrieval, this order-
ing is xed. If users can actually see the contents of the queue and cho ose work items
within constraints such as a minimum/maximum idle p erio d of items, they can inuence
prioritization of work items.
With
multiple queues
, one queue is maintained individually for each workow user. Up on
activation time of an activity, it may b e assigned to a sp ecic workow user and app ears
as a new work item in his worklist handler. This queuing metho d shifts resp onsibility
for equal work distribution to the workow management system. It oers a higher level
of automation and reduces p otentially more overhead. Furthermore it gives a workow
user a clear idea of the anticipated work load and facilitates individual planning. On the
other hand individual queues decrease the level of exibility. If a task has b een assigned
mistakenly or needs manual changes, an additional function for re-queuing work items
is indisp ensable.
Indep endent from a queuing metho d, the moment of role resolution is exible. At the
earliest, it can b e done during instantiation of a pro cess denition, at the latest it has to
b e completed when the activity instance switches into the
activated
state. The earlier
resolution is done, the b etter activities and future engagements can b e planned. If
pro cess instances are rather long-running, then o ccurring changes generate very likely
the need for up dating resolution. These changes can originate from b oth sides, the
organizational mo del and the pro cess instance: Available employees switching p ositions
or b ecoming unavailable as well as altered or stepp ed over activities are examples for such
scenarios. In any of these cases the validity of existing assignments must b e checked and
is an elab orative task. The later task assignments are completed, the more likely they are
stable until pro cessing. Participants' exibility though is reduced by late resolution as
36
2. Requirements
incoming work items are "p opping up" right away and can not b e anticipated throughout
a longer time frame.
Instantiation
Sources that initiate instantiation are all input and output interfaces
as dened in Section 2.3.7 on page 33. External events trigger the instantiation of
pro cess denitions through several dened interfaces: Using interface 2, the initiator is
a workow user who is suciently authorized to instantiate a particular typ e of pro cess
denition. Invoked applications are another source of pro cess enactment using interface
3. They may b e external software such as an Enterprise Resource Planning system up on
the start of a new pro curement transaction. Interface 4 integrates workow management
systems. This also includes that external workow management system can not only
exchange data or synchronize with their internal activities, but can also initiate the
creation of pro cess instances. Finally, also the administrator of a workow management
system can monitor and inuence all asp ects of instances including their creation using
interface 5.
Example 11.
A mechanical engineer receives a new change request from a colleague
as changes collide that were concurrently made on the digital mo ck-up. As change
requests are frequent events during the development pro cess, a generic pre-mo deled
pro cess denition exists. In order to start pro cessing a change request, the engineer
instantiates a change request pro cess denition and executes the instance.
The rst functional requirement is to check whether the instantiation of a pro cess mo del
is executable: Basically, an instance is executable if a start state and a terminal state are
dened and they are "connected" by a sequence of valid state transitions. Furthermore,
no invalid activities, roles or resources are allowed to b e referred to by an instance.
Second, the runtime engine usually applies an initial state transition on instances after
their activation. That is, the execution is initiated by starting the rst activity according
to the instance control ow.
The fact that the runtime engine runs p otentially many instances concurrently imp oses
nonfunctional requirements on it. Van der Aalst and van Hee identify a numb er of
workow b ottlenecks [AH02]: First, the overall numb er of instances in progress can
grow large. If there are many instances in progress, it may indicate an existing prob-
lem. Causes include ma jor uctuations in the supply of instances or resources b eing
to inexible or weak dimensioned for heavier use. However, it may also b e that the
pro cess contains to o many steps that need to b e passed through sequentially. Further-
more, completion time of instances could b e to o long compared to actual pro cessing
time. The actual pro cessing time of an instance sometimes forms only a small fraction
of the total time when it is in progress. If this is the case, there may b e a whole range
of p ossibilities for reducing completion time. Moreover, the level of service can b e to o
low. A workow's level of service is the degree to which an organization is able to com-
plete instances within a certain dead line. If completion time uctuates widely, then the
37
2. Requirements
organization oers a low level of service. In that case it is not p ossible to guarantee a
particular completion time. A low level of service also exists when there are many "no
sales" o ccurring p otential instances can not run b ecause waiting for progression within
the runtime engine will take to o long. When a user knows that it will take a long time
to complete an instance, he will try to circumvent the pro cess. A low level of service can
indicate a lack of exibility, a p o orly designed pro cess or a structural lack of capacity.
The symptoms mentioned ab ove p oint to p ossible b ottlenecks. To identify them one
needs to b enchmark values for these measures, for instance from comparable pro cesses.
Usually, it is not sensible to combat the symptoms using only emergency measures but
to tackle their causes.
Flexibility
Static workows are easy to handle, but fail in scenarios as motivated in
Section 1.1. As exibility is an issue of particular interest in the light of Emergent
Workow, this paragraph is actually sub divided into several p oints of view: First, the
exibility is the requirement emerging out of the need for
change
. Hence, the rst sub-
paragraph will intro duces ways to characterize changes on dierent workow p ersp ectives
(see Section 2.4). Next, the term of exibility will b e broken down into more concrete
measures that allow variable kinds of deviations.
Change classication
Changes during run time arise b ecause parts of the information
that constitutes the workow are not known during build time or changes o ccur while the
system is in pro duction. Van der Aalst and Jablonski prop ose the following classication
[AJ00].
In order to classify, what typ es of fo cus exist when managing changes, a numb er of
change dimensions are intro duced:
•
Maintenance of correctness and consistency.
This p oints at p otential errors
resulting from change, which can b e either syntactic and semantic errors. A se-
mantically correct pro cess instance is able to reach a terminal state without any
errors or deadlo cks.
•
Single-p ersp ective and multi-p ersp ective errors.
With resp ect to the work-
ow p ersp ectives, errors are identied that aect either only one workow p er-
sp ective or multiple p ersp ectives at once. A deadlo ck is only visible in the pro cess
p ersp ective, whereas a task p ointing to nonexistent roles and data ob jects o ccurs
in the organizational and information p ersp ective.
•
Transient and p ermanent errors.
Errors caused by changes can last for dier-
ent amounts of time. Transient changes exist only temp orarily and do not aect
new instances. Permanent errors are lasting longer and aect newly created in-
stances as well.
38
2. Requirements
When solutions are prop osed to implement changes and resolve errors, one can distin-
guish b etween intro ducing
exibility by conguration
and
exibility by adaption
. The
former oers more p owerful design constructs and integrates changes into the meta-
mo del. Flexibility by adaption tries to limit changes, manage multiple versions and
avoid errors by the application of inheritance concepts.
Intro ducing exibility means to allow certain typ es of changes. These typ es can b e
classied by the following six characterizations:
1.
What is the reason for change?
Reasons may b e lo cated in the context of
pro cess execution outside the system like changing requirements or technology, but
can b e triggered also from the inside of the system such as errors and problems
causing failure.
2.
What is the eect of change?
On the one hand,
momentary changes
inuence a
limited set of instances. They o ccur typically as the result of errors or exceptions
and pass by without p ermanently altering the pro cess denition. On the other
hand,
evolutionary changes
take action for all instances starting at a certain p oint
in time. Their typ e of change is rather structural and more p ermanent such as a
changing legislation that eventually changes the pro cess context.
3.
Which p ersp ectives are aected?
The typ e of change is reected very well by
the related workow p ersp ective (Figure 2.14 on page 54). In addition, deletion
or mo dication of pro cess denitions including their tasks and routing are typical
changes app earing in the
process perspective
. Sta changes and other mo dications
of the organizational structure relate to the
organizational perspective
. In case
data structures are added, removed or mo died, these changes b ecome evident
in the
information perspective
. The
operational perspective
shows the exchange
of invoked applications and other op erations related resources. If nally linking
p oints b etween the p ersp ectives such as task assignment are sub ject to change,
these and only these changes will b e reected in the
integration perspective
.
4.
What kind of change?
This refers to the way a change op eration aects the
functionality of a pro cess. As control ow oriented changes deal with the alteration
of tasks and their structural arrangement, functionality can b e
extended
,
reduced
or
replaced
by adding, removing or replacing a task. If the dep endencies are just
rearranged b etween existing tasks, the change is called a
re-linking change
.
5.
When are changes allowed?
A change is either allowed
at entry time
only or
at
any time
. The entry time denotes the very moment an instance's sp ecication is
set up for each involved p ersp ective; after that moment all sp ecics are not allowed
to change any more. Otherwise, changes are allowed at any p oint during workow
execution on-the-y.
6.
How are existing instances handled?
A numb er of alternatives exist for how
running instances may b e handled after a change op eration. A
forward recovery
39
2. Requirements
ab orts old instances and comp ensates them outside the workow management
system.
Backward recovery
ab orts, comp ensates or rolls old instances back in order
to get them restarted with new denitions. Alternatively, one lets old instances
proceed
as they continue running the old way. Only new cases are instantiated
with resp ect to the change. A
transfer
op eration migrates old instances to new
pro cess denition, whereas a momentary
detour
allows the change to settle b efore
actions are taken.
Three frequently named change typ es
exceptions
,
ad-hoc workows
and
dynamic changes
/
migration
, will now b e categorized using the rst ve criteria given ab ove:
Exceptions
are usually unexp ected events which are caused by failure of some comp onent
rather than delib erate changes. Reasons for exceptions are mostly lo cated inside the
system, they have momentary eect on a limited numb er of instances and aect the
information and op erational p ersp ectives. Functionality is either reduced or replaced by
exceptions and they o ccur at any time on-the-y.
Ad-hoc workows
are edited shortly b efore and during enactment on an instance level.
The reason for ad-ho c changes is lo cated outside the system and changes have only
momentary eects. Although any p ersp ective can b e aected by ad-ho c changes, mostly
the pro cess p ersp ective is fo cused. Ad-ho c changes can extend, reduce, replace or re-link
functionality of a pro cess instance at any given time during execution.
Dynamic changes/migration
deals with handling of instances running on an old pro cess
denition after the pro cess schema has b een changed. This is not always straightforward,
e.g. the new mo del may not have an execution state corresp onding to the state of the
old instance which was sp ecied by variables indicating which tasks have already b een
executed. Reasons for migration are usually irrelevant and by mo difying the pro cess
denition, they apply evolutionary changes. They have an impact on all p ersp ectives
and p erform any kind of change as well. Only on-the-y changes have to b e investigated
as entry time changes are considered straightforward: It can b e assumed that any new
pro cess mo del has a correct initial marking state.
Typ es of exible execution
As already mentioned, exibility during execution can b e
created by applying various measures. In the following enumeration, typ es of exibility
are classied according to their degree of exibility in time and are further elab orated
in the following paragraphs.
•
Schema evolution
•
Late mo deling/Case handling
•
Ad-ho c changes
•
Exception
40
2. Requirements
Schema evolution
describ es schematic changeability by iterating a design phase,
late
modeling
predenes limited short-term exibility on details of pro cess denitions.
Ad-
hoc changeability
constitutes sp ontaneous changeability of the execution state of pro cess
instances.
Exception and case hand ling
provides means for sp ontaneous change of state
of pro cess instances.
Schema evolution
or evolutionary mo deling refers to incremental changes applied to
pro cess denitions (compare Wargitsch et al. [WWT98]). Instances of explicitly mo d-
eled pro cess denitions are observed by pro cess designers and improvements according to
analysis outcomes are integrated into pro cess denitions. This metho d contrasts
process
reengineering
where the entire pro cess is radically redesigned to achieve p erformance
improvements (compare Davenp ort and Short [DS90]). This pro cedure adapts to the
workow life cycle as depicted in Figure 1.1 on page 2. Thus exibility is provided for
long-term changes, however it is not helpful for short-term exibility as mentioned in
Section 1.1. In order to enable pro cess mo del evolution, pro cess designers require meth-
o ds that allow them to apply schematic changes to a mo del such as the insertion/removal
of a activity or the alteration of the control ow. Subsequently, running instances have
to b e handled in one of the ways mentioned in the previous paragraph on change classi-
cation. Most desirable is the solution to migrate instances to the new mo del by either
changing their schema on the y or restarting them and auto-execute them until a state
that was dened equivalent to the originating state.
Late mo deling/Case handling
addresses incomplete mo deling with
unstructured
process portions
which are also called black b oxes or placeholders (compare Herrmann et
al. [HSW97]).
Late modeling
means the replacement of placeholders with sp ontaneously
mo deled sub-pro cesses during run time. This information gap has to b e lled up during
run time in order to let the pro cess instance terminate correctly. If a workow user can
cho ose at run time from a numb er of previously dened alternative pro cess fragments
referred to as
cases
in order to replace the black b ox, a
case hand ling method
is applied
(compare Hagemeyer et al. [HHJHS97]).
If pro cess denitions containing black b oxes should b e executable, unstructured pro cess
parts have to b e identied and marked adequately during pro cess design phase. Eventu-
ally they are equipp ed at design time with a
case base
which describ es several alternatives
for structuring the black b ox up on activation. The runtime engine needs to make sure
that each unstructured pro cess p ortion is submo deled b efore it can transfer the activity
in the state
started
. As a subgraph is mo deled individually for each instance by the
workow user in charge, the user also has to examine the case base for a suitable case
that matches the individual context. If such do es not exist, then the ability to alter
existing cases and to add new cases to the case base is required. Not all activities are
meant to b e arbitrarily changeable by workow users, consequently a classication of
exibility for activities has to b e established in the pro cess metamo del (see Figure 2.16
on page 58) and implemented during pro cess design. If a workow user decides to mo d-
ify an existing case or to intro duce a new case, this action inuences secondary related
activities. Such would b e dep endencies like a removed data output which is exp ected by
41
2. Requirements
another activity. Co ordination and propagation of subsequent changes is a task which
needs functional supp ort by the runtime engine. For each activity, it must maintain a
list of dep endent activities and their pro cessing role instances.
Late mo deling oers the b enet of short-term exibility without reiterating through
pro cess design. However, sp ontaneous changes are restrained to pro cess parts where
short-term actions were anticipated and unstructured pro cess p ortions with case base
were either realized during pro cess design phase or are sp ontaneously created during run
time.
Limitations apply when pro cess enactment deviates from planned exibility b ecause an
unexp ected situation has o ccurred. Late mo deling do es not oer sucient functionality
to formalize handling of exceptional situations.
Ad-ho c state changes
are meant to apply instant changes to default state transitions of
instances: An activity can b e skipp ed, moved, inserted or removed. Execution can return
to the previous activity, reset or step over the current activity. These mo dications do
not inuence the pro cess mo del but are restricted to a sp ecic instance.
Each ad-ho c state change p otentially endangers correctness as a change could make a
terminal execution state unreachable. The resp onsibility for avoidance of such "bad"
changes is carried either by the workow user applying the change or by the workow
management system. The latter case requires nontrivial pro cess analysis which validates
the change: As activities are correlated (by control/data ow, usage of resources, . . . ),
manual changes may interfere with pre- and p ostconditions of activities. They might
require successive adaptions of other activity states to prevent unwanted states such as
deadlo cks. Hence, checking and mo difying mechanisms for pro cess instance states are
required.
Exception handling
A computer-based workow management system has its strengths
in structuring, rationalizing and routinizing work. The fewer unscheduled manual inter-
vention is required, the b etter is the system's p erformance.
Exceptions
are dened by
Strong and Miller [SM95] as follows:
We dene
exceptions
in computer-based information processes as cases that
computer systems cannot process correctly without manual intervention [which
is] a denition broader than "errors".
One can distinguish three ma jor p ersp ectives on exceptions:
The
random-event perspective
on exceptions addresses situations which o ccur infre-
quently, are non rep etitive and have random character. While it is assumed that a
workow management system works correctly most of the time, little can b e forecast
ab out exceptions. Such might b e caused by external inuences like p ower downtime or
physical damage that harm information systems as well as internal malfunctions. Due
to their unpredictable nature there is no ecient way of resolution for these kind of ex-
42
2. Requirements
Persp ective Underlying assumption Solution approach
Random-event Exceptions are unpredictable None
Error Errors (from op erations, design,
changing environment)
Eliminate causes
Political system Political system causing conict-
ing interests
Eciently detect and
handle exceptions
Table 2.3.: Persp ectives on exceptions (compare [SM95] Figure 1)
ceptions. Dep ending on the negative impact of sp ecic typ es of exceptions, precautions
may b e taken in order to minimize their probability.
The
error perspective
lo oks at exceptional situations caused by errors in op erations,
pro cess design or changing environment.
Operational
errors are most common when
human interference with input or output is handled incorrectly or the user misunder-
stands the interface or system. Erroneous b ehavior can also b e traced back to
weaknesses
in system design
. The pro cess mo dels can reect the real pro cess incompletely or in-
correctly. That typ e of error is likely to exist due to many factors inuencing correct
functionality, fuzzy knowledge ab out true pro cesses and the problem's high overall com-
plexity. Additionally, errors are intro duced by
changing external requirements
caused by
a exible environment. As an information system do es not evolve as smo othly as real
pro cesses which it depicts and supp orts, over time the electronic pro cess diverges from
the real pro cess. Dierences cause increasing errors, b ecause the workow management
system ends up pro cessing a pro cess it was not designed for. While op erational and
design errors are conceptually tough to avoid, frequent minor adaptions and evolution-
ary changes to pro cess mo dels reduce errors caused by a exible environment. In this
context, the term Total Quality Management
7
(TQM) is often mentioned. It describ es
a management metho dology trying to detect the causes for primary error sources and
to eliminate them.
One can conclude from the estimations given ab ove that exceptions are a regular part of
pro cess exibility and require to a certain extent ecient detection and handling supp ort.
The error p ersp ective mentioned last is the most likely error typ e to b e encountered in
Emergent Workow. As high exibility in the addressed eld of application is likely,
the o ccurrence of an exception in this context do es not mean that such an event is
exceptionally rare, but that exceptions o ccur with many variations they are legitimate
sp ecial cases.
Formally, exceptions are arbitrary ad-ho c deviations to any workow comp onent at run
time. Any workow p ersp ective (see Figure 2.14 on page 54) can b e aected by ex-
ceptions: On the pro cess instance, instantiation, execution or termination of pro cess
instances can b e interrupted by exceptions. A changing organizational mo del causes
p otentially exceptions as well as problems with data ob jects b eing manipulated dur-
7
Compare http://en.wikipedia.org/wiki/Total_quality_management
43
2. Requirements
ing execution. The same applies to client and server application integration or other
resources.
With resp ect to the denition of exception given ab ove,
exception hand ling
denotes
manual interventions in Emergent Workow pro cedures which resolve or comp ensate
an exception's eects. In fact, exception handling splits up into two distinct activities:
Detection & information
and
hand ling
.
First of all, it is necessary to create an awareness within the workow management
system for an exception and to propagate that information. Therefore one needs to
detect
an exception and its typ e. Exceptions can b e caused by external events which
are not system-related or of technical nature. These kinds of exceptions have to b e
entered by an external entity such as a workow user or a software agent. If for example
the user interface of the runtime engine oers an explicit entry form for the description
of exceptions, a reaction can b e directly declared by the user as an exceptional state
transition. If not notied from the outside, the runtime engine has to recognize from
unexp ected situations or other indicators that an exception has o ccurred.
If the exception is system-related and caused by an event within the workow manage-
ment system, then an exception message has to b e broadcasted in order to notify other
comp onents. An example would b e the alteration of the organizational mo del during
run time. As the organizational mo del changes, the re-assignment of tasks for running
instances b ecomes necessary, so the runtime engine should receive a message ab out this.
In return, the runtime engine can come up with a delegation rule and reschedule waiting
jobs in other worklists if p ossible.
44
2. Requirements
Example 12.
In order to comp ensate an exceptions caused by a failed activity, a
workow user can handle the exception by a manual intervention in one of the following
ways:
•
Ignore the exception.
This is the most simple way of exception handling which
might b e helpful under certain conditions.
•
Retry the failed activity. This makes sense if failure was caused by a momentary
reason which has changed.
•
Perform a partial rollback.
With this option, one can try to circumvent the
execution path that lead to the exception. A partial rollback means to undo
or comp ensate a numb er of previous activities until a branching state is reached.
From there, an alternative path can b e chosen that leads to a terminal state without
touching the failed activity.
•
Add extra activities for comp ensation.
Execution continues after the failure,
but an extra activity is inserted in the future pro cess that comp ensates previous
failure.
•
Delete planned activities.
If there are succeeding activities that rely on the
failed activity (e.g. they need its data output), then the solution could b e to delete
all dep endent future activities and to pro ceed with execution.
Annotations
Annotations are supplemental records created during run time by work-
ow users. The idea is to give workow users a to ol to annotate the execution history
of a particular pro cess instance. The addition of an annotation do es not interfere with
the schema of pro cess denitions, but is a user-based to ol to distinguish a certain case
within a case typ e. It evolves from the user's p erception of an individual contextual
situation. If certain conclusions can b e drawn from the context and are valuable for
later reuse, the user may quote it accordingly.
Example 13.
Supp ose during implementation of a software comp onent, a software
engineer realizes that an issue should have b een tackled during comp onent design and is
causing unnecessary work right now. In the last development cycle, the same problem
had shown up, to o. So it would b e nice to give the engineer a to ol to formalize his idea
b ecause otherwise it may b e forgotten until the next cycle. Of course, he can put down
a note in his noteb o ok or email his pro ject manager ab out it, but this will not make
his idea lasting and broadly available. If in fact until the next development cycle team
comp osition changes, his idea may get lost. So it would b e helpful if Emergent Workow
would oer means to annotate instances or activities in this case the comp onent design
activity which have already b een terminated during run time. By adding such notes or
mo difying existing information, reference knowledge ab out an activity is increased and
it can b e used more intelligently when the mo del is re-instantiated or used as a template
for another mo del.
45
2. Requirements
Correctness
In order to avoid errors during enactment, the runtime engine should
take as much of the resp onsibility of assuring correctness for pro cess mo dels and in-
stances as p ossible. In the following paragraph,
semantic
and
syntactic
correctness are
distinguished.
Syntactic correctness
of pro cess mo dels is available if
consistency
and
completeness
of
pro cess mo dels can b e assured
8
If all elements within the mo del notation are suciently
describ ed in the metamo del, a mo del is consistent. Completeness can b e guaranteed if
all mandatory constructs from the metamo del are integrated in a pro cess mo del.
Data in a workow management system is called consistent, if all integrity requirements
are met. Each pro cess instance is supp osed to corresp ond to one asso ciated pro cess
denition. Up on changes to the denition, the conformance of all asso ciated instances
has to b e assured in order to maintain structural identity with its asso ciated denition,
e.g. by migration. If only a subset of all running instances of a pro cess denition
is intended to b e adapted during run time, then the remaining old instances may b e
asso ciated to exclusive old copies of the pro cess denition.
For a runtime engine that allows multiple exible op erations such as late mo deling,
schema changes and ad-ho c mo dication it is nontrivial to uphold consistency and cor-
rectness. This will b e sub ject for discussion throughout the rest of this thesis.
Semantic correctness
addresses whether a built mo del is able to function semantically
as intended. Typical examples for semantically incorrect mo dels are mo dels whose in-
stances can not b e executed or do not terminate correctly up on execution.
Reachability
of termination
issues that an pro cess instance is only executable if its start and termi-
nation state are dened and are "connected" by a sequence of valid state transitions.
Correctness is here given if
any
sequence of transitions b eginning from the start state
leads into a valid termination state.
The correctness requirement for pro cess denitions addresses their b ehavior after changes
during run time. As structure and dep endencies are getting changed and instances are
b eing migrated, the runtime engine has to run checks on them to make sure they are still
able to reach the designated termination state. Alternatively, changes are only allowed in
a way that in conjunction with an appropriate metamo del do es not harm correctness
such as in ADEPT [Rei00, RD98]. Possible incorrect b ehaviors can b e a numb er of state
transitions which lead into a deadlo ck or an innite lo op. These states do not contain a
correct termination state. Other problems after alteration of pro cess denitions can b e
a lacking reachability for activities or unforeseen termination.
8
Compare zur Mühlen [Müh96] p.17 et sqq.
46
2. Requirements
2.3.8. Pro cess matching engine
Central ideas of all data pro cessing in Emergent Workow are do cumentation and reuse
of previously dened structures (compare Section 1.2). The
process matching engine
is
a necessary to ol to accomplish the idea of reuse.
All interfaces of Emergent Workow and comp onents like the pro cess creation engine are
busy with internalizing external data. As a consequence, a massive collection of audit
trails, fragments of pro cess denitions, their instances and comp ositions is accumulated.
Emergent Workow is likely to b e used in an environment that requires adaptability to
changing conditions. That implies that the amount of slightly diering fragments grows
rapidly.
The pro cess matching engine is supp osed to supp ort dierent user groups in nding in-
formation from the rep ository. A workow participant wants to nd pro cess fragments
from previous instantiations in order to build the current instance execution on a tem-
plate. Administrators who monitor actions on the runtime engine want access to the
latest pieces of the audit trail. Pro cess designers want to obtain stored pro cess typ es,
archived instances, comp ositions and audit trails for analysis and improvement.
Input & output characterizations
On the system side, the pro cess matching engine
accesses the rep ository which holds all available data structures (see Section 2.3.9).
These are stored in databases for each typ e and equipp ed eventually with helpful access
constructs such as an index. Complex data structures such as graphs are supp osed to
have attached tags containing imp ortant search criteria. The pro cess search engine must
b e able to read all data structures in the rep ository. Any request is answered with a
(p ossibly empty) set of return elements matching the search.
Theoretically, database systems used for the rep ository already provide access metho ds
for their contents which could b e sucient for Emergent Workow, to o. The reason
why a designated search engine is prop osed lies in the fact that search typ es required
by Emergent Workow exceed common database search metho ds' abilities. All typ es of
users or their client applications interact with the pro cess matching engine by submitting
requests that characterize rep ository elements. These requests contain a numb er of
constraints as well as supplementary data ob jects to characterize their exp ected result
set. Query constructs oered by common database systems are not able to cop e with
similarity matching of data ob ject.
Let us fo cus in the following considerations on the search for fragments of past executions.
Example 14.
A query for a pro cess fragment using constraints and expressed in nat-
ural language could b e "Show me all fragments that have b een created by mechanical
engineerings using the activities A, B and C since two weeks ago and sort them by
descending date".
47
2. Requirements
In this example, the constraints refer to a numb er activities and to information that was
collected during enactment. Typical questions for instance-sp ecic characteristics would
b e:
•
What activities were executed?
•
Which data streams and functions are included?
•
What organizational entities and applications are involved?
•
What was the duration of each executed activity?
•
Which disciplines were involved?
•
What was the pro cess frequency in the past?
A query can b e supplemented by data ob jects which describ e what a return ob ject should
lo ok like.
Example 15.
A pro cess designer has a pro cess fragment and wants to nd out if this
pro cess fragment o ccurs frequently. He passes it to the pro cess matching engine along
with a query "Show me all fragments recorded during the last two weeks which are
similar to my pro cess fragment."
The rst query presented in the Example 14 gave an exact typ e and numb er of constraints
that all result have to comply with. In Example 15, a constraint is given along with an
fuzzy description as a query. Similarity b etween fragments can refer to either
syntactic
(same activities, users, data),
semantic
(same function and eect) or structural (pro cess
graph structure)
similarity
. In this case a result list is exp ected where the most relevant
(similar) match is presented rst, followed by less similar matches in decreasing order.
Obviously, dierent kinds of searches require dierent matching pro cesses.
Matching pro cess
Without sp ecifying a particular matching algorithm, dierent typ es
of algorithms are required for matching according to dierent search typ es:
First, queries requiring exact matching are to b e dierentiated from those requiring
approximate matching.
Exact matching
is characterized by a numb er of quantitative
constraints which can b e comp osed (e.g. with b o olean op erators) to a complex expres-
sion. Each rep ository element is checked for accordance with the expression and either
matches it (and is put into the return set) or do es not. The exact matching algorithm
returns a nite set of matches on the query.
Approximate matching
is needed when the
query contains qualitative constraints such as similarity asp ects. When a qualitative
constraint is used for searching, the result is never absolutely clear but represents a
relative rating of matching quality. When p erforming a similarity search with a given
48
2. Requirements
reference as parameter, the only absolutely "safe" matching is obtained when the found
ob ject matches exactly and equals the search parameter. Otherwise, a rating based on a
similarity metric is added to each matching that indicates its quality. A user query based
on qualitative constraints exp ects a return set of those matches that yield the highest
rating. Notice that without any ltering, the result would b e always the complete set
of searched ob jects available, b ecause any rep ository element receives a (p ossibly low)
rating. Therefore, a
threshold
needs to b e either determined by the pro cess search engine
or is sp ecied by the user in order to cut o results whose matching quality is to o low.
With resp ect to the application domain of searching pro cess-related ob jects, a further
distinction can b e made b etween requests that require descriptive searching and those
involving a schema-matching search. A
descriptive search
contains constraints that can
b e checked without an in-depth analysis of pro cess structures. Rather, each pro cess
element inside the rep ository holds a descriptive tag which roughly classies it. Such
would b e a creation time, the creating user and the overall context. Descriptive search
is supp osed to b e rather simple and quick.
Schema-matching search
denotes searches
asking for details, which are not contained in descriptive tags but have to b e obtained
using more elab orate structural analysis of rep ository ob jects. Typically, fuzzy queries
causing approximate matching rely on schema-matching search.
Having mentioned more and less elab orate matching pro cesses, it is worth to reinforce the
observation that eciency plays a ma jor role for algorithms implemented in the pro cess
matching engine. Searching through a p otentially large numb er of pro cess ob jects and
matching them with complex constraints including structural comparison is a demanding
task for computer hardware and software. However in most situations when a pro cess
search is invoked, a user do es not want to wait for results longer than a short amount of
time. Consequently, a trade-o b etween functionality and p erformance has to b e found
for a useful implementation of pro cess matching.
2.3.9. Rep ository
The rep ository has already b een referenced frequently as all other comp onents' activ-
ities are accessing it. After discussing all other comp onents of Emergent Workow, it
b ecomes evident that basically all kinds of information are stored either temp orarily or
p ermanently. To make that happ en, all comp onents rely on a common
repository
for
data storage and retrieval. In this section, no particular data structures are prop osed
due to the high-level characterization approach and the following characterization of the
pro cess metamo del in Section 2.4.
Storage
Dierent kinds of data are stored either temp orarily or p ermanently.
Tem-
p orarily
stored data is used to depict and up date the current state of the workow
management system. As this topic b ecomes quickly implementation-sp ecic, We will
not go into much detail on this matter. It may b e only said that the core of temp o-
49
2. Requirements
rary data are
states
and their
transitions within the runtime engine
. It runs multiple
instances, all of which have dierent typ es and states. If ad-ho c changeability is al-
lowed on an instance level, supplementary data is attached to instances, indicating and
dening the change op eration.
Time management
is closely integrated into execution of
instances as it sets and checks temp oral dep endencies. This kind of temp orary informa-
tion changes consistently, frequent up dating read and write op erations can b e exp ected
on it during run time of the workow management system.
Permanently
stored data serves the purp ose of preserving and building a collection
of useful knowledge for a longer p erio d of time. In Emergent Workow, this includes
esp ecially traces of current pro cesses and any supp ortive information for reuse. General
knowledge like the
dictionary
is stored p ermanently as it preserves a depiction of the
commonly used vo cabulary. Also the
organizational model
is a p ermanent system rep-
resentation of an organization. It contains a hierarchy of roles, assignments into groups
and asso ciations of roles with real p ersonnel. The fundamental part of reuse-oriented,
p ermanently stored data are
process models
. Descriptions of pro cess mo del are option-
ally supplemented with a classication of granularity that describ es its level of detail.
Furthermore, the allowance of schematic changes on pro cess mo dels extends their repre-
sentation with versioning information, as the schema of a pro cess typ e changes over time.
Parts of temp orarily stored data as describ ed ab ove b ecomes p ermanently stored data.
Instance fragments
created by the pro cess creation engine are archived in the rep ository
for reuse, such as the establishment of a case base (see Section 3.1). Also
compositions
of fragments created by pro cess designers are stored p ermanently as they were created
for the sole purp ose to enable p ost-ho c analysis. Finally the source of pro cess fragments,
audit trail
is also interesting for p ermanent storage to a certain extent. As audit data
represents the most quickly and a p ermanently growing amount of information, practice
has to show whether it is meaningful and p ossible to store the full amount of audit data
p ermanently and eciently.
As ma jor amounts of data are collected and created inside Emergent Workow, data
structures for storage may b e chosen with an eye on space eciency. On the other hand,
a convertible and op en representation would b e recommendable for b etter reusability.
The Workow Management Coalition prop oses for example XPDL
9
, an XML Pro cess
Denition Language which oers a metamo del and an exchangeable representation form
for pro cess denitions. For use with Emergent Workow, this format may b e used if
constructs for exibility requirements are added. Thereby, pro cess mo dels would b ecome
easily exchangeable but also space inecient due to the high verb osity of XML which
makes it a questionable choice for p ermanent storage. The same issue holds for p ossible
representations for the audit trail such as the XML workow log format prop osed by
van der Aalst et al. in [ADH
+
03] or an instance-level case representation prop osed by
Madhusudan et al. in [MZ03].
9
See the XML Process Denition Language Sp ecication Version 1.0 Final Draft:
http://www.wfmc.org/standards/do cs/TC-1025_10_xp dl_102502.p df
50
2. Requirements
Access metho ds
are the necessary counterpart to data representation within a rep osi-
tory to enable reuse. They describ e ways to receive read and write access to all use data.
As any kind of rep ository is most likely based on database technology, basic querying
mechanisms as well organization forms for structured storage are already available. That
includes organization forms such as tree structures, hash tables or indexing and will not
b e elab orated here any further. Notice however that a textual representation of pro cess
structures is neither very "handy" nor very expressive in text-based data structures.
Thus, it is suggested to supply pro cess fragments and comp ositions with a
textual tag
containing a description that can b e used for most common search criteria. Information
such as the creator of a fragment, its start/stop date, its typ e and more can b e easily
derived from the context when archiving a terminated fragment. The same holds for
comp ositions, here the tag could b e comp osition of the tags of all contained fragments.
2.3.10. Requirements summary
In this Section, comp onent-sp ecic requirements are summarized in a tabular repre-
sentation. For each comp onent the source or kind of input and output are giving and
indicated by an "I" and "O" in the left column. Then an enumeration of the most
fundamental prop erties is given. Each prop erty is asso ciated with a unique identier
lo cated in the left column, such as (UI2). These identiers are used in Chapter 3 to
refer to a prop erty match b etween Emergent Workow requirements and related work.
User Interface/Client Application/Agent
I/O Exchange of control and use data b etween runtime engine and a human-
machine interface/an agent
(UI1)
(UI2)
(UI3)
(UI4)
Functional sp ecics for user groups
Usability (intuitivity, simplicity, do cumentation)
Conguration & customization
Creation of accurate/detailed interaction proto cols
Server Interface
I/O Communication with external applications/workow enactment services,
runtime engine
(SI1)
(SI2)
(SI3)
Standardized interfaces for synchronous/asynchronous communication
with external applications and workow enactment services
Supp ort dierent levels of interop erability
Creation of accurate/detailed interaction proto cols
Dictionary
I/O Dictionary contents are communicated with all other comp onents
(D1)
(D2)
(D3)
Establishment of an ontology that explains semantics and correlation of
domain-sp ecic vo cabulary
Completeness/consistency
Structural extensibility
51
2. Requirements
Organizational Mo del
I/O Used by all comp onents for role abstraction
(OM1)
(OM2)
(OM3)
(OM4)
Formal representation of corp orate structure with resp ect to hierarchy,
resp onsibility and sp ecialization
Role abstraction
Coverage of ocial and unocial roles
Completeness/consistency/useful level of detail
Time Management Comp onent
I/O Communicates temp oral constraints with all other comp onents
(TM1)
(TM2)
(TM3)
Control and monitoring of temp oral dep endencies during enactment
Synchronization with other comp onents
Integration of time constraints into workow metamo del
Pro cess Creation Engine
I/O Inputs an audit trail from the runtime engine and outputs pro cess fragments
(PC1)
(PC2)
(PC3)
(PC4)
(PC5)
Creation of instance-sp ecic pro cess fragments from an audit trail and
general knowledge
Goal-dep endent invo cation and creation of pro cess fragments
Robust and congurable input
Metamo del-conformance of output
Supplementation of output with a description
Runtime Engine
I Pro cess mo dels, interaction proto cols
O Audit trail, task assignment, synchronization with externals, monitoring
(RE1)
(RE2)
(RE3)
(RE4)
(RE5)
(RE6)
(RE7)
(RE8)
(RE9)
Rights management/security
Task assignment
Instantiation of pro cess mo dels
Schema evolution
Late mo deling/Case handling
Flexible execution of instances (ad-ho c change, exceptions)
Assure correctness/consistency of running instances
Create an audit trail from events and incoming interaction proto cols
Allow annotations of events
Pro cess Matching Engine
I Queries
O Result set of matching data ob jects, eventually supplemented by a rating
(PM1)
(PM2)
(PM3)
(PM4)
(PM5)
Queries contain quantitative/qualitative constraints and are supplemented
by data ob jects
Exact and approximate matching
Descriptive and schema-matching search
Syntactic, semantic or structural similarity matching
Rated result sets with ltering threshold
52
2. Requirements
Rep ository
I/O All data typ es with all other comp onents
(R1)
(R1a)
(R1b)
(R2)
(R2a)
(R2b)
(R2c)
(R2d)
(R2e)
(R2f )
(R3)
(R4)
Temp orary storage of data:
Runtime engine state information
Time management information
Permanent storage of data:
Dictionary ontology
Organizational mo del
Pro cess mo dels with versioning information
Archived pro cess fragments
Pro cess comp ositions
Audit trail
Ecient data representation
Basic access metho ds to stored information
Table 2.4.: Requirements summary
2.4. Pro cess metamo del
A
model
in the context of workow management reduces the complexity of systems in
the real world in order to make it controllable
10
. By abstracting from reality, individual
ob jects and relations of the real world are reduced to ob ject typ es and relation typ es
by ltering out irrelevant asp ects of reality. The more detail is left, the more complex
a mo del grows. Hence a pro cess designer determines how much information is relevant
and decides on the required level of complexity.
A
metamodel
denes a mo del for all mo dels within a workow management system. It
establishes a formalism that denes the class of constructs which are allowed in mo dels.
Key dimensions
11
of metamo dels are among others its granularity, control ow, data ow,
organizational mo del, role binding and exception handling. Practically sp eaking, the
metamo del determines the maximum expressive capability of all mo dels built according
to it. The metamo del b oth abstracts a "mo deling language" from mo dels and can b e
used to verify the correctness of mo dels.
A
process metamodel
represents a pro cess p ersp ective view on a metamo del and shows
only partial asp ects of the total metamo del as it is used in a workow management
system. The following paragraph puts the pro cess p ersp ective into a bigger picture in
order to give an idea of its classication.
10
Compare [Müh96] p. 13 et sqq.
11
Compare Lei and Sing [LS97] p. 3 et sqq.
53
2. Requirements
Workow p ersp ectives
Van der Aalst and Jablonski identify ve dierent p ersp ec-
tives to characterize dierent asp ects of a workow management system [AJ00]. These
p ersp ectives are a go o d starting p oint to structure as shown in Figure 2.14:
Process perspective
Organization perspective
Information perspective
Operation perspective
Integration
perspective
Figure 2.14.: Workow p ersp ectives (compare [AJ00] Figure 1)
The
process
p ersp ective takes a task and control ow oriented p oint of view fo cusing
on pro cess denitions, their typ e and instantiation. The
organization
p ersp ective fo-
cuses organizational structures characterized by roles, groups, resp onsibilities and their
allo cation. The
information
p ersp ective is a data-centric view dealing with control and
pro duction data. Elementary op erations p erformed by applications and resources form
the
operational
p ersp ective. They are used in the pro cess p ersp ective as elements for
construction of data and control ow. The
integration
p ersp ective nally links all views
together.
This Section deals with the pro cess metamo del of Emergent Workow and therefore
restricts its view to the pro cess p ersp ective. An overview of the most imp ortant com-
p onents of Emergent Workow's pro cess metamo del is given in Figure 2.15. Further
explanation on the shown elements will b e given in the subsequent Sections. Notice that
Figure 2.15 do es not contain instance-sp ecic elements such as instances, fragments or
comp ositions to enhance readability.
54
2. Requirements
Process
definition
Control flow
Activity
Schematic
structure
AND split/join
OR split/join
XOR split/join
Loop
Sequence
Precondition
Context
Atomic
activity
Subprocess
Regular case
Exceptional
case
Role
Postcondition
Black box
has a
has a
consists of
is a
is a
is a
is a
has a
Type
has a
is assigned to
Caseis a
0..n
0..n
0..n
0..n
0..n
0..n
1
0..n
0..n
1
0..n
1..n
1
1..n
0..n
1
Version
1..n
0..n
1..n
1..n
0..1
1
0..1
1
0..1
0..n
0..10..1
1
0..1
0..1
consists of
0..n
Granularity
has a
0..n
0..1
Figure 2.15.: Pro cess metamo del
2.4.1. Pro cess denitions
A
process denition
or pro cess mo del represents the formalization of a business pro cess.
A business pro cess consists of a manual part called the
manual denition
and an auto-
55
2. Requirements
mated part named
workow denition
12
. The attribute "automated" is here used in a
wider sense than addressing only pro cesses which run without any manual interference.
It rather refers to the set of pro cesses which are supp orted by information technology.
Workow denitions consist of a numb er of items and relations expressing an automated
pro cess. These items are activities, resources and data ob jects. They are connected by
structural relations which creating a control ow.
Granularity
An issue with distinguished imp ortance for Emergent Workow is the de-
nition, recognition and application of a pro cess denition's
granularity
. It describ es the
abstraction level of an atomic or basic element within the pro cess metamo del. Emergent
Workow aims at deriving pro cess fragments from interactions and activities of active
users. Users though have dierent p ersp ectives, resp onsibilities and statuses within an
organizational mo del. Thus, their p erception of what an "elementary" task is diers
signicantly. Emergent Workow requires the ability to cop e with inputs that dier in
level of detail and granularity.
Denition and recognition of granularity means to establish a common measure that
allows the classication of all incoming fragments. That refers not only to the recognition
of a top/b ottom level task, but includes also quantitative measurement of intermediate
level tasks.
A lower b ound for the nest level of granularity is represented by the
stability of mod-
els
: A pro cess mo del should b e stable and not change on each instantiation due to
p ersistent changes on the lowest granularity level. An event in a workow management
system represents the smallest recognizable element for an information system, however
tasks outside the system may b e even more detailed. Semantically, an elementary task
should b e chosen as the smallest stable and indep endent set of op erations that form one
logical unit. Being small is here characterized as a minimum amount of b ound time
and resources. The highest granularity level b eing the other end of the sp ectrum is the
top-level process
. It is basically a coarse view on the total pro cess that do es not allow
any further abstraction with less details and a broader scop e without lo osing signicant
information.
Between these two extremes, intermediate levels of granularity exist. Their classication
is most challenging due to the numb er of characterizations indicating a granularity level:
First, the
hierarchical position
of the p erson who executed an instance is an indicator for
the granularity of the underlying pro cess denition. A task regarded as elementary by a
pro ject manager may represent a whole subpro cess for the software tester sub ordinate
to the manager. Second, the involvement of (eventually nested)
transactions
gives a hint
on the abstraction level as transactions may b e used b oth on higher or lower levels. The
used
time
for the completion of one task as well as the
amount of resources
b ound by a
task classies the individual granularity level of a rep orted pro cess fragment.
12
Compare the Workow Management Coalition Reference Mo del [Hol95] p. 7 et sqq.
56
2. Requirements
It app ears very plausible that the total numb er of hierarchies (the "granularity of gran-
ularity levels") has b een dened at some p oint in the workow cycle, e.g. in the or-
ganizational mo del. This establishes an abstraction hierarchy with distinguished levels,
dened by a numb er of quantitative, measurable characteristics. Then it is the job of
the workow management system to examine incoming fragments and classify them in
a granularity level within the dened abstraction hierarchy using one of the characteris-
tics mentioned. Esp ecially with regard to semantic pro cess fragment comp osition, this
represents a fundamental step to enable meaningful comp osition.
Version
One of the exibility measures mentioned in the requirements of Emergent
Workow's runtime engine was schema evolution (see Section 2.3.7). It prop oses that
pro cess mo dels are adapted to a continuous changing environment by the application
of change op erations. Pro cess instances that were instantiated on the same pro cess
denition have p otentially diering pro cess schemata. Consequently, a pro cess typ e
by itself do es not clearly identify the structure of its instances or schema. Hence, a
versioning
of pro cess denitions is prop osed. An incrementing version numb er indicates
a schema change and gives a clear reference to each version of a pro cess denition.
Activity
Within a pro cess denition, activities are elementary functional units. Each
activity consists of many dierent typ es of information whose comp osition allow its
functionality. All parameters combined yield a case its identity. As mentioned b efore,
Emergent Workow do es have requirements in terms of workow exibility and reusabil-
ity. These requirements are reected by the parameters sp ecifying an activity as shown
in Figure 2.16.
An activity p erforms a certain
task
and is identied by a
name
. An activity's character
is sp ecied by stateful
case
information which describ es the case content, case attributes
and conditions
13
. In Emergent Workow,
case
information categorizes an activity and
tells for example whether it is
regular
or
exceptional
. The numb er of case categories is
extensible and they can b e used to classify instance-based entries in an audit trail with
resp ect to their relevance or likeliho o d to reo ccur. As a further dierentiated classi-
cation of cases may b e useful dep ending on the application domain, the extensibility of
this attribute is expressed by one or more
custom
cases. An activity
type
tells whether
additional constraints have to b e taken care of when an activity is pro cessed. The reg-
ular case is an
atomic
activity. However, the activity can also b e a placeholder for a
subprocess
or a
black box
. These imp ose sp ecic execution restrictions to the activity,
e.g. a black b ox (compare Section 2.3.7 on page 41) activity must b e fully submo deled
b efore the activity can b e activated. One or multiple
descriptions
oer ro om to de-
scrib e informally from one or multiple p ersp ectives what an activity do es. A
exibility
parameter tells the workow management system ab out the degree of exibility of this
activity. It can b e either
ful ly
ad-ho c changeable, the change metho ds may b e restricted
13
Compare [AH02] p. 33 et sqq.
57
2. Requirements
Time
Data I/O
Name
Role
Context
Case
Type Postcondition
Precondition
Flexibility
Fully flexible
Limited
Static
Exceptional
Regular
Stop (planned/real)
Start (planned/real)
[Custom]
Atomic
Black box
Subprocess
Description
Duration (planned/real)
Activity
1..n
1
0..n
0..1
0..1
1 0..n
0..n
0..n
0..n
0..n
Figure 2.16.: Activity metamo del
to a
limited
typ e and change time (e.g. only description changes b efore activation) or
the activity is totally
static
and do es not allow any changes. Conditions split up into
preconditions
and
postconditions
: Preconditions tell ab out the conditions ought to b e
met b efore activation and p ostconditions guarantee a dened state after termination of
the activity.
Contextual information
is a generic entry which captures relevant factors
inuencing activity pro cessing or which are needed for p ost-ho c evaluation.
Data input
and output
refers to data ob jects that are created, read or wrote during activity pro cess-
ing.
Time
entries hold temp oral constraints for time management and are used to record
the execution history of an activity instance. They contain start and stop times as well
as a duration elds, each having a eld for the planned and the real value. Finally, the
role
ob ject identies which organizational entities are allowed to pro cess a denition.
Control ow
A
control ow
interconnects activities b eing elementary parts into a con-
tinuous workow. The structural elements of a control ow determine causal relationship
of activities within a control ow. In order to classify the control ow expressiveness of
workows, van der Aalst et al. dene
workow patterns
[AHKB02]. A pattern abstracts
from solutions given for concrete problems an makes more generic recommendations. By
separating basic from more advanced language constructs, an incremental approach to
the requirements on a mo deling language is given.
The following enumeration gives a summary on basic patterns (No. 1 5) and selected
advanced patterns (No. 6 9):
58
2. Requirements
1.
Sequence
. This allows activities to b e executed in sequential order. An activity
is activated after its predecessor terminates.
2.
Parallel split
. The thread of control splits at a parallel split which is also called
AND-split. A thread of control describ es the path of execution which is headed by
the currently executed activity. Multiple activities are activated after a common
predecessor terminates.
3.
Synchronization
. The execution of multiple activities/threads of control is merged
using a synchronization or AND-join. The next activity is activated as so on as all
incoming parallel threads of control have arrived.
4.
Exclusive choice
. The thread of control has multiple choices to pro ceed on
dierent paths. In contrast to a parallel split, only one of the available alternatives
is exclusively chosen which is why this split is also called XOR-split. The choice
is made up on control data or a condition.
5.
Simple merge
. As a counterpart to the exclusive choice, the simple merge or
XOR-join activates the next activity as so on as one of the incoming path is acti-
vated.
6.
Arbitrary cycles
. This construct allows to execute one or more activities rep eat-
edly. Control data or a condition check whether and how often a lo op is passed.
7.
Implicit termination.
When no activity is currently active and none is available
for activation, the pro cess is terminated implicitly without reaching an explicitly
dened terminal state.
8.
Interleaved parallel routing.
When in a set of activities, no two activities
should b e executed at the same time but the order do es not matter, then interleaved
parallel routing allows the activation as an unordered sequence. That is, each
activity is executed only once in a nondeterministic order.
9.
Milestone.
The activation of a certain activity dep ends on whether a milestone
has b een reached without expiring. The milestone b eing a condition is dened as
a sp ecic comp ound state of multiple activities of the control ow.
Patterns 1 through 5 are essential for even very basic structured workows. For more
advanced pro cesses, pattern 6 is useful but complicates execution considerably: The in-
tro duction of a lo op means that activities can b e activated multiple times p er execution
and their state has to reset when a new lo op iteration is started. Analysis b ecomes
harder and due to the p ossibility of innite lo ops, correctness can hardly b e guaran-
teed. Patterns 7 to 9 are not required but "nice-to-have's" as they supp ort goals of
Emergent Workow: Implicit termination facilitates handling and correctness checking
of incomplete pro cess mo dels or late mo deled subpro cesses. Interleaved parallel routing
increases exibility for many scenarios where the order of activities do es not matter:
59
2. Requirements
In fact, any other construct would imp ose articial and unnecessary regulation on such
cases. Finally, the idea of having a milestone element for control ow greatly aligns with
running a quality-gate driven pro cess such as the V-Mo del (see Figure 1.4 on page 8).
Notice that these patterns do not take into account exibility-sp ecic control constructs
for the integration of subpro cesses, exception handling and case-handling. Subpro cesses
need a hierarchical integration which enacts an indep endent pro cess denition up on the
activation of the activity representing a subpro cess. For exception handling, an explicit
description of an exception handling routine and a description on how to jump back
and forth to the routine are desirable. A dedicated version of an XOR-choice/merge
supplemented with implicit termination functionality would b e a starting p oint for a
structural control element giving dedicated supp ort to exception handling.
The question on which workow patterns to integrate in Emergent Workow's pro cess
control structure has conicting goals in its background: High functionality and exi-
bility can b e oered by a complex pro cess mo del with manifold control structures. But
it also brings along much more complicated construction, changeability and correctness
checking than a simple pro cess mo del. Moreover, an easy-to-use pro cess mo del is more
likely to b e understo o d and accepted by most workow users. If a highly functional
mo del is chosen, then an interface must b e built around the mo dels which either pro-
vides strong supp ort or hides the system's complexity by translating the complex internal
mo del to a more simplistic outside view and vice versa.
2.4.2. Pro cess instance
A pro cess instance puts the sp ecications of a pro cess denition into practice. Each
pro cess denition can have multiple instantiations, but each instance refers to only one
denition. An instance is an indep endent ob ject residing inside the runtime engine
during enactment. In the context of a pro cess instance, each activity is instantiated
and asso ciated roles are resolved. That is, an activity is assigned with one ore more
individuals in the organization who o ccupy an according role. How and when resolution
takes place is decided by the runtime engine's role resolution p olicy. During execution,
a pro cess instance o ccupies resources such as the individuals executing it, use data
or server-side applications. Beyond that, it traverses a numb er of states b etween its
instantiation and termination. If from all p ossible states a terminal state is reachable, a
pro cess instance is called
correct
.
Pro cess and activity state mo del
A pro cess instance has usually a dened start and
end state and traverses a numb er of intermediate states from the one to the other. An
initial state transition is mostly p erformed after initialization is completed by activating
the rst activity. The overall state of a pro cess instance is determined by the set of
states of its activities. An exemplary activity instance state mo del is shown in Figure
2.17.
60
2. Requirements
Skipped
Waiting
activated not_activated
Running
startedpaused exec_sub-
process
Terminated
failed completed
Archived
skipped
commited
Activity
instantiation
Figure 2.17.: Activity instance state mo del (adapted from [Rei00] Figure 4-1)
Figure 2.17 shows a coarse state mo del which applies for b oth, an activity and the overall
instance as shaded b oxes. Within the shaded b oxes, white b oxes represent more detailed
activity states. Arrows b etween shaded b oxes and b etween white b oxes indicated state
transitions of the instance and the activity resp ectively. An instance switches in an
initial
waiting
state as so on as its rst activity is instantiated. It moves from there into
a
running
state as so on as the rst activity is running and
terminates
as so on as the
last activity has either failed, completed or was skipp ed. Up on successful termination,
it is b eing
archived
. From any of the rst three states, the instance can b e
skipped
which
means its execution is ab orted at some p oint.
An instance starts in a state
not_activated
and gets
activated
when the thread of control
arrives. From there it transits into a
started
state as so on as all of its resources are
allo cated. While it is running, it can switch back and forth to the sub-states
paused
or
to
exec_subprocess
in case a subpro cess is asso ciated. Up on termination, an activity
can either
fail
, e.g. due to errors during execution or
complete
successfully. The last
step after completion is a
commit
to the archived instance. As multiple paths of control
ow through a pro cess schema exist, an activity can p ossibly b e never activated. In that
case it transits straight form
not_activated
to
skipped
.
As already indicated by the nal archiving state, a history of state transitions is recorded
and saved as part of the audit trail. This is a requirement due to the demand of Emergent
Workow for the analysis and reuse of part instance executions.
The exibility requirement of Emergent Workow (see Requirement summary in Section
2.3.10, (RE5)) to enact incomplete instances has further impact on the metamo del of
61
2. Requirements
pro cess instances. Black b oxes represent missing subpro cesses and are mo deled during
run time. Also ad-ho c changes (RE6) interfere with instance execution. Both cases
mo dify the instance's execution state and after each mo dication, consistency checks
are mandatory to assure the
legality
of a state. If for example a non-activated activity
is inserted in an area which precedes activities that have already terminated, it b ecomes
imp ossible for the instance to terminate correctly. If an instance mo dication leads to
an illegal state, either the user or the runtime engine has to care for its correction (RE7).
Furthermore, each instance should archive any extra
annotations
which were entered
by a workow user during enactment (RE9). This allows him to supplement the the
archived instance with useful, informal notes for later reuse.
Instance fragments
When an audit trail is examined by the pro cess creation engine,
a partial pro cess instance is derived and is referred to as an
instance fragment
(PC1).
It links to the archived execution history and contains thereby references to executing
individuals, o ccupied resources, timing informations and results from instance exibility
measures.
From a system p ersp ective, an instance fragment is a p ortion of an archived pro cess
instance put into a formalism according to the pro cess metamo del. Compared to a
pro cess instance, sp ecic start and end states are missing and the correctness of the
schema is unchecked. Notice that it is built from the audit trail which has a certain
level of detail according to the originator of the trail. That is, each fragment has an
individual
level of granularity
describing its richness of details. An explicit representation
of granularity is fundamental for further reuse of instance fragments as the next Section
reinforces.
2.4.3. Pro cess comp ositions
A complete workow transforms an initial business requirement (the precondition) into
a state that realizes the business goal (the p ostcondition). It do es so by a numb er of
steps implicitly traversing a state-space. The
composition
of fragments equals to the
identication of a sequence of tasks that transforms a precondition state into a state
complying with the nal p ostcondition for an "overall" instance. In fact, comp osition
is p erformed
vertical ly
and
horizontal ly
: Vertical comp osition of fragments represents
the alignment of dierent views and hierarchies related to a common part of the overall
pro cess.
Horizontal
integration links causally related pro cess parts sequentially together.
The overall instance is identied by a business requirement such as an order numb er in
a pro duction pro cess. From an employee's p oint of view, the overall instance is invisible
and app ears only as smaller instances of lower-level tasks. The reassembly of those
fragments reveals the structure of the virtual overall pro cess.
Theoretically it would b e p ossible to combine fragments of dierent instance audit trails.
62
2. Requirements
In fact it could b e very much easier to assemble all parts of an overall pro cess from
multiple instances. However, their comp osition can b e dicult and the usefulness of its
outcomes is questionable. Because of the exibility measures oered by Emergent Work-
ow, dierent instances are individually able to tailor a pro cess by mo difying instances,
schemas and applying cases. When combining dierent cases or schema versions, they
may not only collide syntactically but do not match semantically either: A cross-instance
comp osed overall pro cess starts with an business requirement and ends with a dierent
business goal which do es not reect reality. That is why only comp ositions consisting of
instance fragments b elonging to one overall instance are meaningful.
Relation typ es
Technically, a comp osition is a
relation
dened on a set of pro cess
fragments. The involved typ es of relations are shown in Figure 2.18.
Composition
Disjunct
fragments
Overlapping
fragments
Sequential Parallel Partial Total Hierarchical
Figure 2.18.: Typ es of relations in fragment comp osition
Figure 2.18 makes a distinction b etween
disjunct
and
overlapping
fragment relations. A
sequential
relation directs the control ow after the termination of the rst fragment to
the second fragment. A
paral lel
relation splits the thread of control and directs it to
b oth fragments at the same time. Overlapping relations are more complicated as they
correlate activities within fragments. A
partial ly
overlapping relation correlates a subset
of b oth fragments with each other. If each activity of one fragment is correlated with
an activity in the other fragment, the overlapping is
total
. A sp ecial case of overlapping
relations is a
hierarchical
relation. It depicts subpro cess relations by correlating one
activity with the complete second fragment. When the thread of control arrives at
this activity, the activity pauses and forwards the thread of control to the lower-level
fragment. As so on as the thread of control returns, the activity is terminated and the
top-level fragment continues its execution.
63
2. Requirements
Notice that correlating an activity means the creation of a comp ound activity merged
of the attributes sp ecifying each activity (see Figure 2.16 on page 58). This is either
achieved by adding b oth attributes (e.g. all roles from b oth activities are added to the
new activity) or cho osing one of them (e.g. the choice of a exibility level) When creating
an overlapping relation, either the system or the comp oser must take care of merging
each overlapping activity. Each mentioned relation relates two fragments, hence for the
comp osition of an overall instance, multiple relations must b e applied. That requires a
comp osition to conform with the same requirements as a pro cess fragment, that is, from
an outside lo ok it b ehaves and lo oks like a pro cess fragment.
Supp ortive constructs
One of the key enablers of fragment comp osition is an explic-
itly expressed
level of granularity
on each fragment and comp osition. Any automated
supp ort for nding matching fragments is based on a quantitative metric to assess sim-
ilarity, one of which is granularity. Besides other attributes such as roles and temp oral
information, it helps to determine which fragments can b e comp osed in a semantically
meaningful way and where a hierarchical relation should b e applied.
As it is likely that fragments do not match each other p erfectly or parts of the over-
all pro cess are missing, elementary to ols help to interconnect a control ow with gaps.
These are constructs like a
spontaneous transition
to interconnect activities or an
empty
fragment
in order to easily integrated a hierarchical relation into a comp osition. Fur-
thermore, a
black box fragment
can indicate missing parts. In case the comp osition gets
enacted, this construct lls up gaps which were not covered during comp osition and
b ehaves similarly to a late mo deling instance in the runtime engine.
Fields of use
Pro cess comp osition is p erformed by pro cess designers who use desig-
nated client applications for mo deling supp ort. An example on how relations b etween
fragments could b e detected is given in the example b elow.
Example 16.
Assume an activity "window p ower lifter mounted" with the context "as-
sembly left front do or" is in one fragment, activity "side window lifting motor mounted"
with the context "assembly left front do or" is in another fragment. By doing a dictionary
lo okup, a pro cess designer can nd out that the side window lifting motor is a part of
the window p ower lifter assembly unit (see Figure 2.10 on page 22). From that informa-
tion he can conclude, that the corresp onding activity "mounting window lifter motor"
is a sub-activity of the activity "mounting window lifter". If further examination of the
temp oral execution history, the involved roles and further context information (such as
a serial numb er on the b o dy) conrms that assumption, very likely a subpro cess relation
has b een found.
As a comp osition to ol is considered as a sp ecial case of user interface and the elds
of use were not mentioned in Section 2.3.1, a short paragraph on the elds of use for
comp ositions is added here. Pro cess comp ositions are created by pro cess designers for
64
2. Requirements
in-depth
analysis
. By constructing a comp osition, designers receive a big scale view
on the course of execution of an instance. While workow participants are most able
to optimize a partial pro cess on a small scale due to their knowledge and exp erience,
pro cess designers use a comp osition as a to ol to understand and optimize big scale
dep endencies of an overall pro cess. Such analysis can b e supplemented by a
simulation
of
past executions using the continuous do cumentation given in a comp osition. Annotations
made by workow users are attached to fragments and accumulated on them is given
in a comp osition. They represent an excellent summary on
lessons learned
during the
execution of an instance. Drawbacks and conclusions lead to improvements in the big
scale pro cess and can b e applied for example to the V mo del (see Figure 1.4 on page 8).
65
3. Related approaches
This Chapter presents a numb er of approaches which are related to asp ects of Emergent
Workow. Each Section intro duces at the b eginning the fundamentals of the underly-
ing eld of research. By summarizing selected pro jects, interesting asp ects of mostly
recent work are highlighted. Each Section closes with an assessment of usefulness of the
presented concepts in the light of Emergent Workow.
3.1. Case-based reasoning
3.1.1. Fundamentals
Case-based reasoning (CBR) is a metho dology that can b e used to enhance exibility
in pro cess management. It builds fundamentally on the hyp othesis that reasoning is
reminding of useful information. The origin of this automated learning approach lies in
Articial Intel ligence
research.
As intro duced by Aamo dt and Plaza [AP94], the idea of CBR is to solve problems by
using knowledge gained by previous exp eriences which are referred to as
cases
. Because
each solved case is added to a
case base
, it extends incrementally the available exp erience
within a problem domain. CBR is a
learning
technique b ecause the knowledge ab out
the problem grows indep endently from the reasoning metho d and fosters b etter or easier
nding of solutions.
Commonly the term CBR is used in a wider sense and refers to various reasoning meth-
o ds. Strictly sp eaking it diers however from other reasoning typ es. Those varying
asp ects include metho ds for retrieval, management and utilization of past cases and
general domain knowledge as well as matching and adaption pro cedures. A list of re-
lated reasoning metho ds is given b elow:
•
Exemplar-based reasoning
Here a
concept
is dened as the set of its exemplars.
Solving a case in this scop e denotes a
classication task
where the matching class of
problem is found. As each class represents one single solution for a particular typ e
of problem, the class that shows most similarities is chosen as a solution. A concept
denition is learned when an unclassied problem can b e classied correctly.
•
Instance-based reasoning
This is a sp ecialization of exemplar-based reasoning
that aims at
automated learning
without user interference and fo cuses on a
syn-
66
3. Related approaches
tax
-oriented approach. Less background information is available, the data mo del
is relatively simple and a bigger numb er of cases is necessary to nd a concept
denition.
•
Memory-based reasoning
The case base is seen here as a large piece of memory.
The reasoning pro cedure corresp onds to navigating and searching through the the
memory. Consequently, herein typ es of organizing and accessing the memory and
pro cessing metho ds are fo cused.
•
Case-based reasoning
Although the term
case-based reasoning
is used more
generic throughout the thesis, it diers typically from the other reasoning metho ds
mentioned in a numb er of asp ects. First, a case is considered rich of information
and has a rather complex organization in contrast to the data mo del of instance-
based reasoning. Second, more general background knowledge can b e used in a
situation-dep endent context. Finally, CBR distinguishes itself by the ability to
modify
a retrieved solution, which allows and implies user interference.
•
Analogy-based reasoning
Although closely related to CBR,
analogy-based rea-
soning
fo cuses on nding
analogies
b etween problem domains. That ability char-
acterizes metho ds which solve new problems by basing their solutions on solved
problems of
dierent domains
, whereas CBR matches cases within one problem
domain.
Pro cess mo del view on CBR
Eective problem solving with CBR involves a numb er
of steps. When a new case comes up, it must b e rst analyzed to determine the typ e
of problem. Next the case based can b e searched for similar cases that match the new
problem suciently with resp ect to chosen criteria. If a previous case matches the new
case, it is used as a prop osal for a new solution. After eventually necessary adaptions
have b een made to the prop osal and it has b een accepted as a solution for the new case,
it can b e added to the case base and b ecomes a
learned case
. From this p oint on, the
solution for the next new case relies on the improved case base. Formally, these actions
are represented by
retrieval
,
reuse
,
revision
and
retainment
phases. The cyclic nature
of this pro cedure b ecomes evident by a glance at Figure 3.1 which illustrates the steps
mentioned in a generic CBR cycle.
67
3. Related approaches
New
case
Problem
Retrieved
case
New
case
Solved
case
Tested/
Repaired
case
Learned
case
previous
cases
previous
cases
Previous
cases
General
knowledge
Confirmed
solution
Suggested
solution
retrieve
reuse
revise
retain
Figure 3.1.: CBR cycle (compare [AP94] Figure 1)
The generic CBR cycle in Figure 3.1 consists of the CBR main tasks: Up on the reception
of an incoming new case, the user retrieves the most similar cases by using general
domain-sp ecic knowledge and provided case retrieval metho ds. He further reuses the
available information to solve the new case, revises the prop osed solution and retains
interesting and relevant information in a learned case for future cases.
As the illustrated CBR cycle already indicates, the main problem areas of CBR are
knowledge representation and metho ds for retrieval, reuse, revision and retainment.
Within each area, one faces a numb er of questions whose architectural answers aect
the functionality of a CBR implementation.
Knowledge representation
Within a case base, gained exp erience and learned lessons
are stored. Together with generic domain knowledge it is fundamental for the overall
problem solving pro cess. Thus, it is crucial to decide on a data structure that is b oth an
eective knowledge representation and eciently accessible. What information should
68
3. Related approaches
b e stored in a case? The more information is packed into it, the more likely it is to
detect commonalities b etween related cases. Much irrelevant or redundant information
however makes the case base hard to use and reduces eciency. The need for ecient
structures do es not only apply to the organization of cases, but also to the internal
structure of each case. A chosen data structure needs to b e extensible as the case base
incrementally grows with each learned case. The more indexes and other data structures
are created for accelerated output, the more administrative data has to b e up dated for
each alteration of the case base. Finally general domain knowledge has to b e integrated
with the case base in a way that integrates them in requests. It may have for example
the form of a rule base containing "b est-practice" rules which are applied to each query
b efore it is directed to the case base.
Case retrieval
is clearly identied by its input and output: It starts with the reception
of an incomplete problem description as input and outputs the b est matching case from
the case base. Three ma jor steps lead to the desired outcomes. The input is rst
analyzed in order to
identify its features
. This corresp onds to the acquisition of a true
understanding for the present problem. The set of features is used for an
initial matching
procedure
in order to identify a numb er of candidates within the case base that are
p otential solutions. Next a
selection process
of the most promising results renes the
matching set until a b est matching case b ecomes evident. Eventually matching and
selection are one single step, but they usually dier from each other by the applied
depth of analysis. While matching is more sup ercial, selection analyzes more detailed
the relevance of identical and non-identical features.
Case retrieval needs a measure or metric to compare the similarity of cases and the
relevance of features: Those measures can b e either based on
syntactic
or
semantic
similarities. Syntactic measures are simpler to apply and return a rather sup ercial result
while semantic similarities are more accurate and more complex to obtain. Semantic
matching requires general domain knowledge in order to interpret for example contextual
information. Identifying a set of features from the given input and concluding on a
problem typ e requires a typ e of a semantic network that correlates terminology.
Example 17.
A straightforward example for a similarity metric is used in CBRFlow
[WWB04]. A query
Q
on the case base represents a new problem and is matched
against a solved problem
C
from the case base for similarity. Features of cases are
detected in this approach by a question-answer pro cess; thus a set of answered questions
{QA1,...,QAm}
comes with
Q
. A comparison of these questions and answers in pairs
yields an observation whether the pair is matching or not. The similarity is calculated
as the normalized dierence b etween the numb er of shared observations and the numb er
of conicting observations.
sim
(Q, C) =
same
(QQA, CQA)−
di
(QQA, CQA)
|CQA|
Case reuse
is based on the identication of matching and diering attributes b etween
69
3. Related approaches
the old and new case. While the useful parts of the old case have to b e extracted into the
new case, the non-matching parts are to b e left out. In a more simplistic scenario it is
sucient to make a comparison for similarities the dierences b etween the cases app ear
irrelevant and are abstracted away. Then b oth cases are reduced to the problem class
and the retrieved case is
copied
as a solution to the new case. More realistic however is
a scenario where the retrieved case can not b e transferred immediately to the new case
but requires
adaption
.
Adaption is achieved by either nding a
transformation
that translates the old solution
into a new solution or
deriving
the past metho ds such that it pro duces a solution for
the new case. Transforming the solution is only appropriate though if the case is rather
output oriented and the pro cedures themselves are not crucial to the success of a case.
Example 18.
During the pro cess of designing a car b o dy, mechanical engineers use a
virtual prototyp e called
digital mock-up
which is equipp ed with metho ds to check for
collisions of b o dy parts during development. Dep endent on the typ e and severeness
of collisions, synchronization of collab orate work and resolution of problems can b e
classied in several cases. For minor issues the transformation of older solutions is
likely to b e sucient b ecause here only the outcome (which is a resolved collision) is
relevant. However, if the collision is more complicated and involves meetings of several
disciplines, then the resolution pro cess itself in the form of inter-p ersonal communication
is imp ortant as well and is inuenced by many external parameters. Comparable cases
from the case base must then b e adapted and reenacted instead of a replication and
mo dication of their former solution.
Case revision
evolves out the lack of correctness or completeness of a reused solution.
It includes the evaluation of the reused case in order to clarify its deviation from current
requirements. After this has b een found out by simulation or applying domain knowl-
edge, a learning eect is accomplished by extending the case base with the new ndings.
Furthermore, faults in the reused case may b e repaired by generating explanations for
them. Based on an explanation, mo dications can b e develop ed to repair a case solu-
tion. After a case has b een revised, it should b e assured that it can b e applied without
exceptional b ehavior.
Case retainment
enables the learning pro cedure within CBR by incrementally extend-
ing its case base. Dep ending on whether the new case has b een derived from a past case
or was newly dened, existing cases are generalized by supplemental features or new
cases are added. Problem and solution descriptors as well as indexes for case retrieval
metho ds have to b e refreshed for the up dated case base to take eect.
3.1.2. Applications
CODAW
The Case-Oriented Design Assistant for Workow Mo deling (CODAW) is
an approach that aims at supp orting workow mo del reuse during workow design.
70
3. Related approaches
Madhusudan et al. p oint out the lack of useful standards regarding pro cess mo del
storage, retrieval, reuse and assembly. In [MZ03, MZM04], they present an architectural
prop osal for
case representation
,
case retrieval
and
case composition
.
Manual pro cess mo deling is here considered a traversal of a "design space" dened by
a large numb er of pro cess mo del alternatives and the selection of an optimal pro cess
mo del that reects the given problem b est. Two phases are identied within pro cess
design:
In the rst phase, relevant business tasks are put into a
partial ordering
that satises all
preconditions and p ostconditions. Multiple pro cess mo dels can b e found that meet these
requirements. In the second phase, the favored pro cess mo del is
selected
and
completed
:
Routing is optimized with resp ect to exibility and parallelity and appropriate agents
and resources are asso ciated with the mo del. In b oth phases of design, pro cess knowledge
from the rep ository in the form of cases may b e reused.
Search for existing process
models with similar
requirements
Apply minor modifications
and reuse case
Compose a new case
Apply modifications using
domain knowledge:
Validate/verify new solution
Use domain knowledge and
partial matches to create
new process alternatives:
Store new case in repository
Similar solution does not
exist but partial matches
Similar solution exists
New Business
Requirement
Deploy solution
Repository
Domain
knowledge
Select tasks, constraints,
generate alternative
process sequences
manually or automatically
allocate resources and
agents
Flow of process model
Flow of repository
knowledge
RETRIEVE
REUSE REVISE
RETAIN
adapt tasks/task structures
change resource
allocation, agent routing, ..
Figure 3.2.: CODAW workow design pro cess (adapted from [MZ03] Figure 2)
71
3. Related approaches
Figure 3.2 shows the simplied design pro cess of pro cess mo deling using CODAW. In
compliance with the generic CBR cycle (Figure 3.1 on page 68), its pro cedure splits
up into four phases: Retrieval, reuse, revision and retainment. An incoming business
requirement initiates
retrieval
by searching the rep ository for pro cess mo dels with sim-
ilar requirements. If a match is made, then the found case is slightly
modied
and
reused
, otherwise a new pro cess must b e comp osed. The mo dication for reuse are mi-
nor structural/semantic changes such as the replacement of a task or the mo dication of
the pro cess schema. Additionally, instance-sp ecic settings such as resource allo cation
need to b e set up individually, even for pro cesses of the same typ e. Validation and
verication uses measures such as domain-sp ecic correctness checks, visualization or
simulation and assures the correctness of a repro duced case. For knowledge
retainment
,
the newly develop ed pro cess is not only deployed to the workow management system
after checking, but also stored into the rep ository for later reuse. If no suitable template
could b e found during case retrieval, a new case has to b e comp osed. Creation relies
on domain knowledge and eventual partial matches for the synthesis of new pro cess al-
ternatives. This is done either entirely manual or is supp orted by a planning software,
whose basic principles will b e mentioned b elow. Revision is nalized in the same way by
validation and verication, retainment and the solution is deployment just like a reused
case.
Case representation
is here approached by separating
prototypical cases
from
instance-
level cases
. In the terminology of this thesis, a prototypical case comes close to what
we refer to as a pro cess denition and an instance-level case would then b e a pro cess
instance. Prototypical cases contain the sequence of activities and represent a pro cess
schema for a generic business requirement. Instance-level cases depict the execution trail
of a prototypical case for a sp ecic input. One prototypical case can b e asso ciated with
several instance-level cases.
In CODAW's pro cess ontology, the existence of primitive tasks which can b e combined
into more complex pro cesses is assumed. A pro cess schema denes then internal struc-
ture of a comp osite task. Furthermore, it is p ossible to create hierarchical structures by
reusing a schema as a comp onent tasks in another pro cess.
The implementation of pro cess denitions and instances is based on XML Schema and
leans towards standards such as XPDL
1
, WSFL
2
, XLANG
3
and BPEL
4
. A rep ository
organizes prototypical and instance-level cases as well as a collection of primitive tasks.
Cases are arranged in a hierarchical directory structure in at XML les. It indexes
cases according to their functional application area, task and organizational structure.
1
See the XML Process Denition Language Sp ecication Version 1.0 Final Draft:
http://www.wfmc.org/standards/do cs/TC-1025_10_xp dl_102502.p df
2
See the Web Services Flow Language Version 1.0:
http://www4.ibm.com/software/solutions/webservices/pdf/WSFL.p df
3
See the XLANG Initial Public Draft Release http://www.gotdotnet.com/team/xml_wssp ecs/xlang-
c/default.htm
4
See the Web Services Business Pro cess Execution Language Version 2.0: http://www.oasis-
op en.org/committees/download.php/11600/wsbpel-sp ecication-draft-022705.htm
72
3. Related approaches
Retrieval is implemented by plain text search or XQuery requests doing exact matches
on dened XML tags.
An example of the XML representation of a new pro duct development pro cess schema
is given in App endix A.1.1. It b ecomes evident by the example that a pro cess schema
consists of three sets of tags (in parentheses the corresp onding line numb ers of the exam-
ple is given): General
descriptive
tags for ID, name, typ e and description of the schema
(lines 2 5),
workow level structural
tags to describ e the overall pro cess (lines 6 14)
and
task level
tags sp ecifying tasks and their parameters (lines 15 64). It is substan-
tial to notice that each task is dened in three ways: First, a state-space declarative
AI planning based representation is given by the tag
TaskDesign
(lines 21 37) and
is used for case comp osition. Second a formal mo del representation using pro cess alge-
braic representation is denoted by tag
TaskFormal
(lines 38 40). In the example, this
is textual description of a simple sequential nite state automaton. Third, a pro cedural
task denition denoted by
TaskDefn
(lines 41 63) highlights the implementation of
related attributes of the task such as roles (lines 42 48, named "Agent"), pro cedure
description (lines 49 53) and data I/O (lines 54 62).
An illustration of the XML schema of an instance representation is shown in Figure
A.1 in App endix A.1.2. IDs identify the instance and the pro cess schema it originates
from. It captures its execution history by recording data inputs and outputs, execution
p erformance metrics and a history of events.
Similarity-based case retrieval
emb o dies a exible notion of similarity that combines
features of domain knowledge and pro cess graph structures. Case retrieval in CODAW
relies on an algorithm by Melnik et al. named
Similarity Flooding Schema Matching
Algorithm
[MGMR02]. It is an inexact and generic similarity based schema matching
algorithm. The strength of this approach lies in its versatility that makes it applicable
to many structures, including b oth pro cess schemata and instances.
It takes two graphs as input and generates a mapping b etween no des that app ear to
corresp ond. A threshold is dened in order to lter out the most relevant matches.
Similarity Flo o ding is meant to supp ort a human in the matching pro cess rather than
creating a complete matching autonomously. That is why the nal step is to present the
most relevant matches to a human who revises and corrects them where needed.
The algorithm can b e briey describ ed as follows: First it transforms the two input
structures into directed lab eled graphs. The core idea of the matching pro cedure b etween
those graphs is to combine two ideas: As a starting p oint, a string comparison of common
prexes and suxes b etween designations of graph elements is p erformed. Based on the
assumption that, if two no des are similar, then their neighb oring no des are similar as
well, an iterative xp oint computation follows. Thus, a no de propagates its similarity
to its adjacent no des, who themselves continue propagation of similarity up dates until
a stable state, the xp oint, has b een reached. Propagation relies on o o ding algorithms
73
3. Related approaches
(such as the Distance Vector Multicast Routing Proto col
5
) which explains the naming of
Similarity Flo o ding. Notice that this algorithm do es not have any semantic knowledge
ab out the contents of the input it is pro cessing. Instead, semantic knowledge ab out
pro cess mo dels is replaced by the explicit representation and mutual inuence of name,
typ e and attributes of pro cess mo del elements.
Similarity Flo o ding for workows runs on a graph representation that explicitly mo dels
no des for tasks and control structures such as in a Petri Net. While task no des are named
according to their underlying task typ e, all control no des share a common descriptor in
order to make their common typ e recognizable for Similarity Flo o ding. By dening
the similarity measure b etween any control and task no de as 0, an accidental match
b etween dierent element typ es is avoided. While similarity values applying for matches
of control no des are limited to discrete values 0 or 1 (representing no match or full match
resp ectively), matches of task no des can range continuously b etween 0 and 1 according
to their substring similarity.
The matching algorithm results in a ranked list of map pairs including their nal sim-
ilarity after convergence, from which the most relevant subset can b e chosen as a nal
mapping. As a manual selection of this map would turn out to b e a tedious task, a lter-
ing pro cess is applied b efore the resulting table is b eing presented to the user. Filtering
rules rely on exp erimentally determined similarity thresholds or can make use of domain
sp ecic knowledge. The accuracy and eciency of Similarity Flo o ding for workows is
mainly determined by a go o d choice of threshold and is further examined exp erimentally
as found in [MGR02].
Functional limitations apply to Similarity Flo o ding as it only works and p erforms on
directed graphs suciently. Based on its algorithmic idea, it accounts only for semantic
similarity which is b eing reected by no de and edge lab els and top ological similarity of
the compared graphs. As far as computational resources are concerned, the size of input
graph no des is limited by the fact that intermediate graph structures are based on cross
pro duct op erations with exp onential costs.
Case comp osition
is invoked by CODAW if either case retrieval fails to nd a matching
recent case or when retrieved cases have to b e comp osed. If no matching case was found,
a new pro cess mo del is generated by the comp osition of primitive tasks. The input of case
comp osition describ es a business problem dened in a planning language. The output
is a set of declarative pro cess mo dels that characterize its attributes and constraints in
an enumerative style.
Case-based planning in the CODAW framework uses the
Simple Hierarchical Ordered
Planning
(SHOP) algorithm, an implementation of the Hierarchical Task Network plan-
ning technique. Its approach is to create plans by task decomp osition and constraint
satisfaction. The SHOP algorithm supp orts reasoning on interactions b etween task
preconditions and p ostconditions during state-space search for developing plans. Addi-
5
Dened in RFC 1075, compare also Kurose and Ross [KR93] p.308 et sqq.
74
3. Related approaches
tionally, SHOP allows reuse of appropriate prototypical and instance-level cases from
rep ositories during problem solving.
The SHOP algorithm works roughly as follows: A planning problem is rst sp ecied by
an initial task network, which is a collection of tasks that need to b e p erformed under
a sp ecied set of constraints. The planning pro cess decomp oses tasks in the initial
task network into progressively smaller subtasks until the task network contains only
primitive tasks or op erators. The decomp osition of a task into subtasks is p erformed
using a metho d from a domain description. This metho d sp ecies how to decomp ose the
task into a set of subtasks. Each metho d is asso ciated with various constraints that limit
the applicability of the metho d to certain conditions and dene the relations b etween
the subtasks of the metho d. The planning algorithm p erforms a recursive search of the
planning state space via task decomp osition and constraint satisfaction. It terminates
either when all a solution has b een found that meets all pre- and p ostconditions or
when it tries to backtrack a comp osite task that do es not oer any more metho ds to
decomp ose successfully.
The SHOP algorithm is able to generate a sequential workow which requires p ost-
pro cessing in order to add concurrently executed tasks by the analysis of data and
causal dep endencies. The eectiveness of the SHOP algorithm strongly dep ends on
an appropriate design of the predicates, op erators and metho ds. In the worst case, it
explores the complete search space incurring exp onential costs. With resp ect to that
issues, time-out mechanisms may b e used to ensure termination.
Conversational case-based reasoning
A
conversational case-based reasoning
(CCBR)
system as prop osed by Web er et al. in their system CBRFlow [WWB04] is a hybrid rea-
soning approach combined with user interaction.
Rule-based reasoning
pro cedures are
supplemented by
case-based reasoning
which improves adaptivity of the overall system.
Business rules are a set of statements representing general, domain-sp ecic knowledge
that regulate the course of pro cesses, such as instantiation or exception handling. A set
of business rules is predened in the pro cess mo del and is annotated during run time
with cases having context-sp ecic information. The business rule set denes the de-
fault system, whereas cases add sp ecic knowledge gained by previous concrete problem
situations.
CCBR approaches to integrate machine learning metho ds from CBR with continuous
user interaction in order to enhance the learning pro cess and to overcome weaknesses of
pure machine approaches. A case in CBRFlow consists of a free textual
description
, a set
of question-answer pairs give the
reason
for the case and
actions
. An action is sp ecied
by the change op erations taken and the sub ject they are op erating on. In contrast to
traditional CBR, problems do not need to b e sp ecied a priori completely in CCBR.
Instead, the system is assisted by user interaction in an initiated dialogue of questions
and answers that helps to retrieve the desired case or to evaluate the relevance of case
features. This dialogue pro ceeds incrementally until the user has pinp ointed a solution.
75
3. Related approaches
Process
modeler
Process
user
Rule base Case base
is abstracted to
adds rule adds case
is annotated by
Process design time Process enactment time
Figure 3.3.: Adaptive workow management approach with CCBR (compare [WWB04]
Figure 1)
The adaptive workow management approach of CCBR as shown in Figure 3.3 starts
with an initial mo del. It consists of a set of business rules which are formalized for
example in event-condition-action (ECA) form. These rules describ e the mo del's control
ow. During run time, instances of a mo del are created and users work with them.
Whenever changing requirements or exceptions cause deviations from the mo del, a user
annotates the corresp onding business rule by adding a case. The case describ es, in which
context what kind of deviation b etween reality and mo del o ccurred. Over time a case
base b ecomes established and shows, which kinds of exceptions from business rules o ccur
more frequently than others. Based on that information, pro cess mo delers analyze those
cases which describ e concrete exceptional situations and abstract from them changes
on business rules that incorp orate the mo died requirements. Thus the original pro cess
mo del is adapted to changing environments. As changes to case and rule base can b e
temp orally overlapping or take place concurrently, a pro cess mo del adapts incrementally
without strictly separated design and enactment phases.
The fundamental distinction b etween rules and cases is that rules are applied auto-
matically, whereas cases require user interaction. Reasons that induce cases such as
exceptions or helpful annotations are to o manifold than to b e pro cessed automatically
and need to b e checked manually. Cases are used in two ways: One typ e supplements
the rule base by referring to sp ecic contexts that cause changes. Alternatively a case
up dates a sp ecic rule by "hardco ding" the case with it. That way a case can up date a
particular rule.
Applying hybrid reasoning in the form of CCBR b ears several b enets over pure rule-
based reasoning: Explicit initial pro cess mo deling is allowed to b e incomplete or rather
low-detailed. Esp ecially b efore pro cess enactment it is very hard or exp ensive to nd
all imp ortant rules or parameters inuencing the pro cess. As improvement of mo dels
with CCBR is more continuous than reengineering the rule base, a starting mo del is
more exibly adapted to the starting and continuously changing environment. Cases
enable users to express immediate manual adaptions and serve as a decision supp ort
system. The selective transfer of cases into rules dierentiates one-time exceptions from
76
3. Related approaches
more systematic changes caused by new circumstances. Due to its high frequency, the
latter is abstracted into the mo del and b ecomes more ecient b ecause it is executed
fully automated.
WorkBrain
WorkBrain
is a system presented by Wargitsch et al. in [WWT97 , WWT98 ]
that integrates an
evolutionary
workow management system with an
Organizational
Memory Information System
(OMIS). A workow management system b eing evolution-
ary addresses here a step-by-step development of the workow that involves its partici-
pants in incremental pro cess design.
The concept of an
Organizational Memory
represents an organization's ability to retain
previously made exp erience, so-called "learned lessons". Its existence is desirable as
it leads to improved p erformance and higher eectiveness. Usually it do es not exist
implicitly within an organization's structure but has to b e established explicitly. An
OMIS tries to implement the concept of an organizational memory with information
technology. On its own, an OMIS do es not dier substantially from common information
systems or databases that span over a large knowledge domain. Therefore, it do es suer
the same weaknesses b ecause its access metho ds are often insucient to nd data and
to interpret them correctly: Usability is hard to manage for p otentially many typ es of
involved users, the costs for maintenance in order to keep the data basis up-to-date,
consistent and correct are high.
By integrating an OMIS with a workow management system, WorkBrain attempts to
overcome each individual system's deciencies
6
. In order to put its evolutionary idea into
practice, its concrete learning approach is twofold:
Learning by example
enables workow
users to intro duce sp ontaneously new elements into the pro cess. This provides a more
creative way of design and p ositions its results closer to op erations. At the same time,
pro cess designers observe and reect those changes of the users and apply revisions that
are more durable and ecient. This part of an evolving workow management system
is called
learning by supervision
. Together, these learning cycles form a
double-loop
learning approach
that is depicted in Figure 3.4.
6
The deciencies of a regular workow management system were presented in Section 1.1
77
3. Related approaches
Process
designer
Process
user
General
knowledge
Cases
Organizational
memory
Modification
Analysis
Archiving
Execution
Planning
Outer cycle: Inner cycle:
“Learning by examples”“Learning by supervision”
Figure 3.4.: Double-lo op learning (compare [WWT98] Figure 1)
Central comp onent of double-lo op learning is the organizational memory. One part is a
case base lled with terminated workows and related audit data. The other part b ears
domain sp ecic knowledge. Both learning lo ops are attached to the organizational mem-
ory, "learning by sup ervision" as the outer cycle and "learning by examples" as the inner
cycle. The pro cess designer analyzes cases within the organizational memory by observ-
ing their structure and frequency and mo dies pro cess mo dels accordingly. Pro cess users
plan their activities and pro cess executed instances. For treatment of up coming excep-
tions during execution, they rely on the organizational memory. Subsequent solutions
for exceptions are archived as cases in the case base.
In order to simplify usage, partial pro cesses called "single building blo cks" are stored
as cases rather that entire pro cesses. By this mo dularization, the numb er of variations
within cases decreases signicantly. Building blo cks exist on various level of granularity,
that is, blo cks are based on a varying level of detail. The lowest level represents an
elementary activity, intermediate levels are sets of activities or subpro cesses. The top
level is represented by a complete pro cess phase. For each level, a catalog describ es the
available cases within the case base.
A further implemented concept is separation of control: Organized in two layers, a man-
agement layer denes milestones, b eneath actions are self-managed by subunits and users
in a second layer. On the management layer the pro cess is automated and for subunits
an ad-ho c changeable subpro cess allows optimization and more control on details.
The advantage of using an OMIS is that it integrates pro cesses and information. Knowl-
edge b ecomes explicitly stored and do es not get lost when employees leave an organiza-
tion. Both parties, pro cess users and designers apply changes to pro cess instances and
typ es resp ectively. Thus pro cesses can adapt to changing internal and external require-
78
3. Related approaches
ments. Due to the outer learning cycle, continuous analysis makes it easy to check for
p erformance, goal attainment and to apply b enchmarking and monitoring metho ds.
The WorkBrain approach app ears very similar to CCBR: Both improve the pro cess
incrementally by allowing the user to make adaptions according to his current situation
using a case base. However, in contrast to CBRFlow, WorkBrain interprets and uses
the case base in a broader sense as a part of an organizational memory. While in CCBR
a case base is a set of deviations, exceptions and adaptions, in WorkBrain it contains
b oth fundamental and supplemental data.
Exception handling with CBR
Hwang et al. aim in [HHT99] at supp orting users on
exception handling with a case base of past exceptions. When a new exception shows up,
the system prop oses solutions of previously exp erienced exceptions based on similarity
measures.
Two typ es of exceptions are dierentiated: Those that are
expected
and are treated by
implementing explicit mo deling for exceptions. These are typically adaptive workow
approaches, such as ADEPT [RD98]. The other typ e of exceptions which o ccur com-
pletely
unexpected
are dealt with in this approach: Reactions for exceptions include
ignoring them, retry the failed activity, p erform a partial rollback of the pro cess, add
comp ensation activities or delete planned activities and make general evaluations for
correctness.
Their idea of exception handling has two steps: First, a rule base is consulted. Each rule
refers to a typ e of exceptions. If a matching rule could b e found, then the rule tells how
to resolve the exception. The rule base represents domain sp ecic knowledge that makes
it p ossible to sp ecify instantly the correct treatment of a predened typ e of exception.
If the rule base fails, then in a second step the user searches through a case base lled
with exceptions for similar exceptions and their resolution. Search is done by a similarity
metric, that is based on a numb er of attributes that characterize a particular exception:
•
Pro cess instance status
holds the execution state of a pro cess instance and all
its constituent activities (compare Section 2.4.2)
•
Activity
describ es which activity caused the exception
•
Event
gives a semantic description of the typ e of exception sp ecied by keywords
and/or free text
•
Who
exp erienced/noticed the exception?
•
When
in time did the exception happ en?
A complete matching b etween all attributes of the current exception and an stored
exception in the case base is very unlikely. In order to implement a similarity measure,
79
3. Related approaches
a key idea of this pro ject is to formalize and classify the relevance of attributes and their
inuence on the similarity of exceptions in
concept hierarchies
. For each attribute typ e,
concepts are ordered hierarchically in a tree structure such that the most general concept
is the ro ot of the tree and more sp ecic concepts are organized in branches. Within
hierarchic trees, the
depth
of a no de denotes its distance from the ro ot.
Levels
in contrast
describ e the depth of a no de
i
with regard to the tree's lowest leaves. That is,
leveli=
depthm−depthi
with
m=max{depthn|n∈T
,
n
is a no de,
T
is a concept tree
}
.
Example 19.
A concept hierarchy for the attribute
Activity
corresp onds to a task
decomp osition of the activity as shown in Figure 3.5.
Window power
lifter assembly
ME components EE components SD components
Button GearsMotor Controller SensorsActors Firmware Software
Level
2
0
1
Figure 3.5.: Example: Concept hierarchy of a window p ower lifter assembly
The assembly of a window p ower lifter constitutes comp onents from the three disciplines
mechanical engineering, electrical engineering and software development. The leafs of
the tree represent the lowest level 0. With each parent no de, the level increments.
Let the tuple
< a1, a2,...,ak>
b e a numb er of
k
attributes that describ e the current
exception. This is matched against the attributes of solutions
< s1, s2,...,sk>
in the
case base. A function
leastCommonAncestor(< ai, si>)
takes two attributes as input
and returns the least common ancestor
l
of b oth in the concept tree. That is, it returns
the no de
l
in the concept tree at the lowest level p ossible, that contains b oth
ai
and
si
in its child branches. The level of
l
is an measure for the similarity of the compared pair
of problems and solutions with resp ect to the
i
th
attribute: The lower the level of
l
, the
more similar is the solution to the given problem.
80
3. Related approaches
Example 20.
This example illustrates the
least common ancestor
concept building
on Example 19. Supp ose a problem is describ ed among others by an attribute
ai
that
sp ecies the activity typ e. Two solutions
s
and
s0
are found in the case base. The values
for each one of these attributes are shown in Figure 3.6.
Window power
lifter assembly
ME components EE components SD components
Button GearsMotor Controller SensorsActors Firmware Software
Level
2
0
1
aisis’i
li
l’i
Figure 3.6.: Example: Least common ancestor in a concept hierarchy
The least common ancestor
li
for
< ai, si>
and
< ai, s0
i>
has level 1 and level 2
resp ectively. Because of its lower common ancestor level, solution
si
is preferable over
s0
i
: This makes sense b ecause an exception that o ccurred during the assembly of gears
is more similar to an exception on button assembly than an exception during rmware
upload.
If additionally a weight function is dened, the relevance of each attribute can b e
weighted individually. Adding the weighted attributes up returns a similarity index
b etween the current exception and the solution. Based on this index, the b est matching
solution is prop osed. The b est solution with the lowest overall index matches as the
most relevant solution on the lowest level in the concept tree.
Apart from eciency and implementational issues
7
, the concept tree approach is limited
by two issues: First, a weight function inuences the matching pro cess heavily and has
to b e set for each up coming problem individually in order to optimize results. Finding
a generic weight function that matches most problems well might to turn out to b e very
hard. Second, the foundational assumption of concept trees is that all attributes can b e
broken down hierarchically. This is not necessarily true for all typ es of attributes and can
b e ambiguous, to o. An
Activity
attribute might b e decomp osed either in a more logical
fashion or a way that reects b etter the temp oral asp ects of the tasks that constitute
the activity. The rst would b e formally more correct, while the second reects b etter
on reality.
7
Implementational issues are discussed in [HHT99] in detail
81
3. Related approaches
3.1.3. Assessment of usefulness
CBR in general b ears many useful asp ects for Emergent Workow: Its learning & reuse-
based approach has b enets for handling recurring problems more eciently. In ap-
plication, it has b een identied to b e well suitable for slight variations around clearly
identiable tasks. As an integrated approach, CBR must b e combined with new case
creation metho ds in order to b e useful.
CODAW on page 70 intro duces multiple interesting asp ects for Emergent Workow: Its
XML based pro cess mo del and instance represents a lightweight alternative to BPEL,
XPDL and other standardization eorts. In fact, this may b e due to the fact that
CODAW including its case representation has b een develop ed for an engineering appli-
cation eld which allows to reduce generic constructs. With resp ect to the Emergent
Workow requirements summarized in Table 2.4, Section 2.3.10, these representations
can b e used for temp orary instance representation (R1a, R1b) and p ermanent storage of
pro cess mo dels (R2c) and fragments (R2d). In particular, this instance representation
allows annotations (RE9) (this feature is here meant for administrators, but could b e
used by users as well). Its state-space declarative representation allows the represen-
tation of task comp ositions (R2e). As the representation is XML based, basic access
metho ds like XQUERY for full-text search exist(R4). Furthermore, the similarity o o d-
ing schema matching algorithm is versatile enough to b e used in the pro cess matching
engine for searches with qualitative constraints (PM1). It p erforms an approximate,
schema-matching search (PM2, PM3) on syntactic similarity (PM4) and allows ltering
of its outputs (PM5). The planning algorithm SHOP can b e used for automated case
selection and planning supp orting the recognition of cases (RE5). As it is able to com-
p ose and decomp ose comp osite tasks, it may b e used by pro cess designers for fragment
comp osition (UI1).
CCBR on page 75 improves human-machine interaction: Fundamental to this approach
is the separation of automatic rules and manual cases. A mixed-initiative, conversation-
based case nding enhances usability of a system (UI2). Furthermore, reinstantiation of a
dened case is done manually but already predened (RE5). It invokes an exact matching
algorithm (PM2) based on descriptive and quantitative attributes and constraints (PM2,
PM3). The analysis of the case base is done manually (RE5).
WorkBrain on page 77 intro duces the concept of an Organizational Memory Information
System. This integrates general knowledge with cases representing archived instances
(R2d). The dictionary and organizational mo del in Emergent Workow can b e seen
as a reduced version or a part of the organizational memory (R2a, R2b). Double-lo op
learning addresses the evolution of pro cess mo dels initiated by workow users (RE6,
RE9) and revised and p ermanently implemented by pro cess designers (RE4, RE7).
The work by Hwang et al. on exception handling on page 79 intro duces exception han-
dling (RE6) by using a rule base for automated handling and a case base that supp orts
manual resolution of exceptions (RE5). Based on their idea of concept hierarchies, this
82
3. Related approaches
approach p erforms similarity matching b etween exceptions using exception attributes.
This is a quantitative (PM1) and exact (PM2) matching typ e based on a descriptive
(PM3) search for structural similarity (PM4). The concept of least common ancestors
allows to put an index on results and to sort them (PM5).
3.2. Pro cess mining
3.2.1. Fundamentals
Explicit creation of pro cess mo dels is a lengthy task and its outcomes do not always
reect the real pro cess accurately. The goal of
process mining
is to reverse the pro cess
and collect data at run time to supp ort workow design and analysis. Van der Aalst et
al. describ e
process mining
resp ectively
workow mining
in [ADH
+
03] as follows:
The term
process mining
refers to methods for distil ling a structured process
description from a set of real executions. Because these methods focus on
so-cal led case-driven process that are supported by contemporary workow
management systems, we also use the term
workow mining
.
Diagnosis
Process
design
System configuration
Process
enactment
Workflow mining
Traditional approach
Delta analysis
Figure 3.7.: Workow mining in the business pro cess life cycle (compare [ADH
+
03] Fig-
ure 1)
The business pro cess life cycle has already b een intro duced in Section 1.1 (Figure 1.1 on
page 2). In Figure 3.7, the role of workow mining is shown in the context of the business
83
3. Related approaches
pro cess life cycle. While the traditional approach starts with pro cess design and develops
mo dels which are later enacted, workow mining takes the outputs of pro cess enactment
and supp orts pro cess design. This is p ossible b ecause implicitly pro cesses do always
exist, even if they were not explicitly mo deled in a preceding design phase. Involved
software such as an ERP system usually keeps track of events and transactions and
provides logging functionality. Pro cess mining can use this information as a starting
p oint for the derivation of a formalization of the ongoing pro cess. A
delta analysis
compares bidirectional the designed pro cess mo dels with mined real pro cesses from the
enactment phase. This "delta" gap b etween a mo del and its actual b ehavior shows
discrepancies that can indicate weaknesses of mo dels. These are very useful e.g. for
iterative pro cess improvement.
Input & output
A minimum
input
for a workow mining algorithm is a sequential
list of entries describing an event of the execution of a pro cess instance each. This list
is also referred to as a
log
. A log le must meet following minimum requirements:
•
Each log event refers to a task
•
Each log event refers to an instance
•
The log events are totally ordered
A minimal log is shown in Table 3.1.
Instance identier Task identier
Instance 1 Task A
Instance 2 Task A
Instance 1 Task B
Instance 2 Task C
.
.
.
.
.
.
Table 3.1.: Simplistic minimum activity log
When real-life information systems record proto cols of events, usually much more in-
formation is put into a log le: For each event, an
event type
is sp ecied such as
"start/stop". Additionally, a time stamp as well as further context-sp ecic can b e sup-
plied for each entry. Such would b e a transaction status, indication of exceptions, a user
causing the event or a case description within a certain instance. Notice that such addi-
tional information is necessary for a more sophisticated semantic analysis as Emergent
Workow intends to do (see Section 2.3.6).
The
output
of a mining algorithm is a representation of a pro cess mo del or an incomplete
template indicating its schema. The outcome determines how much of the business
pro cess cycle can b e skipp ed by mining (see Figure 3.7 on page 83) a log le. Workow
84
3. Related approaches
mining is either able to step over the whole pro cess design phase if resulting mo dels are
ready for enactment or gives a starting p oint for pro cess designers who revise a provided
template.
Problem denition
Mining a pro cess graph can b e seen as two subproblems:
•
Finding of a schematic graph structure that generates the log output.
The extraction of a set of structural dep endencies (which are usually visualized
in a pro cess graph) from a set of logged events is what most mining algorithms
are dealing with. With some limitations, this can b e done based on a minimum
input log by a syntax-analyzing algorithm without user interaction. Notice that
most algorithms do not fo cus on the reconstruction of the
exact
generating graph
but create a
sound
and
equivalent
graph which has the same output. That is, any
reachable marking state in the graph is legal and terminates correctly with the
same functional result as the original.
•
Finding of edge conditions.
The second step of recreating a pro cess mo del is
less straightforward as it requires an understanding of the semantics of a pro cess.
Real pro cesses make use of conditional constructs such as exclusive branching and
lo ops. During the rst step, the fact that a conditional construct exists has b een
detected now it has to b e added
what
the condition was. If this is planned to b e
done by information provided by the pro cess log only, then the pro cess log must
b e enriched with supplemental data describing a task's and instance's context. For
example an exclusive conditional splits up two distinct alternatives identied by
a condition. If these two cases can b e identied, then it is p ossible to derive a
condition.
Complexity & Incompleteness
One can lo ok at a graph that represents a pro cess
mo del
P M
as a nite state automaton
8
. The pro cess schema denes here a grammar
on an alphab et
P
whose symb ols are tasks. A formal language
L
on
P
is then dened
by any subset of
P∗
.
L
consists of all words that can b e generated by a given grammar
over
P
. Then there exists an onto
9
function that maps each pro cess instance that was
enacted on
P M
to a word of
L
. The existence of such a function is evident b ecause
instances are not only sp ecied by their sequence of tasks, but also by their context.
What pro cess mining actually tries to do is to draw a conclusion on the pro cess schema
from a limited set of instances. As real-life business pro cesses are rather large, this set
is almost certain to b e incomplete. This situation equals to having an incomplete set
of words of an unknown language. Now one tries to guess a grammar that creates the
unknown language. This pro cedure is very unlikely to yield a correct guess. Therefore,
8
See any b o ok introducing language theory, e.g. M. Sipser "Introduction to the Theory of Computa-
tion".
9
Note to German readers: "Onto" translates into German "surjektiv".
85
3. Related approaches
there will b e always a dierence b etween the real pro cess and its mined reconstruction,
even though mining techniques attempt to make a very realistic guess that matches the
original pro cess mo del for certain classes of pro cesses quite well.
Example 21.
In this example, the conceptual idea of the
α
-algorithm [AWM03]
is given: The
α
-algorithm inputs an event log as shown in Table 3.1 and outputs a
Place/Transition net (P/T-net). P/T-nets extend the Petri Net formalism for use with
multiple concurrently running tokens
a
.
Fundamental for most mining algorithms is the idea of
causal relations
. It is dened
as follows: An activity B
fol lows
an activity A (
A→B
) if either B starts after the
termination of A or there exists an activity C such that C follows A and B follows C
(
A→C∧C→B
) in each instance log. If
A→B∧B9A
, then B
causal ly fol lows
A.
If
A→B∧B→A
or
A9B∧B9A
, then A and B are
independent
.
The basic functionality of the
α
-algorithm is the following: A task
exists
in the resulting
net if it app ears in any log trace. A task is either the rst task of a pro cess mo del or
has an ingoing edge for each task that this task
causal ly fol lows
. In an analogy, a task
is either the last task of a pro cess mo del or has an outgoing edge for each task that
causal ly fol lows
it. If a task is neither the rst or last task in a pro cess mo del nor do es it
have any causal relations, then it do es not receive any ingoing and outgoing edges. This
version of the
α
-algorithm mines simply structured graphs (including sequence, parallel
and conditional branching) mostly correct, but fails on structures containing short lo ops,
invisible or duplicate tasks and other advanced constructs. Supp ort for them requires
extensions which are further discussed in [ADH
+
03, MAW03].
a
See W. Reisig and G. Rozenb erg in "Lectures on Petri Nets I: Basic Mo dels", volume 1491 of "Lecture
Notes in Computer Science".
Diculties
Besides the conceptual problems of pro cess mo del recovery from log les,
additional conditions complicate the functionality of pro cess mining.
Noise
in pro cess logs describ es the fact that pro cess logs can b e not only incomplete,
but also incorrect. Due to human or technical errors, a log le is p ossibly disordered
or events themselves contain wrong information. Even with correct input logs, wrong
mo dels can b e mined due to coincidentally colliding events that are not related but are
misinterpreted by mining algorithms. Certain mining approaches try overcome this by
the intro duction of sto chastic mo dels and frequency tables that help to detect and ignore
erroneous entries
10
.
Privacy
is a non-functional issues that has ma jor impact of the usability of pro cess
mining. As an event log contains p ersonalized information ab out individuals interacting
with an information system, the storage and pro cessing of pro cess logs may b e sub ject
to restriction due to federal legislation or corp orate ethics. Functionality to anonymize
data b efore collecting it in an event log may b e required in certain situations.
10
Compare the work of Herbst and Karagiannis referred to in [ADH
+
03]
86
3. Related approaches
3.2.2. Multi-phase pro cess mining
Van Dongen and van der Aalst present in [DA04 ] a pro cess mining approach in a control-
ow p ersp ective, that creates visualizations of individual pro cess instances. It splits the
mining pro cess up into two phases: The rst step creates representations for each running
instance individually, the second step optionally merges the instance representations into
an overall pro cess mo del.
This is motivated by the fact that, during run time, analysis of p erformance is inter-
esting, such as the average time to transfer a task from one p erson to another. The
implemented pro cesses however dier from actual execution, therefore their analysis is
not sucient. Rather, individual execution trails are discovered by mining an individual
pro cess instance history from pro cess logs. So the basic idea is to lo ok at each instance
individually rather that lo oking at a combined, overall trace of events.
Without giving formal sp ecics,
instance graphs
are created as follows: A pro cess log
consists of a sequence of log entries that refer to multiple pro cess instances. Pro cesses
are mined by rst extracting an
instance net
and transforming that into an
instance
graph
. An instance net is based on an
instance domain
which links each log entry to a
task. This is necessary as duplicate tasks may app ear in a log le. The instance domain
indexes the log entries and enables their clear referral. The instance net is an ordered
set of log entries which stem from one pro cess instance. As an instance net has already
b een executed in the past, no choice or lo op constructs are needed. The prop erties of
this ordering relation (referred to as
in the following list) are:
•
is irreexive, asymmetric and acyclic
•
If an entry
i
app ears b efore an entry
j
in the log, then
ji
can not exist
•
For any
ij
there is no common intermediate element
k
such that
ik
and
k+j
.
The symb ol
+
expresses that there may exist any sequence of
0. . . n
intermediate
ordering relations
b etween
k
and
j
.
•
If duplicate tasks app ear in the log, then they must b e related with
+
This ordering creates relations b etween the closest tasks, each of which have a causal
relation. As a causal relation indicates a sequential structure, no symmetric causal
relations with the exception of short lo ops are allowed.
Creating an instance graph from an instance net is straightforward: Each task from the
instance net represents a no de in the instance graph and each causal relation creates
an edge. If tasks have no causal relation with their predecessor or successor, their no de
representation are parallel branches. Due to the retrosp ective view on the pro cess as a
log, choice branching is not supp orted. Finally, a start and end no de are added with in-
and outgoing edges resp ectively going into no des that have no predecessor or successor.
An instance graph holds the prop erty of b eing strongly connected. Furthermore, an
87
3. Related approaches
entry in the log only app ears if all its predecessors in the directed graph have already
app eared in the graph
11
. These assure the correctness of the reconstructed ow of tasks
in terms of executability and conformance with the records provided by the pro cess log.
Instance mining may b e b enecial when pro cess logs are not complete as their complete-
ness is not required to pro duce useful results. Primary ways of usage include instant
instance visualization and other related functionality supp orting the analysis, control
and planning of pro cesses. As a secondary option, an instance graph can b e either used
to b e transformed into other data formats
12
which may oer further pro cessing such as
the aggregation of multiple instance graphs into one pro cess schema. Usage limitations
apply when dealing with erroneous logs that require preceding ltering steps. Moreover,
meaningful aggregation is hard to accomplish when more complex routing structures are
involved.
3.2.3. Assessment of usefulness
The pro cess mining approach clearly aligns with the functional requirements of the
pro cess creation engine of Emergent Workow (see Section 2.3.6). All requirements
references in paranthesis refer to the requirements summary in Table 2.4, Section 2.3.10
if not noted otherwise.
In Emergent Workow, the audit trail comp osed of user interaction and system events
represents an event log enriched with context data (see Section 2.3.7 on page 33) which
meets the pro cess creation engine's input requirements (PC1, PC I/O). Regular workow
mining as describ ed on page 83 prop oses algorithms that require as input completed logs
of suciently many instances in order to function prop erly. Therefore, they are fo cused
on ad p osteriori analysis. With resp ect to the dierent purp oses of do cumentation shown
in Table 2.2 on page 29, workow mining oers means to do cument for later reuse, but
do es not supp ort planning or synchronization of ongoing op erations (PC2). In order to
achieve robustness against real-life circumstance such as noisy log les, advanced mining
metho ds have b een prop osed (PC3).
Multi-phase pro cess mining on page 87 is a mining approach of particular interest for
Emergent Workow. Its rst phase p erforms individual instance mining which aligns
p erfectly with the creation of pro cess fragments by a pro cess creation engine (PC2). It
is not as complicated as regular pro cess mining b ecause it restricts itself to log analysis
of single instances. Thereby, the outputted metamo del is simpler as for example no
conditional branching is allowed and necessary (PC4). Moreover, its output format can
b e easily transformed into other representations (PC4). Most noticeable is the fact that
instance-based mining is useful for immediate and individual supp ort for workow users.
While regular workow mining is rather a p ost-ho c analysis, instance-based mining can
b e done during execution as it do es not require completeness of its input (PC2, PC3).
11
Compare [DA04] page 8/369 for pro ofs
12
Such as an Instance Event-driven Process Chain in [DA04] page 8/369 et sqq.
88
3. Related approaches
Finally, one can compare the results of instance-based pro cess mining with the planned
overall pro cess. This allows an analysis of the exibility of pro cess mo dels and their
average level of deviation from the planned pro cess.
3.3. Flexibility approaches
Approaches that intro duce exibility on pro cess mo dels during run time can b e classied
into two categories:
Ad-hoc change of process instances
applied to instances during run
time and
schematic changes
applied to pro cess mo dels. As already motivated in Section
2.3.7 on page 40, instance-based changes are used for exceptional situations or changes
aecting only selected instances. Schematic changes indicate incremental systematic
change that applies to all instances and causes the pro cess typ e to evolve.
3.3.1. Schema evolution and propagation
Schema evolution consists of a
static
part mo difying the pro cess mo dels and a
dynamic
part which refers to managing the migration of running instances [CCPP96].
A
static
evolution is the issue of mo difying the workow description and includes check-
ing for syntactic correctness.
Dynamic
evolution refers to managing running instances
whose typ e was mo died. They require some form of assistance to adapt to the new re-
quirements formulated by the typ e change. Their consistency regarding their execution
state needs to b e checked and assured.
Change op erations on a pro cess can have an impact on any one of its p ersp ectives
(see Figure 2.14 on page 54): For instance the assignment of tasks to users or the
organizational structure can change as well as asso ciated applications and use data.
The mo dication of the
control ow
is fo cused in the following Section due to its high
relevance.
A set of op erations mo difying the control ow holds characteristics such as b eing
com-
plete, minimal
and
consistent
. Completeness is achieved if any schema can b e trans-
formed into any other schema. Minimality refers to the fact that only a minimum set of
op erations is oered that meets the completeness requirement. Consistency means that
the change op eration reinduces no errors during run time.
Dynamic schematic changes o ccur during workow execution when the pro cess mo del
adapts to a changing environment. Possible strategies to handle these changes during
execution are:
•
Flushing the system.
The enactment of new instances is delayed until all
running instances have terminated. Then changes are applied and enactment is
89
3. Related approaches
restarted. This strategy is safe but time costly and not acceptable when dealing
with many and long-running instances.
•
Ab ortion of all jobs in progress.
Running instances are ab orted, the pro cess
mo del is altered and instances are re-run using the new schema. Again, this
strategy is unacceptable due to the high costs of restarting all instances and redoing
all the work to reach the originating state.
•
Run old and new versions simultaneously.
Here, running instances remain
running on the "old" pro cess mo del while newly enacted instances use the new
pro cess mo del. The old pro cess mo del remains active until all old instances have
terminated. This strategy is p otentially unsafe and inconsistencies are esp ecially
likely if the schematic change interferes with data dep endencies or the change
downsizes the mo del (see b elow).
•
Safe migration of instances from one version to another.
The change is
applied to the pro cess mo del and running instances are individually migrated to
conform with the new pro cess schema. Here, safety is an issue b ecause correctness
and consistency need to b e checked explicitly.
Obviously, a safe migration of executed instances up on schematic change is the most
challenging and promising strategy at the same time.
Synthetic cut-over change
Ellis et al. deal in [EKR95] with the dynamic change
problem and ways to verify the correctness of one class of dynamic change. They present
a certain class of pro cesses for which the consistency of migrated instances can b e proved.
Their approach is to dene a
change region
as that part of a pro cess mo del which is b eing
aected by a structural change. The
old change region
existing prior to the change is then
replaced with a
new change region
containing the change while ob eying the pro cedural
sp ecications in order to maintain correctness. Correctness is maintained if all instances
resume and nish according to either the old version or the new version of the pro cedure.
A sp ecial class of changes referred to as
synthetic cut-over change
is observed when the
new change region contains b oth the old and the new region.
A Petri Net formalism
13
is chosen to represent pro cess mo dels as marked networks. In
Petri Nets, a change is a replacement of a marked subnet by another marked subnet.
The
old change region
is dened as the smallest net containing all activities aected
by the change op eration. Those parts of the net connecting the change region to its
context are describ ed as the
interface
. Thus communication b etween change-aected
and non-aected regions is restricted to the interface. Intuitively, the changed network
is obtained by removing the old change region from the network and plugging the new
change region into the interface.
13
An basic introduction to the Petri Net formalism is given e.g. in [EKR95] p. 14 et sqq.
90
3. Related approaches
Dynamic change correctness with resp ect to the used formal mo del splits in three key
issues:
Fault prevention
means to disallow any changes such that the marked network
can not reach a terminal (nal) marking state. Assuming that the initial marking of
the old and new network b oth comply with the fault prevention prop erty, a
system
replacement
which cancels all instances in progress and restarts everything should main-
tain correctness as well. If the system is not restarted, then the
consistency
of hybrid
executing sequences needs to b e assured. A hybrid sequence consists of a pre-change
sequence and a p ost-change sequence which is supp osed to continue the work initiated
b efore the change. Hence, each marking state that leads to a valid terminal state in the
old network must do so as a pre-change part of a hybrid sequence on the new network
as well. Additionally, all hybrid sequences must b e valid execution sequences of the new
network.
A dynamic change can b e either
immediate
of
delayed
. In the prior case, any change
op eration takes eect on all involved instances immediately as the change region is
replaced and existing tokens representing instances have immediately migrated into a
new schematic environment. The prop osed solution to delay a change op eration is
motivated by increased safety in certain cases. The idea named
synthetic cut-over change
is to maintain the old and new change region b oth at the same time within the pro cess
mo del. Already existing tokens in the old change region practically do not take notice
of the change op eration whereas new tokens entering the change region will only get in
touch with the new change region. The change app ears to b e immediate for all tokens
but those in the old change region. The following example visualizes a synthetic cut-over
change.
Example 22.
Supp ose a pro duct development pro cess. Part of this pro cess is the
construction of a comp onent. As depicted on top of Figure 3.8 and named "The old
change region", the activity "Construction" is followed by comp onent integration and
simultaneously the analysis of up coming problems. Up on the completion of b oth activ-
ities, an interdisciplinary meeting is held in order to discuss the encountered problems.
Notice that the shaded circles indicate the interface of the change region. Let us now
assume that in this scenario the parallel pro cessed activities "Integration" and "Problem
analysis" are changed into a sequential order "Integration", "Problem analysis". In or-
der to achieve a delayed change, the old change region is transformed in the new change
region shown on the b ottom of Figure 3.8. It consists of the old change region
and
the
new sequential pro cedure whose output interface is connected. This assures that newly
generated tokens traverse the new schema whereas existing tokens in the old change
region will not notice the change.
91
3. Related approaches
Interdisciplinary
meeting
Interdisciplinary
meeting
Construction Integration
Construction
Integration
Problem
analysis
Problem analysis
The new
change region
Interdisciplinary
meeting
Construction
Problem analysis
Integration
The old
change region
Figure 3.8.: The old and new change region in the case of a synthetic cut-over change
The formal distinction b etween immediate and delayed changes is justied by diering
change safety. Change regions can b e split up into a numb er of elementary op erations.
Dep ending on the change op eration, prop erties called
upsizing
and
downsizing
can b e
informally established as follows: If the new change region contains all elements of the
old change region (it can "do more" such as the insertion of a new activity), then the
change is called
upsizing
. In the reverse case the old change region contains all elements
of the new change region (e.g. a delete op eration) and the change is
downsizing
. Ellis et
al. prove
14
the correctness of any immediate upsizing change. However, only the delayed
version of a downsizing change is always provable correct.
3.3.2. Ad-ho c instance change
Ad-ho c adaptive workow with ADEPT
In static workow management system,
pro cess designers create pro cess mo dels and take resp onsibility for pro ducing only mo dels
whose instantiations run and terminate correctly. When alterations are made to them
sp ontaneously by users, correctness and consistence is usually no longer guaranteed.
14
Compare Ellis C., Keddara, K., Rozenberg, G., "The Mo deling of Dynamic Change Within Workow
Systems"
92
3. Related approaches
ADEPT
15
presents a framework that allows a user to p erform ad-ho c changes on running
instances without shifting the resp onsibility for correctness to him. ADEPT
flex
by
Reichert and Dadam [RD98, Rei00] contains a set of change op erations applied to pro cess
instances and fo ots on the designated ADEPT workow mo del.
The ADEPT workow mo del holds a numb er of characteristics which are essential for
the functionality of dynamic structural change metho ds. Fundamental to the structural
design of ADEPT is its concept of
symmetrical control structures
. It means that tasks are
partitioned into symmetrical blo cks with well-dened start and end no des. These blo cks
are not allowed to overlap but can b e nested. Elements of control structure are applied
to whole blo cks in the same way as they are applied to primitive tasks. In the following
paragraphs, an overview of ADEPT's control ow, data ow, change management and
undo capabilities of temp orary changes is given.
ADEPT's
control ow
is represented by a directed structured graph. Available basic
control structures are
sequence
and
paral lel processing
(n-of-n split and join), exclusive
conditional routing
(1-of-n split and join) and
paral lel branching with nal selection
(n-
of-n split and 1-of-n join). It do es also provide advanced control structures such as
loops
,
failure edges
and
synchronization edges
.
Loops
allow cyclic structures within the pro cess
graph by inserting a lo op edge that connects a unique start no de with a unique end no de
within a blo ck. A lo op condition at the end no de is used to check whether the lo op edge
or the next task is chosen next. A
failure edge
is a second outgoing edge from an activity
n
failed
that p oints to another activity
n
restart
that precedes
n
failed
. This edge is signaled
on failure of the activity and resets all activities succeeding
n
restart
and preceding
n
failure
.
Synchronization edges
are intro duced in order to enable synchronization of tasks from
dierent branches that are pro cessed in parallel.
A control ow is considered
correct
, if from every reachable state a correct terminal
state can b e reached by a numb er of valid state transitions (
safeness
) and each no de is
reachable by a numb er of valid state transitions from the start no de (
reachability
).
Data ow
in ADEPT constitutes
data elements
,
I/O parameters
and
auxiliary services
.
Data elements
are global elements within a workow representing data ob jects that
are collab oratively read and wrote by tasks.
Input and output parameters
of tasks
referring to data elements dene the data ow within a workow schema. As various
tasks implement dierent data input and output formats,
auxiliary services
are meant
to provide a common interface to data elements for all tasks. They are individually
asso ciated with each task and transform data inputs and outputs accordingly.
In order to uphold correctness with regard to the data ow, all input and output para-
meters and auxiliary services have to b e available in time. That is, input and auxiliary
services are required to b e ready b efore execution and output b efore termination. Glob-
ally accessible data elements b ear the p ossibility of data inconsistency if tasks manipu-
late data elements concurrently without synchronization. Therefore, tasks of an instance
15
ADEPT stands for Application Development Based on Encapsulated Premo deled Pro cess Templates
93
3. Related approaches
work on individual copies of the data element instead of the original. Up on successful
task termination, the global data element is replaced with the most recent version but
not discarded though. This holds two advantages: First, tasks in parallel branches can
work indep endently on lo cal data copies. In order to maintain correctness, their up dates
on termination must b e synchronized. Second, in case of a rollback (which is an essential
exceptional scenario within exible workow management as further discussed b elow)
data elements can b e reset to their initial state as their history is still available.
ADEPT
flex
represents a set of op erations that allows dynamic schema changes on run-
ning workow instances. Analogous with prop erties presented for schema change op era-
tions, the main fo cus designing these op erations is put on the following three prop erties:
•
Correctness/consistency
: The application of a change op eration to a work-
ow instance should neither aects its structural schematic correctness nor the
consistency of its execution state.
•
Adequacy/completeness
: Each change op eration should b e applicable to any
kind of correct and consistent workow instance. Completeness is met if any kind
of structural change can b e achieved by the application of a sequence of basic
change op erations.
•
Minimality
: The set of op erations is minimum if the removal of any op eration
violates the completeness requirement.
ADEPT
flex
consists of the following basic op erations:
•
Insertion
of a task into the pro cess graph
•
Deletion
of a task from the pro cess graph
•
Changing task sequence
during run time
These are used to skip tasks for fast forwarding, to jump to currently inactive parts of the
pro cess graph, to serialize previously parallel tasks and to rollback and undo temp orary
changes. Higher level op erations can b e achieved by rep etition and/or a comp osition of
these basic op erations. For example an ad-ho c workow denition can b e achieved by
starting with an empty workow and applying an insert op eration rep etitively on it.
Change management
Problematic scenarios can arise when multiple workow in-
stances are changed concurrently. Exemplarily a few are mentioned: For instance dier-
ent changes can b e made to multiple instances of the same typ e concurrently. Changes
can also b e made to an already changed typ e. Some changes may require secondary ad-
ditional changes (
concomitant changes
) in order to preserve correctness and consistency
of the underlying workow mo del. Finally, there exist changes that last only temp orarily
and have to b e undone some time after their application.
94
3. Related approaches
In order to enable prop er handling of such scenarios, each workow instance
pi
maintains
the following information:
1. A pro cess graph
Pall
representing the current pro cess schema which includes all
changes and state information of
pi
.
2. A pro cess graph
Pperm
whose graph structure contains only p ermanent changes
temp orary changes as well as state information is left out.
3. A
change history
C
which is a chronologically ordered vector of all
changes
applied
to
pi
. Each change record consists of the following information:
•
The
type
of a change op eration
•
The
durability
of a change (can b e either temp orary or p ermanent)
•
The
initiator
of a change
•
The
start region
of the change in order to determine whether and when to
undo a change
•
Additional
concomitant changes
to maintain correctness/consistency
•
A list of the applied
change primitives
in order to break down change op era-
tions into graph mo dication primitives
Temp orary changes
ct
are done by rst checking for correctness and consistency after
their application to
Pall
. If unresolvable problems p ersist, the user has to resolve excep-
tions an other issues manually. The change is p erformed and it is added to end of the
change list
C
. Permanent changes require consistency checking for
Pall
as well as
Pperm
b efore a change op eration
cp
can b e applied to b oth of them.
Undo temp orary changes
Particular changes can b e undone by removing them from
the graph structure
Pall
. Part of each change record is the denition of a
start region
that describ es a set of no des in the pro cess graph: If each no de within the start region
is within a terminal state, the undo function of the temp orary change is triggered.
Undoing a temp orary insert or delete change op eration
cl
works similar to the roll-
back/recovery concept of a transaction oriented system
16
as visualized in Figure 3.9: A
change list consists of
n
sequential changes where
c1
represents the oldest and
cn
the
latest change. As undoing
cl
can cause a state change for a set of no des (the so-called
backward region), other changes whose start region overlaps with the backward region
need to b e undone as well. (1) Hence, the oldest change
ck(1 ≤k≤l≤n)
whose
start region interferes with the backward region of
cl
has to b e found. (2) Then b oth
p ermanent and temp orary changes are undone in reversed order starting from
cn
up to
ck
. (3) Finally, all p ermanent changes b etween
ck
and
cn
are redone in forward direction.
16
Compare e.g. the lecture notes on "Database Systems winter term 2003", University of Ulm
95
3. Related approaches
Temp orary changes are redone if their start region is not covered by
cl
's backward region
and correctness and consistency of
Pall
remains.
c1c2ck-1 ckck+1
... ...
1. Find first influenced change
cl-1 clcl+1
... cn-1 cn
2. Traverse and undo all changes
3. Traverse and redo permanent changes
Figure 3.9.: Undoing a change within a change list
3.3.3. Integration of schema evolution and ad-ho c instance
mo dication
Pro cess-aware information system
(PAIS) A very recent approach by Web er, Rinderle
et al. [WRWR05, RWRW05] named PAIS prop oses the integration of the systems
ADEPT (see Section 3.3.2 on page 92) and CBRFlow (see Section 3.1.2 on page 75)
which were intro duced earlier in this thesis. Its goals are to oer reusability of instance-
based ad-ho c changes and to accomplish a derivation of evolutionary schematic changes.
ADEPT contributes to this comp osite pro ject with the abilities of a full-feature workow
management system including mo deling, analysis, execution and monitoring capabilities
[RD98]. As already mentioned b efore, ad-ho c change functions are provided by ADEPT.
Additionally, it oers schema change op erations for pro cess typ es. Its pro cess represen-
tation based on symmetrical control structures allows on-the-y migration of running
instances while preserving pro cess consistency for most classes of instances (see Rinderle
et al. [RRD02, RRD04]). The shortcoming of this system is however that its ad-ho c
adaptions are not reusable.
CBRFlow contributes a case-based reasoning (CBR) approach including all of CBR's
characteristic features (see Section 3.1). It do cuments the reason for instance changes
and makes them reusable for the future.
This joint approach now aims at covering the whole
process life cycle
with a combination
of b oth functionalities: Figure 3.10 illustrates how ad-ho c changes and typ e changes are
integrated with reuse of altered instances in a case base. From a given schema, pro cess
instances are created. As now the user exp eriences an exception during run time, he
requests similar cases from the case base and either retrieves a matching case or adds a
new one. Deviations are mo deled with change constructs and a do cumentation on the
case is added which makes the case immediately reusable. The reuse of existing cases
is counted and in case a dened maximum numb er (the threshold) is exceeded, pro cess
designers are triggered with a notication indicating the p ossible need for a pro cess typ e
change. In case the pro cess typ e was up dated, existing cases in the case base must b e
96
3. Related approaches
Updated process
schema
Process schema
Process Schema
Process Schema
Process Instances
Process Schema
Process Schema
Changed process
Instances
Process instance change
Case usage threshold
exceeded
User
Process
designer
Case
retrieval/addition
CCBR
Case base
Process type change
Instantiation
Case base
migration
Figure 3.10.: Pro cess life cycle of the integrative PAIS approach (compare [WRWR05]
Figure 2)
migrated to the new schema. Due to b oth system's characteristics, correct and consistent
ad-ho c mo dication can b e assumed along with a memorization of changes and adaptive
pro cess typ es.
An extended CBR cycle (compare Figure 3.1 on page 68) is realized by PAIS in the
following way: Up on the
addition of a new case
to the case base, a free textual
description
of the exception is given along with a set of question-answer pairs describing
the exception's
reason
. A subset of the change op erations made available by ADEPT
and supplemented with parameters are available to pro cess-creating users to sp ecify the
resolving
action
which is taken by the case. Notice that a retained case refers to a
sp ecic pro cess schema version.
Case retrieval
works in the same way as it did for CBRFlow: A dialog is initiated
which consists of a set of questions and answers. The user's
answers
and additional
parameters
sp ecify a matching on cases, which is rened by optionally given
operations
and a
subject
. Based on that information, the case base is ltered and a
similarity
measure
similar to the one shown in Example 17 is used to present the b est matches to
97
3. Related approaches
a requesting user.
Case reuse
is assisted by case retrieval as describ ed ab ove. Change op erations oered
by ADEPT are used to revise the case. However their application requires some ex-
p erience and is not in any case straightforward, b ecause changes may imply additional
concomitant changes
in order to uphold correctness and consistency. The numb er of
reuses is counted for each case.
Case evaluation
as a part of case retainment is a feedback channel describing the useful-
ness of an applied case. A task containing a simple evaluation (p ositive/neutral/negative)
and a descriptive text eld is added at the end of a reused/retained case. This yields a
ranking of reputation amongst cases and is displayed during retrieval. It helps nding
the most successfully used cases in the past.
Case revision
fo ots on the evaluation system and is invoked when a case receives
negative feedback. This triggers pro cess designers to either revise the case or to remove
it from the case base.
As requirements evolve, exceptions show up more frequently. The
derivation of a
pro cess typ e change
is started when CBRFlow noties that certain exception typ es
are used very frequently. Pro cess designers can react on this situation with a pro cess
typ e change. The notication is sent out as so on as a certain
threshold
of reuse fre-
quency has b een exceeded. However, typ e change induces a migration of running cases:
ADEPT makes a distinction b etween
compliant
and
not compliant
instances. The for-
mer designates a class of instances on which the change can b e applied. Not compliant
changes can not b e changed and the resp ective cases continue running on the old schema.
Compliant cases can b e either
biased
if they contain ad-ho c changes or
unbiased
if they
do not. Unbiased cases are directly relinked to the new pro cess schema, whereas biased
cases require additional correctness checks.
3.3.4. Assessment of usefulness
Flexibility of pro cess mo dels and their instances is the
decisive
requirement for the
runtime engine of Emergent Workow if we leave elementary functionality like (RE1 -
RE3 with resp ect to Table 2.4 in Section 2.3.10) aside.
The intro duced work by Ellis et al. on page 90 considers schema evolution (RE4) and
presents an approach to verify correctness for migrating instances to a new schema
(RE7). On the underlying Petri Net formalism, immediate changes are p otentially un-
safe. That is why Ellis et al. prop ose to articially delay the transition of running
instances to the new schema by a construct named
synthetic cut-over change
. This as-
sures for certain typ es of changes a consistent migration of Petri Nets in the middle of
execution (RE7). Notice however that if this is put into practice and applied more often
to a schema (which is surely the case for Emergent Workow), it grows more and more
"dead" branches. As a matter of fact, for iterative changes clean-up steps that cut the
98
3. Related approaches
old change regions o are mandatory in order to maintain a meaningful pro cess mo del.
Next, ADEPT is presented on page 92 as a fully functional pro cess management frame-
work. Notice that only the ad-ho c change functionality of this framework is considered
here [RD98](RE6). Fundamental for all asp ects of ADEPT's prop erties are its
sym-
metrical control structures
which cause a highly rigid blo ck structure. This is why its
schematic elements are roughly outlined rst. Among others, p owerful control structures
such as lo ops and failure edges are included in ADEPT which increase its expressive
p ower, but induce also a more dicult handling. For instance the lo op construct creates
the necessity for an advanced change management and metho ds for undoing temp orary
changes, which complicate its handling. The most distinguishing feature however is at
the same time the biggest b enet of ADEPT over other approaches: The application of
its set of change op erations do es not shift the resp onsibility for correctness and consis-
tency checking to a user or pro cess designer, Instead, ADEPT is able to a assure b oth
for most cases on-the-y (RE7).
The last presented exibility approach on page 96 is PAIS by Web er, Rinderle et al. Its
decisive quality is that it integrates many features from two approaches which are already
p owerful by themselves: ADEPT mentioned ab ove and CBRFlow. It oers the full range
of functional features oered by b oth systems plus some synergetic eects. Schema
evolution (RE5) with automatic consistency assurance for instance migration (RE7)
and ad-ho c changability (RE6) are integrated in the CBR cycle. Conversational case-
based reasoning allows the reuse of cases (RE5) and annotates them with descriptions
(RE9). On top of that, the CBR cycle is extended with case evaluation functionality
which improves the accuracy of individual cases.
99
4. Architectural prop osal
"Grasp and reuse"
Emergent Workow is aiming at a way to
grasp
the current pro cedures and pro cesses
and to
reuse
them in a way which is most simple, fast and exible enough to b e accepted
by users. From a functional p oint of view, no single approach presented in Chapter 3
do es cover all aspired asp ects of Emergent Workow. In order to receive the fo cused
goals of Emergent Workow, relevant ideas of dierent approaches have to b e bundled
and integrated into one system.
Not only technical issues are decisive factors, but in the rst place users representing
the
human factor
are. It may b e emphasized at this p oint that the ma jor motivation for
Emergent Workow is to overcome acceptance deciencies that conventional workow
management systems are confronted with.
It app ears recommendable to prop ose a
staged introduction
of an Emergent Workow
System for a numb er of reasons: First, the high complexity of a system implementing all
kinds of desired functions and related technologies would b e hard to implement, manage,
administer and use for all involved groups develop ers, pro cess designers, administrators
and users. Second, a step-by-step intro duction is more likely to b e accepted by users
which is a crucial success factor for Emergent Workow in particular. Finally the emer-
gent approach implies that small-scale resp onsibility for pro cess creation and planning is
shifted to users. These are however demanding tasks that require knowledge, predictive
thinking and not at last exp erience. Intro duction phases allow users to slowly adjust
to new pro cedures and give them the chance to get acquainted with new to ols and to
master their new tasks b efore they b ecome mission-critical.
Creative activities are the most valuable and at the same time the most critical and
fragile part of knowledge intensive work. Therefore a ma jor amount of care is suggested
when any kind of change is applied to them as their reaction to change is most sen-
sitive. The intro duction of information technology such as Emergent Workow has a
massive impact on the way creative pro cesses function. That is why it is prop osed that
those comp onents of Emergent Workow that intro duce the most profound changes are
integrated at last.
The main ob jective of the architectural
rst stage
is to gain user acceptance. It fo cuses
rather on non-functional issues. Workow technology is used at this stage in a way in-
visible to the user and
grasps
information. However, functional improvements and
reuse
100
4. Architectural prop osal
asp ects are p ostp oned to the next stage. The
second stage
brings functional changes
into play: It intro duces a workow management system enriched with comp onents for
exibility enhancement used for routine pro cess parts only. Exception handling is here
pioneering Emergent Workow's ability to
reuse
past exp erience. The nal
third stage
shifts controls and initiative to users. This oers a high p otential to
reuse
past pro cess
fragments and the workow b ecomes "emergent", but at the same time b ecomes also
more complex to handle.
4.1. Stage 1 Basic functionality
The goal of the intro duction of basic functionality in the rst stage is to obtain user
acceptance for a minimum set of functions in the rst place. A critical user should
decrease rejective opinions by observing that the new system "actually do es not harm"
or even "helps a little". The idea is to keep as much familiarity of the user with to ols he
is used to instead of throwing him into a radically newly designed system environment.
Automatizing some minor routine work should help decrease aversion.
User
Appl Appl Appl
GUI
Appl
Process creation
engine
Organizational
model
Interaction protocol
Process
designer
Analysis
Figure 4.1.: Prop osal stage 1
Figure 4.1 shows the arrangement of some basic workow comp onents intro duced by the
rst stage. A Graphical User Interface (GUI) is presented to workow users which inte-
grates their applications into one common interface. The GUI creates a rough interaction
proto col and forwards it to the pro cess creation engine. Supp orted by an organizational
mo del, it helps pro cess designers to analyze the interactions of users.
Notice that at this stage, no formal workow management is intro duced regarding the
pro cess p ersp ective (see Figure 2.14 on page 54). Workow comp onents have only pas-
sive, "observing" functionality for analysis and prepare next steps. That implies that
101
4. Architectural prop osal
existing work patterns are not harmed or changed. Only b ehind the curtains invisible
for the user changes and analysis take place in the form of pro cess creation. The
following paragraphs give more details on the function of comp onents at this stage.
Integrated GUI
A common interface that integrates most applications and to ols is a
cornerstone for building an Emergent Workow. Functionally, this GUI must b e able
to create and output a proto col of user interactions. This includes basic information
such as which application have b een started or stopp ed. Additionally, it oers a generic
interface to client applications who can plug into the common architecture. First, an
extensible application interface helps to ll the user interaction stream with details on
intra-application interaction. Combined, an interaction proto cols tells what applications
a user chose (e.g. started billing software) and what actions were p erformed inside the
applications (e.g. chose customer order overview, edited the latest order, sent out bills).
Second, the application interface facilitates the invo cation of applications with parame-
ters sp ecifying a context, e.g. a customer ID. For certain roles, user dened variables
determining a stateful GUI can automatically set application parameters, e.g. a part
numb er set once is a parameter for all applications. Moreover, dierent groups of users
employ dierent applications. Therefore, this interface must b e tailored individually for
each user typ e, e.g. by using authentication mechanisms. This suggests the creation of a
basic organizational mo del: If users and their roles are known, then the interface can b e
comp osed of mo dular role-dep endent elements such that a user receives an individually
comp osed desktop. Finally, an abstraction from the op erating system of a GUI is desir-
able in terms of lo ok and feel. If the lo ok and feel of an interface is easily congurable
on each given platform, then future hard- and software changes will hardly aect users
any more.
Organizational mo del
With resp ect to the workow p ersp ectives (Figure 2.14 on page
54) the organizational p ersp ective is the only p ersp ective of a workow management
system which is visible for users at this stage. It is represented by an organizational
mo del (see Figure 2.12 on page 2.12 for an example) that is used to abstract roles and
groups from individuals. At this stage, the fo cus lies rather on role/user translation
than on hierarchical relations b etween roles as it is mainly used for role-resolution by
the GUI and the pro cess creation engine.
Pro cess creation engine
A basic version of the pro cess creation engine collects in-
teraction proto cols from users and oers basic data mining functionality. That includes
an instance-based visualization of interaction proto cols and elementary ltering options.
Pro cess designers rely on it to get an overview of the structure and typ es of individ-
ual users' activities. If privacy is an issue, anonymization of captured information by
role abstraction helps to protect privacy and reduces user rejection and disapproval. It
do es neither fo cus on cross-role or departmental pro cess relation nor do es it present its
outputs as feedback to users.
102
4. Architectural prop osal
Metamo del
As neither a real workow management system nor a formal pro cess repre-
sentation is present, only a very limited workow metamo del is needed at this stage and
comprises two parts: First, the organizational mo del formalizes roughly the corp orate
hierarchy. Role abstraction by itself do es not capture formal collab orative dep endencies
in the form of pro ject or work groups. Second, the basic pro cess creation engine is used
by pro cess designers to get an idea of the structure of each individual's tasks. Hence, a
simple representation of pro cess instances b eing fragments of a more complete pro cess
is necessary. That includes simple activities, basic control structures and no explicitly
dened granularity level.
4.2. Stage 2 Advanced functionality
The second stage provides advanced functionality and intro duces a more complete work-
ow supp ort and a reuse asp ect while trying to maintaining simplicity. After users have
gotten used to a new interface, now it is the goal to intro duce functionality that creates
a p ositive user exp erience like "This saves really time!" or "I had to typ e this only once!"
At this stage, the desired result is the retainment of current work for later reuse without
intermediate steps involving third parties such as pro cess designers.
A workow management system is intro duced which is meant to supp ort routine work,
but not creative work. As it is known that the acceptance of a regular workow manage-
ment system would b e to o low due to its inexibility and rigidity, two things are done:
Supp ort is restricted to rather static small-scale routine pro cesses and deviations from
routine are handled by a case base.
During the rst stage, pro cess designer were able to observe and analyze activities of
users and to identify recurring routine tasks. Now designers create simple pro cess mo del
representations of these pro cesses and oer them to users in the integration GUI. If
deviations from common pro cedures o ccur, users can do cument the situation, apply
instance-level changes and put the case into a case base for later reuse.
As Figure 4.2 shows, additional comp onents extend the system intro duced in stage 1.
These new comp onents fo cus on the supp ort of
routine work
. Any kind of work (including
creative work) is b eing captured by an interaction proto col, but only parts identied
by pro cess designers as routine work are further considered. In fact, by analyzing the
interaction proto cols, pro cess designers cho ose static recurring pro cesses, create a pro cess
mo del (not shown in the picture) and add it as a default case to the case base. Users
p erforming routine work can (1) retrieve the default case and (2) enact it on the runtime
engine. If one encounters an exceptional situation, it can b e do cumented and ad-ho c
changes inside the system are applied. After termination, (3) the case is retained and
can b e retrieved for later reuse. Do cumentation makes use of the dictionary by using
existing or new keywords to describ e the stored case. This description helps to nd
cases of a certain typ e during retrieval. Notice that the organizational mo del is here a
103
4. Architectural prop osal
Dictionary
Appl Appl Appl
GUI
Appl
Process creation
engine
Organizational model
Interaction protocol
Process
designer
Analysis
Runtime
engine
Ad-hoc
changes
Case base
1. Case
retrieval
3. Case
retainment
2. Case
Enactment
Case addition
Routine work Creative work
User
Figure 4.2.: Prop osal stage 2
comp onent commonly used by all other comp onents connecting edges are left out in
Figure 4.2 for b etter readability.
Case base
Initially, pro cess designers p opulate the case base with
regular
cases of dif-
ferent typ es. As only routine work is put into cases, deviations from cases are usually
caused by exceptional situation which have to b e indicated explicitly by users. When en-
tering a new case, the creator must provide a description characterizing the case. A case
description answers for instance the following questions: When happ ened what typ e of
exception and what is the comp ensation action? Was the exception comp ensated inside
or outside the system? That information allows to classify typ es of exceptions. Com-
p ensation of exceptions can b e taken care of inside the system by the ad-ho c adaption
abilities of the runtime engine.
As cases inside the case base must b e structured according to their typ e of exception,
the description of a case do es not only comprise free text, but also
keywords
. These
keywords are dened in the
dictionary
attached to the case base. It represents a simple
ontology of keywords that describ es the attributes of all exceptions. Pro cess designers
104
4. Architectural prop osal
are supp osed to initiate the dictionary, but users should b e able to extend the dictionary
with new terminology as they describ e their case. This makes sure that user exp erience
is immediately available for further reuse.
The goal is to p opulate a case base around established pro cess typ es with numerous cases
representing solutions for common exception typ es that were exp erienced in the past.
When new exceptions show up, the case base is searched using descriptive keywords
from the dictionary. That way, the organization, description and retrieval are highly
related with each other. This b ears the advantage that users actually are motivated to
add accurate do cumentation to their pro cesses. The b etter a case is describ ed, the more
likely it will b e for a user to nd and reuse a case later on.
Example 23.
A minimum framework for a dictionary with key informations describing
an exception scenario could b e given as follows:
Who
(role, p erson, group) p erformed
what task
(typ e and instance)
when
(p oint of time, duration) and
what exception
(typ e:
functional/nonfunctional, description) happ ened and was handled using what
compen-
sation
(ad-ho c change op erations inside the system/outside the system). Alternatively,
the characteristics of exceptions as given in Section 3.1.2 on page 79 by Hwang et al.
gives hints on relevant data typ es.
Ad-ho c instance adaption
Ad-ho c adaption functionality on instances during run-
time allows to comp ensate or resolve o ccurring exceptions inside the system. Therefore,
individual users must b e allowed to apply simple structural and state changes on run-
ning instances representing cases from the case base. A relatively small set of change
constructs is made available to them in order to p erform changes that are necessary
for exception handling. They include the insertion or deletion of a task in sequence or
parallel. It is recommended that the set of change op erations oered to users is
mini-
mal
(not more op erations available than needed), but
not complete
(not every allowed
instance structure can b e reached from any given structure) with regard to the given
workow metamo del. As the default cases created by pro cess designers might contain
advanced control structures, the complexity of a complete set of change op erations would
very likely overwhelm common users. For example conditional forks and joins require
the formulation of b o olean expressions. Such tasks may intro duce a level of complexity
which is to o high for unfamiliar users. This decision tries to realize treatment of ex-
ceptions inside the system by means that are straightforward enough to b e applied by
unexp erienced users.
Metamo del
In stage 2, a fully functional workow management system is intro duced.
Therefore the organizational mo del from stage 1 is extended with metamo del constructs
b elonging to the
process perspective
.
Process types
are dened by pro cess designers
including structural elements to dene the control ow b etween activities. In order to
reduce complexity, no or a very simple data mo del (compare the
information perspective
)
may b e used. An instance of each pro cess mo del resides as a
regular
case in the case
105
4. Architectural prop osal
base and makes the pro cess typ e accessible to users. Each instance put into the case
base must b e supplemented with a description consisting of dictionary-related keywords
and some free text elds.
Basic change op erations (insert, delete, b oth either sequential or parallel) on pro cess
instances are required to enable exception handling. As already mentioned in the pre-
vious paragraph, ad-ho c change op erations available to users do not cover the complete
metamo del used by pro cess designers to create pro cess typ es.
4.3. Stage 3 Full functionality
The goal of the third stage is to provide supp ort for all typ es of tasks. Here the key ideas
of Emergent Workow are made available for use with exible tasks. After the user gets
acquainted with the functionality, his exp erience should express something like "I don't
know how we did our work b efore we had this system!". This means to create a system
that formalizes pro cesses relatively detailed without formalizing and complicating the
view on them. A user p erforming creative work will typically receive a roughly structured
bigger task assignment. He requires individual choice and freedom on the way the task
is split up into single steps and accomplished. A supp ortive system oers, but do es not
force him to take a lo ok at past executions of similar tasks and eventually adapt and
reuse one of them. This stage tries to accomplish that by p ermanently monitoring the
interactions a user. As he pro ceeds and requests supp ort, the system may nd similar
patterns in previously recorded actions and prop oses to reuse them. The user can then
either agree to copy his previous pro cedures or decline and continue on his own.
It can b e seen from Figure 4.3 that the previous stage's functionality is included and
extended. The case-based reasoning cycle is still integrated and the numb ering of its
steps are prexed with "C". What has b een added is the ability for
schema evolution
of
pro cess typ es in the runtime engine. The dictionary has b een extracted from the case
base and forms together with the organizational mo del a comp onent
general know ledge
.
It is commonly used by all other comp onents. The newly created cycle prexed by an
"F" represents the ow of fragments supp orting the reuse of creative work patterns.
First, the interaction proto col enters the runtime engine (F1) and is consolidated with
server-side events (which are not shown in Figure 4.3) into an
audit trail
. Notice that the
time management component
as sp ecied in Section 2.3.5 is considered an integral part
of the runtime engine and is not shown in Figure 4.3 for b etter readability either. The
pro cess creation engine reads the audit trail (F2) and outputs pro cess fragments. A user
can signal in the interaction proto col that he completed a subtask. If, as a consequence,
the workow fragment represents a completed subtask, then the fragment is stored
to a fragment base (F3b). Otherwise, an incomplete fragment is sent to the pro cess
matching engine (F3a) which compares it on-the-y with stored existing fragments (F4).
If suciently go o d matches are found, these are presented to the user who can select
from the prop osed fragments (F5) and reuse them by reenactment (F6). Apart from
106
4. Architectural prop osal
that, pro cess designers analyze the fragment base and the case base. On the one hand,
they p erform schema evolution on the pro cess typ es in the case base if necessary and
take care of the migration of running instances. On the other hand, they attempt to
compose
an overall pro cess out of the pro cess typ es, cases and stored fragments.
User
Appl Appl Appl
GUI
Appl
Process creation
engine
Process
designer
Analysis &
Composition
Runtime
engine
Ad-hoc
changes
Case base
C1. Case
retrieval
F1. Interaction
protocol
F2. Audit trail
Schema
evolution
Fragment
base
F3b.
Fragment
storage
Process
matching engine
F3a. Fragment
comparison
F5. Fragment
selection
General knowledge
Organizational model Dictionary
F6. Fragment
enactment
C3. Case
retainment
C2. Case
enactment
F4. Fragment
retrieval
Creative workRoutine work
Process type changes &
instance migration
Figure 4.3.: Prop osal stage 3
Schema evolution
Schema evolution
on the case base resembles the double-lo op learn-
ing approach of Wargitsch et al. (compare Figure 3.4 on page 78): Workow users par-
ticipate in the incremental design of non-exible, slowly evolving pro cesses: They can
create cases for exceptions and annotate their changes with keywords and descriptions.
Users p erform changes on a small scale basis as they mo dify only the pro cess parts they
work on. Pro cess designers rely on these when they adapt routine pro cess typ es to new
107
4. Architectural prop osal
requirements. In fact, just as in the example approaches discussed in Section 3.1, pro cess
designers observe the growing case base. When exceptions get more frequent and show a
strong bias towards a certain exception typ e, they can revise the existing pro cess mo dels
according to the changed requirements and up date the regular case of a certain pro cess
typ e. According to the chosen metamo del, running instances can b e either migrated
automatically or need to b e handled manually. Notice that on this stage, the part of the
system handling routine work shows strong functional similarities to the PAIS approach
intro duced in the related work Section 3.3.3 on page 96.
Pro cess matching engine
Captured interaction proto cols is now not only an analysis
to ol for pro cess designers, but is also used as a comparison and reuse to ol for work-
ow users. A partial in-progress pro cess instance needs to b e matched with archived
instances for criteria given by the user. If the user signals the invo cation, a partial audit
trail is translated into a pro cess fragment. Due to the exible nature of creative work,
exact matches are highly unlikely. Therefore, the pro cess matching engine needs to im-
plement approximate search algorithms that compare syntax and structural similarity.
Furthermore, an adjustable ltering threshold p opulates and limits the resulting list of
matches. From there, the user checks manually on the results for semantically similar
matches and eventually cho oses one of them.
Analysis & Pro cess comp osition
A big danger at this stage is that individual users
take control of the pro cess at a small scale level and a general direction and overview
passes out of fo cus. This is where analysis and pro cess comp osition b ecomes a vital
part of the Emergent Workow Pro cess they allow to gather an overview of what is
going on in order to make big scale adjustments where needed. Furthermore, user-based
changes need to b e consolidated as to avoid collision of incompatible changes.
Practically, analysis includes as a ma jor step the creation of current pro cess typ es fol-
lowed by their comp osition. The
analysis
and derivation of pro cess mo dels from instance-
based fragments oers p ost-ho c insights in characteristics of the real small-scale pro cess:
Where show instance of exible pro cesses commonalities? How do exible pro cesses
evolve over time? Thereby it serves as a foundation for e.g. cross-departmental syn-
chronization.
Composing
an overall pro cess of derived pro cess mo dels yields a "big
picture" that shows deciencies which span over individual users' and groups' horizon.
As each user participates with a dierent view on the pro cess, hierarchical comp osition
of fragments requires the consideration of each fragments granularity level. However, as
exible pro cess fragments are likely to b e very diverse, a common formal pro cess typ e
can also b e very complex. It can yield a comp osition that lo oks like totally dierent
instances were stitched together in parallel which do es not help very much. In that case,
a separate comp osition of instance fragment returns a view on the overall pro cess of one
single individual instance.
108
4. Architectural prop osal
Metamo del
The intro duction further functionality at this stage requires an extension
of the pro cess metamo del. First, pro cess typ es in the case base can now b e changed
schematically. That induces a set of change op erations on pro cess typ es. As the pro cess
typ e evolves now, its schema must b e versioned in order to b e clearly referrable. As
ad-ho c alteration of cases is still allowed, instance changes apply to a certain schema
version only. This leads to an ordered list of ad-ho c and schematic changes asso ciated
with and applied on each instantiated case from the case base. As already mentioned
b efore, typ e change of running instances is not a trivial problem, therefore the use of a
safe pro cess metamo del as prop osed by Web er, Rinderle et al. [WRWR05] is suggested.
Incomplete pro cess fragments are created during run time and stored for later reenact-
ment. They are based on a pro cess mo del that allows the instantiation of incomplete
mo dels. For each activity, parameters changing during enactment (compare Section
2.4.1 pages 57 et sqq.) have to b e reset to an initial state. The comp osition of fragments
leads to comp ound instances which hold the same prop erties as their elements. For
overlapping and esp ecially hierarchical comp ositions, a measure for the relative level of
detailedness of a fragment is intro duced. It intro duces
levels of granularity
according
to hierarchical levels in the organizational mo del. As all events caused by user activi-
ties are captured, one can assume that each individual's interaction proto col presents a
maximum level of detail. Therefore the p osition of a role determines the granularity of
its recorded pro cess.
109
5. Discussion
As many asp ects of Emergent Workow and its requirements were already discussed in
Chapters 2 and 3, the following discussion will conne itself to issues which may arise
from the integration of approaches presented in the architectural prop osal, Chapter 4.
Functional issues of integration
Namely, Case-based reasoning (CBR), ad-ho c adaption of instances, schema evolution,
pro cess mining and pro cess comp osition were intro duced throughout this thesis. The
following Table 5.1 couples approaches pairwise and assigns each pair a numb er. Re-
ferring to that enumeration, the following paragraphs discuss shortly the problems of
coupling the two approaches, if they have not b een discussed yet and are relevant.
Ad-ho c
adaption
Schema
evolution
Pro cess
mining
Comp osition
CBR (1) (2) (3) (4)
Ad-ho c adaption (5) (6) (7)
Schema evolution (8) (9)
Pro cess mining (10)
Table 5.1.: Comp osition of ideas
(1) CBR and Ad-ho c adaption
As it has b ecome evident in Section 3.1 on case-based
reasoning, ad-ho c adaption can b e made an integral comp onent of CBR: Case
revision implies the adaption of a retrieved case b efore its enactment. Ad-ho c
adaption as a revision to ol can actually extend the allowed revision phase to the
complete enactment phase. That makes the CBR cycle more exible and allows
the ad-ho c adjustment of cases to any up coming situation. However, the allowance
of changed cases can also lead to a problem of classication: If a complete set of
change op erations is provided, theoretically one case can b e mo died in such a way
that at the end it resembles more to another case than the originating case. This
arises the question whether during case retainment, it should b e stored as case of
the rst or the second case typ e. One can either cho ose to keep the case system
rigid or exible. The latter allows to change a case typ e during run time whereas
the former keeps the case typ e static as so on as a case has b een instantiated. A
exible case management must allow the re-classication of a case at any given time
110
5. Discussion
b efore retainment. Static case management requires the establishment of common
criteria for cases as within case typ es, structural corresp ondence of instances can
not b e guaranteed. Case classication needs to b e based on parameters that remain
unchanged by any ad-ho c adaption.
(2) CBR and Schema evolution
The integration of CBR and schema evolution has
b een issued in the intro duction of PAIS in Section 3.3.3.
(3) CBR and Pro cess mining
Integration of CBR and pro cess mining is twofold: If
cases are enacted and the events of execution are used for pro cess mining, nothing
sp ecial happ ens. That is not surprising, b ecause after all, cases are during en-
actment regular pro cess instances with a supplementary categorization. Without
further engagement, it is however problematic to add instance-based mining out-
puts to a case base. The reason therefore lies in the fact that common audit trails
do not indicate by default the asso ciation of a running instance with a case typ e.
Actually case creation or retrieval happ ens b efore pro cess enactment. Therefore,
no do cumented activity inside a pro cess instance indicates a case typ e.
There exist two p ossible resolutions for that matter: The rst p ossibility is to
merge case attributes of each instance into the audit trail. That makes it easily
p ossible to identify the case aliation of each single event. The alternative to this
very verb ose and redundant marking is to embrace case selection or retrieval for a
new pro cess instance as explicitly mentioned rst task to the instance. That way,
the runtime engine can execute the virtual "assignment" task and one single event
identifying the case shows up in the audit trail.
(4) CBR and Comp osition
Issues caused by the integration of CBR and fragment
comp osition are strongly dep endent on the way a case base is used: If it is used
to mo del exceptions around a regular case which corresp onds to the underlying
pro cess denition, then cases make no dierence to a p ost-ho c comp osition of
archived instances. See for that case
(7) Ad-ho c adaption and Comp osition
.
Either way, comp osition has to deal with instances that deviate from the given
pro cess mo del in a rather unstructured way. The other application of case base
is for pro cesses that have no regular case but a couple of equivalent cases. Here,
comp osition may b e only able to comp ose cases of the same typ e as each case
represents a distinctive sub-typ e of a pro cess denition. Cross-case comp osition
would result in syntactically inhomogeneous and semantically incorrect overall
pro cesses.
(5) Ad-ho c adaption and Schema evolution
The roles and co op erative functions of
ad-ho c instance adaption and schema evolution have b een issued in Chapter 2,
Sections 2.3.7 and 2.4.
(6) Ad-ho c adaption and Pro cess mining
Commonly, pro cess mining do es not recog-
nize whether an event in the log was caused by a regular or by an exceptional
activity. Consequently, changed instances containing adaptions that were caused
111
5. Discussion
by exceptional circumstances are rated equivalent to those instances with a reg-
ular schema and course of state transitions. Without further consideration, this
would lead to the creation of wrong pro cess typ es. In order to resolve this sit-
uation, a dierentiation of regular and changed/exceptional events is required to
enable pro cess mining to recognize the status of events. Having this knowledge,
p olicies that handle event typ es with dierent weights can b e put into practice.
The desired outcome is a pro cess mo del whose structure is inuenced by the level
of imp ortance of its contained events. Notice that this idea is comparable to min-
ing algorithms that use sto chastic mo dels and frequency tables to lter out noise
from the audit trail. Here, varying typ es of events have to b e recognized, classied
and are integrated into a preliminary pro cess mo del. Finally, only those events
exceeding a minimum weight threshold are integrated into the pro cess mo del.
(7) Ad-ho c adaption and Comp osition
Ad-ho c changes are applied to fragments of
the overall pro cess by each user individually. When comp osing fragments, these
numerous views are aggregated into the overall pro cess. Let now an exception o ccur
at a certain p oint in the pro cess. Multiple users with dierent p ersp ectives on the
pro cess will encounter the exception. The comp osition of fragments contributed
by them will b e overlapping at the exceptional p oint. The question here is whether
all of them interpret the situation in the same way. If they do, then all of them
will apply comparable ad-ho c adaptions that resolve the situation from their p oint
of view. In that case, fragment comp osition should work awlessly. If however,
each user develops a dierent understanding of the situation, then p eople will take
comp ensating actions that do match semantically. As a result, comp osition of
fragments will either not yield a meaningful result or the dierence are so strong
that fragments collide already syntactically.
In order to enable successful combination of ad-ho c adaption and the comp osition
of fragments, a minimum level of synchronization b etween users is required to
allow a common understanding and adaption of such situations. Then overlapping
fragments match a common problem and their comp osition delivers an overall
understanding.
(8) Schema evolution and Pro cess mining
As the schema of a pro cess denition evolves,
pro cess instances b eing enacted on dierent schema versions lo ok dierent. As it
has already b een broadly discussed in Section 3.3.1, the migration of already run-
ning instances from an old to a new schema is a complicated issue. These kinds of
instances also complicate the outcomes of pro cess mining. The entries in an audit
trail created by a migrated instance refer half to the old schema and half to the
new schema. Consequently mining algorithms applied on events from migrated
instances deliver
hybrid process fragments and types
. These kinds of outputs are
not useful for purp oses such as comp osition or reenactment.
Therefore, the runtime engine needs to indicate instance migration either by mark-
ing aected instances or creating a system event in the audit trail. This helps a
112
5. Discussion
pro cess mining application to recognize events from migrated instances and to
ignore them.
(9) Schema evolution and comp osition
What has b een observed on intra-fragment
scale in the previous paragraph
(8)
holds for the overall pro cess when schema
evolution is coupled with fragment comp osition. If pro cess typ es are changed at
any time, an
overal l process
that started b efore the change and ended after it,
contains p otentially three typ es of archived instances: Those according to the
old
schema,
hybrid
instances containing b oth schemata and instances enacted on
the
new
schema. Thus, one can consider it an
overal l hybrid process
. From a use-
oriented p oint of view, this kind of comp osition is highly interesting as it do cuments
in detail how well the overall pro cess handled the migration. Diculties that
showed up either b efore, after or during the schematic transition b ecome evident
from the comp osition.
The critical momentum can b e seen in a situation where no hybrid instance exists
but all instances either terminated b efore or started after the pro cess typ e evolved.
If fundamental dierence were intro duced by the typ e change, it might b ecome hard
to comp ose syntactically and semantically diering instances. Eventually, pro cess
designers need to insert an additional
transiting instance
which connect the gap
b etween old and new instances.
(10) Pro cess Mining and Comp osition
Pro cesses are comp osed vertically and hori-
zontally:
Vertical
comp osition of fragments represents the alignment of dierent
views and hierarchies related to a common part of the overall pro cess.
Horizon-
tal
integration relates causally dep endent pro cess parts either sequentially or in
parallel.
As already mentioned in Section 4.3, vertical comp osition of pro cess fragments
is based on an explicit sp ecication of their granularity (compare also Section
2.4). As multiple fragments yield multiple overlapping views on common pro cess
parts, hierarchical correlations have to b e identied. Moreover, comp osition can
only b e accomplished with activities containing a sucient amount of descriptive
characteristics in order to detect equivalences. For horizontal comp osition, those
matching activities represent the interfaces b etween the individual views. However,
the more detailed activities on fragment is, the less likely it is to match them with
other interfaces. Therefore, one needs to identify attributes which are
instance-
specic
, but not
view-specic
, such as temp oral constraints.
113
5. Discussion
Example 24.
In a quality gate-driven pro cess, all engineers have to reach a certain
development stage until a deadline (the quality gate), which was sp ecically given for this
pro ject (the overall instance). The activity "Delivery of results for the current quality
gate" may b e named dierently for engineers in dierent disciplines and have diering
related ob jects, roles, applications etc. these attributes are
view-specic
. In the audit
trail, the common interface events can b e identied by for example the timestamps
of their execution. They are all alike for each discipline, but
instance-specic
as the
deadline was given for this pro ject only.
114
6. Conclusion
6.1. Summary and conclusion
In the industry and many other elds of work, organizations have aligned their business
according to pro cesses. Workow management systems oering technological supp ort for
pro cesses b ear in principle many advantages. However until to day, these gains could not
b e widely realized as the traditional business pro cess cycle tends to b e to o inexible for
many applications. As a result, knowledge and pro cess awareness gets lost b ecause users
circumvent the workow management system and resolve issues outside the system.
Emergent workow has the vision to oer individual users immediate supp ort without
the need for pre-mo deled pro cesses. By capturing fragments of the real pro cess, it aspires
to gain user acceptance, improve reuse of work pattern and increase pro cess transparency.
The contribution of this thesis to Emergent Workow is a detailed requirements analy-
sis, an intro duction of related work, a conceptual prop osal and a discussion of p ossible
obstacles. The identication and sp ecication of use cases, comp onents, interfaces and
a suitable pro cess metamo del represents ab out half of this thesis. It identies numerous
functional and nonfunctional asp ects in a structured manner. Moreover, selected related
work is considered and assessed according to the outcomes of the preceding requirements
analysis. The related work part surveys work on case-based reasoning, pro cess mining
and exible workow management and restricts its view on fundamentals and some
interesting advanced work. The conceptual draft for the architecture of an Emergent
Workow Management System prop oses a successive intro duction of features with in-
creasing functionality and complexity. As the prop osal integrates ideas collected from
various related work, a nal discussion reects on up coming obstacles with integration
and further practical asp ects of the prop osal.
As a conclusion on this work, we observe that for most of the requirements considered
isolated from each other, practical approaches and partial solutions exist. From our p oint
of view, the true challenge for Emergent Workow is the integration of manifold ideas
into one functional
and
usable system. Given the set of requirements, one is tempted to
fo cus technical and functional asp ects only and to forget that a resulting highly complex
workow management system do es not solve the problems it was meant to overcome.
Therefore, we would formulate as a maxim for further work on Emergent Workow:
"Try to accomplish as much as p ossible with as few as p ossible."
115
6. Conclusion
6.2. Omitted and future work
As this thesis we settled on a conceptual level, working on it resulted in covering a very
broad range of involved topics. We have to say that the related work part mentioned
herein represents a very incomplete and punctual view on the eld of relevant related
work. As a result, many topics with high relevance were either not mentioned at all or
not treated adequately with resp ect to their imp ortance. The following list mentions
some topics worth of further investigation:
•
Access metho ds
for client applications on various levels of interactivity. They
enable workow users to make use of collections of fragments, pro cess typ es, cases
and terminology.
•
Pro cess designer applications
used for fragment analysis and comp osition.
•
Design of a dictionary ontology and organizational mo del
with resp ect to
their creation, maintenance and usability.
•
Workow security
that manages user allowance to access, mo dify, create and
extend any typ es of data.
•
Transaction supp ort
of business pro cesses including suitable constructs and
execution mo dels.
•
Inter-workow co ordination
to allow an integration of the Emergent Workow
approach with other typ es of workow management systems.
As this thesis has an intro ducing character on Emergent Workow at b est, future work
on this topic is manifold. Based on the given conceptual architectural prop osal, a more
concrete architectural sp ecication has to follow. That starts with conceptual decisions
based on the given requirements: From the available approaches, those may b e chosen
which show b est functional and integrative abilities. Then more sp ecic questions re-
garding algorithms, proto cols, ontologies and storage issues have to b e answered. As by
now, the nal step would b e marked by a prototypical implementation.
116
A. Supplementary Listings and Figures
A.1. CODAW
A.1.1. Pro cess data mo del
1
<?xml version="1.0"?><!DOCTYPE WorkflowSchema []>
2
<WSID> WS2</WSID>
3
<WSName> Market-Pull Workflow </WSName>
4
<WSType> ProductDevelopment</WSType>
5
<WSDesc> A product development process for a new chip </WSDesc>
6
<TaskList> (Project_Selection, Product_Definition,... ) </TaskList>
7
<ComponentWorkflowsUnModified> WS21 </ComponentWorkflowsUnModified >
8
<ComponentWorkflowsModified> Null </ComponentWorkflowsModified>
9
<WorkflowInstances> (WFIns1 WFIns22 WFIns23) </WorkflowInstances>
10
<WFFormalModel>
11
<PNModel>
12
PN-WS2
13
</PNModel>
14
</WFFormalModel>
15
<Tasks>
16
<Task>
17
<TaskType> Business </TaskType>
18
<TaskName> Project_Selection</TaskName>
19
<TaskDesc> Selects a list of new product ideas to work on </TaskDesc>
20
<TaskID> 1 </TaskID>
21
<TaskDesign>
22
<Parameters>
23
<Param> ?project_list </Param>
24
<Param> ?total_budget</Param>
25
<Param> ?resource_list</Param>
26
</Parameters>
27
<PreConditions>
28
<Predicate> (available ?project_list) </Predicate>
29
<Predicate> (available ?resource_list) </Predicate>
30
</PreConditions>
31
<PostEffects>
117
A. Supplementary Listings and Figures
32
<Effect> (add (new_proj_list ?new_list)) </Effect>
33
<Effect> (add (new_budget ?new_budget)) </Effect>
34
</PostEffects>
35
<SubWF> WS25 - A subprocess
36
</SubWF>
37
</TaskDesign>
38
<TaskFormal>
39
<FSP> PS = ( init -> sort_by_cost -> review -> vote -> select </FSP>
40
</TaskFormal>
41
<TaskDefn>
42
<Agent> General_Manager </Agent>
43
<Agent> Marketing </Agent>
44
<Agent> Engg_Design </Agent>
45
<Agent> Manfg </Agent>
46
<Agent> QA </Agent>
47
<Agent>Purchasing</Agent>
48
<Agent> Customer_Service</Agent>
49
<Procedure>
50
<ProcedureName> Select_Project </ProcedureName>
51
<ProcedureSource> HandBook </ProcedureSource>
52
<Implementation_type> Manual_Team_Execution </Implementation_type>
53
</Procedure>
54
<Inputs>
55
<DataItem> budget </DataItem>
56
<DataItem> resources </DataItem>
57
<DataItem> projects </DataItem>
58
</Inputs>
59
<Outputs>
60
<DataItem> selected_projects </DataItem>
61
<DataItem> remaining_budget </DataItem>
62
</Outputs>
63
</TaskDefn>
64
</Task>
118
A. Supplementary Listings and Figures
A.1.2. Instance level workow schema
WFInstance WFInstanceID
WFSchemaID
WFDataInputs
WFDataOutput
WFDateStarted
WFDateCompleted
PerformanceMetrics
EventsList
SysAdminComments
NameVal
NameVal
TotalTime
AgentTime
Event EventID
DuringTask
EventType
EventCause
EventRepair
Figure A.1.: CODAW instance schema (compare [MZ03] Figure 7)
119
Bibliography
[Aal02] W.M.P. van der Aalst. Business Pro cess Management: A p ersonal view,
2002.
[ADH
+
03] W. M. P. van der Aalst, B. F. van Dongen, J. Herbst, L. Marustera,
G. Schimm, and A. J. M. M. Weijters. Workow mining: A survey of
issues and approaches.
Data & Know ledge Engineering, Volume 47, Issue
2 , November 2003
, pages 237267, Novemb er 2003.
[AH02] W.M.P. van der Aalst and K.M. van Hee.
Workow Management: Models,
Methods, and Systems
. MIT press, Cambridge, MA, 2002.
[AHKB02] W.M.P. van der Aalst, A.H.M. ter Hofstede, B. Kiepuszewski, and
A. P. Barros. Workow Patterns. QUT Technical rep ort, FIT-TR-
2002-02, Queensland University of Technology, Brisbane, 2002. (See also
http://www.tm.tue.nl/it/research/patterns.).
[AJ00] W.M.P. van der Aalst and S. Jablonski. Dealing with Workow Change:
Identication of Issues and Solutions.
International Journal of Computer
Systems, Science, and Engineering
, 15(5):267276, 2000.
[AP94] Agnar Aamo dt and Enric Plaza. Case-based reasoning: foundational issues,
metho dological variations, and system approaches.
AI Communications
,
7(1):3959, 1994.
[AWM03] W.M.P. van der Aalst, A. Weijters, and L. Maruster. Workow mining:
Discovering pro cess mo dels from event logs, 2003.
[Bus01] Christoph Bussler. The Role of B2B Proto cols in Inter-Enterprise Pro cess
Execution.
Lecture Notes in Computer Science
, 2193:1634, 2001.
[CCPP96] Fabio Casati, Stefano Ceri, Barbara Pernici, and Guisepp e Pozzi. Workow
Evolution. In
ER '96: Proceedings of the 15th International Conference on
Conceptual Modeling
, pages 438455, London, UK, 1996. Springer-Verlag.
[DA04] Boudewijn F. van Dongen and Wil M. P. van der Aalst. Multi-phase Pro cess
Mining: Building Instance Graphs. In
ER
, pages 362376, 2004.
[DFAB98] Alan Dix, Janet Finlay, Gregory Ab owd, and Russell Beale.
Human-
Computer Interaction 2nd Edition
. Prentice Hall, 1998.
120
Bibliography
[DS90] T. H. Davenp ort and J. E. Short. The new industrial engineering: Informa-
tion technology and business pro cess redesign.
Sloan Management Review
,
pages 1127, Summer 1990.
[EKR95] Clarence Ellis, Karim Keddara, and Grzegorz Rozenb erg. Dynamic Change
Within Workow Systems. In
COCS '95: Proceedings of conference on
Organizational computing systems
, pages 1021, New York, NY, USA, 1995.
ACM Press.
[GAHL01] P. Grefen, K. Ab erer, Y. Honer, and H. Ludwig. CrossFlow: Cross-
organizational Workow Management in Dynamic Virtual Enterprises.
International Journal of Computer Systems, Science, and Engineering
,
15(5):277290, 2001.
[HHJHS97] J. Hagemeyer, T. Herrmann, K. Just-Hahn, and R. Striemer. Flexibilität
b ei Workow-Management-Systemen. In
Usability Engineering: Integra-
tion von Mensch-Computer-Interaktionen und Software-Entwicklung, Fach-
tagung Software-Ergonomie 1997, Dresden, 3.-6.3.97, Stuttgart
, pages 179
190. Teubner, 1997.
[HHT99] San-Yih Hwang, Sun-Fa Ho, and Jian Tang. Mining Exception Instances to
Facilitate Workow Exception Handling. In
DASFAA
, pages 4552, 1999.
[Hol95] David Hollingsworth. Workow Management Coalition Sp ecication. The
Workow Reference Mo del, January 1995. Do cument Status - Issue 1.1.
[HSW97] Thomas Herrmann, August-Wilhelm Scheer, and Herb ert Web er.
Verbesserung von Geschäftsprozessen mit exiblen Workow-Management-
Systemen 1
. Physica-Verlag, 1997.
[JB96] Stefan Jablonski and Christoph Bussler.
Workow Management Mod-
eling Concepts, Architecture and Implementation
. International Thomson
Computer Press, 1996.
[KR93] James E. Kurose and Keith W. Ross.
Computer Networking. A Top-Down
Approach Featuring the Internet
, volume Second Edition. Addison-Wesley,
2993.
[LS97] K. Lei and M. Singh. A Comparison of Workow Metamo dels, 1997.
[MAW03] A.K.A. de Medeiros, W.M.P. van der Aalst, and A.J.M.M. Weijters. Work-
ow Mining: Current Status and Future Directions. In R. Meersman et al.,
editor,
CoopIS/DOA/ODBASE 2003
, volume LNCS 2888, pages 389 406.
Springer-Verlag Berlin Heidelb erg, 2003.
[MGMR02] Sergey Melnik, Hector Garcia-Molina, and Erhard Rahm. Similarity o o d-
ing: A versatile graph matching algorithm and its application to schema
matching. In
ICDE
, pages 117128, 2002.
121
Bibliography
[MGR02] S. Melnik, H. Garcia-Molina, and E. Rahm. Similarity Flo o ding: A Versatile
Graph Matching Algorithm and its Application to Schema Matching. In
Proc. 18th ICDE
, San Jose, CA, February 2002.
[Müh96] Michael zur Mühlen. Der Lösungsb eitrag von Metamo dellen und Kontroll-
uÿprimitiven b eim Vergleich von Workowmanagementsystemen. Master's
thesis, Westfälische Wilhelms-Universität Münster, Septemb er 1996.
[MZ03] Therani Madhusudan and J. Leon Zhao. A Case-Based Framework for
Workow Mo del Management. Springer-Verlag Berlin Heidelb erg, 2003.
[MZM04] Therani Madhusudan, J. Leon Zhao, and Byron Marshall. A case-based
reasoning framework for workow mo del management.
Data Know l. Eng.
,
50(1):87115, 2004.
[RD98] Manfred Reichert and Peter Dadam. Adept
ex
-supp orting dynamic changes
of workows without losing control.
J. Intel l. Inf. Syst.
, 10(2):93129, 1998.
[Rei00] Manfred Reichert.
Dynamische Ablaufänderungen in Workow-
Management-Systemen
. PhD thesis, Universität Ulm, 2000.
[RRD02] Stefanie Rinderle, Manfred Reichert, and Peter Dadam. Eziente
Verträglichkeitsprüfung und automatische Migration von Workow-
Instanzen b ei der Evolution von Workow-Schemata.
Inform., Forsch. En-
twickl.
, 17(4):177197, 2002.
[RRD04] Stefanie Rinderle, Manfred Reichert, and Peter Dadam. Correctness criteria
for dynamic changes in workow systems - a survey.
Data Know l. Eng.
,
50(1):934, 2004.
[RWRW05] S. Rinderle, B. Web er, M. Reichert, and W. Wild. Integrating Pro cess
Learning and Pro cess Evolution - A Semantics Based Approach. submitted
for publication., 2005.
[Shn98] Ben Shneiderman.
Designing the User Interface 3rd Edition
. Addison-
Wesley, 1998.
[SM95] D. M. Strong and S. M. Miller. Exceptions and exception handling in
computerized information pro cesses.
ACM Transactions on Information
Systems
, 13(2):206233, 1995.
[Ver04] Verein Deutscher Ingenieure, editor.
VDI 2206. Entwicklungsmethodik für
mechatronische Systeme - Design methodologies for mechatronic systems
.
VDI-Gesellschaft Entwicklung Konstruktion Vertrieb, June 2004.
[Wor99] Workow Management Coalition. Terminology & Glossary, 1999. Do cument
Numb er WFMC-TC-1011.
122
Bibliography
[WRWR05] Barbara Web er, Stefanie Rinderle, Werner Wild, and Manfred Reichert.
CCBR-Driven Business Pro cess Evolution. In
Proc. 6th Int'l Conf. on
Case-Based Reasoning (ICCBR'05) (accepted for publication)
, Chicago, IL,
August 2005.
[WWB04] B. Web er, W. Werner, and R. Breu. CCBRenabled adaptive workow man-
agement. In
Proc. European Conf. on Case-Based Reasoning (ECCBR'04)
,
LNCS 3155, Madrid, 2004.
[WWT97] Christoph Wargitsch, Thorsten Wewers, and Felix Theisinger. Workbrain:
Merging Organizational Memory and Workow Management Systems. In
Proceedings on 21st Annual German Conference on AI '97
, 1997.
[WWT98] Christoph Wargitsch, Thorsten Wewers, and Felix Theisinger. An
Organizational-Memory-Based Approach for an Evolutionary Workow
Management System - Concepts and Implementation. In
HICSS '98: Pro-
ceedings of the Thirty-First Annual Hawaii International Conference on
System Sciences-Volume 1
, page 174. IEEE Computer So ciety, 1998.
123
Erklärung
Name: Florian Bertele
Matrikelnummer: 463675
Ich erkläre, dass ich diese Diplomarb eit selbst verfasst und keine anderen als die angegeb e-
nen Quellen und Hilfsmittel verwendet hab e.
Ulm, den 29. April 2005
125
