Automatic generation of optimized business process models from constraint-based specifications

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
AUTOMATIC GENERATION OF OPTIMIZED
BUSINESS PROCESS MODELS FROM
CONSTRAINT-BASED SPECIFICATIONS
IRENE BARBA∗ and CARMELO DEL VALLE†
Dp o. Lenguajes y Sis emas In o m´a icos
Uni e si y o Se ille, A da Reina Me cedes s/n
Se ille, 41012, Spain
∗i [email p o ec ed]
†[email p o ec ed]
BARBARA WEBER
Depa men o Compu e Science
Uni e si y o Innsb uck, Technike s aße 21a
Innsb uck, 6020, Aus ia
[email p o ec ed]
ANDR´ES JIM´ENEZ
Dp o. Lenguajes y Sis emas In o m´a icos
Uni e si y o Se ille, A da Reina Me cedes s/n
Se ille, 41012, Spain
[email p o ec ed]
Business p ocess (BP) models a e usually defined manually by business analys s h ough
impe a i e languages conside ing ac i i y p ope ies, cons ain s imposed on he ela- ions
be ween he ac i i ies as well as diffe en pe o mance objec i es. Fu he mo e, alloca ing
esou ces is an addi ional challenge since scheduling may significan ly impac BP
pe o mance. The e o e, he manual specifica ion o BP models can be e y com-plex and
ime-consuming, po en ially leading o non-op imized models o e en e o s. To
o e come hese p oblems, his wo k p oposes he au oma ic gene a ion o impe a i e
op imized BP models om decla a i e specifica ions. The s a ic pa o hese decla a- i e
specifica ions (i.e. con ol-flow and esou ce cons ain s) is expec ed o be use ul on a long-
e m basis. This s a ic pa is complemen ed wi h in o ma ion ha is less s able and
which is po en ially unknown un il s a ing he BP execu ion, i.e. es ima es ela ed o (1)
numbe o p ocess ins ances which a e being execu ed wi hin a pa icula ime ame, (2)
ac i i y du a ions, and (3) esou ce a ailabili ies. Unlike con en ional p oposals, an
impe a i e BP model op imizing a se o ins ances is c ea ed and deployed on a sho - e m
basis. To p o ide o un- ime flexibili y he p oposed app oach addi ion-ally allows
decisions o be de e ed o un- ime by using complex la e-planning ac i i ies, and he
impe a i e BP model o be dynamically adap ed du ing un- ime using eplan-ning. To
alida e he p oposed app oach, diffe en pe o mance measu es o a se o
∗Co esponding au ho .
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
es models o a ying complexi y a e analyzed. The esul s indica e ha , despi e he
NP-ha d complexi y o he p oblems, a sa is ac o y numbe o sui able solu ions can be
p oduced.
Keywo ds: Business p ocess managemen ; cons ain p og amming; planning;
scheduling.
1. In oduc ion
A business p ocess (BP) consis s o a se o ac i i ies which a e pe o med in coo di-
na ion in an o ganiza ional and echnical en i onmen ,1 and which join ly ealize a
business goal. Nowadays, he e exis s a g owing in e es in aligning in o ma ion sys-
ems in a p ocess-o ien ed way1,2 as well as in he effec i e managemen o BPs. BP
imp o emen has been anked as he numbe one p io i y o op managemen by
he 2010 Ga ne su ey.3 BP managemen (BPM) can be seen as suppo ing BPs
using me hods, echniques, and so wa e in o de o design, enac , con ol, and ana-
lyze ope a ional p ocesses in ol ing humans, o ganiza ions, applica ions, and o he
sou ces o in o ma ion.4 Typically, he adi ional BPM li e cycle1 includes se e al
phases: P ocess Design & Analysis, sys em configu a ion, p ocess enac men and
e alua ion. The BP Design & Analysis phase has he goal o gene a e a BP model,
i.e. o define he se o ac i i ies and he execu ion cons ain s be ween hem,1 by
o malizing he in o mal BP desc ip ion using a pa icula BP modeling no a ion.
The P ocess Design & Analysis phase plays an impo an ole in he BPM li e cycle
o any imp o emen ini ia i e, since i g ea ly influences he emaining phases o
his cycle. In addi ion, also un- ime aspec s a e impo an o BP imp o emen ,
e.g. esou ce alloca ions and scheduling may significan ly impac BP pe o mance.
1.1. P oblem s a emen
T adi ionally, wo s eps a e conside ed in he BP Design & Analysis phase o c ea e
aBPmodel.5 The fi s s ep consis s o analyzing he BP, e.g. by in e iewing
s akeholde s (people in ol ed in he p ocess), in o de o d aw an ini ial BP model
(as-is model). Second, in o de o imp o e his ini ial model, diffe en echniques
can be employed like simula ion6 o BP edesign,7 esul ing in he gene a ion o a
o-be model. Typically, diffe en quali y dimensions like ime, cos , flexibili y and
quali y can be diffe en ia ed7 be ween which ade-off decisions ha e o be made
when c ea ing a BP design. Once a ce ain p ocess design has been chosen and
implemen ed, BPs a e execu ed acco ding o his design.a Du ing p ocess execu ion,
scheduling decisions a e hen ypically made by he BPM sys ems (BPMSs), by
au oma ically assigning ac i i ies o esou ces.8
aIn his wo k, we make he assump ion ha he e is a BPM sys em execu ing he BPs.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
In mos cases, he o e all p ocess o c ea ing a BP model is ca ied ou manu-
ally by business analys s, who speci y he BP in o ma ion h ough an impe a i e
language by choosing be ween se e al diffe en al e na i e designs he one which
bes mee s he pe o mance goals o he o ganiza ion. The e o e, analys s mus
deal wi h se e al aspec s in o de o gene a e a sui able BP model, such as: (1)
he ac i i y p ope ies, e.g. ac i i y du a ion, esou ce o ole which is equi ed
o ac i i y execu ion (i.e. he ole-based alloca ion pa e n is conside ed8), (2) he
ela ions be ween he ac i i ies, i.e. con ol-flow o he BP, and (3) he op imiza ion
o se e al objec i es, e.g. minimiza ion o comple ion ime. The manual specifica-
ion o impe a i e BP models can he e o e o m a e y complex p oblem, i.e. i can
consume a g ea quan i y o ime and human esou ces, may cause ce ain ailu es,
and may lead o non-op imized models since he aci na u e o human knowledge
is o en an obs acle o elici ing accu a e p ocess models.9
No only he p ocess design, bu also he alloca ion o esou ces du ing p ocess
execu ion has a g ea influence on p ocess pe o mance. Howe e , scheduling is
only conside ed o a limi ed deg ee in exis ing BPMSs, and is ypically done du ing
un- ime by assigning wo k o esou ces.
The si ua ion is u he complica ed by he ac ha ypically mul iple ins ances
o a p ocess ge concu en ly execu ed wi hin a pa icula ime ame. In o de o
ensu e ha he execu ion o a p ocess is no only locally op imized o a single
ins ance, he whole se o ins ances whicha eexecu edwi hina pa icula ime-
ame has o be conside ed.
1.2. Con ibu ion
To suppo p ocess analys s in he defini ion o op imized BP models we sug-
ges a me hod o au oma ically gene a ing impe a i e BP models using a ificial
in elligence (AI) planning echniques om cons ain -based specifica ions. Unlike
impe a i e models, he specifica ion o p ocess p ope ies in a decla a i e way, e.g.
using a cons ain -based specifica ion, only equi es p ocess designe s o s a e wha
has o be done ins ead o ha ing o speci y how i has o be done.b In he p o-
posed app oach, he s a ic pa o he inpu decla a i e model (i.e. con ol-flow
and esou ce cons ain s) is expec ed o be use ul on a long- e m basis since i
emb aces in o ma ion which is no supposed o change o en. The base decla a i e
model (i.e. only including he s a ic pa ) is complemen ed wi h in o ma ion ha
is less s able and which is po en ially unknown un il s a ing he BP execu ion,
i.e. es ima es ela ed o (1) numbe o p ocess ins ances which a e being execu ed
wi hin a pa icula ime ame, (2) ac i i y du a ions, and (3) esou ce a ailabili ies.
F om his ex ended model, he p oposed app oach is in cha ge o de e mining how
bThe ad an ages o using decla a i e languages o BP modeling ins ead o impe a i e languages,
e.g. acili a ing he human wo k in ol ed in he BP modeling, a e discussed in se e al s udies, e.g.
Re s. 10–15.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
o sa is y he cons ain s imposed by he decla a i e specifica ion and a he same
ime o a ain an op imiza ion o ce ain objec i e unc ions (e.g. minimiza ion o
comple ion ime). Fo his op imiza ion, scheduling is done on a sho - e m basis
by conside ing he op imiza ion o a se o ins ances.
Unlike con en ional p oposals, in ou app oach each gene a ed model is c e-
a ed and deployed o a specific planning pe iod, conside ing changing in o ma ion
such as he numbe o p ocess ins ances which a e being execu ed wi hin a specific
ime ame. Fo he nex execu ions o he decla a i e model, new models will be
gene a ed conside ing he specific alues which a e gi en o he changing in o ma-
ion. Since planning is done on a sho - e m basis, he gene a ed models a e less
p one o change.
Figu e 1 p o ides an o e iew o ou app oach. Taking he cons ain -based
specifica ions as a s a ing poin (c . Fig. 1(1)), enac men plans can au oma i-
cally be gene a ed (c . Fig. 1(2)). Fo his, ac i i ies o be execu ed ha e o be
selec ed and o de ed (planning p oblem16) conside ing he con ol-flow imposed by
he cons ain -based specifica ion. Mo eo e , o au oma ically p opose execu ion
plans which mee he pe o mance goals bes (e.g. minimizing he o e all comple-
ion ime (OCT), i.e. ime needed o comple e all p ocess ins ances which we e
planned o a ce ain pe iod), he cons ain -based model is complemen ed wi h
in o ma ion ela ed o es ima es ega ding he numbe o ins ances, ac i i y du a-
ions, and esou ce a ailabili ies (scheduling p oblem17). Fo planning and schedul-
ing (P&S) he ac i i ies such ha he p ocess objec i e unc ion is op imized, a
cons ain -based app oach is p oposed since cons ain p og amming18 supplies a
sui able amewo k o modeling and sol ing p oblems in ol ing P&S aspec s.19
The gene a ed enac men plans a e hen au oma ically ansla ed in o a Business
P ocess Model and No a ion (BPMN) model20 (c . Fig. 1(3)), which can be hen
u he imp o ed by a business analys , whe e necessa y. In mos cases, BPMN
models can be ansla ed in o an execu ion language,21 such as BPEL,22 which
enables BP designs o be deployed in o BPMS and le hei ins ances be execu ed
by a BPM engine. To p o ide o an inc eased flexibili y he BPMN model can be
dynamically adap ed du ing un- ime by using eplanning (c . Fig. 1(4)).
No e ha he BPMN model is gene a ed wi h he goal o making he decla a-
i e model au oma ically execu able by a BPMS by conside ing he specific alues
o he changing in o ma ion which a e gi en jus be o e s a ing he execu ion he
Fig. 1. AI P&S echniques o he gene a ion o op imized BP models.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
p ocess. In his way, applica ion o decision de e al pa e ns is au oma ed,23 i.e.
he ole o he BPMS is a he ocused on enabling con ol and ensu ing compli-
ance (decisions a e au oma ically made by he BPMS). Rega ding decision de e al
pa e ns, ou app oach belongs o he la e modeling and composi ion pa e n, i.e.
allowing o modeling and au oma ic composi ion o a p ocess model jus be o e
s a ing he execu ion o a b anch o p ocess ins ances. The e o e, ou app oach can
be amed wi hin dynamic p ocess-based composi ion (i.e. comple ely c ea ing he
execu able p ocess model dynamically a un- ime), which cons i u es an example
o he au oma ed a ian o he la e modeling and composi ion pa e n.
The main con ibu ions o his pape can be summa ized as ollows:
(i) The defini ion o a language o he cons ain -based specifica ion o BPs which
ex ends ConDec,11,24 named ConDec-R (c . Sec. 3,S ep1inFig.1), o enable
he easoning abou esou ces.
(ii) Au oma ic planning and scheduling o he BP ac i i ies o he gene a ion o
op imized BP enac men plans om he ConDec-R specifica ions, h ough a
cons ain -based app oach (c . Sec. 4,S ep2inFig.1).
(iii) Au oma ic gene a ion o op imized BP models in BPMN om op imized BP
enac men plans (c . Sec. 5,S ep3inFig.1).
(i ) P o iding o un- ime flexibili y by allowing decisions o be de e ed a un-
ime and he BPMN model o be dynamically adap ed du ing un- ime (c .
Sec. 6,S ep4inFig.1).
( ) Valida ion o he p oposed app oach h ough he analysis o diffe en pe o -
mance measu es ela ed o a ange o es models o a ying complexi y (c .
Sec. 8).
In his way, he au oma ic gene a ion o BP models simplifies he BP design
phase by acili a ing he human wo k in mos cases, p e en ing ailu es in he de el-
oped BP models, and enabling be e op imiza ion o be a ained in he enac men
phase. Fu he mo e, impe a i e BP models can dynamically be gene a ed om
s a ic cons ain -based specifica ions jus be o e s a ing he BP enac men , once
some alues o he enac men pa ame e s, e.g. esou ce a ailabili ies, a e known.
Mo eo e , he au oma ic gene a ion o BP models can deal wi h complex p oblems
o g ea size in a simple way (as will be demons a ed in Sec. 8). The e o e, a wide
s udy o se e al aspec s can be ca ied ou , such as hose ela ed o he equi e-
men o esou ces o diffe en oles, o he es ima ed comple ion ime o he BP
enac men , by gene a ing se e al kinds o al e na i e specifica ions. In addi ion,
in o de o add ess un- ime flexibili y he p oposed app oach allows decisions o
be de e ed a un- ime by using complex la e-planning ac i i ies, and he BPMN
model o be dynamically adap ed du ing un- ime using eplanning.
The emainde o his pape is o ganized as ollows: Sec. 2 in oduces back-
g ounds needed o he u he unde s anding o he pape , Secs. 3–6 de ail he
p oposals o his wo k, Sec. 7 explains an example, Sec. 8 deals wi h he e alua ion

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
o he p oposed app oach, Sec. 9 summa izes ela ed wo k, Sec. 10 p esen s a c i i-
cal discussion o he ad an ages and limi a ions o ou p oposal, and finally, Sec. 11
includes some conclusions and u u e wo k.
2. Backg ound
Ou wo k combines aspec s o scheduling, planning, and cons ain p og amming
in o de o au oma ically gene a e op imized BP enac men plans om cons ain -
based specifica ions. The op imized enac men plans a e hen ansla ed in o BPMN
models. Sec ion 2.1 p o ides backg ounds ega ding cons ain -based p ocesses. Sec-
ion 2.2 gi es an o e iew o planning, scheduling, and cons ain p og amming.
Sec ion 2.3 summa izes he BPMN s anda d.
2.1. Cons ain -based BP models
Diffe en pa adigms o p ocess modeling exis , e.g. impe a i e and decla a i e. I e-
spec i e o he chosen app oach, desi ed beha io mus be suppo ed by he p ocess
model, while o bidden beha io mus be p ohibi ed.11,25,26 While impe a i e p o-
cess models speci y exac ly how hings ha e o be done, decla a i e p ocess models
ocus on wha should be done. In li e a u e, se e al ule-based and cons ain -based
languages o decla a i e BP modeling a e p oposed (e.g. Re s. 11, 24, 27–29). In
ou p oposal we use ConDec11,24 o he BP con ol-flow specifica ion. We conside
ConDec o be a sui able language, since i allows he specifica ion o BP ac i i ies
oge he wi h he cons ain s which mus be sa isfied o co ec BP enac men
and o he goal o be achie ed. Mo eo e , ConDec allows o speci y a wide se o
BP models in a simple and flexible way. ConDec is based on cons ain -based BP
models (c . Defini ion 2.1), i.e. including in o ma ion abou (1) ac i i ies ha can
be pe o med as well as (2) cons ain s p ohibi ing undesi ed p ocess beha io .
De ini ion 2.1. A cons ain -based p ocess model S =(A, CBP) consis s o a se o
ac i i ies A, and a se o cons ain s CBP p ohibi ing undesi ed execu ion beha io .
Fo each ac i i y a ∈ A esou ce cons ain s can be specified by associa ing a
ole wi h ha ac i i y. The ac i i ies o a cons ain -based p ocess model can be
execu ed a bi a ily o en i no es ic ed by any cons ain s.
Cons ain s can be added o a ConDec model o speci y o bidden beha io ,
es ic ing he desi ed beha io . Fo his, ConDec p oposes an open se o empla es,
i.e. pa ame ized g aphical ep esen a ions o cons ain s o e he BP ac i i ies,
which can be di ided in o h ee g oups ( o a desc ip ion o he comple e se o
empla es, c . Re . 30):
(i) Exis ence empla es: Una y ela ionships conce ning he numbe o imes one
ac i i y is execu ed. As an example, Exac ly(N,A) specifies ha Amus be
execu ed exac ly N imes.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
(ii) Rela ion empla es: Posi i e bina y ela ionships used o es ablish wha should
be execu ed. As an example, P ecedence(A, B) specifies ha o execu e ac i i y
B, ac i i y Aneeds o be execu ed be o e.
(iii) Nega ion empla es: Nega i e bina y ela ionships used o o bid he execu-
ion o ac i i ies in specific si ua ions. As an example, No Coexis ence(A, B)
specifies ha i Bis execu ed, hen Acanno be execu ed, and ice e sa.
While una y ela ionships desc ibe cons ain s ela ed o one ac i i y (e.g. exis-
ence cons ain s), bina y cons ain s desc ibe ela ionships be ween ac i i ies (e.g.
p ecedence cons ain s). Bina y empla es a e composed by a sou ce ac i i y (c .
Defini ion 2.2) and a sink ac i i y (c . Defini ion 2.3).
De ini ion 2.2. A sou ce ac i i y o a bina y empla e is an ac i i y which appea s
in he fi s pa ame e o he empla e. Fo empla es which s a e p ecedence ela-
ions be ween ac i i ies, a sou ce ac i i y is a p edecesso ac i i y.
De ini ion 2.3. A sink ac i i y o a bina y empla e is an ac i i y which appea s
in he second pa ame e o he empla e. Fo empla es which s a e p ecedence
ela ions be ween ac i i ies, a sink ac i i y is a successo ac i i y.
Figu e 2shows a simple cons ain -based model which is composed by ac i i-
ies A,B,andC, and cons ain s C1 (Exac ly(2, A)), C2 (P ecedence(A, B)), C3
(P ecedence(A, C)), and C4 (No Coexis ence(B,C)).
Fu he mo e, bina y empla es can be ex ended by defining b anched empla es,
as desc ibed in Re . 26. The b anched empla es o he bina y empla es can be
es ablished be ween se e al BP ac i i ies in he ollowing way:
•The b anched empla e is es ablished be ween se e al sou ce ac i i ies and one
sink ac i i y, so ha he ela ion is gi en be ween a leas one o he sou ces
and he sink.
Fig. 2. Simple cons ain -based model.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
•The b anched empla e is es ablished be ween one sou ce ac i i y and se e al
sink ac i i ies, so ha he ela ion is gi en be ween he sou ce and a leas one
o he sinks.
As he execu ion o a cons ain -based model p oceeds, in o ma ion ega ding
he execu ed ac i i ies is eco ded in an execu ion ace (c . Defini ion 2.4).
De ini ion 2.4. Le S=(A, CBP) be a cons ain -based p ocess model wi h ac i -
i y se Aand cons ain se CBP. Then: A ace σis composed by a sequence
o s a ing and comple ing e en s e1,e
2,...,e
n ega ding ac i i y execu ions ai,
a∈A, i.e. e en s can be:
(i) s a (ai,
jk, ), i.e. he i- h execu ion o ac i i y ausing k- h esou cewi h ole
jis s a ed a ime .
(ii) comp(ai, ), i.e. he i- h execu ion o ac i i y ais comple ed a ime .
Due o hei flexible na u e, equen ly se e al ways o execu e cons ain -based
p ocess models exis , i.e. e e y hing which is enabled can be execu ed. The decisions
ela ed o which o he enabled ac i i ies o execu e and in wha o de can be made
using se e al mechanisms23:
•Goal-based: Decisions be ween al e na i es (selec ion o a pa icula p ocess ag-
men , ac o , o ac i i y implemen a ion) a e made conside ing he o e all goals
(c . Defini ion 2.5) o he p ocess.
De ini ion 2.5. The goal o a BP is specified h ough he cons ain s which mus
be sa isfied in he BP enac men .
Fo example, acescAABand AACa e wo alid ways o execu ing he
cons ain -based model o Fig. 2, while ace AABCis in alid due o C4. The
diffe en alid execu ion al e na i es, howe e , can a y g ea ly in espec o hei
quali y, i.e. how well diffe en pe o mance objec i e unc ions (c . Defini ion 2.6)
like minimizing cycle ime can be achie ed. Op imiza ion decisions can be amed
as goal-based decisions (i.e. he e al e na i es o each a specific goal and he op i-
miza ion o gi en objec i e unc ions should be conside ed o selec one o hese
al e na i es).
De ini ion 2.6. The objec i e unc ion o a BP is he unc ion o be op imized
du ing he BP enac men , e.g. minimiza ion o OCT.
•Rule-based: Decisions be ween diffe en al e na i es a e made based on a se o
ules.
cFo he sake o cla i y, aces ep esen sequences o ac i i ies so ha no pa allelism is conside ed
in he examples. Mo eo e , only comple ed e en s o ac i i y execu ions a e included in he ace
ep esen a ion.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
•Expe ienced-based: Decisions be ween diffe en al e na i es a e made by elying
on pas expe iences made in simila con ex .
•Use -based: Decisions be ween diffe en al e na i es a e made by lea ing decision
making o he human expe .
In ou base p oposal, we conside all he choice-like cons uc s o ConDec as
op imiza ion o goal decisions, i.e. decision making is goal-based. Assuming ha
all decisions a e goal-based, he base app oach migh be alid o some en i on-
men s like o example ce ain web se ice se ings. I mo e flexibili y is equi ed,
in Sec. 6.1 we p opose an app oach ha allows decisions which a e no goal-based
o be de e ed o un- ime and enables he op imiza ion wi hin decision agmen s
which ame non-goal-based decisions. Mo eo e , o p o ide o an inc eased un-
ime flexibili y, he e is he possibili y o use eplanning (c . Sec. 6.2).
2.2. Planning, scheduling and cons ain p og amming
Fo gene a ing op imized BP enac men plans op imizing he pe o mance objec i e
unc ions (c . Defini ion 2.6) o cons ain -based p ocess models, ac i i ies o be
execu ed ha e o be planned16 and scheduled17 by conside ing he cons ain -based
specifica ion. To do his, a cons ain -based app oach is p oposed.19
The a ea o scheduling17 includes p oblems in which i is necessa y o de e mine
an enac men plan o a se o ac i i ies ela ed by empo al cons ain s (in ou con-
ex he con ol-flow cons ain s oge he wi h he esou ce cons ain s, i.e. equi ed
esou ces, in oduced in Sec. 2.1). Mo eo e , since he execu ion o ac i i ies may
equi e he same esou ces, hey may compe e o limi ed esou ces. In gene al, he
objec i e in scheduling is o find a easible plan which sa isfies bo h empo al and
esou ce cons ain s. Se e al objec i e unc ions a e usually conside ed o be op i-
mized, in mos cases ela ed o empo al measu es (e.g. minimiza ion o comple ion
ime), o conside ing he op imal use o esou ces.
In a wide pe spec i e, in AI planning,16 he ac i i ies o be execu ed a e no
es ablished ap io i, hence i is necessa y o selec hem om a se o al e na i es
and o es ablish an o de ing. In mos cases, he specifica ion o planning p oblems
includes he ini ial s a e o he wo ld, he goal (a p edica e ep esen ing a se o
possible final s a es) ha mus be eached, and a se o ope a o s (ac ions) which
can be applied o one s a e in o de o each ano he s a e. Fu he mo e, in planning
p oblems, usually he op imiza ion o ce ain objec i e unc ions is conside ed.
Cons ain p og amming (CP)18 (c . Fig. 3) can be used, among o he s, o
planning and scheduling pu poses.19 In o de o sol e a p oblem h ough cons ain
p og amming, i needs o be modeled as a cons ain sa is ac ion p oblem (CSP)
(c . Defini ion 2.7).
De ini ion 2.7. A CSP P =(V, D, CCSP) is composed by a se o a iables V ,
ase o domains D, which is composed o he domain o alues domi o each
a iable a i ∈ V , and a se o cons ain s CCSP be ween a iables, so ha each
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
cons ain is added o he CSP model, i.e. Exis ence(2,A), P ecedence(A, B),
P ecedence(A, C), and No Coexis ence(B, C) o he cons ain -based model
depic ed in Fig. 5.
De ini ion 4.3. A CSP-ConDec p oblem ela ed o a ConDec-R p ocess model
CR =(Ac s, CBP,Res) (c . Defini ion 3.1) is a COP Po =(V, D, CCSP,o)(c .
Defini ion 2.9) whe e:
(i) The se o a iables Vis composed by all he CSP a iables included in he
p esen ed CSP model plus he CSP a iable ela ed o he OCT, i.e. V=
{n (a),(a, ole, du )∈Ac s}∪{s (ai),e (ai), es(ai),sel(ai),(a, ole, du )∈
Ac s, i ∈[1 ...UB(n (a))]}∪{OCT }.
(ii) The se o domains Dis composed by he domains o each CSP a iable ,
Dom( ), i.e. D={Dom(n (a)) = {0...MC},(a, ole, du )∈Ac s}∪
{Dom (s (ai)) = Dom(e (ai)) = {0...MC ×(a, ole,du )∈Ac s du (a)},
(a, ole, du )∈Ac s, i ∈[1 ...UB(n (a))]}∪{Dom( es(ai)) = {1...# ole,
( ole, # ole)∈Res},(a, ole, du )∈Ac s, i ∈[1 ...UB(n (a))]}∪{Dom
(sel(ai)) = {0...1},(a, ole, du )∈Ac s,i∈[1 ...UB (n (a))]},whe eMC
is he maximum ca dinali y o he BP ac i i ies, i.e. n (es ablished by exis-
ence ela ions in he cons ain -based model). In his way, MC is used o
es ablishing ini ial uppe bounds (i.e. UB) o he domain o se e al a iables
(including n a iables).
(iii) The se o cons ain s CCSP is composed by he global cons ain s (imple-
men ed by he fil e ing ules, c . Sec. 4.2) ela ed o he ConDec-R cons ain s
included in CBP oge he wi h he cons ain s om he p oposed CSP model,
i.e. ∀i:1≤i<n (a):e (ai)≤s (ai+1), ∀i:1≤i≤UB(n (a)) : sel(ai)==
n (a)>=i o each epea ed ac i i y (a, ole, du )∈Ac s.
(i ) Theobjec i e unc ionois minimizing he OCT a iable.
In he p oposed cons ain -based app oach esou ces a e implici ly cons ained
since COMET p o ides a high-le el cons ain modeling specific o scheduling which
includes an efficien managemen o sha ed esou ces. No e ha , besides he ole-
based alloca ion pa e n, he CSP a iables which a e included in he model can
be also used o speci ying u he esou ce cons ain s.8 As an example, sepa a ion
o du ies (i.e. he abili y o speci y ha wo ac i i ies a and b mus be alloca ed o
diffe en esou ces in a gi en wo kflow case) can be specified by including he nex
cons ain in he p oposed CSP model: ∀ i :1 ≤ i ≤ n (a), ∀ j :1≤ j ≤ n (b):
ai · es = bj · es.
Figu e 5 includes he ansla ion om a ConDec-R specifica ion in o a CSP so
ha he CSP a iables and cons ain s a e s a ed as explained in Defini ion 4.3
(c . S ep 2). In gene al, o each epea ed ac i i y a,a CSP a iable n is added
o he CSP model. The eby, he alue o LB(n (a)) is ini ially se o 0 (i will
be au oma ically upda ed du ing he sol ing p ocess i an exis ence cons ain is
added h ough he co esponding fil e ing ule, c . Sec. 4.2), and o UB(n (a))

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
a ough ini ial es ima e is made by conside ing he maximum obliga o y ca -
dinali y MC o all epea ed ac i i ies which is s a ed by exis ence cons ain s.
Fo he cons ain -based model depic ed in Fig. 5, o example, he uppe bound
o all epea ed ac i i ies is ini ially se o 2 (due o he exis ence cons ain
ela ed o ac i i y A). This alue is high enough o ensu e a easible solu ion
( he op imal solu ion, howe e , in gene al includes lowe alues o n o se e al
ac i i ies).
Mo eo e , LB(OCT) is ini ially se o 0, and UB(OCT) is es ima ed as he
maximum ca dinali y imes he sum o he du a ion o all he BP ac i i ies, i.e.
2 × (5 + 3 + 4) in he example o Fig. 5. This is since he wo s solu ion which can
be ob ained esul s in a plan which includes he execu ion o each BP ac i i y he
maximum numbe o imes when all ac i i ies a e sequen ially execu ed.
Fo simila easons, o each scheduling ac i i y ai, lowe and uppe bounds
o s and e a e se o lowe and uppe bounds o OCT. Fu he mo e, in gen-
e al, Dom( es(ai)) = {1 ...# ole( ole(a))}, i.e. Dom( es(Ai)) = {1 ...2} and
Dom( es(Ci)) = {1 ...2} o any i since #R1 =2,andDom( es(Bi)) = {1}
o any i since #R2 = 1 o he cons ain -based model depic ed in Fig. 5.In
addi ion, o each scheduling ac i i y ai, Dom(sel(ai)) = {0 ...1},since sel is a
bina y a iable indica ing whe he o no he scheduling ac i i y is selec ed o be
execu ed.
4.2. Fil e ing ules
To imp o e he modeling o he p oblems and o efficien ly handle he cons ain s
in he sea ch o solu ions, ou cons ain -based p oposal includes o each ConDec
empla e a ela ed global cons ain implemen ed h ough a fil e ing ule ( espon-
sible o emo ing alues which do no belong o any solu ion) o he defini ion
o he high-le el ela ions be ween he BP ac i i ies. In his way, he cons ain s
s a ed in he ConDec-R specifica ion (c . Defini ion 3.1) a e included in he CSP
model h ough he ela ed global cons ain s. These global cons ain s acili a e he
specifica ion o he p oblem. A he same ime, he ela ed fil e ing ules enable he
efficiency in he sea ch o solu ions o inc ease. This is since du ing he sea ch
p ocess hese fil e ing ules emo e inconsis en alues om he domains o he
a iables. In he CSP model specifica ion, ini ial es ima es a e made o uppe and
lowe bounds o a iable domains (c . Sec. 4.1), and hese alues a e efined du ing
he sea ch p ocess. The de eloped fil e ing ules (c . Re . 34) a e conside ed in he
sea ch algo i hms.
4.3. Sol ing he COP
Once he p oblem is modeled, se e al cons ain -based mechanisms can be used o
ob ain he solu ion o he COP, i.e. op imized enac men plans (c . Defini ion 4.4).
Since he gene a ion o op imized plans p esen s NP-complexi y,35 i is no possible
o ensu e he op imali y o he gene a ed plans o all he cases. The de eloped
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
cons ain -based app oach, howe e , allows sol ing he conside ed p oblems in an
efficien way.
De ini ion 4.4. A BP enac men plan is composed by: (i) he numbe o imes each
BP ac i i y is execu ed, (ii) he s a and he comple ion imes o each ac i i y
execu ion, and (iii) he esou ce which is used o each ac i i y execu ion.
By aking in o accoun he NP-complexi y o he conside ed p oblems, we
adap ed he exis ing sol e COMET42 by applying an incomple e sea ch o sol ing
he specific conside ed p oblems. We also e alua e i s sui abili y o he gene a ion
o BPMN models om cons ain -based specifica ions (c . Sec. 8). This incomple e
sea ch includes andomized componen s in o de o di e si y he sea ch. By means
o his app oach, a fi s easible solu ion is quickly ound by a andomized g eedy
algo i hm. The same g eedy algo i hm is used o i e a i ely imp o ing he bes
solu ion ound un il a ime limi is eached. Th ough his incomple e sea ch, all he
solu ions can be eached and he sea ch p ocedu e efficien ly explo es a wide ange
o solu ions om di e sified a eas o he sea ch space.
In gene al, when op imizing a CSP a iable, i a easible solu ion which is known
exis s, he alue o he a iable o op imize in he known solu ion can be used o
disca ding la ge subse s o ui less candida es by using uppe and lowe es ima ed
bounds o he quan i y being op imized du ing he sea ch p ocess. Thus, i a known
easible solu ion S o he p oblem o sol e exis s, he objec i e alue o his
solu ion (SOCT) is a aluable in o ma ion which can be added o he cons ain
model h ough he cons ain OCT <SOCT. Thus, some non-op imal candida es,
i.e. candida es whose OCT alue canno be less han SOCT in any case, a e disca ded
du ing he sea ch, inc easing he efficiency in he sea ch o solu ions.
Mo eo e , in ou p oposal, du ing he sea ch p ocess, some o he alues which
only lead o non- easible solu ions, i.e. inconsis en alues, a e emo ed om he
domains o he CSP a iables h ough he de eloped fil e ing ules (c . Sec. 4.2)in
o de o educe he sea ch space by main aining a c consis ency (c . Defini ion 4.5).
De ini ion 4.5. ACSP=(V, D, CCSP)p esen sa c consis ency iff o all pai s o
CSP a iables ( a 1, a 2) | a 1, a 2 ∈ V , o each alueo a 1 in he domain
o a 1 he e is some alue in he domain o a 2 ha sa is y all he cons ain s
s a ed in CCSP be ween a 1 and a 2,and ice e sa.
In he p oposed app oach, he de eloped fil e ing ules and CSP modeling (c .
Sec. 4.1) a e implemen ed such ha hey main ain he a c consis ency o all pai s
o CSP a iables du ing all he sea ch p ocess.
5. F om Op imized Enac men Plans o Op imized Business
P ocess Models
Sec ion 4 has desc ibed how op imized BP enac men plans can be gene a ed om
ConDec-R specifica ions. This sec ion desc ibes how a BPMN model which includes
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
he same ac i i ies o be execu ed in he same o de ing and also using he same
esou ces can be gene a ed om he op imized enac men plan.
Fo each ole in he BP enac men plan, a BPMN pool (c . Defini ion 5.1)
is c ea ed, which con ains as many lanes as numbe o a ailable esou ces o
ha ole.
De ini ion 5.1. ABPMN pool BPMNPool =( ole, # ole) is a pool o a BPMN
model, which is composed o # ole lanes.
Mo eo e , o each scheduling ac i i y in he BP enac men plan a BPMN ac i -
i y (c . Defini ion 5.2) is c ea ed. Addi ionally, one s a ac i i y and one end ac i -
i y a e included in he BPMN model.
De ini ion 5.2. ABPMN ac i i y BPMNAc =(pool, lane, du , s ) is an ac i i y
o a BPMN model placed in he lane named lane o he pool named pool,wi h
du a ion du and s a ime s .
One o he mos impo an aspec s o be conside ed o he gene a ion o op i-
mized BPMN models a e he p ecedence ela ions be ween he BPMN ac i i ies
(scheduling ac i i ies). Fo es ablishing hese p ecedence ela ions he alues o he
s a and he end imes o he scheduling ac i i ies in he enac men plan a e con-
side ed. These p ecedence ela ions a e hen used as a basis o gene a ing BPMN
models (c . Defini ion 5.6) om BP enac men plans. Some ela ed defini ions a e
gi en below:
De ini ion 5.3. In a BP enac men plan ega ding a CSP solu ion S, a scheduling
ac i i y aiis a p edecesso o ano he scheduling ac i i y bj,ai∈p edecesso s(bj),
i he ela ion Se (ai)≤Ss (bj)holds due o esou ce o empla e ela ions.
De ini ion 5.4. In a BP enac men plan, a scheduling ac i i y aiis a di ec p e-
decesso o ano he scheduling ac i i y bj,ai∈DP(bj), i ai∈p edecesso s(bj)∧
 ∃ck∈p edecesso s(bj)|ai∈p edecesso s(ck).
De ini ion 5.5. In a BP enac men plan, a scheduling ac i i y aiis an indi ec
p edecesso o ano he scheduling ac i i y bj,ai∈IP(bj), i ai∈p edecesso s(bj)∧
∃ck∈p edecesso s(bj)|ai∈p edecesso s(ck).
De ini ion 5.6. ABPMN model BPMN =(Pools, Ac i i ies, SequenceF lows,
Pa allelM) ela ed o a ConDec-R p ocess model CR =(Ac s, CBP,Res) (c . De -
ini ion 3.1) and o a solu ion S(c . Defini ion 2.8) o he ela ed CSP-ConDec
p oblem (c . Defini ion 4.3) is a BP model specified h ough he BPMN language,
whe e:
(1) P ools ={BPMNPool( ole, # ole),( ole, # ole)∈Res}.
(2) Ac i i ies ={BPMNAc ( ole(a), S es(ai),du (a), Ss (ai)), (a, ole, du )∈
Ac s,i∈[1 ...Sn (a)]}∪{s a =BPMNAc (P0,L
0,0,0)}∪{end =BPMNAc
(P0,L
0,0,max(a, ole,du )∈Ac s,i∈[1...Sn (a)]Se (ai))}.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
(3) Le he se P edecesso s be:
(i) {(s a , ai)|(a, ole, du )∈Ac s, i ∈[1 ...Sn (a)],Ss (ai)=0}∪
(ii) {(aSn (a),end)|(a, ole, du )∈Ac s,  ∃bi,i∈[1 ...Sn (b)], (b, oleb,du
b)∈
Ac s,aSn (a)∈p edecesso s(bi)}∪
(iii) {(bi,c
j)|i∈[1 ...Sn (b)], (b, oleb,du
b)∈Ac s,j∈[1 ...Sn (c)], (c, olec,
du c)∈Ac s, bi∈DP(cj)},
Then:
(a) SequenceFlows ={(bi,c
j)|(((b, oleb,du
b)∈Ac s ∧i∈[1 ...Sn (b)]) ∨
bi=s a )∧(((c, olec,du
c)∈Ac s ∧j∈[1 ...Sn (c)]) ∨cj=end)∧
(bi,c
j)∈P edecesso s∧|{dk,(((d, oled,du
d)∈Ac s∧k∈[1 ...Sn (d)])∨
dk=s a ),(dk,c
j)∈P edecesso s}| =1)}.
(b) Pa allelM ={(Sou ces,cj)|(((c, olec,du
c)∈Ac s ∧j∈[1 ...Sn (c)]) ∨
cj=end)∧Sou ces ={bi,(((b, oleb,du
b)∈Ac s ∧i∈[1 ...n (b)]) ∨bi=
s a )∧(bi,c
j)∈P edecesso s}∧|Sou ces|>1}.
In his way, h ough he se P edecesso s, he p ecedence ela ions be ween
ac i i ies a e s a ed so ha (i) he s a ac i i y is p edecesso o all scheduling
ac i i ies whose s alue is equal o 0, (ii) he ac i i ies which a e no p edecesso s
o any o he ac i i y, a e p edecesso o he end ac i i y, and (iii) in gene al, one
ac i i y bi is p edecesso o ano he ac i i y cj iff bi is di ec p edecesso o cj (c .
(3) in Defini ion 5.6). The se P edecesso s is ep esen ed in he BPMN model by
BPMN sequence flows be ween a sou ce ac i i y bi and a sink ac i i y cj,in he case
ha bi is he only p edecesso o cj (c . (3)(a) in Defini ion 5.6), o by a pa allel
me ging ga eway be ween a se o sou ce ac i i ies Sou ces and a sink ac i i y cj in
he case ha cj has mo e han one p edecesso (c . (3)(b) in Defini ion 5.6). No e
ha pa allel me ging ga eways (i.e. pa allel ga eways which ha e se e al sou ces and
only one sink) need o be explici ly included in he esul ing BPMN model, since
hey do no ha e he same meaning as se e al bina y sequence flows om se e al
sou ces and one sink. Howe e , pa allel spli ing ga eways (i.e. pa allel ga eways
which ha e se e al sinks and only one sou ce) do no need o be explici ly included
in he esul ing BPMN model since se e al bina y sequence flows be ween one
sou ce ac i i y and se e al sink ac i i ies ha e he same meaning as a pa allel
spli ing ga eway in he BPMN language.
The pseudocode and complexi y analysis o he algo i hms which we e de el-
oped o gene a ing BPMN models om op imized BP enac men plans a e included
in Appendix A. As a b ie summa y o his appendix, he e is a main algo i hm,
Algo i hm A.1, which cons uc s a BPMN model om a ConDec-R model and om
a ela ed op imized BP enac men plan (c . Defini ion 5.6). As s a ed be o e, one o
he mos impo an aspec s o be conside ed o his model gene a ion a e he p ece-
dence ela ions be ween he scheduling ac i i ies o he plan, which a e managed
by Algo i hm A.2. These p ecedence ela ions a e due o (1) esou ce cons ain s,
i.e. he ac i i ies a e alloca ed in he esou ces in a specific o de in he gene -
a ed enac men plan, and (2) ConDec-R cons ain s ela ed o p ecedence be ween
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
ac i i ies. Typically, unlike esou ce p ecedence ela ions, p ecedence ela ions due
o ConDec-R cons ain s canno be easily ob ained. To his end, each ConDec-
R empla e p esen s a me hod which is in cha ge o de e mining he p ecedence
ela ions which a e gi en be ween he scheduling ac i i ies ela ed o he epea ed
ac i i ies which a e in ol ed in ha ConDec-R empla e. The men ioned me hod
o some ep esen a i e ConDec-R empla es is de ailed in Algo i hms A.3–A.5.
6. Allowing o Run-Time Flexibili y
The execu ion plans gene a ed in Sec. 4 p o ide an op imal way o execu ing
he sou ce ConDec model assuming ce ain es ima ed alues and all decision o
be goal-based. E en hough hese assump ions a e alid o ce ain en i onmen s
(e.g. ce ain web se ice se ings) es ima es migh no always be accu a e o some
decisions migh depend on un- ime in o ma ion. Fo his, he app oach desc ibed
in Secs. 3–5 is ex ended in his sec ion o allow decisions o be de e ed a un- ime
(c . Sec. 6.1), and o allow he BPMN model o be dynamically adap ed du ing
un- ime (c . Sec. 6.2).
6.1. La e-planning ac i i ies
Execu ing a ConDec model usually en ails dealing wi h decisions ela ed o (1) how
many imes one ac i i y is being execu ed, and (2) he o de o execu ion o he
ac i i ies. We assume ha a leas he decisions ela ed o he o de o execu ion o
he ac i i ies a e goal-based. Howe e , we conside non-goal-based decisions (e.g.
use -based decisions), i needed, ega ding he numbe o execu ions o a pa icula
ac i i y. Rela ed o hese decisions, in u n, in ConDec one ac i i y can be execu ed
a bi a ily o en i no es ic ed by any cons ain . Howe e , he e a e some ConDec
empla es which cons ain he numbe o execu ions o he ac i i ies, esul ing ei he
in a specific alue (e.g. A mus be execu ed exac ly wice), o in a ange (e.g. A
mus be execu ed ei he once o wice). The numbe o imes one ac i i y should
be execu ed can be s a ed by one specific cons ain (e.g. Exac ly(A, 2)), o by he
combina ion o se e al cons ain s (e.g. he combina ion o Exac ly(A, 2) oge he
wi h ChainSuccession(A, B) implies ha B should be execu ed exac ly wice). To
be able o deal wi h decisions ela ed o he numbe o imes ce ain ac i i ies a e
being execu ed which a e no goal-based, we p opose o encapsula e hese ac i i ies
( oge he wi h he ela ions in which hey a e in ol ed) in a complex decla a i e
la e-planning ac i i y when speci ying he ConDec-R model, i.e. we p opose he use
o hie a chical models. In decla a i e models he ac i i ies included in a complex
ac i i y should be such ha hey can be execu ed in isola ion om he op-le el
p ocess.37
Encapsula ing decisions which a e no goal-based in a agmen allows deal-
ing wi h each sub-p ocess (i.e. complex ac i i y) as i i we e a black box, and
he e o e, ou app oach can be di ec ly applied (e en enabling mul iple ins ance

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
op imiza ion). The e o e, when c ea ing he op imized enac men plans om he
ConDec-R specifica ion (c . Sec. 4), each la e-planning ac i i y is ea ed as an
a omic ac i i y, and i is managed as a epea ed ac i i y (c . Defini ion 4.1). In
his way, when gene a ing he BPMN model (c . Sec. 5) he complex ac i i ies a e
hen in eg a ed in o he BPMN model by subs i u ing he BPMN ac i i y ela ed
o he complex ac i i y by he associa ed impe a i e agmen . The ollowing sec-
iosn desc ibes he gene a ion p ocess. Fo sake o cla i y we desc ibe in diffe en
subsec ions how cons ain s (c . Sec. 6.1.1), esou ces (c . Sec. 6.1.2), and du a ions
(c . Sec. 6.1.3) a e managed.
6.1.1. Cons ain s
The BPMN agmen associa ed o a specific complex ac i i y is gene a ed as
ollows:
(1) Gene a ing all possible combina ions o decla a i e models in such a way ha all
diffe en possibili ies o n (i.e. numbe o imes) o each ac i i y a e co e ed.
This is done by s a ing Exac ly cons ain s o all he possible alues o he
numbe o execu ions o all he ac i i ies which belong o he complex ac i i y.
Specifically, o each ac i i y A whose numbe o execu ions should be in a
ange[Min...Max], hegene a edmodelsshouldco e all hepossibili ies (i.e.
Exac ly(A, n ), ∀n ∈[Min ...Max]) in combina ion wi h all he possibili ies
o he o he ac i i ies. No e ha he maximum numbe o execu ion imes o
each ac i i y belonging o a complex ac i i y needs o be es ablished, o he wise,
he possibili ies a e no fini e.
(2) Fo each decla a i e model which is gene a ed, ela ed op imized enac men
plans a e c ea ed (i.e. local op imiza ion o each possible easible decla a-
i e model is add essed) h ough he p oposed cons ain -based app oach (c .
Sec. 4).
(3) These op imized plans a e hen ansla ed o BPMN agmen s (c . Sec. 5).
(4) These agmen s a e hen linked by using exis ing me ging algo i hms (e.g.
Re . 38). No e ha he esul ing agmen will include XOR ga eways when
necessa y.
When gene a ing he diffe en combina ions o decla a i e models (i.e. s ep (1))
i is possible ha some un easible combina ions exis . In hese cases, no ela ed
op imized enac men plan is gene a ed, and he e o e, he ela ed BPMN agmen
is no conside ed when me ging.
Figu e 6 shows an example o he comple e p ocess o e a agmen which
includes fi e BP ac i i ies (A, B, C, D and E) and fi e exis ence ela ions (i.e. all
ac i i ies should be execu ed a mos once) oge he wi h fi e bina y ela ions (i.e.
(1) ExChoice(A, C), implying ha ei he A o C (bu no bo h) mus be exe-
cu ed, (2) ExChoice(B, D), implying ha ei he B o D (bu no bo h) mus be
execu ed, (3) Response(A, B), implying ha a e he execu ion o A, B should
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
Fig. 6. Gene a ing BPMN agmen s om decla a i e complex ac i i ies.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
be e en ually execu ed, (4) P ecedence(C, D), implying ha be o e he execu ion
o D, C should be execu ed, and (5) Succession(D, E), implying ha a e he
execu ion o D, E should be execu ed and be o e he execu ion o E, D should be
execu ed). Gi en ha decla a i e specifica ion, he e a e h ee easible scena ios,
i.e. h ee possible ways o execu e he specifica ion ensu ing ha all cons ain s a e
sa isfied:
(a) Ais execu ed once; Cis no execu ed due o ExChoice(A, C); Bis exe-
cu ed once a e Adue o he Response(A, B)cons ain ;Dis no exe-
cu ed due o ExChoice(B,D), he e o e also Ecanno be execu ed due o
Succession(D, E).
(b) Cis execu ed once; Ais no execu ed due o ExChoice(A, C); Bis execu ed
once; Dis no execu ed due o ExChoice(B,D), he e o e also Ecanno be exe-
cu ed due o Succession(D, E). In he ela ed op imized enac men plan, bo h
op ions (Bsucceeding Co Csucceeding B) a e easible. Fo his example, we
conside ha he op ion Bsucceeding Cis mo e op imized han Csucceeding
B(no e ha o each easible scena io only he mos op imized plan is selec ed
o he me ging, as explained in he s ep (2) o he p ocess).
(c) Cis execu ed once; Ais no execu ed due o ExChoice(A, C)); Dis execu ed
once; Bis no execu ed due o ExChoice(B,D). Since Dis execu ed, Eshould
be also execu ed due o Succession(D, E). In he ela ed op imized enac men
plan, Cshould p ecede Ddue o P ecedence(C, D), and Dshould p ecede E
due o Succession(D, E).
In his example, some un easible combina ions o n exis . Fo example, he
scena io in which A is execu ed once and D is execu ed once is un easible since wo
ela ions (i.e. Response(A, B)and P ecedence(C, D)) a e iola ed.
In Fig. 6, he diffe en BPMN agmen s ( ela ed o he op imized enac men
plans) which a e ob ained om he h ee easible scena ios ha e been me ged using
he ool p esen ed in Re . 38. Fo he sake o cla i y, in Fig. 6 in o ma ion ela ed
o esou ces and du a ions o ac i i ies has been omi ed.
No e ha op imiza ion is locally applied wi hin each complex ac i i y since
o each decla a i e model which is gene a ed (i.e. o each possibili y) op imized
enac men plans a e gene a ed.
6.1.2. Resou ces
Fo each complex ac i i y, equi ed esou ces need o be s a ed when including his
ac i i y in he ConDec-R model. When all he ac i i ies which belong o he same
complex ac i i y equi e esou ces ela ed o he same ole, he complex ac i i y
will also equi e ha ole, and he p oposed app oach can be di ec ly applied (c .
Fig. 7(a), whe e all he ac i i ies equi e a esou ce o ole R0). Howe e , when
he ac i i ies which belong o he same complex ac i i y equi e esou ces ela ed
o diffe en oles, some adjus men s a e equi ed, e.g. encapsula ing he decla a i e
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
(a)
(b)
Fig. 7. Complex ac i i ies: Dealing wi h esou ces. (a) Ac i i ies equi ing esou ces ela ed o
he same ole, (b) ac i i ies equi ing esou ces ela ed o diffe en oles.
sub-p ocess in a complex ac i i y which equi es as many esou ces as diffe en oles
a e included in he sub-p ocess (c . Fig. 7(b)), i.e. he cons ain -based app oach
needs o be adap ed o allow o ac i i ies which equi e mul iple esou ces, esul ing
in a cumula i e scheduling p oblem.39 This ex ension can be easily achie ed since
mos cons ain -based sys ems p o ide a high-le el cons ain modeling specific
o scheduling which includes an efficien managemen o sha ed esou ces o well-
known scheduling p oblems, which is he case o he cumula i e scheduling p oblem.
When gene a ing he BPMN model, each ac i i y o he sub-p ocess needs o be
associa ed o he sui able lane (c . Fig. 7). No e ha , in he p oposed app oach,
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
Fig. 10. Op imized Gan cha and BPMN o he a el agency p oblem o #P =4, #A =1
and #B =1.
As commen ed, in o de o define an ins ance (#P, #A, #B) o he a el
agency p oblem, he ollowing pa ame e s mus be s a ed: numbe o clien eques s
(#P), numbe o esou ces a ailable in he agency (#A), and numbe o esou ces
a ailable in he company (#B).
In his sec ion, wo ins ances a e s udied as illus a ions, specifically P oblem 1
defined by (#P =4, #A =1, #B = 1), and P oblem 2 defined by (#P =4,
#A =2, #B = 2). Fo P oblem 1, Fig. 10 shows bo h he op imized Gan cha
(OCT = 47) and he BP model which a e ob ained h ough ou p oposal. I can
be seen ha ega ding he fi s clien eques , depic ed by G1 in he Gan dia-
g am), he ip plan is c ea ed by he agency (TP1 ac i i y), while he anspo
and accommoda ion sea ch a e ca ied ou by he company (CT&AS1). Once bo h
ac i i ies TP1 and CT&AS1 s a , he second clien eques can be ecei ed (G2).
The ac ha anac i i y B can only s a a e ano he ac i i y A has s a ed is
s a ed by conside ing he p edecesso s o A as p edecesso s o B.In hiscase, he
p edecesso o TP1 and CT&AS1 (i.e. G1) mus (di ec ly o indi ec ly) p ecede G2.
Rega ding he second Ge Reques ac i i y (G2), he ip plan is o ganized by he
company (CTP2 ac i i y), while he anspo and accommoda ion sea ch a e ca -
ied ou by he agency (TS2 and AS2 ac i i ies). In his case, ac i i y AS2, which
is ela ed o he second eques , is pos poned un il a e he end o he execu ion
o o he ac i i ies ela ed o he hi d eques (G3, TP3), o efficiency easons
(no ice ha he e is no cons ain be ween he epea ed ac i i ies TP and AS).
Once bo h ac i i ies CTP2 and TS2 s a , he hi d clien eques can be ecei ed
(G3). Rega ding he hi d Ge eques (G3), he ip plan is c ea ed by he agency

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
(TP3 ac i i y), while he anspo and accommoda ion sea ch a e ca ied ou by
he company (CT&AS3 ac i i y). Once bo h ac i i ies TP3 and CT&AS3 s a , he
ou h Ge eques can be ecei ed (G4). Rega ding he ou h eques (G4), he ip
plan is c ea ed by he company (CTP4 ac i i y), while he anspo and accommo-
da ion sea ch a e ca ied ou by he agency (TS4 and AS4 ac i i ies). A e all he
clien eques s which a e ca ied ou by he company a e finished, he Send Repo
(SR) ac i i y can be execu ed. A e his, he Recei e Repo (RR) ac i i y can be
execu ed. Finally, a e all ac i i y execu ions, he Clien Repo s (CR) ac i i y is
execu ed.
In a simila way, o P oblem 2, Fig. 11 shows he op imized Gan cha (OCT =
33) and he BP model which a e ob ained wi h ou p oposal.
7.4. Dynamic p og amming o he a el agency p oblem
A easible solu ion o a model o a numbe o ins ances can be ob ained by conca e-
na ing known solu ions o he same model wi h a smalle numbe o ins ances. The
Fig. 11. Op imized Gan cha and BPMN o he a el agency p oblem o #P =4, #A =2
and #B =2.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
op imal way o pe o m his conca ena ion can be achie ed by dynamic p og am-
ming (DP).41 Fo he a el agency p oblem, DP can be applied o ob aining good
solu ions by joining op imal solu ions o smalle p oblems. Le OCTa,b(p)be he
bes OCT which is known o an ins ance (p, a, b) o he a el agency p oblem.
DP can be applied o he a el agency p oblem so ha he bes OCT o (p, a, b)
ob ained h ough DP, OCT DPa,b(p), can be defined by:
OCT DPa,b(p)= min
1≤i≤p/2(OCTa,b(i)+OCT
a,b(p−i)−du (CRepo s))j
i.e. he bes combina ion o wo op imal/op imized solu ions o smalle p oblems
is chosen.
8. Empi ical E alua ion
In o de o e alua e he efficiency o he p oposal, a con olled expe imen is con-
duc ed. Sec ion 8.1 desc ibes he design unde lying he expe imen , and Sec. 8.2
shows he expe imen al esul s and he da a analysis.
8.1. Expe imen al design
Pu pose: The pu pose o he empi ical e alua ion is o analyze ou p oposal in
he gene a ion o op imal enac men plans om ConDec-R specifica ions, specifi-
cally, he goals a e: (1) he compa ison o ou cons ain -based p oposal wi h DP
(c . Sec. 8.2.1) and (2) he demons a ion o i s use o simula ion pu poses (c .
Sec. 8.2.2).
Objec s: We used he a el agency p oblem as example o ou e alua ion, since
i includes a ious and ep esen a i e ela ions o se e al ypes and complexi y om
he se o all he ConDec-R empla es.k
Independen Va iables: Fo he empi ical e alua ion, he numbe o clien
eques s, #P , he numbe o esou ces o oleA,#A, and he numbe o esou ces
o ole B,#B, a e aken as independen a iables.
Response Va iables: Some pe o mance measu es (c . Table 3) ela ed o he
bes gene a ed plan a e epo ed o he gene a ed p oblems (Figs. 12;Tables4–6).
Expe imen al Design: Based on he a el agency p oblem we gene a ed a wide
se o p oblem ins ances by a ying he diffe en independen a iables: #P,#A
and #B. Fo a iable #P , he alues1...100 a e conside ed, o #A, he alues
1 ...5 a e conside ed, and o #B, he alues 1...5 a e conside ed.
Expe imen al Execu ion: Fo he expe imen s, he cons ain -based sea ch algo-
i hm is un un il a 10-min CPU ime limi is eached. The machine o all expe -
imen s is an In el Co e2, 2.13 GHz, 1.97 GB memo y, unning on Windows XP.
jCRepo s ac i i y mus be execu ed only once, and mus be alloca ed a e he execu ion o all
o he ac i i ies.
kA ool o gene a ing op imized BP models o he a el agency p oblem can be ound a
h p:// egula.lsi.us.es/AgenciesOp imizedModels/, whe e some es s can be ca ied ou .
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
Table 3. Response a iables.
Id Desc ip ion
CP/DP(s1+s2) The way in which he bes solu ion is ound, which can be by means o
he p oposed cons ain -based app oach, CP, o by DP h ough
combining s1ands2, DP(s1+s2).
OCT OCT o he gene a ed op imized enac men plan.
%BusyA A e age pe cen age o use o esou ces o ole A, ega ding he OCT.
%BusyB A e age pe cen age o use o esou ces o ole B, ega ding he OCT.
0
200
400
600
800
1000
1200
1400
B1 B2 B3 B4 B5 B1 B2 B3 B4 B5 B1 B2 B3 B4 B5 B1 B2 B3 B4 B5 B1 B2 B3 B4 B5
P = 100
P = 90
P = 80
P = 70
P = 60
P = 50
P = 40
P = 30
P = 20
P = 10
A1 A5A4A3A2
OCT
Resou ces
(a)
0
200
400
600
800
1000
1200
1400
A1 A2 A3 A4 A5 A1 A2 A3 A4 A5 A1 A2 A3 A4 A5 A1 A2 A3 A4 A5 A1 A2 A3 A4 A5
B1 B5B4B3B2
Resou ces
OCT
P = 100
P = 90
P = 80
P = 70
P = 60
P = 50
P = 40
P = 30
P = 20
P = 10
Legend
An: n esou ces
wi h ole A
Bn: n esou ces
wi h ole B
(b)
Fig. 12. OCT depending on #A,#B. (a) Resou ces a e g ouped by #A, (b) esou ces a e
g ouped by #B.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
Table 4. %OCT o he bes solu ion ound and me hod (CP o DP) ha eaches i .
P(#A, #B) OCT CP/DP(s1+s2) P(#A, #B) OCT CP/DP(s1+s2)
1 (1, 1) 20 CP 11 (1, 1) 119 DP(5 + 6)
1 (2, 2) 19 CP 11 (2, 2) 72 CP
1 (3, 3) 19 CP 11 (3, 3) 68 CP
1 (4, 4) 19 CP 11 (4, 4) 68 CP
1 (5, 5) 19 CP 11 (5, 5) 67 CP
2 (1, 1) 27 CP 12 (1, 1) 128 DP(6 + 6)
2 (2, 2) 21 CP 12 (2, 2) 80 DP(5 + 7)
2 (3, 3) 21 CP 12 (3, 3) 71 CP
2 (4, 4) 21 CP 12 (4, 4) 70 CP
2 (5, 5) 21 CP 12 (5, 5) 70 CP
3 (1, 1) 38 CP 13 (1, 1) 139 DP(6 + 7)
3 (2, 2) 28 CP 13 (2, 2) 85 CP
3 (3, 3) 28 CP 13 (3, 3) 78 CP
3 (4, 4) 28 CP 13 (4, 4) 75 CP
3 (5, 5) 28 CP 13 (5, 5) 75 CP
4 (1, 1) 47 CP 14 (1, 1) 149 DP(6 + 8)
4 (2, 2) 33 CP 14 (2, 2) 92 DP(7 + 7)
4 (3, 3) 33 CP 14 (3, 3) 84 CP
4 (4, 4) 33 CP 14 (4, 4) 84 CP
4 (5, 5) 33 CP 14 (5, 5) 84 CP
5 (1, 1) 57 CP 15 (1, 1) 160 DP(7 + 8)
5 (2, 2) 36 CP 15 (2, 2) 98 DP(7 + 8)
5 (3, 3) 35 CP 15 (3, 3) 91 DP(5 + 10)
5 (4, 4) 35 CP 15 (4, 4) 88 CP
5 (5, 5) 35 CP 15 (5, 5) 88 CP
6 (1, 1) 66 CP 16 (1, 1) 170 DP(8 + 8)
6 (2, 2) 44 CP 16 (2, 2) 103 CP
6 (3, 3) 43 CP 16 (3, 3) 97 CP
6 (4, 4) 43 CP 16 (4, 4) 93 CP
6 (5, 5) 43 CP 16 (5, 5) 93 CP
7 (1, 1) 77 CP 17 (1, 1) 181 DP(8 + 9)
7 (2, 2) 48 CP 17 (2, 2) 110 DP(8 + 9)
7 (3, 3) 45 CP 17 (3, 3) 101 DP(7 + 10)
7 (4, 4) 45 CP 17 (4, 4) 99 CP
7 (5, 5) 45 CP 17 (5, 5) 99 CP
8 (1, 1) 87 CP 18 (1, 1) 190 DP(6 + 12)
8 (2, 2) 54 CP 18 (2, 2) 116 DP(9 + 9)
8 (3, 3) 52 CP 18 (3, 3) 104 CP
8 (4, 4) 52 CP 18 (4, 4) 104 CP
8 (5, 5) 52 CP 18 (5, 5) 104 CP
9 (1, 1) 98 CP 19 (1, 1) 201 DP(7 + 12)
9 (2, 2) 60 CP 19 (2, 2) 122 DP(8 + 11)
9 (3, 3) 57 CP 19 (3, 3) 112 DP(7 + 12)
9 (4, 4) 57 CP 19 (4, 4) 111 DP(7 + 12)
9 (5, 5) 57 CP 19 (5, 5) 111 DP(7 + 12)
10 (1, 1) 109 DP(4+6) 20 (1, 1) 211 DP(8 + 12)
10 (2, 2) 67 CP 20 (2, 2) 128 DP(9 + 11)
10 (3, 3) 60 CP 20 (3, 3) 116 DP(10 + 10)
10 (4, 4) 60 CP 20 (4, 4) 116 DP(10 + 10)
10 (5, 5) 60 CP 20 (5, 5) 116 DP(10 + 10)
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
Table 5. %Busy A e sus #P.
#A#P
10 20 30 40 50 60 70 80 90 100
1 95.2 95.1 95.0 95.0 95.0 95.0 95.0 95.0 95.0 95.0
2 79.8 82.6 81.4 83.1 82.2 81.7 82.6 83.3 82.8 82.4
3 73.5 74.8 74.3 75.5 75.1 74.8 75.4 75.9 75.6 75.4
4 57.8 59.0 59.1 59.6 59.6 59.5 59.7 59.9 59.8 59.8
5 43.9 46.0 45.9 46.5 46.3 46.2 46.5 46.7 46.6 46.5
Table 6. %Busy B e sus #P.
#B#P
10 20 30 40 50 60 70 80 90 100
1 78.6 80.8 80.3 82.0 81.4 81.0 81.9 82.6 82.2 81.9
2 72.7 71.1 75.3 72.2 74.6 76.2 74.3 72.8 74.1 75.1
3 46.7 48.1 49.1 48.9 49.3 49.6 49.4 49.3 49.5 49.7
4 30.5 30.7 31.3 31.2 31.4 31.6 31.5 31.4 31.5 31.6
5 26.4 27.2 27.5 27.7 27.7 27.8 27.8 27.9 27.9 27.9
In o de o sol e he cons ain -based p oblems (c . Sec. 4), he de eloped algo-
i hms ha e been in eg a ed wi h he sys em COMET,42 which is able o gene a e
high-quali y solu ions o highly cons ained p oblems in an efficien way.
8.2. Expe imen al esul s and da a analysis
As commen ed, he pu pose o he empi ical e alua ion is wo- old, i.e. analyzing
he sui abili y o ou p oposal h ough a compa ison wi h DP (c . Sec. 8.2.1), and
h ough he use o simula ion (c . Sec. 8.2.2).
8.2.1. Compa ison wi h DP
DP (c . Sec. 4.3) is a widely used echnique in sol ing op imiza ion p oblems, leading
o solu ions o high quali y in mos cases. Specifically, o he a el agency p oblem,
DP can be applied (c . Sec. 7.4). We would like o e alua e whe he ou cons ain -
based p oposal usually imp o es he solu ion o good quali y which can be ob ained
by DP, i.e. wo ks efficien ly.
Table 4 shows he OCT o he bes solu ions which a e ound o some ep e-
sen a i e ins ances, oge he wi h he me hod (ei he DP o CP) which finds he
bes solu ion (column CP/DP(s1+s2) in Table 4). The eby DP(s1+s2) means
ha he bes solu ion is ound by DP h ough combining s1and s2. Fo ins ances
in which bo h echniques each solu ions which p esen he same alues o OCT,
DP(s1+s2) is depic ed. I can be obse ed ha o 1 ≤ #P ≤ 14, he cons ain -
based app oach ob ains be e solu ions han DP o almos all o he ins ances.
Mo eo e , o 15 ≤ #P ≤ 18, in some cases DP ob ains solu ions ha a e be e
han o equal o hose ob ained h ough CP, and in o he cases CP ob ains he

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
bes solu ion. Fu he mo e, o 19 ≤ #P ≤ 20, DP ob ains solu ions ha a e be -
e han o equal o hose ob ained h ough CP o all he ins ances. Fu he mo e,
i seems ha he solu ions o #P = {6, 7, 8, 9, 10 and 12} a e la gely op imized
since hey widely appea in he DP solu ions. The esul s (c . Table 4) show ha
ou cons ain -based app oach, i.e. CP, is able o imp o e he solu ion ob ained by
DP in mos o he cases. This shows ha ou cons ain -based app oach wo ks effi-
cien ly in he gene a ion o op imized enac men plans, and hence, o he au oma ic
gene a ion o op imized BPMN models.
In sho , ou da a indica es ha o he gene a ion o op imized BP models, CP
enables complex p oblems o be sol ed in a mo e efficien way han hey would be
h ough o he al e na i e me hods, such as DP o he manual specifica ion o BP
models.
Addi ionally, when #P inc eases, he complexi y o he p oblem ises sha ply,
and hence he manual ea men o he p oblem would become almos inex icable.
In con as , when using ou app oach an op imized solu ion o la ge p oblems,
such as o #P = 100 can be ob ained in only 10 min.
Th ea s o alidi y: The e a e se e al ac o s which may h ea en he alidi y o
ou expe imen s o he a ainmen o gene alizable conclusions:
•The specific cha ac e is ics o he conside ed example, i.e. he empi ical e alua-
ion only conside s a conc e e p oblem wi h a specific numbe o BP ac i i ies
and specific ela ions be ween he BP ac i i ies.
•The way in which he op imal/op imized solu ions o p oblems o a ce ain
size a e combined in o de o ob ain solu ions o la ge p oblems is specific
o he conside ed example. In mos cases, easible solu ions o la ge p oblems
can be gene a ed by conca ena ing solu ions o smalle p oblems h ough DP.
Howe e , he way in which solu ions o p oblems o a gi en size can be com-
bined o p o ide a solu ion o a la ge p oblem depends on he ype o p oblem
conside ed.
8.2.2. Use o simula ion
Ou app oach can be used o simula ion pu poses in he BP design and analysis
phase in o de o s udy he ele ance o se e al pa ame e s in he quali y o he gen-
e a ed plans, e.g. esou ce a ailabili y. As an example, he ele ance o he numbe
o a ailable esou ces o he a el agency p oblem is analyzed as ollows.
Figu e 12 shows he comple ion ime o he bes BP enac men plan (OCT)
which is gene a ed h ough ou app oach. In bo h g aphics o Fig. 12, he OCTis
shown depending on he numbe o esou ces o oles A and B.Fi s , he consid-
e ed esou ces a e g ouped acco ding o #A (Fig. 12(a)). Secondly, he conside ed
esou ces a e g ouped acco ding o #B (Fig. 12(b)). I can be seen, in mos cases,
ha he OCT g ea ly dec eases as #A inc eases. Addi ionally, in mos cases, he
OCT emains almos he same when #B inc eases. The e o e, #A seems o be
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
much mo e influen ial han #B o he OCT, i.e. A is a mo e c i ical esou ce o
he conside ed a el agency p oblem.
In Tables 5 and 6, he a e age pe cen ages o use o he esou ces o oles A and
ole B, espec i ely, ega ding he OCT, a e shown. In all cases, o he same alue
o #P , hese pe cen ages dec ease as he numbe o esou ces o he associa ed ole
inc eases. Mo eo e , as expec ed, he a e age pe cen age o use o esou ces o ole
A is g ea e han he a e age pe cen age o use o esou ces o ole B o he same
alue o #P .
9. Rela ed Wo k
Ou app oach makes a p oposal o in eg a ing P&S wi h BPMSs. Mos ela ed
wo k on such an in eg a ion ocuses on he enac men phase in o de o make
dispa ching decisions as o which ac i i y should be execu ed using a esou ce when
i becomes ee (dynamic scheduling),43–48 while e y ew in eg a ions a e ca ied
ou du ing he modeling phase, as p esen ed he e.
Also ela ed o ou p oposal is esea ch on he gene a ion o BP models, e.g.
Re s. 9, 49–53. While he p oposals o Re s. 49 and 50 p o ide he BP in o ma ion
h ough an execu ion/in e change language, XPDL, ou app oach, in u n, uses a
decla a i e modeling language based on a o mal logic (LTL). As s a ed, he usage
o decla a i e specifica ions allows he use o speci y wha has obedoneins ead
o how, he eby acili a ing he human wo k in ol ed and a oiding ailu es. In con-
as o XPDL, whe e he use has o speci y he model in an impe a i e way,
in ou p oposal he gene a ion o impe a i e BP models is au oma ically done by
he sys em. In a ela ed way, in Re . 51, planning ools a e used o he semiau o-
ma ic gene a ion o BP models, by conside ing he knowledge in oduced h ough
BP Reenginee ing languages. In Re . 51, hey p opose an objec -o ien ed s uc u e
modeling ool ha ollows hei own ule-based app oach, while we p opose he use
o an ex ension o ConDec, a widely e e enced language in he con ex o BPM
(e.g. Re s. 26 and 55), which also allows a highe le el o abs ac ion. Addi ion-
ally, Re . 52 p oposes a planning o malism o he modeling o BPs h ough an
SAP specifica ion (S a us and Ac ion Managemen , SAM), which is a a ian o
PDDL. Unlike ou wo k, nei he he esou ce pe spec i e no he op imiza ion o
se e al ins ances a e conside ed since in Re . 52 each non-de e minis ic ac ion (i.e.
ac i i y) canno be epea ed in he gene a ed solu ion. Mo eo e , Re . 53 p esen s
a se ice-o ien ed app oach which ans o ms high-le el BP models in o web se -
ices composi ion models. This app oach uses UML o speci y he BP models om
an MDA poin o iew, which lacks an implemen a ion iew o BP models,56 in
con as o ConDec, which is a g aphical and specific language o he modeling o
BPs. Fu he mo e, Re . 9 p oposes o efine BP models by combining lea ning and
planning echniques, s a ing om p ocesses which a e no ully desc ibed. Unlike
ou wo k, Re . 9 needs pas p ocess execu ions and examples p o ided by he use
o apply lea ning echniques. Mo eo e ,9 does no conside he op imiza ion o any
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
objec i e unc ion in he gene a ion o he plans. Fu he mo e, in Re . 9 execu able
plans a e gene a ed, while we p opose he gene a ion o BP models which a e spec-
ified in a s anda d language, i.e. BPMN, which can also be imp o ed by business
analys s i necessa y.
Rela ed o he combined used o decla a i e and impe a i e models, Re . 57
p oposes he use o decla a i e BP models o speci ying p ocesses independen ly
o a pa icula en i onmen in o de o align op ional p ocess cus omiza ions. This
in o ma ion is complemen ed wi h impe a i e BP specifica ions which con ain in o -
ma ion ela ed o he con ol flow o he p ocesses, o en specific o a gi en en i on-
men . In Re . 57 bo h decla a i e and impe a i e BP models need o be (manually)
specified, while in ou p oposal he op imized impe a i e models a e au oma ically
gene a ed. Las ly, Re . 58 analyzes he need o ansi ions be ween diffe en BP
modeling pa adigms, i.e. decla a i e, impe a i e and hyb id p oposals, suppo ing
ou p oposal.
Addi ionally, he e exis some p oposals which could be used o gene a e op i-
mized enac men plans o BPs om cons ain -based p ocess specifica ions. Specifi-
cally, Re . 59 p oposes he gene a ion o a non-de e minis ic fini e s a e au oma on
om cons ain -based specifica ions based on linea empo al logic (LTL) which
ep esen s exac ly all aces ha sa is y he LTL o mulas. When ex ending his
app oach by including es ima es, he OCT o all he aces could hen be cal-
cula ed (e.g. Re . 60). Howe e , he big disad an age ollowing such an app oach
would be ha i can lead o pe o mance p oblems when con on ed wi h la ge
cons ain -based models since he au oma on gene a ed o he conca ena ed LTL
o mulas is exponen ial wi h espec o he size o he o mula,61 and, unlike
he p oposed app oach, no heu is ic has been used. In a simila way, CLIMB26
could be used o gene a e easible aces, i.e. aces which mee all he cons ain s
imposed by he decla a i e specifica ion, and calcula e i s comple ion ime. Then,
he bes aces could be selec ed. Unlike ou app oach, Re . 26 does nei he con-
side op imali y no esou ce a ailabili ies. The e o e, his would only co e he
planning pa o ou p oposal, bu no he scheduling aspec s add essed by ou
app oach.
The e is some ela ed wo k (e.g. Re s. 62–65)which is ocusedon he au oma ed
composi ion o web se ices using planning echniques, i.e. gi en a se o se ices
which a e published on he web and a goal, he aim is o gene a e a composi-
ion o he a ailable se ices which sa isfies he goal. Like ou app oach, dynamic
p ocess-based composi ion app oaches also s a om a decla a i e specifica ion.
Howe e , while hey only conside ac i i ies wi h p econdi ions and effec s, we
allow o an inc eased exp essi eness h ough he ConDec language. Suppo ing
he sui abili y o ConDec o speci ying web se ices, he wo k66 p oposes he lan-
guage DecSe Flow (which is a sis e language o ConDec, i.e. bo h sha e he same
concep s and ools) as a decla a i e se ice flow language. Mo eo e , unlike,62–65
ou app oach conside s mul iple ins ances which a e execu ed wi hin a pa icula
ime ame, which is undamen al o achie ing global op imiza ion.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
10. Discussion and Limi a ions
In BP mos en i onmen s, he P ocess Design & Analysis phase is manually ca ied
ou by business analys s, who mus deal wi h se e al aspec s, such as esou ce
alloca ion, he ac i i y p ope ies and he ela ions be ween hem, and may e en
ha e o handle he op imiza ion o se e al objec i es. The e o e, in some cases, he
manual specifica ion o BP models can consume g ea quan i y o esou ces, cause
ailu es, and lead o non-op imized models, esul ing in a e y complex p oblem.9
Hence, i should be emphasized ha he au oma ic gene a ion o BP models
acili a es he human wo k in mos cases, p e en s ailu es in he de eloped BP
models, and enables be e op imiza ion o be a ained in he enac men phase.
Addi ionally, he specifica ion o p ocess p ope ies in a decla a i e way allows
he use o speci y wha is o be done, and he p oposed AI-based ool is in cha ge
o de e mining how i is o be done in o de o sa is y he p oblem specifica ions,
and o a ain he op imiza ion o ce ain objec i e unc ions.
Unlike con en ional BPMN models, in ou app oach each gene a ed model com-
p ises he execu ion o a se o ins ances. The e o e, ou app oach always add esses,
a leas , global in e -ins ance op imiza ion (e en when op imiza ion wi hin each
ins ance is no comple ely add essed). In his way, op imiza ion o e a se o
ins ances is always add essed (e.g. he esou ces which a e sha ed by he diffe en
ins ances a e alloca ed in an op imized way by conside ing all ins ances o be exe-
cu ed). Addi ionally, in mos cases, in a-ins ance op imiza ion is also (comple ely
o pa ially) add essed, as explained in Sec. 6.1.
Mo eo e , he au oma ic gene a ion o BP models can deal wi h complex p ob-
lems o g ea size in a simple way, as demons a ed in Sec. 8. The e o e, a wide
s udy o se e al aspec s can be ca ied ou by simula ion, such as hose ela ed o
he equi emen o esou ces o diffe en oles, o he es ima ed comple ion ime o
he BP enac men , by gene a ing se e al kinds o p oblems.
Fu he mo e, he p oposed cons ain -based app oach can be used o efficien ly
sol e u he planning and scheduling p oblems which include simila ela ions
be ween epea ed ac i i ies, and which a e un ela ed o BP en i onmen s.
I should also be cla ified ha he BP models a e gene a ed o execu ion pu -
poses, and hence cla i y o meaning o he use s o he gene a ed models is no
conside ed ele an in he cu en p oposal.
No e ha he gene a ion o op imized enac men plans om cons ain -based
specifica ions is, om ou poin o iew, he mos challenging ask o he p o-
posed app oach. Exis ing cons ain -based BPMSs like Decla e32 could be used
(in combina ion wi h planning) o decide which ac i i ies ha e o be done in he
cu en s a e. In a ela ed way, op imized enac men plans can be used o help
use s o find good/op imal ways o execu e a decla a i e p ocess by sugges ing
ecommenda ions, as explained in one o ou p e ious wo ks (c . Re . 67). Howe e ,
in he cu en wo k, he mo i a ion o gene a ing BPMN models om hese enac -
men plans is wo- old: (1) isualize he gene a ed enac men plan in a s anda d
BP modeling language he use s a e amilia wi h, wi h he goal o allowing he
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
Algo i hm A.2: C ea eDependencies
inpu : So edSe P&SAc ac s o de ed by s
Se Cons ain cons ain s
Se Role oles
ou pu :MapP&SAc ,Se P&SAc  di ec P edecesso s
MapP&SAc ,Se P&SAc  allP edecesso s ←∅;
1
o each in olesdo2
o each es in . esou ces do3
Lis P&SAc ac sRes ← es.ac s;4
o each i in i:1..ac sRes.size-1 do5
allP edecesso s(ac sResi+1)←{ac sResi};6
o each cincons ain sdo7
c.includeP edecesso s(allP edecesso s);8
MapP&SAc ,Se P&SAc  indi ec P edecesso s ←∅;9
o each ac in ac s do10
di ec P edecesso s(ac )←allP edecesso s(ac );11
o each p in allP edecesso s(ac )do12
di ec P edecesso s(ac )←13
di ec P edecesso s(ac ) allP edecesso s(p);
indi ec P edecesso s(ac )←
14
indi ec P edecesso s(ac )∪allP edecesso s(p);
allP edecesso s(ac )←15
allP edecesso s(ac )∪indi ec P edecesso s(ac );
e u n di ec P edecesso s;16
cons ain s ela ed o p ecedence be ween ac i i ies. Algo i hm A.2 gene a es a map
in which each scheduling ac i i y is associa ed o a se o scheduling ac i i ies ha
a e i s di ec p edecesso s (c . Defini ion 5.2). Fo his, h ee maps a e managed in
his algo i hm: (1) di ec P edecesso s, which associa es each scheduling ac i i y o
he se o i s di ec p edecesso s, (2) indi ec P edecesso s, which associa es each
scheduling ac i i y o he se o i s indi ec p edecesso s (c . Defini ion 5.3), and
(3) allP edecesso s, which associa es each scheduling ac i i y o he se o all i s
di ec and indi ec p edecesso s. In Algo i hm A.2, fi s , he p ecedences equi ed
due o he use o he same esou ce a e included (lines 2–6). Secondly, he p ece-
dences equi ed due o he high-le el ela ions (i.e. ConDec-R cons ain s) be ween
he epea ed ac i i ies which a e s a ed in he model a e included h ough he
me hod includeP ed o each cons ain (lines 7 and 8). Typically, unlike esou ce
p ecedence ela ions, p ecedence ela ions due o ConDec-R cons ain s canno be
easily ob ained. To his end, each ConDec-R empla e p esen s a me hod which is in

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
cha ge o de e mining he p ecedence ela ions which a e gi en be ween he schedul-
ing ac i i ies ela ed o he epea ed ac i i ies which a e in ol ed in ha ConDec-R
empla e. The men ioned me hod o some ep esen a i e ConDec-R empla es is
de ailed in Algo i hms A.3–A.5. Las ly, he indi ec p edecesso s a e emo ed om
he map di ec P edecesso s in o de o a oid edundan connec ions, by aking
in o accoun ha he so ed se ac s is o de ed by s , and hence, he scheduling
ac i i ies a e managed om mino o majo s in he ex e nal loop (lines 9–15).
The p ope ies o he maps which a e used in Algo i hm A.2 a e demons a ed by
P oposi ion A.1.
P oposi ion A.1. This p oposi ion con ains wo ela ed pa s:
(a) A e execu ing lines 1–9 o Algo i hm A.2,(1)di ec P edecesso s =∅,(2)
indi ec P edecesso s =∅,and (3) allP edecesso s associa es each scheduling
ac i i y wi h all i s di ec p edecesso s (c . De ini ion 5.4) andasubse o i s
indi ec p edecesso s (c . De ini ion 5.5).
(b) A he end o Algo i hm A.2,as a esul o execu ing lines 10–15,∀ac ∈ac s :
(1) he map di ec P edecesso s associa es ac wi h exac ly all i s di ec p e-
decesso s (c . De ini ion 5.4),(2) he map indi ec P edecesso s associa es
ac wi h exac ly all i s indi ec p edecesso s (c . De ini ion 5.5),and (3) he
map allP edecesso s associa es ac wi h exac ly all i s di ec and indi ec
p edecesso s.
P oo .
(a) The s a emen s di ec P edecesso s =∅and indi ec P edecesso s =∅
hold since hese maps ha e been only ini ialized. On one hand, he map
allP edecesso s con ains all he di ec p edecesso s since all esou ce and Con-
Dec ela ions a e conside ed (lines 2–6 and 7–8, espec i ely). Mo eo e , some
indi ec p edecesso s ha e p obably been included since edundan connec ions
ha e no been a oided.
(b) (Ma hema ical Induc ion):
(i) The base case: Since ac s is a so ed se o de ed by s ,ac s1does no
ha e any p edecesso (i.e. allP edecesso s(ac s1)=∅). The e o e, a
he end o Algo i hm A.2, as a esul o execu ing lines 10–15:
(1) di ec P edecesso s(ac s1)=∅,(2)indi ec P edecesso s(ac s1)=∅,
and (3) allP edecesso s(ac s1)=∅, i.e. he s a emen holds o he base
case.
(ii) The induc i e s ep: I he s a emen holds ∀i∈1...n−1ac si, hen he s a e-
men also holds o ac sn.
(1) di ec P edecesso s(ac sn): in line 11, his se is ini ialized wi h all
he p ecedence ela ions o ac snwhichwe ep e iouslyob ainedin he
p e ious s ep un il line 8, i.e. all i s di ec p edecesso s and a subse o i s
indi ec p edecesso (c . P oposi ion A.1(a)). A e ha , o each di ec
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
p edecesso po ac sn(line 12), all he di ec and indi ec p edecesso s
o p, which a e he e o e indi ec p edecesso s o ac sn, a e emo ed
om he se di ec P edecesso s(ac sn) (line 13). Due o he induc ion
hypo hesis, he se allP edecesso s(p) is assumed o con ain all di ec
and indi ec p edecesso s o psince we a e assuming ha he s a emen
holds o ∀i∈1...n−1ac si(due o pis a p edecesso o ac snand ac s is
aso edse , hen∃i∈1...n−1|ac si=p).
(2) indi ec P edecesso s(ac sn): Fo each di ec p edecesso po ac sn
(line 12), all he di ec and indi ec p edecesso s o p,whicha e
he e o e indi ec p edecesso s o ac sn, a e included in he se
indi ec P edecesso s(ac sn) (line 14).
(3) allP edecesso s(ac sn): A e line 9, he se allP edecesso s(ac sn)
con ains all he di ec p edecesso s and a subse o indi ec p edecesso
o ac sn(c . P oposi ion A.1(a)). In o de o ensu e ha all indi ec
p edecesso s a e included, allP edecesso s(ac sn) is upda ed by con-
side ing all he indi ec p edecesso s (line 15).
Algo i hm A.3: includeP ed me hod o he b anched P ecedence em-
pla e wi h se e al sou ce ac i i ies and one sink ac i i y
inpu :MapP&SAc ,Se P&SAc  p ed
ou pu :MapP&SAc ,Se P&SAc  p ed
Se P&SAc mee ←{a1|a∈ his.sou ces, a1.e ≤ his.sink1.s };1
P&SAc sel ←a gmina∈mee (a.e );2
p ed( his.sink1)←p ed( his.sink1)∪sel;3
e u n p ed;4
Wi h espec o he includeP ed me hod, some ep esen a i e empla es a e
selec ed o illus a ion pu poses (o he empla es can be desc ibed in a simila
way). In Algo i hm A.3, he empla e ega ding he b anched P ecedence em-
pla e wi h se e al sou ce ac i i ies and one sink ac i i y (i.e. i is modeled by
a Cons ain Sou ces objec , c . Fig. A.1) is shown. The loca ion o a b anched
p ecedence empla e be ween se e al sou ces and one sink implies ha he fi s
execu ion o a leas one o he sou ces mus finished be o e he s a o he fi s
execu ion o he sink. In line 1, he se o scheduling ac i i ies which comply wi h
he P ecedence empla e (i.e. he fi s execu ions o he sou ces which end be o e
he s a o he fi s execu ion o he sink) a e included in he se mee .A leas
one scheduling ac i i y will be included in his se since he P ecedence empla e
is sa isfied, howe e i may be possible o find mo e han one. In o de o gene -
a e a BPMN model which is compa ible wi h bo h he op imized enac men plan
and he ConDec-R specifica ion, as is he pu pose o ou app oach, any scheduling
ac i i y o he se mee can be selec ed o be he p edecesso o he sink in he
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
BPMN model. One scheduling ac i i y o he se mee is hen selec ed o be he
p edecesso o he sink. Specifically, he scheduling ac i i y which p esen s mo e
slack is selec ed (line 2) in o de o cons uc a obus BPMN model. In line 3, he
selec ed p edecesso is included in he map, and is associa ed o he p edecesso s o
he fi s execu ion o he sink. The ac ha an ac i i y Bcan s a a e ano he
ac i i y Ahas finished (ES, de aul op ion), is s a ed by including Ain he se p ed
o B(line 3) o Algo i hm A.4.
Algo i hm A.4: includeP ed me hod o he b anched Al e na e
P ecedence Templa e wi h se e al sou ce ac i i ies and one sink ac i i y
inpu :MapP&SAc ,Se P&SAc  p ed
ou pu :MapP&SAc ,Se P&SAc  p ed
Se P&SAc mee ←{a1|a∈ his.sou ces, a1.e ≤ his.sink1.s };1
P&SAc sel ←a gmina∈mee (a.e );2
p ed( his.sink1)←p ed( his.sink1)∪sel;3
o each i in 2.. his.sink.n do4
Se P&SAc mee ←{aj|a∈ his.sou ces, j ∈5
1..a.n , his.sinki−1.e ≤aj.s ∧aj.e ≤ his.sinki.s };
P&SAc
6
sel ←a gmaxa∈mee ((a.s − his.sinki−1.e )+( his.sinki.s −a.e ));
p ed(sel)←p ed(sel)∪ his.sinki−1;7
p ed( his.sinki)←p ed( his.sinki)∪sel;8
e u n p ed;9
The b anched Al e na eP ecedence empla e be ween se e al sou ces and one
sink implies ha be o e he execu ion o he sink, a leas one o he sou ces mus be
execu ed, and be ween each wo execu ions o he sink, a leas one o he sou ces
mus be execu ed. As discussed, he e exis wo a ian s o he same empo al
ela ion, which a e ep esen ed by adding SS o ES a he end o he name o
he empla e. In he Al e na eP ecedence empla e, wo empo al ela ions mus
be indica ed: fi s , wha “sink be o e sou ce” means, and secondly, wha “sou ce
be o e sink” means. The e o e, he b anched empla e Al e na eP ecedenceES-ES
(de aul op ion) specifies ha “sink be o e sou ce” means ha he end ime o
he sink mus be less han o equal o he s a ime o he sou ce, and “sou ce
be o e sink” means ha he end ime o he sou ce mus be less han o equal o
he s a ime o he sink. The includeP ed me hod o he b anched empla e
Al e na eP ecedenceES-ES wi h se e al sou ce ac i i ies and one sink ac i i y
(i.e. i is modeled by a Cons ain Sou ces objec , c . Fig. A.1) is shown in Algo-
i hm A.4. Fo lines 1–3, he idea is he same as ha in Algo i hm A.3.Mo eo e ,
be ween each wo successi e execu ions o he sink, sinki−1 and sinki, one schedul-
ing ac i i y mus be execu ed. Se e al scheduling ac i i ies ela ed o he sou ces
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
can mee his condi ion (line 5). As be o e, he scheduling ac i i y which p esen s
mo e slack is selec ed (line 6) o be he p edecesso o sinki (line 8), and a he
same ime sinki−1 is selec ed as he p edecesso o he selec ed scheduling ac i i y.
Algo i hm A.5: includeP ed me hod o he b anched Al e na e
P ecedenceSS-ES Templa e wi h se e al sou ce ac i i ies and one sink ac i i y
inpu :MapP&SAc ,Se P&SAc  p ed
ou pu :MapP&SAc ,Se P&SAc  p ed
Se P&SAc mee ←{a1|a∈ his.sou ces, a1.e ≤ his.sink1.s };1
P&SAc sel ←a gmina∈mee (a.e );2
p ed( his.sink1)←p ed( his.sink1)∪sel;3
o each i in 2.. his.sink.n do4
Se P&SAc mee ←{aj|a∈ his.sou ces, j ∈5
1..a.n , his.sinki−1.s ≤aj.s ∧aj.e ≤ his.sinki.s };
P&SAc
6
sel ←a gmaxa∈mee ((a.s − his.sinki−1.e )+( his.sinki.s −a.e ));
p ed(sel)←p ed(sel)∪p ed( his.sinki−1);7
p ed( his.sinki)←p ed( his.sinki)∪sel;8
e u n p ed;9
In a simila way, he b anched empla e Al e na eP ecedenceSS-ES specifies
ha “sink be o e sou ce” means ha he s a ime o he sink mus be less han
o equal o he s a ime o he sou ce, and “sou ce be o e sink” means ha he
end ime o he sou ce mus be less han o equal o he s a ime o he sink.
The includeP ed me hod o he b anched empla e Al e na eP ecedenceSS-ES
wi h se e al sou ce ac i i ies and one sink ac i i y (i.e. i is modelled by a
Cons ain Sou ces objec , c . Fig. A.1) is shown in Algo i hm A.5. This algo i hm
is iden ical o Algo i hm A.4, excep o line 7. As men ioned ea lie , he ac ha
an ac i i y B can s a a e ano he ac i i y A has finished (ES, de aul op ion), is
s a ed by including A in he se p ed o B. Addi ionally, he ac ha an ac i i y B
can only s a a e ano he ac i i y A has s a ed, label SS, is s a ed by including
he se p ed(A)in hese p ed o B, as can be seen in line 7 o Algo i hm A.5.
The complexi y analysis o all he algo i hms p e iously desc ibed is included in
A.1, and he equi alence be ween he defini ions gi en in Sec. 5 and he algo i hms
included in his sec ion is de ailed in A.2.
A.1. Complexi y analysis
This sec ion p esen s he complexi y analysis o he algo i hms p e iously desc ibed.
P oposi ion A.2. I implemen ed p ope ly, he wo s -case ime complexi y o Algo-
i hm A.3 is O(n), whe e n is he numbe o Repea ed Ac i i ies o he p oblem.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
P oo . The wo s -case ime complexi y o line 1 is O(n), since #sou ces ≤ n.
The wo s -case ime complexi y o line 2 is also O(n), since #mee ≤ n.The
ime complexi y o line 3 is cons an . The e o e, he wo s -case ime complexi y o
Algo i hm A.3 is O(n)+O(n) + Θ(1), equal o O(n).
P oposi ion A.3. I implemen ed p ope ly, he wo s -case ime complexi y o Algo-
i hms A.4 and A.5 is O(n × n ), whe e n is he numbe o Repea ed Ac i i ies o
he p oblem, and n is he maximum numbe o imes ha a epea ed ac i i y is
execu ed.
P oo . The wo s -case ime complexi y o line 1 is O(n), since #sou ces ≤ n.
The wo s -case ime complexi y o line 2 is also O(n), since #mee ≤ n.The ime
complexi y o line 3 is cons an . The wo s -case ime complexi y o lines 4–8 is
O(n × n ) since lines 5–7 (wi h complexi y O(n) om he p oo o P oposi ion A.1)
a e execu ed a mos n imes. The e o e, he wo s -case ime complexi y o Algo-
i hms A.4 and A.5 is O(n)+O(n)+Θ(1)+ O(n × n )equal o O(n × n ).
P oposi ion A.4. I implemen ed p ope ly, he wo s -case ime complexi y o Algo-
i hm A.2 is O(c×n×n +nps2), whe e n is he numbe o Repea ed Ac i i ies o he
p oblem,n is he maximum numbe o imes ha a epea ed ac i i y is execu ed,c
is he numbe o cons ain s ha appea in he de ini ion o he p oblem, and nps
is he numbe o scheduling ac i i ies in he op imized plan.
P oo . The ime complexi y o lines 1–5 is Θ(nps), since each scheduling ac i i y
is conside ed exac ly once (each ac i i y uses a specific esou ce o a specific ole).
The wo s -case ime complexi y o lines 6 and 7 is O(c×n×n ), since he wo s -case
ime complexi y o he me hod includeP ed is O(n×n ) (P oposi ion A.2), and his
me hod is in oked c imes. The wo s -case ime complexi y o lines 9–12 is O(nps2),
since o each scheduling ac i i y, i s p edecesso s (a mos , nps) a e conside ed.
The e o e, he wo s -case ime complexi y o Algo i hm A.2 is O(c ×n× n + nps2).
P oposi ion A.5. I implemen ed p ope ly, he wo s -case ime complexi y o Algo-
i hm A.1 is O(c×n×n +nps2), whe e n is he numbe o Repea ed Ac i i ies o he
p oblem,n is he maximum numbe o imes ha a epea ed ac i i y is execu ed,c
is he numbe o cons ain s ha appea in he de ini ion o he p oblem, and nps
is he numbe o scheduling ac i i ies in he op imized plan.
P oo . The wo s -case ime complexi y o line 1 is O(c ×n× n + nps2), by P opo-
si ion A.3. The wo s -case ime complexi y o line 3 is O(n), since # ole ≤ n.The
ime complexi y o line 4 is Θ(nps). The wo s -case ime complexi y o lines 6 and
15 is O(nps). The ime complexi y o lines 7–13 is Θ(nps). The e o e, he wo s -case
ime complexi y o Algo i hm A.1 is O(c × n × n + nps2).

2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
A.2. Equi alence be ween de ini ions in Sec. 5and
algo i hms in Appendix A
The defini ions which appea in Sec. 5define he gene a ion o BPMN models om
a o mal poin o iew, while he algo i hms in he appendix desc ibe he same
gene a ion om an implemen a ion poin o iew (e.g. some in o ma ion has been
duplica ed and o de ed in a diffe en way o acili a e he implemen a ion). The e-
o e, he ypes used in he appendix a e no exac ly he same han he defini ions
gi en h oughou he pape . Howe e , bo h Defini ion 5.6 and Algo i hm A.1 gen-
e a e he same BPMN model om he same inpu ConDec-R model and om he
same solu ion, as explained in he ollowing.
Rega ding he inpu pa ame e s: (1) Defini ion 5.6 includes (i) a ConDec-R
p ocess model CR =(Ac s,CBP,Res) and (ii) a solu ion S o a CSP-ConDec
p oblem as inpu pa ame e s, while (2) Algo i hm A.1 includes (i) a so ed se o
objec s o ype P&SAc , ac s, o de ed by s ; (ii) a se o objec s o ype Cons ain ,
c; (iii) and a se o objec s o ype Role, . The inpu pa ame e s o Algo i hm A.1
can be ob ained om he inpu pa ame e s o Defini ion 5.6 as ollows:
• he in o ma ion o each P&SAc aiin ac s (i.e. s ,e and es, c . UML diag am
o Fig. 12) is aken so ha ai·s =Ss (ai),ai·e =Se (ai),ai· es =S es(ai)
(i.e. om he CSP a iables which a e ela ed o he scheduling ac i i y aiin he
solu ion o he CSP-ConDec p oblem, c . Defini ion 4.3).
•c=CBP, i.e. he se o objec s o ype Cons ain , c, con ains he same cons ain s
which a e included in he ConDec-R model.
• ={ ole, ( ole, # ole)∈Res, ole. esou ces ={ esk,k ∈[1 ...# ole], es
k·
ac s ={ai∈ac s, ai· es = esk}}}, i.e. he e is one objec o ype Role in
o each ole in Res. Mo eo e , o each objec o ype Role ole, he ea e
# ole objec s o ype Resou ce in he lis esou ces o ole. Each objec o ype
Resou ce eskcon ains, in u n, an o de ed lis o objec s o ype P&SAc which
a e ela ed o he P&S ac i i ies which a e alloca ed in ha esou ce.
Fu he mo e, he equi alence be ween Defini ion 5.6 and Algo i hm A.1 is
de ailed as ollows:
•(1) in Defini ion 5.6 is equi alen o line 2 in Algo i hm A.1, i.e. bo h include a
pool o each ole in he esul ing BPMN model.
•(2) in Defini ion 5.6 is equi alen o lines 3–5 in Algo i hm A.1, i.e. bo h include a
BPMN ac i i y o each BP ac i i y, plus one ac i i y ela ed o he s a BPMN
ac i i y, plus one ac i i y ela ed o he end BPMN ac i i y.
•(3) in Defini ion 5.6 is equi alen o lines 6–20 in Algo i hm A.1. The se
p edecesso s in Defini ion 5.6 (c . (3)) s a es he di ec p ecedences be ween
all he ac i i ies, including: he p ecedences be ween he P&S ac i i ies, and he
p ecedences in which he BPMN s a and end ac i i ies a e in ol ed. Howe e ,
in Algo i hm A.1, he p ecedences in which he BPMN s a and end ac i i ies
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
a e in ol ed a e handled diffe en ly om he es o ac i i ies due o implemen-
a ion easons. The equi alence be ween (3) in Defini ion 5.6 and lines 6–20 in
Algo i hm A.1 is explained as ollows:
— (3)(i) in combina ion wi h (3)(a) in Defini ion 5.6 is equi alen o line
6 in Algo i hm A.1, i.e. bo h include sequence flows be ween he BPMN
s a ac i i y and all he ac i i ies whose s a ime is equal o 0 (i.e. a e
di ec successo s o he s a ac i i y). Specifically, in (3)(i) all he p ece-
dence ela ions in which he s a ac i i y is in ol ed a e included in he se
P edecesso s, and in (3)(a) sequence flows be ween he s a ac i i y and all
i s di ec successo s a e included. Howe e , in Algo i hm A.1, hese sequence
flows a e di ec ly included in line 6. No e ha he s a ac i i y is ne e
in ol ed in pa allel me ging ga eways since his ac i i y does no ha e any
p edecesso .
— (3)(ii) in combina ion wi h (3)(a) and 3(b) in Defini ion 5.6 is equi alen o
lines 15–20 in Algo i hm A.1, i.e. bo h include ei he a sequence flow o a
pa allel me ging ga eway be ween he BPMN end ac i i y and all i s di ec
p edecesso s. Specifically, in (3)(ii) all he p ecedence ela ions in which he
end ac i i y is in ol ed a e included in he se P edecesso s. In a simila way,
in line 15 o Algo i hm A.1, all he di ec p edecesso s o he end ac i i y a e
s o ed in he se finals. Then, i he e is only one di ec p edecesso o he
end ac i i y, a sequence flow be ween his p edecesso and he end ac i i y
is included (lines 16–18 in Algo i hm A.1, (3)(a) in Defini ion 5.6). Howe e ,
i he e a e mo e han one di ec p edecesso o he end ac i i y, a pa allel
me ging ga eway be ween all p edecesso s and he end ac i i y is included
(lines 19 and 20 in Algo i hm A.1, (3)(b) in Defini ion 5.6). No e ha he
end ac i i y may be in ol ed in pa allel me ging ga eways since his ac i i y
may ha e mo e han one p edecesso .
— (3)(iii) in combina ion wi h (3)(a) and 3(b) in Defini ion 5.6 is equi alen
o lines 7–14 in Algo i hm A.1, i.e. bo h include ei he a sequence flow o
a pa allel me ging ga eway be ween each ac i i y and all i s di ec p ede-
cesso s. Specifically, in (3)(iii) all he p ecedence ela ions in which each
ac i i y is in ol ed a e included in he se P edecesso s. In a simila way,
in line 7 o Algo i hm A.1, all he di ec p edecesso s o each ac i i y a e
s o ed in he map p ed. Fo his, Algo i hm A.2 (i.e. C ea eDependencies)
is used. Algo i hm A.2 is equi alen o (3)(iii) since, as demons a ed in
P oposi ion A.1, Algo i hm A.2 e u ns a map which ela es each ac i i y
wi h i s di ec p edecesso s (c . Defini ion 5.4). Then, o each ac i i y (line
8 in Algo i hm A.1) i he e is only one di ec p edecesso o ha ac i i y, a
sequence flow be ween his p edecesso and he ac i i y is included (lines 9–11
in Algo i hm A.1, (3)(a) in Defini ion 5.6). Howe e , i he e a e mo e han
one di ec p edecesso o ha ac i i y, a pa allel me ging ga eway be ween
all i s p edecesso s and he ac i i y is included (lines 12–14 in Algo i hm A.1,
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
(3)(b) in Defini ion 5.6). No e ha each ac i i y may be in ol ed in pa allel
me ging ga eways, since i may ha e mo e han one p edecesso .
Re e ences
1. M. Weske, Business P ocess Managemen : Concep s, Languages A chi ec u es
(Sp inge , Be lin, Ge many, 2007).
2. M. Dumas, W. an de Aals and A. e Ho s ede, P ocess-Awa e In o ma ion Sys-
ems: B idging People and So wa e Th ough P ocess Technology (Wiley-In e science,
Hoboken, NJ, 2005).
3. G. G oup, Leading in Times o T ansi ion: The 2010 CIO Agenda (EXP P emie
Repo No. Janua y 2010), in Repo ,Ga ne ,Inc(2010).
4. W. an de Aals , A. e Ho s ede and M. Weske, Business p ocess managemen : A
su ey, in P oc. BPM (2003), pp. 1–12.
5. R. Aguila -Sa ´en, Business p ocess modelling: Re iew and amewo k, In . J. P od.
Econom. 90(2) (2004) 129–149.
6. J. Ba jis and A. Ve b aeck, The ele ance o modeling and simula ion in en e p ise
and o ganiza ional s udy, in P oc. EOMAS (2010), pp. 15–26.
7. H. Reije s, Design and Con ol o Wo k low P ocesses (Sp inge -Ve lag Be lin,
Heidelbe g, 2003).
8. N. Russell, W. an de Aals , A. e Ho s ede and D. Edmond, Wo kflow esou ce
pa e ns: Iden ifica ion, ep esen a ion and ool suppo , in P oc. CAiSE (2005),
pp. 216–232.
9. H. M. Fe ei a and D. R. Fe ei a, An in eg a ed li e cycle o wo kflow manage-
men based on lea ning and planning, In . J. Coop. In o m. Sys . 15(4) (2006)
485–505.
10. J. Waine , F. Beze a and P. Ba helmess, Tucupi: A flexible wo kflow sys em based
on o e idable cons ain s, in P oc. SAC (2004), pp. 498–502.
11. M. Pesic, M. Schonenbe g, N. Sido o a and W. an de Aals , Cons ain -based wo k-
flow models: Change made easy, in OTM Con e ences (1) (2007), pp. 77–94.
12. I. Rychko a, G. Rege and A. Wegmann, High-le el design and analysis o busi-
ness p ocesses: The ad an ages o decla a i e specifica ions, in P oc. RCIS (2008),
pp. 99–110.
13. D. Fahland, D. L¨ubke, J. Mendling, H. Reije s, B. Webe , M. Weidlich and S. Zugal,
Decla a i e e sus impe a i e p ocess modeling languages: The issue o unde s and-
abili y, in P oc. BPMDS and EMMSAD (2009), pp. 353–366.
14. D. Fahland, J. Mendling, H. Reije s, B. Webe , M. Weidlich and S. Zugal, Decla a i e
e sus impe a i e p ocess modeling languages: The issue o main ainabili y, in P oc.
BPM Wo kshops (2010), pp. 477–488.
15. P. Pichle , B. Webe , S. Zugal, J. Pingge a, J. Mendling and H. Reije s, Impe a i e
e sus decla a i e p ocess modeling languages: An empi ical in es iga ion, in P oc.
ER-BPM (2011), pp. 383–394.
16. M. Ghallab, D. Nau and P. T a e so, Au oma ed Planning: Theo y and P ac ice (Mo -
gan Kau mann, Ams e dam, 2004).
17. P. B ucke and S. Knus , Complex Scheduling (GOR-Publica ions) (Sp inge -Ve lag,
New Yo k, Inc., Secaucus, NJ, USA, 2006).
18. F. Rossi, P. an Beek and T. Walsh (eds.), Handbook o Cons ain P og amming
(Else ie , New Yo k, USA, 2006).
19. M. Salido, In oduc ion o planning, scheduling and cons ain sa is ac ion, J. In ell.
Manu . 21(1) (2010) 1–4.
2nd Reading
Oc obe 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009
20. Business P ocess Model and No a ion (BPMN), Ve sion 2.0., h p://www.omg.o g/
spec/BPMN/2.0/ (2011) [Online; accessed 3-Oc obe -2011].
21. C. Ouyang, W. an de Aals , M. Dumas and A. e Ho s ede, T ansla ing BPMN o
BPEL (2006).
22. Web Se ices Business P ocess Execu ion Language Ve sion 2.0: OASIS S anda d,
h p://docs.oasis-open.o g/wsbpel/2.0/wsbpel- 2.0.h ml (2007) [Online; accessed 3-
Oc obe -2011].
23. M. Reiche and B. Webe , Enabling Flexibili y in P ocess-Awa e In o ma ion Sys ems
(Sp inge , 2012).
24. M. Pesic and W. an de Aals , A decla a i e app oach o flexible business p ocesses
managemen , in P oc. BPM Wo kshops (2006), pp. 169–180.
25. W. an de Aals , M. Pesic and H. Schonenbe g, Decla a i e wo kflows: Balancing
be ween flexibili y and suppo , Compu . Sci. — Res. De elop. 23(2) (2009) 99–113.
26. M. Mon ali, Specifica ion and e ifica ion o decla a i e open in e ac ion models: A
logic-based app oach, Ph.D. hesis, Depa men o Elec onics, Compu e Science and
Telecommunica ions Enginee ing, Uni e si y o Bologna, 2009.
27. P. Dou ish, J. Holmes, A. MacLean, P. Ma q a dsen and A. Zbyslaw, F eeflow: Medi-
a ing be ween ep esen a ion and ac ion in wo kflow sys ems, in P oc. CSCW (1996),
pp. 190–198.
28. J. Waine and F. De Lima Beze a, Cons ain -based flexible wo kflows, in P oc.
CRIWG (2003), pp. 151–158.
29. R. Lu, S. Sadiq, V. Padmanabhan and G. Go e na o i, Using a empo al cons ain
ne wo k o business p ocess execu ion, in P oc. ADC (2006), pp. 157–166.
30. W. M. P. an de Aals and M. Pesic, DecSe Flow: Towa ds a T uly Decla a i e
Se ice Flow Language, in LNCS 4184 (2006), pp. 1–23.
31. I. Ba ba and C. Del Valle, A cons ain -based app oach o planning and scheduling
epea ed ac i i ies, in P oc. COPLAS (2011), pp. 55–62 [Online; h p://icaps11.icaps-
con e ence.o g/p oceedings/coplas/coplas2011-p oceedings.pd ; accessed 3-Oc obe -
2011].
32. Decla e, h p://www.win. ue.nl/decla e/ (2013) [Online; accessed 11-Feb ua y-2013].
33. J. F. Allen, Main aining knowledge abou empo al in e als, in Communica ions o
he ACM (1983), pp. 832–843.
34. I. Ba ba and C. Del Valle, Fil e ing Rules o ConDec Templa es — Pseudocode
and Complexi y, h p://www.lsi.us.es/∼qui i /i ene/Fil e ingRules o ConDec Tem-
pla es.pd (2011) [Online; accessed 3-Oc obe -2011].
35. M. R. Ga ey and D. S. Johnson, Compu e s and In ac abili y: A Guide o he Theo y
o NP-Comple eness (W. H. F eeman & Co., New Yo k, NY, USA, 1979).
36. C. Cou bis and A. Finkels ein, Wea ing aspec s in o web se ice o ches a ions, in
P oc. ICWS 2005 (2005), pp. 219–226.
37. S. Zugal, P. Soffe , J. Pingge a and B. Webe , Exp essi eness and unde s and-
abili y conside a ions o hie a chy in decla a i e business p ocess models, in P oc.
BMMDS/EMMSAD 2012 (2012), pp. 167–181.
38. M. La Rosa, M. Dumas, R. Uba and R. Dijkman, Me ging business p ocess models,
in P oc. OTM, Vol. 6426(1) (2010), pp. 96–113.
39. W. Nuij en and E. Aa s, Sequencing wi h ea liness and a diness penal ies: A e iew,
Eu . J. Ope . Res. 90(2) (1996) 269–284.
40. A is aFlow BPM Sui e BPM09-Demo, h p://www.uni-ulm.de/ein ich ungen/a is a
flow- o um/sc eencas s.h ml (2009) [Online; accessed 05-Feb ua y-2013].
41. R. Bellman, Dynamic P og amming (P ince on Uni e si y P ess, P ince on, NJ,
1957).