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

2nd Reading October 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† Dpto. Lenguajes y Sistemas Inform´aticos University of Seville, Avda Reina Mercedes s/n Seville, 41012, Spain ∗ir[email protected] †[email protected] BARBARA WEBER Department of Computer Science University of Innsbruck, Technikerstraße 21a Innsbruck, 6020, Austria [email protected] ANDR´ES JIM´ENEZ Dpto. Lenguajes y Sistemas Inform´aticos University of Seville, Avda Reina Mercedes s/n Seville, 41012, Spain [email protected] Business process (BP) models are usually defined manually by business analysts through imperative languages considering activity properties, constraints imposed on the rela-tions between the activities as well as different performance objectives. Furthermore, allocating resources is an additional challenge since scheduling may significantly impact BP performance. Therefore, the manual specification of BP models can be very com-plex and time-consuming, potentially leading to non-optimized models or even errors. To overcome these problems, this work proposes the automatic generation of imperative optimized BP models from declarative specifications. The static part of these declara-tive specifications (i.e. control-flow and resource constraints) is expected to be useful on a longterm basis. This static part is complemented with information that is less stable and which is potentially unknown until starting the BP execution, i.e. estimates related to (1) number of process instances which are being executed within a particular timeframe, (2) activity durations, and (3) resource availabilities. Unlike conventional proposals, an imperative BP model optimizing a set of instances is created and deployed on a short-term basis. To provide for run-time flexibility the proposed approach addition-ally allows decisions to be deferred to run-time by using complex late-planning activities, and the imperative BP model to be dynamically adapted during run-time using replan-ning. To validate the proposed approach, different performance measures for a set of ∗Corresponding author. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 test models of varying complexity are analyzed. The results indicate that, despite the NP-hard complexity of the problems, a satisfactory number of suitable solutions can be produced. Keywords: Business process management; constraint programming; planning; scheduling. 1. Introduction A business process (BP) consists of a set of activities which are performed in coordination in an organizational and technical environment,1 and which jointly realize a business goal. Nowadays, there exists a growing interest in aligning information systems in a process-oriented way1,2 as well as in the effective management of BPs. BP improvement has been ranked as the number one priority for top management by the 2010 Gartner survey.3 BP management (BPM) can be seen as supporting BPs using methods, techniques, and software in order to design, enact, control, and analyze operational processes involving humans, organizations, applications, and other sources of information.4 Typically, the traditional BPM life cycle1 includes several phases: Process Design & Analysis, system configuration, process enactment and evaluation. The BP Design & Analysis phase has the goal to generate a BP model, i.e. to define the set of activities and the execution constraints between them,1 by formalizing the informal BP description using a particular BP modeling notation. The Process Design & Analysis phase plays an important role in the BPM life cycle for any improvement initiative, since it greatly influences the remaining phases of this cycle. In addition, also run-time aspects are important for BP improvement, e.g. resource allocations and scheduling may significantly impact BP performance. 1.1. Problem statement Traditionally, two steps are considered in the BP Design & Analysis phase to create aBPmodel.5 The first step consists of analyzing the BP, e.g. by interviewing stakeholders (people involved in the process), in order to draw an initial BP model (as-is model). Second, in order to improve this initial model, different techniques can be employed like simulation6 or BP redesign,7 resulting in the generation of a to-be model. Typically, different quality dimensions like time, cost, flexibility and quality can be differentiated7 between which trade-off decisions have to be made when creating a BP design. Once a certain process design has been chosen and implemented, BPs are executed according to this design.a During process execution, scheduling decisions are then typically made by the BPM systems (BPMSs), by automatically assigning activities to resources.8 aIn this work, we make the assumption that there is a BPM system executing the BPs. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 In most cases, the overall process of creating a BP model is carried out manually by business analysts, who specify the BP information through an imperative language by choosing between several different alternative designs the one which best meets the performance goals of the organization. Therefore, analysts must deal with several aspects in order to generate a suitable BP model, such as: (1) the activity properties, e.g. activity duration, resource or role which is required for activity execution (i.e. the role-based allocation pattern is considered8), (2) the relations between the activities, i.e. control-flow of the BP, and (3) the optimization of several objectives, e.g. minimization of completion time. The manual specification of imperative BP models can therefore form a very complex problem, i.e. it can consume a great quantity of time and human resources, may cause certain failures, and may lead to non-optimized models since the tacit nature of human knowledge is often an obstacle to eliciting accurate process models.9 Not only the process design, but also the allocation of resources during process execution has a great influence on process performance. However, scheduling is only considered to a limited degree in existing BPMSs, and is typically done during run-time by assigning work to resources. The situation is further complicated by the fact that typically multiple instances of a process get concurrently executed within a particular timeframe. In order to ensure that the execution of a process is not only locally optimized for a single instance, the whole set of instances whichareexecutedwithina particulartimeframe has to be considered. 1.2. Contribution To support process analysts in the definition of optimized BP models we suggest a method for automatically generating imperative BP models using artificial intelligence (AI) planning techniques from constraint-based specifications. Unlike imperative models, the specification of process properties in a declarative way, e.g. using a constraint-based specification, only requires process designers to state what has to be done instead of having to specify how it has to be done.b In the proposed approach, the static part of the input declarative model (i.e. control-flow and resource constraints) is expected to be useful on a long-term basis since it embraces information which is not supposed to change often. The base declarative model (i.e. only including the static part) is complemented with information that is less stable and which is potentially unknown until starting the BP execution, i.e. estimates related to (1) number of process instances which are being executed within a particular timeframe, (2) activity durations, and (3) resource availabilities. From this extended model, the proposed approach is in charge of determining how bThe advantages of using declarative languages for BP modeling instead of imperative languages, e.g. facilitating the human work involved in the BP modeling, are discussed in several studies, e.g. Refs. 10–15. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 to satisfy the constraints imposed by the declarative specification and at the same time to attain an optimization of certain objective functions (e.g. minimization of completion time). For this optimization, scheduling is done on a short-term basis by considering the optimization of a set of instances. Unlike conventional proposals, in our approach each generated model is created and deployed for a specific planning period, considering changing information such as the number of process instances which are being executed within a specific timeframe. For the next executions of the declarative model, new models will be generated considering the specific values which are given for the changing information. Since planning is done on a short-term basis, the generated models are less prone to change. Figure 1 provides an overview of our approach. Taking the constraint-based specifications as a starting point (cf. Fig. 1(1)), enactment plans can automatically be generated (cf. Fig. 1(2)). For this, activities to be executed have to be selected and ordered (planning problem16) considering the control-flow imposed by the constraint-based specification. Moreover, to automatically propose execution plans which meet the performance goals best (e.g. minimizing the overall completion time (OCT), i.e. time needed to complete all process instances which were planned for a certain period), the constraint-based model is complemented with information related to estimates regarding the number of instances, activity durations, and resource availabilities (scheduling problem17). For planning and scheduling (P&S) the activities such that the process objective function is optimized, a constraint-based approach is proposed since constraint programming18 supplies a suitable framework for modeling and solving problems involving P&S aspects.19 The generated enactment plans are then automatically translated into a Business Process Model and Notation (BPMN) model20 (cf. Fig. 1(3)), which can be then further improved by a business analyst, where necessary. In most cases, BPMN models can be translated into an execution language,21 such as BPEL,22 which enables BP designs to be deployed into BPMS and let their instances be executed by a BPM engine. To provide for an increased flexibility the BPMN model can be dynamically adapted during run-time by using replanning (cf. Fig. 1(4)). Note that the BPMN model is generated with the goal of making the declarative model automatically executable by a BPMS by considering the specific values of the changing information which are given just before starting the execution the Fig. 1. AI P&S techniques for the generation of optimized BP models. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 process. In this way, application of decision deferral patterns is automated,23 i.e. the role of the BPMS is rather focused on enabling control and ensuring compliance (decisions are automatically made by the BPMS). Regarding decision deferral patterns, our approach belongs to the late modeling and composition pattern, i.e. allowing for modeling and automatic composition of a process model just before starting the execution of a branch of process instances. Therefore, our approach can be framed within dynamic process-based composition (i.e. completely creating the executable process model dynamically at run-time), which constitutes an example of the automated variant of the late modeling and composition pattern. The main contributions of this paper can be summarized as follows: (i) The definition of a language for the constraint-based specification of BPs which extends ConDec,11,24 named ConDec-R (cf. Sec. 3,Step1inFig.1), to enable the reasoning about resources. (ii) Automatic planning and scheduling of the BP activities for the generation of optimized BP enactment plans from the ConDec-R specifications, through a constraint-based approach (cf. Sec. 4,Step2inFig.1). (iii) Automatic generation of optimized BP models in BPMN from optimized BP enactment plans (cf. Sec. 5,Step3inFig.1). (iv) Providing for run-time flexibility by allowing decisions to be deferred at runtime and the BPMN model to be dynamically adapted during run-time (cf. Sec. 6,Step4inFig.1). (v) Validation of the proposed approach through the analysis of different performance measures related to a range of test models of varying complexity (cf. Sec. 8). In this way, the automatic generation of BP models simplifies the BP design phase by facilitating the human work in most cases, preventing failures in the developed BP models, and enabling better optimization to be attained in the enactment phase. Furthermore, imperative BP models can dynamically be generated from static constraint-based specifications just before starting the BP enactment, once some values for the enactment parameters, e.g. resource availabilities, are known. Moreover, the automatic generation of BP models can deal with complex problems of great size in a simple way (as will be demonstrated in Sec. 8). Therefore, a wide study of several aspects can be carried out, such as those related to the requirement of resources of different roles, or the estimated completion time for the BP enactment, by generating several kinds of alternative specifications. In addition, in order to address run-time flexibility the proposed approach allows decisions to be deferred at run-time by using complex late-planning activities, and the BPMN model to be dynamically adapted during run-time using replanning. The remainder of this paper is organized as follows: Sec. 2 introduces backgrounds needed for the further understanding of the paper, Secs. 3–6 detail the proposals of this work, Sec. 7 explains an example, Sec. 8 deals with the evaluation 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 of the proposed approach, Sec. 9 summarizes related work, Sec. 10 presents a critical discussion of the advantages and limitations of our proposal, and finally, Sec. 11 includes some conclusions and future work. 2. Background Our work combines aspects of scheduling, planning, and constraint programming in order to automatically generate optimized BP enactment plans from constraintbased specifications. The optimized enactment plans are then translated into BPMN models. Section 2.1 provides backgrounds regarding constraint-based processes. Section 2.2 gives an overview of planning, scheduling, and constraint programming. Section 2.3 summarizes the BPMN standard. 2.1. Constraint-based BP models Different paradigms for process modeling exist, e.g. imperative and declarative. Irrespective of the chosen approach, desired behavior must be supported by the process model, while forbidden behavior must be prohibited.11,25,26 While imperative process models specify exactly how things have to be done, declarative process models focus on what should be done. In literature, several rule-based and constraint-based languages for declarative BP modeling are proposed (e.g. Refs. 11, 24, 27–29). In our proposal we use ConDec11,24 for the BP control-flow specification. We consider ConDec to be a suitable language, since it allows the specification of BP activities together with the constraints which must be satisfied for correct BP enactment and for the goal to be achieved. Moreover, ConDec allows to specify a wide set of BP models in a simple and flexible way. ConDec is based on constraint-based BP models (cf. Definition 2.1), i.e. including information about (1) activities that can be performed as well as (2) constraints prohibiting undesired process behavior. Definition 2.1. A constraint-based process model S =(A, CBP) consists of a set of activities A, and a set of constraints CBP prohibiting undesired execution behavior. For each activity a ∈ A resource constraints can be specified by associating a role with that activity. The activities of a constraint-based process model can be executed arbitrarily often if not restricted by any constraints. Constraints can be added to a ConDec model to specify forbidden behavior, restricting the desired behavior. For this, ConDec proposes an open set of templates, i.e. parametrized graphical representations of constraints over the BP activities, which can be divided into three groups (for a description of the complete set of templates, cf. Ref. 30): (i) Existence templates: Unary relationships concerning the number of times one activity is executed. As an example, Exactly(N,A) specifies that Amust be executed exactly Ntimes. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 (ii) Relation templates: Positive binary relationships used to establish what should be executed. As an example, Precedence(A, B) specifies that to execute activity B, activity Aneeds to be executed before. (iii) Negation templates: Negative binary relationships used to forbid the execution of activities in specific situations. As an example, NotCoexistence(A, B) specifies that if Bis executed, then Acannot be executed, and vice versa. While unary relationships describe constraints related to one activity (e.g. existence constraints), binary constraints describe relationships between activities (e.g. precedence constraints). Binary templates are composed by a source activity (cf. Definition 2.2) and a sink activity (cf. Definition 2.3). Definition 2.2. A source activity of a binary template is an activity which appears in the first parameter of the template. For templates which state precedence relations between activities, a source activity is a predecessor activity. Definition 2.3. A sink activity of a binary template is an activity which appears in the second parameter of the template. For templates which state precedence relations between activities, a sink activity is a successor activity. Figure 2shows a simple constraint-based model which is composed by activities A,B,andC, and constraints C1 (Exactly(2, A)), C2 (Precedence(A, B)), C3 (Precedence(A, C)), and C4 (NotCoexistence(B,C)). Furthermore, binary templates can be extended by defining branched templates, as described in Ref. 26. The branched templates for the binary templates can be established between several BP activities in the following way: •The branched template is established between several source activities and one sink activity, so that the relation is given between at least one of the sources and the sink. Fig. 2. Simple constraint-based model. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 •The branched template is established between one source activity and several sink activities, so that the relation is given between the source and at least one of the sinks. As the execution of a constraint-based model proceeds, information regarding the executed activities is recorded in an execution trace (cf. Definition 2.4). Definition 2.4. Let S=(A, CBP) be a constraint-based process model with activity set Aand constraint set CBP. Then: A trace σis composed by a sequence of starting and completing events e1,e 2,...,e nregarding activity executions ai, a∈A, i.e. events can be: (i) start(ai,r jk,t), i.e. the i-th execution of activity ausing k-thresourcewithrole jis started at time t. (ii) comp(ai,t), i.e. the i-th execution of activity ais completed at time t. Due to their flexible nature, frequently several ways to execute constraint-based process models exist, i.e. everything which is enabled can be executed. The decisions related to which of the enabled activities to execute and in what order can be made using several mechanisms23: •Goal-based: Decisions between alternatives (selection of a particular process fragment, actor, or activity implementation) are made considering the overall goals (cf. Definition 2.5) of the process. Definition 2.5. The goal of a BP is specified through the constraints which must be satisfied in the BP enactment. For example, tracescAABand AACare two valid ways of executing the constraint-based model of Fig. 2, while trace AABCis invalid due to C4. The different valid execution alternatives, however, can vary greatly in respect to their quality, i.e. how well different performance objective functions (cf. Definition 2.6) like minimizing cycle time can be achieved. Optimization decisions can be framed as goal-based decisions (i.e. there alternatives to reach a specific goal and the optimization of given objective functions should be considered to select one of these alternatives). Definition 2.6. The objective function of a BP is the function to be optimized during the BP enactment, e.g. minimization of OCT. •Rule-based: Decisions between different alternatives are made based on a set of rules. cFor the sake of clarity, traces represent sequences of activities so that no parallelism is considered in the examples. Moreover, only completed events for activity executions are included in the trace representation. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 •Experienced-based: Decisions between different alternatives are made by relying on past experiences made in similar context. •User-based: Decisions between different alternatives are made by leaving decision making to the human expert. In our base proposal, we consider all the choice-like constructs of ConDec as optimization or goal decisions, i.e. decision making is goal-based. Assuming that all decisions are goal-based, the base approach might be valid for some environments like for example certain web service settings. If more flexibility is required, in Sec. 6.1 we propose an approach that allows decisions which are not goal-based to be deferred to run-time and enables the optimization within decision fragments which frame non-goal-based decisions. Moreover, to provide for an increased runtime flexibility, there is the possibility to use replanning (cf. Sec. 6.2). 2.2. Planning, scheduling and constraint programming For generating optimized BP enactment plans optimizing the performance objective functions (cf. Definition 2.6) of constraint-based process models, activities to be executed have to be planned16 and scheduled17 by considering the constraint-based specification. To do this, a constraint-based approach is proposed.19 The area of scheduling17 includes problems in which it is necessary to determine an enactment plan for a set of activities related by temporal constraints (in our context the control-flow constraints together with the resource constraints, i.e. required resources, introduced in Sec. 2.1). Moreover, since the execution of activities may require the same resources, they may compete for limited resources. In general, the objective in scheduling is to find a feasible plan which satisfies both temporal and resource constraints. Several objective functions are usually considered to be optimized, in most cases related to temporal measures (e.g. minimization of completion time), or considering the optimal use of resources. In a wider perspective, in AI planning,16 the activities to be executed are not established apriori, hence it is necessary to select them from a set of alternatives and to establish an ordering. In most cases, the specification of planning problems includes the initial state of the world, the goal (a predicate representing a set of possible final states) that must be reached, and a set of operators (actions) which can be applied to one state in order to reach another state. Furthermore, in planning problems, usually the optimization of certain objective functions is considered. Constraint programming (CP)18 (cf. Fig. 3) can be used, among others, for planning and scheduling purposes.19 In order to solve a problem through constraint programming, it needs to be modeled as a constraint satisfaction problem (CSP) (cf. Definition 2.7). Definition 2.7. A CSP P =(V, D, CCSP) is composed by a set of variables V , aset of domains D, which is composed of the domain of values domi for each variable vari ∈ V , and a set of constraints CCSP between variables, so that each 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 constraint is added to the CSP model, i.e. Existence(2,A), P recedence(A, B), P recedence(A, C), and NotCoexistence(B, C) for the constraint-based model depicted in Fig. 5. Definition 4.3. A CSP-ConDec problem related to a ConDec-R process model CR =(Acts, CBP,Res) (cf. Definition 3.1) is a COP Po =(V, D, CCSP,o)(cf. Definition 2.9) where: (i) The set of variables Vis composed by all the CSP variables included in the presented CSP model plus the CSP variable related to the OCT, i.e. V= {nt(a),(a, role, dur)∈Acts}∪{st(ai),et(ai),res(ai),sel(ai),(a, role, dur)∈ Acts, i ∈[1 ...UB(nt(a))]}∪{OCT }. (ii) The set of domains Dis composed by the domains of each CSP variable v, Dom(v), i.e. D={Dom(nt(a)) = {0...MC},(a, role, dur)∈Acts}∪ {Dom (st(ai)) = Dom(et(ai)) = {0...MC ×(a,role,dur)∈Acts dur(a)}, (a, role, dur)∈Acts, i ∈[1 ...UB(nt(a))]}∪{Dom(res(ai)) = {1...#role, (role, #role)∈Res},(a, role, dur)∈Acts, i ∈[1 ...UB(nt(a))]}∪{Dom (sel(ai)) = {0...1},(a, role, dur)∈Acts,i∈[1 ...UB (nt(a))]},whereMC is the maximum cardinality for the BP activities, i.e. nt (established by existence relations in the constraint-based model). In this way, MC is used for establishing initial upper bounds (i.e. UB) for the domain of several variables (including nt variables). (iii) The set of constraints CCSP is composed by the global constraints (implemented by the filtering rules, cf. Sec. 4.2) related to the ConDec-R constraints included in CBP together with the constraints from the proposed CSP model, i.e. ∀i:1≤i<nt(a):et(ai)≤st(ai+1), ∀i:1≤i≤UB(nt(a)) : sel(ai)== nt(a)>=ifor each repeated activity (a, role, dur)∈Acts. (iv) Theobjectivefunctionois minimizing the OCT variable. In the proposed constraint-based approach resources are implicitly constrained since COMET provides a high-level constraint modeling specific to scheduling which includes an efficient management of shared resources. Note that, besides the rolebased allocation pattern, the CSP variables which are included in the model can be also used for specifying further resource constraints.8 As an example, separation of duties (i.e. the ability to specify that two activities a and b must be allocated to different resources in a given workflow case) can be specified by including the next constraint in the proposed CSP model: ∀ i :1 ≤ i ≤ nt(a), ∀ j :1≤ j ≤ nt(b): ai · res = bj · res. Figure 5 includes the translation from a ConDec-R specification into a CSP so that the CSP variables and constraints are stated as explained in Definition 4.3 (cf. Step 2). In general, for each repeated activity a,a CSP variable nt is added to the CSP model. Thereby, the value for LB(nt(a)) is initially set to 0 (it will be automatically updated during the solving process if an existence constraint is added through the corresponding filtering rule, cf. Sec. 4.2), and for UB(nt(a)) 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 a rough initial estimate is made by considering the maximum obligatory cardinality MC of all repeated activities which is stated by existence constraints. For the constraint-based model depicted in Fig. 5, for example, the upper bound for all repeated activities is initially set to 2 (due to the existence constraint related to activity A). This value is high enough to ensure a feasible solution (the optimal solution, however, in general includes lower values of nt for several activities). Moreover, LB(OCT) is initially set to 0, and UB(OCT) is estimated as the maximum cardinality times the sum of the duration of all the BP activities, i.e. 2 × (5 + 3 + 4) in the example of Fig. 5. This is since the worst solution which can be obtained results in a plan which includes the execution of each BP activity the maximum number of times when all activities are sequentially executed. For similar reasons, for each scheduling activity ai, lower and upper bounds for st and et are set to lower and upper bounds of OCT. Furthermore, in general, Dom(res(ai)) = {1 ...#role(role(a))}, i.e. Dom(res(Ai)) = {1 ...2} and Dom(res(Ci)) = {1 ...2} for any i since #R1 =2,andDom(res(Bi)) = {1} for any i since #R2 = 1 for the constraint-based model depicted in Fig. 5.In addition, for each scheduling activity ai, Dom(sel(ai)) = {0 ...1},since sel is a binary variable indicating whether or not the scheduling activity is selected to be executed. 4.2. Filtering rules To improve the modeling of the problems and to efficiently handle the constraints in the search for solutions, our constraint-based proposal includes for each ConDec template a related global constraint implemented through a filtering rule (responsible for removing values which do not belong to any solution) for the definition of the high-level relations between the BP activities. In this way, the constraints stated in the ConDec-R specification (cf. Definition 3.1) are included in the CSP model through the related global constraints. These global constraints facilitate the specification of the problem. At the same time, the related filtering rules enable the efficiency in the search for solutions to increase. This is since during the search process these filtering rules remove inconsistent values from the domains of the variables. In the CSP model specification, initial estimates are made for upper and lower bounds of variable domains (cf. Sec. 4.1), and these values are refined during the search process. The developed filtering rules (cf. Ref. 34) are considered in the search algorithms. 4.3. Solving the COP Once the problem is modeled, several constraint-based mechanisms can be used to obtain the solution for the COP, i.e. optimized enactment plans (cf. Definition 4.4). Since the generation of optimized plans presents NP-complexity,35 it is not possible to ensure the optimality of the generated plans for all the cases. The developed 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 constraint-based approach, however, allows solving the considered problems in an efficient way. Definition 4.4. A BP enactment plan is composed by: (i) the number of times each BP activity is executed, (ii) the start and the completion times for each activity execution, and (iii) the resource which is used for each activity execution. By taking into account the NP-complexity of the considered problems, we adapted the existing solver COMET42 by applying an incomplete search for solving the specific considered problems. We also evaluate its suitability for the generation of BPMN models from constraint-based specifications (cf. Sec. 8). This incomplete search includes randomized components in order to diversify the search. By means of this approach, a first feasible solution is quickly found by a randomized greedy algorithm. The same greedy algorithm is used for iteratively improving the best solution found until a time limit is reached. Through this incomplete search, all the solutions can be reached and the search procedure efficiently explores a wide range of solutions from diversified areas of the search space. In general, when optimizing a CSP variable, if a feasible solution which is known exists, the value of the variable to optimize in the known solution can be used for discarding large subsets of fruitless candidates by using upper and lower estimated bounds of the quantity being optimized during the search process. Thus, if a known feasible solution S for the problem to solve exists, the objective value for this solution (SOCT) is a valuable information which can be added to the constraint model through the constraint OCT <SOCT. Thus, some non-optimal candidates, i.e. candidates whose OCT value cannot be less than SOCT in any case, are discarded during the search, increasing the efficiency in the search for solutions. Moreover, in our proposal, during the search process, some of the values which only lead to non-feasible solutions, i.e. inconsistent values, are removed from the domains of the CSP variables through the developed filtering rules (cf. Sec. 4.2)in order to reduce the search space by maintaining arc consistency (cf. Definition 4.5). Definition 4.5. ACSP=(V, D, CCSP)presentsarc consistency iff for all pairs of CSP variables (var1,var2) | var1,var2 ∈ V ,foreachvalueofvar1 in the domain of var1 there is some value in the domain of var2 that satisfy all the constraints stated in CCSP between var1 and var2,andviceversa. In the proposed approach, the developed filtering rules and CSP modeling (cf. Sec. 4.1) are implemented such that they maintain the arc consistency for all pairs of CSP variables during all the search process. 5. From Optimized Enactment Plans to Optimized Business Process Models Section 4 has described how optimized BP enactment plans can be generated from ConDec-R specifications. This section describes how a BPMN model which includes 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 the same activities to be executed in the same ordering and also using the same resources can be generated from the optimized enactment plan. For each role in the BP enactment plan, a BPMN pool (cf. Definition 5.1) is created, which contains as many lanes as number of available resources for that role. Definition 5.1. ABPMN pool BPMNPool =(role, #role) is a pool of a BPMN model, which is composed of #role lanes. Moreover, for each scheduling activity in the BP enactment plan a BPMN activity (cf. Definition 5.2) is created. Additionally, one start activity and one end activity are included in the BPMN model. Definition 5.2. ABPMN activity BPMNAct =(pool, lane, dur, st) is an activity of a BPMN model placed in the lane named lane of the pool named pool,with duration dur and start time st. One of the most important aspects to be considered for the generation of optimized BPMN models are the precedence relations between the BPMN activities (scheduling activities). For establishing these precedence relations the values for the start and the end times of the scheduling activities in the enactment plan are considered. These precedence relations are then used as a basis for generating BPMN models (cf. Definition 5.6) from BP enactment plans. Some related definitions are given below: Definition 5.3. In a BP enactment plan regarding a CSP solution S, a scheduling activity aiis a predecessor of another scheduling activity bj,ai∈predecessors(bj), if the relation Set(ai)≤Sst(bj)holds due to resource or template relations. Definition 5.4. In a BP enactment plan, a scheduling activity aiis a direct predecessor of another scheduling activity bj,ai∈DP(bj), if ai∈predecessors(bj)∧  ∃ck∈predecessors(bj)|ai∈predecessors(ck). Definition 5.5. In a BP enactment plan, a scheduling activity aiis an indirect predecessor of another scheduling activity bj,ai∈IP(bj), if ai∈predecessors(bj)∧ ∃ck∈predecessors(bj)|ai∈predecessors(ck). Definition 5.6. ABPMN model BPMN =(Pools, Activities, SequenceF lows, ParallelM) related to a ConDec-R process model CR =(Acts, CBP,Res) (cf. Definition 3.1) and to a solution S(cf. Definition 2.8) of the related CSP-ConDec problem (cf. Definition 4.3) is a BP model specified through the BPMN language, where: (1) P ools ={BPMNPool(role, #role),(role, #role)∈Res}. (2) Activities ={BPMNAct(role(a), Sres(ai),dur(a), Sst(ai)), (a, role, dur)∈ Acts,i∈[1 ...Snt(a)]}∪{start =BPMNAct(P0,L 0,0,0)}∪{end =BPMNAct (P0,L 0,0,max(a,role,dur)∈Acts,i∈[1...Snt(a)]Set(ai))}. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 (3) Let the set P redecessors be: (i) {(start, ai)|(a, role, dur)∈Acts, i ∈[1 ...Snt(a)],Sst(ai)=0}∪ (ii) {(aSnt(a),end)|(a, role, dur)∈Acts,  ∃bi,i∈[1 ...Snt(b)], (b, roleb,dur b)∈ Acts,aSnt(a)∈predecessors(bi)}∪ (iii) {(bi,c j)|i∈[1 ...Snt(b)], (b, roleb,dur b)∈Acts,j∈[1 ...Snt(c)], (c, rolec, durc)∈Acts, bi∈DP(cj)}, Then: (a) SequenceFlows ={(bi,c j)|(((b, roleb,dur b)∈Acts ∧i∈[1 ...Snt(b)]) ∨ bi=start)∧(((c, rolec,dur c)∈Acts ∧j∈[1 ...Snt(c)]) ∨cj=end)∧ (bi,c j)∈P redecessors∧|{dk,(((d, roled,dur d)∈Acts∧k∈[1 ...Snt(d)])∨ dk=start),(dk,c j)∈P redecessors}| =1)}. (b) ParallelM ={(Sources,cj)|(((c, rolec,dur c)∈Acts ∧j∈[1 ...Snt(c)]) ∨ cj=end)∧Sources ={bi,(((b, roleb,dur b)∈Acts ∧i∈[1 ...nt(b)]) ∨bi= start)∧(bi,c j)∈P redecessors}∧|Sources|>1}. In this way, through the set P redecessors, the precedence relations between activities are stated so that (i) the start activity is predecessor of all scheduling activities whose st value is equal to 0, (ii) the activities which are not predecessors of any other activity, are predecessor of the end activity, and (iii) in general, one activity bi is predecessor of another activity cj iff bi is direct predecessor of cj (cf. (3) in Definition 5.6). The set P redecessors is represented in the BPMN model by BPMN sequence flows between a source activity bi and a sink activity cj,inthe case that bi is the only predecessor of cj (cf. (3)(a) in Definition 5.6), or by a parallel merging gateway between a set of source activities Sources and a sink activity cj in the case that cj has more than one predecessor (cf. (3)(b) in Definition 5.6). Note that parallel merging gateways (i.e. parallel gateways which have several sources and only one sink) need to be explicitly included in the resulting BPMN model, since they do not have the same meaning as several binary sequence flows from several sources and one sink. However, parallel splitting gateways (i.e. parallel gateways which have several sinks and only one source) do not need to be explicitly included in the resulting BPMN model since several binary sequence flows between one source activity and several sink activities have the same meaning as a parallel splitting gateway in the BPMN language. The pseudocode and complexity analysis of the algorithms which were developed for generating BPMN models from optimized BP enactment plans are included in Appendix A. As a brief summary of this appendix, there is a main algorithm, Algorithm A.1, which constructs a BPMN model from a ConDec-R model and from a related optimized BP enactment plan (cf. Definition 5.6). As stated before, one of the most important aspects to be considered for this model generation are the precedence relations between the scheduling activities of the plan, which are managed by Algorithm A.2. These precedence relations are due to (1) resource constraints, i.e. the activities are allocated in the resources in a specific order in the generated enactment plan, and (2) ConDec-R constraints related to precedence between 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 activities. Typically, unlike resource precedence relations, precedence relations due to ConDec-R constraints cannot be easily obtained. To this end, each ConDecR template presents a method which is in charge of determining the precedence relations which are given between the scheduling activities related to the repeated activities which are involved in that ConDec-R template. The mentioned method for some representative ConDec-R templates is detailed in Algorithms A.3–A.5. 6. Allowing for Run-Time Flexibility The execution plans generated in Sec. 4 provide an optimal way for executing the source ConDec model assuming certain estimated values and all decision to be goal-based. Even though these assumptions are valid for certain environments (e.g. certain web service settings) estimates might not always be accurate or some decisions might depend on run-time information. For this, the approach described in Secs. 3–5 is extended in this section to allow decisions to be deferred at run-time (cf. Sec. 6.1), and to allow the BPMN model to be dynamically adapted during run-time (cf. Sec. 6.2). 6.1. Late-planning activities Executing a ConDec model usually entails dealing with decisions related to (1) how many times one activity is being executed, and (2) the order of execution of the activities. We assume that at least the decisions related to the order of execution of the activities are goal-based. However, we consider non-goal-based decisions (e.g. user-based decisions), if needed, regarding the number of executions of a particular activity. Related to these decisions, in turn, in ConDec one activity can be executed arbitrarily often if not restricted by any constraint. However, there are some ConDec templates which constrain the number of executions of the activities, resulting either in a specific value (e.g. A must be executed exactly twice), or in a range (e.g. A must be executed either once or twice). The number of times one activity should be executed can be stated by one specific constraint (e.g. Exactly(A, 2)), or by the combination of several constraints (e.g. the combination of Exactly(A, 2) together with ChainSuccession(A, B) implies that B should be executed exactly twice). To be able to deal with decisions related to the number of times certain activities are being executed which are not goal-based, we propose to encapsulate these activities (together with the relations in which they are involved) in a complex declarative late-planning activity when specifying the ConDec-R model, i.e. we propose the use of hierarchical models. In declarative models the activities included in a complex activity should be such that they can be executed in isolation from the top-level process.37 Encapsulating decisions which are not goal-based in a fragment allows dealing with each sub-process (i.e. complex activity) as if it were a black box, and therefore, our approach can be directly applied (even enabling multiple instance 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 optimization). Therefore, when creating the optimized enactment plans from the ConDec-R specification (cf. Sec. 4), each late-planning activity is treated as an atomic activity, and it is managed as a repeated activity (cf. Definition 4.1). In this way, when generating the BPMN model (cf. Sec. 5) the complex activities are then integrated into the BPMN model by substituting the BPMN activity related to the complex activity by the associated imperative fragment. The following sectiosn describes the generation process. For sake of clarity we describe in different subsections how constraints (cf. Sec. 6.1.1), resources (cf. Sec. 6.1.2), and durations (cf. Sec. 6.1.3) are managed. 6.1.1. Constraints The BPMN fragment associated to a specific complex activity is generated as follows: (1) Generating all possible combinations of declarative models in such a way that all different possibilities for nt (i.e. number of times) for each activity are covered. This is done by stating Exactly constraints for all the possible values for the number of executions for all the activities which belong to the complex activity. Specifically, for each activity A whose number of executions should be in a range[Min...Max],thegeneratedmodelsshouldcoverallthepossibilities (i.e. Exactly(A, nt), ∀nt ∈[Min ...Max]) in combination with all the possibilities for the other activities. Note that the maximum number of execution times for each activity belonging to a complex activity needs to be established, otherwise, the possibilities are not finite. (2) For each declarative model which is generated, related optimized enactment plans are created (i.e. local optimization for each possible feasible declarative model is addressed) through the proposed constraint-based approach (cf. Sec. 4). (3) These optimized plans are then translated to BPMN fragments (cf. Sec. 5). (4) These fragments are then linked by using existing merging algorithms (e.g. Ref. 38). Note that the resulting fragment will include XOR gateways when necessary. When generating the different combinations of declarative models (i.e. step (1)) it is possible that some unfeasible combinations exist. In these cases, no related optimized enactment plan is generated, and therefore, the related BPMN fragment is not considered when merging. Figure 6 shows an example of the complete process over a fragment which includes five BP activities (A, B, C, D and E) and five existence relations (i.e. all activities should be executed at most once) together with five binary relations (i.e. (1) ExChoice(A, C), implying that either A or C (but not both) must be executed, (2) ExChoice(B, D), implying that either B or D (but not both) must be executed, (3) Response(A, B), implying that after the execution of A, B should 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 Fig. 6. Generating BPMN fragments from declarative complex activities. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 be eventually executed, (4) P recedence(C, D), implying that before the execution of D, C should be executed, and (5) Succession(D, E), implying that after the execution of D, E should be executed and before the execution of E, D should be executed). Given that declarative specification, there are three feasible scenarios, i.e. three possible ways to execute the specification ensuring that all constraints are satisfied: (a) Ais executed once; Cis not executed due to ExChoice(A, C); Bis executed once after Adue to the Response(A, B)constraint;Dis not executed due to ExChoice(B,D), therefore also Ecannot be executed due to Succession(D, E). (b) Cis executed once; Ais not executed due to ExChoice(A, C); Bis executed once; Dis not executed due to ExChoice(B,D), therefore also Ecannot be executed due to Succession(D, E). In the related optimized enactment plan, both options (Bsucceeding Cor Csucceeding B) are feasible. For this example, we consider that the option Bsucceeding Cis more optimized than Csucceeding B(note that for each feasible scenario only the most optimized plan is selected for the merging, as explained in the step (2) of the process). (c) Cis executed once; Ais not executed due to ExChoice(A, C)); Dis executed once; Bis not executed due to ExChoice(B,D). Since Dis executed, Eshould be also executed due to Succession(D, E). In the related optimized enactment plan, Cshould precede Ddue to P recedence(C, D), and Dshould precede E due to Succession(D, E). In this example, some unfeasible combinations for nt exist. For example, the scenario in which A is executed once and D is executed once is unfeasible since two relations (i.e. Response(A, B)and P recedence(C, D)) are violated. In Fig. 6, the different BPMN fragments (related to the optimized enactment plans) which are obtained from the three feasible scenarios have been merged using the tool presented in Ref. 38. For the sake of clarity, in Fig. 6 information related to resources and durations of activities has been omitted. Note that optimization is locally applied within each complex activity since for each declarative model which is generated (i.e. for each possibility) optimized enactment plans are generated. 6.1.2. Resources For each complex activity, required resources need to be stated when including this activity in the ConDec-R model. When all the activities which belong to the same complex activity require resources related to the same role, the complex activity will also require that role, and the proposed approach can be directly applied (cf. Fig. 7(a), where all the activities require a resource of role R0). However, when the activities which belong to the same complex activity require resources related to different roles, some adjustments are required, e.g. encapsulating the declarative 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 (a) (b) Fig. 7. Complex activities: Dealing with resources. (a) Activities requiring resources related to the same role, (b) activities requiring resources related to different roles. sub-process in a complex activity which requires as many resources as different roles are included in the sub-process (cf. Fig. 7(b)), i.e. the constraint-based approach needs to be adapted to allow for activities which require multiple resources, resulting in a cumulative scheduling problem.39 This extension can be easily achieved since most constraint-based systems provide a high-level constraint modeling specific to scheduling which includes an efficient management of shared resources for wellknown scheduling problems, which is the case of the cumulative scheduling problem. When generating the BPMN model, each activity of the sub-process needs to be associated to the suitable lane (cf. Fig. 7). Note that, in the proposed approach, 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 Fig. 10. Optimized Gantt chart and BPMN for the travel agency problem for #P =4, #A =1 and #B =1. As commented, in order to define an instance (#P, #A, #B)forthetravel agency problem, the following parameters must be stated: number of client requests (#P), number of resources available in the agency (#A), and number of resources available in the company (#B). In this section, two instances are studied as illustrations, specifically Problem 1 defined by (#P =4, #A =1, #B = 1), and Problem 2 defined by (#P =4, #A =2, #B = 2). For Problem 1, Fig. 10 shows both the optimized Gantt chart (OCT = 47) and the BP model which are obtained through our proposal. It can be seen that regarding the first client request, depicted by G1 in the Gantt diagram), the trip plan is created by the agency (TP1 activity), while the transport and accommodation search are carried out by the company (CT&AS1). Once both activities TP1 and CT&AS1 start, the second client request can be received (G2). Thefactthatanactivity B can only start after another activity A has started is stated by considering the predecessors of A as predecessors of B.In thiscase,the predecessor of TP1 and CT&AS1 (i.e. G1) must (directly o indirectly) precede G2. Regarding the second Get Request activity (G2), the trip plan is organized by the company (CTP2 activity), while the transport and accommodation search are carried out by the agency (TS2 and AS2 activities). In this case, activity AS2, which is related to the second request, is postponed until after the end of the execution of other activities related to the third request (G3, TP3), for efficiency reasons (notice that there is no constraint between the repeated activities TP and AS). Once both activities CTP2 and TS2 start, the third client request can be received (G3). Regarding the third Get request (G3), the trip plan is created by the agency 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 (TP3 activity), while the transport and accommodation search are carried out by the company (CT&AS3 activity). Once both activities TP3 and CT&AS3 start, the fourth Get request can be received (G4). Regarding the fourth request (G4), the trip plan is created by the company (CTP4 activity), while the transport and accommodation search are carried out by the agency (TS4 and AS4 activities). After all the client requests which are carried out by the company are finished, the Send Report (SR) activity can be executed. After this, the Receive Report (RR) activity can be executed. Finally, after all activity executions, the Client Reports (CR) activity is executed. In a similar way, for Problem 2, Fig. 11 shows the optimized Gantt chart (OCT = 33) and the BP model which are obtained with our proposal. 7.4. Dynamic programming for the travel agency problem A feasible solution to a model of a number of instances can be obtained by concatenating known solutions for the same model with a smaller number of instances. The Fig. 11. Optimized Gantt chart and BPMN for the travel agency problem for #P =4, #A =2 and #B =2. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 optimal way to perform this concatenation can be achieved by dynamic programming (DP).41 For the travel agency problem, DP can be applied for obtaining good solutions by joining optimal solutions to smaller problems. Let OCTa,b(p)be the best OCT which is known for an instance (p, a, b) of the travel agency problem. DP can be applied to the travel agency problem so that the best OCT for (p, a, b) obtained through 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)−dur(CReports))j i.e. the best combination of two optimal/optimized solutions to smaller problems is chosen. 8. Empirical Evaluation In order to evaluate the efficiency of the proposal, a controlled experiment is conducted. Section 8.1 describes the design underlying the experiment, and Sec. 8.2 shows the experimental results and the data analysis. 8.1. Experimental design Purpose: The purpose of the empirical evaluation is to analyze our proposal in the generation of optimal enactment plans from ConDec-R specifications, specifically, the goals are: (1) the comparison of our constraint-based proposal with DP (cf. Sec. 8.2.1) and (2) the demonstration of its use for simulation purposes (cf. Sec. 8.2.2). Objects: We used the travel agency problem as example for our evaluation, since it includes various and representative relations of several types and complexity from the set of all the ConDec-R templates.k Independent Variables: For the empirical evaluation, the number of client requests, #P , the number of resources of roleA,#A, and the number of resources of role B,#B, are taken as independent variables. Response Variables: Some performance measures (cf. Table 3) related to the best generated plan are reported for the generated problems (Figs. 12;Tables4–6). Experimental Design: Based on the travel agency problem we generated a wide set of problem instances by varying the different independent variables: #P,#A and #B. For variable #P ,the values1...100 are considered, for #A,the values 1 ...5 are considered, and for #B,the values 1...5 are considered. Experimental Execution: For the experiments, the constraint-based search algorithm is run until a 10-min CPU time limit is reached. The machine for all experiments is an Intel Core2, 2.13 GHz, 1.97 GB memory, running on Windows XP. jCReports activity must be executed only once, and must be allocated after the execution of all other activities. kA tool for generating optimized BP models for the travel agency problem can be found at http://regula.lsi.us.es/AgenciesOptimizedModels/, where some tests can be carried out. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 Table 3. Response variables. Id Description CP/DP(s1+s2) The way in which the best solution is found, which can be by means of the proposed constraint-based approach, CP, or by DP through combining s1ands2, DP(s1+s2). OCT OCT for the generated optimized enactment plan. %BusyA Average percentage of use of resources of role A, regarding the OCT. %BusyB Average percentage of use of resources of role B, regarding the 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 Resources (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 Resources OCT P = 100 P = 90 P = 80 P = 70 P = 60 P = 50 P = 40 P = 30 P = 20 P = 10 Legend An: n resources with role A Bn: n resources with role B (b) Fig. 12. OCT depending on #A,#B. (a) Resources are grouped by #A, (b) resources are grouped by #B. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 Table 4. %OCT of the best solution found and method (CP or DP) that reaches it. 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 October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 Table 5. %Busy Aversus #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 Bversus #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 order to solve the constraint-based problems (cf. Sec. 4), the developed algorithms have been integrated with the system COMET,42 which is able to generate high-quality solutions for highly constrained problems in an efficient way. 8.2. Experimental results and data analysis As commented, the purpose of the empirical evaluation is two-fold, i.e. analyzing the suitability of our proposal through a comparison with DP (cf. Sec. 8.2.1), and through the use for simulation (cf. Sec. 8.2.2). 8.2.1. Comparison with DP DP (cf. Sec. 4.3) is a widely used technique in solving optimization problems, leading to solutions of high quality in most cases. Specifically, for the travel agency problem, DP can be applied (cf. Sec. 7.4). We would like to evaluate whether our constraintbased proposal usually improves the solution of good quality which can be obtained by DP, i.e. works efficiently. Table 4 shows the OCT for the best solutions which are found for some representative instances, together with the method (either DP or CP) which finds the best solution (column CP/DP(s1+s2) in Table 4). Thereby DP(s1+s2) means that the best solution is found by DP through combining s1and s2. For instances in which both techniques reach solutions which present the same values for OCT, DP(s1+s2) is depicted. It can be observed that for 1 ≤ #P ≤ 14, the constraintbased approach obtains better solutions than DP for almost all of the instances. Moreover, for 15 ≤ #P ≤ 18, in some cases DP obtains solutions that are better than or equal to those obtained through CP, and in other cases CP obtains the 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 best solution. Furthermore, for 19 ≤ #P ≤ 20, DP obtains solutions that are better than or equal to those obtained through CP for all the instances. Furthermore, it seems that the solutions for #P = {6, 7, 8, 9, 10 and 12} are largely optimized since they widely appear in the DP solutions. The results (cf. Table 4) show that our constraint-based approach, i.e. CP, is able to improve the solution obtained by DP in most of the cases. This shows that our constraint-based approach works efficiently in the generation of optimized enactment plans, and hence, for the automatic generation of optimized BPMN models. In short, our data indicates that for the generation of optimized BP models, CP enables complex problems to be solved in a more efficient way than they would be through other alternative methods, such as DP or the manual specification of BP models. Additionally, when #P increases, the complexity of the problem rises sharply, and hence the manual treatment of the problem would become almost inextricable. In contrast, when using our approach an optimized solution for large problems, such as for #P = 100 can be obtained in only 10 min. Threats to validity: There are several factors which may threaten the validity of our experiments for the attainment of generalizable conclusions: •The specific characteristics of the considered example, i.e. the empirical evaluation only considers a concrete problem with a specific number of BP activities and specific relations between the BP activities. •The way in which the optimal/optimized solutions for problems of a certain size are combined in order to obtain solutions for larger problems is specific for the considered example. In most cases, feasible solutions for larger problems can be generated by concatenating solutions to smaller problems through DP. However, the way in which solutions to problems of a given size can be combined to provide a solution to a larger problem depends on the type of problem considered. 8.2.2. Use for simulation Our approach can be used for simulation purposes in the BP design and analysis phase in order to study the relevance of several parameters in the quality of the generated plans, e.g. resource availability. As an example, the relevance of the number of available resources for the travel agency problem is analyzed as follows. Figure 12 shows the completion time of the best BP enactment plan (OCT) which is generated through our approach. In both graphics of Fig. 12,the OCTis shown depending on the number of resources of roles A and B.First,the considered resources are grouped according to #A (Fig. 12(a)). Secondly, the considered resources are grouped according to #B (Fig. 12(b)). It can be seen, in most cases, that the OCT greatly decreases as #A increases. Additionally, in most cases, the OCT remains almost the same when #B increases. Therefore, #A seems to be 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 much more influential than #B for the OCT, i.e. A is a more critical resource for the considered travel agency problem. In Tables 5 and 6, the average percentages of use of the resources of roles A and role B, respectively, regarding the OCT, are shown. In all cases, for the same value of #P , these percentages decrease as the number of resources of the associated role increases. Moreover, as expected, the average percentage of use of resources of role A is greater than the average percentage of use of resources of role B for the same value of #P . 9. Related Work Our approach makes a proposal for integrating P&S with BPMSs. Most related work on such an integration focuses on the enactment phase in order to make dispatching decisions as to which activity should be executed using a resource when it becomes free (dynamic scheduling),43–48 while very few integrations are carried out during the modeling phase, as presented here. Also related to our proposal is research on the generation of BP models, e.g. Refs. 9, 49–53. While the proposals of Refs. 49 and 50 provide the BP information through an execution/interchange language, XPDL, our approach, in turn, uses a declarative modeling language based on a formal logic (LTL). As stated, the usage of declarative specifications allows the user to specify what hastobedoneinstead of how, thereby facilitating the human work involved and avoiding failures. In contrast to XPDL, where the user has to specify the model in an imperative way, in our proposal the generation of imperative BP models is automatically done by the system. In a related way, in Ref. 51, planning tools are used for the semiautomatic generation of BP models, by considering the knowledge introduced through BP Reengineering languages. In Ref. 51, they propose an object-oriented structure modeling tool that follows their own rule-based approach, while we propose the use of an extension of ConDec, a widely referenced language in the context of BPM (e.g. Refs. 26 and 55), which also allows a higher level of abstraction. Additionally, Ref. 52 proposes a planning formalism for the modeling of BPs through an SAP specification (Status and Action Management, SAM), which is a variant of PDDL. Unlike our work, neither the resource perspective nor the optimization of several instances are considered since in Ref. 52 each non-deterministic action (i.e. activity) cannot be repeated in the generated solution. Moreover, Ref. 53 presents a service-oriented approach which transforms high-level BP models into web services composition models. This approach uses UML to specify the BP models from an MDA point of view, which lacks an implementation view of BP models,56 in contrast to ConDec, which is a graphical and specific language for the modeling of BPs. Furthermore, Ref. 9 proposes to refine BP models by combining learning and planning techniques, starting from processes which are not fully described. Unlike our work, Ref. 9 needs past process executions and examples provided by the user to apply learning techniques. Moreover,9 does not consider the optimization of any 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 objective function in the generation of the plans. Furthermore, in Ref. 9 executable plans are generated, while we propose the generation of BP models which are specified in a standard language, i.e. BPMN, which can also be improved by business analysts if necessary. Related to the combined used of declarative and imperative models, Ref. 57 proposes the use of declarative BP models for specifying processes independently of a particular environment in order to align optional process customizations. This information is complemented with imperative BP specifications which contain information related to the control flow of the processes, often specific to a given environment. In Ref. 57 both declarative and imperative BP models need to be (manually) specified, while in our proposal the optimized imperative models are automatically generated. Lastly, Ref. 58 analyzes the need of transitions between different BP modeling paradigms, i.e. declarative, imperative and hybrid proposals, supporting our proposal. Additionally, there exist some proposals which could be used to generate optimized enactment plans for BPs from constraint-based process specifications. Specifically, Ref. 59 proposes the generation of a non-deterministic finite state automaton from constraint-based specifications based on linear temporal logic (LTL) which represents exactly all traces that satisfy the LTL formulas. When extending this approach by including estimates, the OCT of all the traces could then be calculated (e.g. Ref. 60). However, the big disadvantage following such an approach would be that it can lead to performance problems when confronted with large constraint-based models since the automaton generated for the concatenated LTL formulas is exponential with respect to the size of the formula,61 and, unlike the proposed approach, no heuristic has been used. In a similar way, CLIMB26 could be used to generate feasible traces, i.e. traces which meet all the constraints imposed by the declarative specification, and calculate its completion time. Then, the best traces could be selected. Unlike our approach, Ref. 26 does neither consider optimality nor resource availabilities. Therefore, this would only cover the planning part of our proposal, but not the scheduling aspects addressed by our approach. There is some related work (e.g. Refs. 62–65)which is focusedonthe automated composition of web services using planning techniques, i.e. given a set of services which are published on the web and a goal, the aim is to generate a composition of the available services which satisfies the goal. Like our approach, dynamic process-based composition approaches also start from a declarative specification. However, while they only consider activities with preconditions and effects, we allow for an increased expressiveness through the ConDec language. Supporting the suitability of ConDec for specifying web services, the work66 proposes the language DecSerFlow (which is a sister language of ConDec, i.e. both share the same concepts and tools) as a declarative service flow language. Moreover, unlike,62–65 our approach considers multiple instances which are executed within a particular timeframe, which is fundamental for achieving global optimization. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 10. Discussion and Limitations In BP most environments, the Process Design & Analysis phase is manually carried out by business analysts, who must deal with several aspects, such as resource allocation, the activity properties and the relations between them, and may even have to handle the optimization of several objectives. Therefore, in some cases, the manual specification of BP models can consume great quantity of resources, cause failures, and lead to non-optimized models, resulting in a very complex problem.9 Hence, it should be emphasized that the automatic generation of BP models facilitates the human work in most cases, prevents failures in the developed BP models, and enables better optimization to be attained in the enactment phase. Additionally, the specification of process properties in a declarative way allows the user to specify what is to be done, and the proposed AI-based tool is in charge of determining how it is to be done in order to satisfy the problem specifications, and to attain the optimization of certain objective functions. Unlike conventional BPMN models, in our approach each generated model comprises the execution of a set of instances. Therefore, our approach always addresses, at least, global inter-instance optimization (even when optimization within each instance is not completely addressed). In this way, optimization over a set of instances is always addressed (e.g. the resources which are shared by the different instances are allocated in an optimized way by considering all instances to be executed). Additionally, in most cases, intra-instance optimization is also (completely or partially) addressed, as explained in Sec. 6.1. Moreover, the automatic generation of BP models can deal with complex problems of great size in a simple way, as demonstrated in Sec. 8. Therefore, a wide study of several aspects can be carried out by simulation, such as those related to the requirement of resources of different roles, or the estimated completion time for the BP enactment, by generating several kinds of problems. Furthermore, the proposed constraint-based approach can be used to efficiently solve further planning and scheduling problems which include similar relations between repeated activities, and which are unrelated to BP environments. It should also be clarified that the BP models are generated for execution purposes, and hence clarity of meaning for the users of the generated models is not considered relevant in the current proposal. Note that the generation of optimized enactment plans from constraint-based specifications is, from our point of view, the most challenging task of the proposed approach. Existing constraint-based BPMSs like Declare32 could be used (in combination with planning) to decide which activities have to be done in the current state. In a related way, optimized enactment plans can be used to help users to find good/optimal ways to execute a declarative process by suggesting recommendations, as explained in one of our previous works (cf. Ref. 67). However, in the current work, the motivation for generating BPMN models from these enactment plans is two-fold: (1) visualize the generated enactment plan in a standard BP modeling language the users are familiar with, with the goal of allowing the 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 Algorithm A.2: CreateDependencies input : SortedSetP&SActacts ordered by st SetConstraintconstraints SetRoleroles output:MapP&SAct,SetP&SAct directP redecessors MapP&SAct,SetP&SAct allP redecessors ←∅; 1 foreach rinrolesdo2 foreach res in r.resources do3 ListP&SActactsRes ←res.acts;4 foreach i in i:1..actsRes.size-1 do5 allPredecessors(actsResi+1)←{actsResi};6 foreach cinconstraintsdo7 c.includeP redecessors(allPredecessors);8 MapP&SAct,SetP&SAct indirectP redecessors ←∅;9 foreach act in acts do10 directP redecessors(act)←allPredecessors(act);11 foreach p in allPredecessors(act)do12 directP redecessors(act)←13 directP redecessors(act)\allPredecessors(p); indirectP redecessors(act)← 14 indirectP redecessors(act)∪allPredecessors(p); allPredecessors(act)←15 allPredecessors(act)∪indirectP redecessors(act); return directP redecessors;16 constraints related to precedence between activities. Algorithm A.2 generates a map in which each scheduling activity is associated to a set of scheduling activities that are its direct predecessors (cf. Definition 5.2). For this, three maps are managed in this algorithm: (1) directP redecessors, which associates each scheduling activity to the set of its direct predecessors, (2) indirectP redecessors, which associates each scheduling activity to the set of its indirect predecessors (cf. Definition 5.3), and (3) allP redecessors, which associates each scheduling activity to the set of all its direct and indirect predecessors. In Algorithm A.2, first, the precedences required due to the use of the same resource are included (lines 2–6). Secondly, the precedences required due to the high-level relations (i.e. ConDec-R constraints) between the repeated activities which are stated in the model are included through the method includePred of each constraint (lines 7 and 8). Typically, unlike resource precedence relations, precedence relations due to ConDec-R constraints cannot be easily obtained. To this end, each ConDec-R template presents a method which is in 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 charge of determining the precedence relations which are given between the scheduling activities related to the repeated activities which are involved in that ConDec-R template. The mentioned method for some representative ConDec-R templates is detailed in Algorithms A.3–A.5. Lastly, the indirect predecessors are removed from the map directP redecessors in order to avoid redundant connections, by taking into account that the sorted set acts is ordered by st, and hence, the scheduling activities are managed from minor to major st in the external loop (lines 9–15). The properties of the maps which are used in Algorithm A.2 are demonstrated by Proposition A.1. Proposition A.1. This proposition contains two related parts: (a) After executing lines 1–9 of Algorithm A.2,(1)directP redecessors =∅,(2) indirectP redecessors =∅,and (3) allPredecessors associates each scheduling activity with all its direct predecessors (cf. Definition 5.4) andasubsetofits indirect predecessors (cf. Definition 5.5). (b) At the end of Algorithm A.2,as a result of executing lines 10–15,∀act ∈acts : (1) the map directP redecessors associates act with exactly all its direct predecessors (cf. Definition 5.4),(2) the map indirectP redecessors associates act with exactly all its indirect predecessors (cf. Definition 5.5),and (3) the map allPredecessors associates act with exactly all its direct and indirect predecessors. Proof. (a) The statements directP redecessors =∅and indirectP redecessors =∅ hold since these maps have been only initialized. On one hand, the map allPredecessors contains all the direct predecessors since all resource and ConDec relations are considered (lines 2–6 and 7–8, respectively). Moreover, some indirect predecessors have probably been included since redundant connections have not been avoided. (b) (Mathematical Induction): (i) The base case: Since acts is a sorted set ordered by st,acts1does not have any predecessor (i.e. allPredecessors(acts1)=∅). Therefore, at the end of Algorithm A.2, as a result of executing lines 10–15: (1) directP redecessors(acts1)=∅,(2)indirectP redecessors(acts1)=∅, and (3) allPredecessors(acts1)=∅, i.e. the statement holds for the base case. (ii) The inductive step: If the statement holds ∀i∈1...n−1actsi, then the statement also holds for actsn. (1) directP redecessors(actsn): in line 11, this set is initialized with all the precedence relations of actsnwhichwerepreviouslyobtainedinthe previous step until line 8, i.e. all its direct predecessors and a subset of its indirect predecessor (cf. Proposition A.1(a)). After that, for each direct 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 predecessor pof actsn(line 12), all the direct and indirect predecessors of p, which are therefore indirect predecessors of actsn, are removed from the set directP redecessors(actsn) (line 13). Due to the induction hypothesis, the set allPredecessors(p) is assumed to contain all direct and indirect predecessors of psince we are assuming that the statement holds for ∀i∈1...n−1actsi(due to pis a predecessor of actsnand acts is asortedset,then∃i∈1...n−1|actsi=p). (2) indirectP redecessors(actsn): For each direct predecessor pof actsn (line 12), all the direct and indirect predecessors of p,whichare therefore indirect predecessors of actsn, are included in the set indirectP redecessors(actsn) (line 14). (3) allPredecessors(actsn): After line 9, the set allPredecessors(actsn) contains all the direct predecessors and a subset of indirect predecessor of actsn(cf. Proposition A.1(a)). In order to ensure that all indirect predecessors are included, allPredecessors(actsn) is updated by considering all the indirect predecessors (line 15). Algorithm A.3: includePred method for the branched Precedence template with several source activities and one sink activity input :MapP&SAct,SetP&SAct pred output:MapP&SAct,SetP&SAct pred SetP&SActmeet ←{a1|a∈this.sources, a1.et ≤this.sink1.st};1 P&SAct sel ←argmina∈meet(a.et);2 pred(this.sink1)←pred(this.sink1)∪sel;3 return pred;4 With respect to the includePred method, some representative templates are selected for illustration purposes (other templates can be described in a similar way). In Algorithm A.3, the template regarding the branched Precedence template with several source activities and one sink activity (i.e. it is modeled by a ConstraintSources object, cf. Fig. A.1) is shown. The location of a branched precedence template between several sources and one sink implies that the first execution of at least one of the sources must finished before the start of the first execution of the sink. In line 1, the set of scheduling activities which comply with the Precedence template (i.e. the first executions of the sources which end before the start of the first execution of the sink) are included in the set meet.At least one scheduling activity will be included in this set since the Precedence template is satisfied, however it may be possible to find more than one. In order to generate a BPMN model which is compatible with both the optimized enactment plan and the ConDec-R specification, as is the purpose of our approach, any scheduling activity of the set meet can be selected to be the predecessor of the sink in the 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 BPMN model. One scheduling activity of the set meet is then selected to be the predecessor of the sink. Specifically, the scheduling activity which presents more slack is selected (line 2) in order to construct a robust BPMN model. In line 3, the selected predecessor is included in the map, and is associated to the predecessors of the first execution of the sink. The fact that an activity Bcan start after another activity Ahas finished (ES, default option), is stated by including Ain the set pred of B(line 3) of Algorithm A.4. Algorithm A.4: includePred method for the branched Alternate Precedence Template with several source activities and one sink activity input :MapP&SAct,SetP&SAct pred output:MapP&SAct,SetP&SAct pred SetP&SActmeet ←{a1|a∈this.sources, a1.et ≤this.sink1.st};1 P&SAct sel ←argmina∈meet(a.et);2 pred(this.sink1)←pred(this.sink1)∪sel;3 foreach i in 2..this.sink.nt do4 SetP&SActmeet ←{aj|a∈this.sources, j ∈5 1..a.nt, this.sinki−1.et ≤aj.st ∧aj.et ≤this.sinki.st}; P&SAct 6 sel ←argmaxa∈meet((a.st −this.sinki−1.et)+(this.sinki.st −a.et)); pred(sel)←pred(sel)∪this.sinki−1;7 pred(this.sinki)←pred(this.sinki)∪sel;8 return pred;9 The branched AlternatePrecedence template between several sources and one sink implies that before the execution of the sink, at least one of the sources must be executed, and between each two executions of the sink, at least one of the sources must be executed. As discussed, there exist two variants for the same temporal relation, which are represented by adding SS or ES at the end of the name of the template. In the AlternatePrecedence template, two temporal relations must be indicated: first, what “sink before source” means, and secondly, what “source before sink” means. Therefore, the branched template AlternatePrecedenceES-ES (default option) specifies that “sink before source” means that the end time of the sink must be less than or equal to the start time of the source, and “source before sink” means that the end time of the source must be less than or equal to the start time of the sink. The includePred method for the branched template AlternatePrecedenceES-ES with several source activities and one sink activity (i.e. it is modeled by a ConstraintSources object, cf. Fig. A.1) is shown in Algorithm A.4. For lines 1–3, the idea is the same as that in Algorithm A.3.Moreover, between each two successive executions of the sink, sinki−1 and sinki, one scheduling activity must be executed. Several scheduling activities related to the sources 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 can meet this condition (line 5). As before, the scheduling activity which presents more slack is selected (line 6) to be the predecessor of sinki (line 8), and at the same time sinki−1 is selected as the predecessor of the selected scheduling activity. Algorithm A.5: includePred method for the branched Alternate PrecedenceSS-ES Template with several source activities and one sink activity input :MapP&SAct,SetP&SAct pred output:MapP&SAct,SetP&SAct pred SetP&SActmeet ←{a1|a∈this.sources, a1.et ≤this.sink1.st};1 P&SAct sel ←argmina∈meet(a.et);2 pred(this.sink1)←pred(this.sink1)∪sel;3 foreach i in 2..this.sink.nt do4 SetP&SActmeet ←{aj|a∈this.sources, j ∈5 1..a.nt, this.sinki−1.st ≤aj.st ∧aj.et ≤this.sinki.st}; P&SAct 6 sel ←argmaxa∈meet((a.st −this.sinki−1.et)+(this.sinki.st −a.et)); pred(sel)←pred(sel)∪pred(this.sinki−1);7 pred(this.sinki)←pred(this.sinki)∪sel;8 return pred;9 In a similar way, the branched template AlternatePrecedenceSS-ES specifies that “sink before source” means that the start time of the sink must be less than or equal to the start time of the source, and “source before sink” means that the end time of the source must be less than or equal to the start time of the sink. The includePred method for the branched template AlternatePrecedenceSS-ES with several source activities and one sink activity (i.e. it is modelled by a ConstraintSources object, cf. Fig. A.1) is shown in Algorithm A.5. This algorithm is identical to Algorithm A.4, except for line 7. As mentioned earlier, the fact that an activity B can start after another activity A has finished (ES, default option), is stated by including A in the set pred of B. Additionally, the fact that an activity B can only start after another activity A has started, label SS, is stated by including the set pred(A)inthesetpred of B, as can be seen in line 7 of Algorithm A.5. The complexity analysis of all the algorithms previously described is included in A.1, and the equivalence between the definitions given in Sec. 5 and the algorithms included in this section is detailed in A.2. A.1. Complexity analysis This section presents the complexity analysis of the algorithms previously described. Proposition A.2. If implemented properly, the worst-case time complexity of Algorithm A.3 is O(n), where n is the number of Repeated Activities of the problem. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 Proof. The worst-case time complexity of line 1 is O(n), since #sources ≤ n. The worst-case time complexity of line 2 is also O(n), since #meet ≤ n.The time complexity of line 3 is constant. Therefore, the worst-case time complexity of Algorithm A.3 is O(n)+O(n) + Θ(1), equal to O(n). Proposition A.3. If implemented properly, the worst-case time complexity of Algorithms A.4 and A.5 is O(n × nt), where n is the number of Repeated Activities of the problem, and nt is the maximum number of times that a repeated activity is executed. Proof. The worst-case time complexity of line 1 is O(n), since #sources ≤ n. The worst-case time complexity of line 2 is also O(n), since #meet ≤ n.The time complexity of line 3 is constant. The worst-case time complexity of lines 4–8 is O(n × nt) since lines 5–7 (with complexity O(n) from the proof of Proposition A.1) are executed at most nt times. Therefore, the worst-case time complexity of Algorithms A.4 and A.5 is O(n)+O(n)+Θ(1)+ O(n × nt)equal to O(n × nt). Proposition A.4. If implemented properly, the worst-case time complexity of Algorithm A.2 is O(c×n×nt+nps2), where n is the number of Repeated Activities of the problem,ntis the maximum number of times that a repeated activity is executed,c is the number of constraints that appear in the definition of the problem, and nps is the number of scheduling activities in the optimized plan. Proof. The time complexity of lines 1–5 is Θ(nps), since each scheduling activity is considered exactly once (each activity uses a specific resource of a specific role). The worst-case time complexity of lines 6 and 7 is O(c×n×nt), since the worst-case time complexity of the method includeP red is O(n×nt) (Proposition A.2), and this method is invoked c times. The worst-case time complexity of lines 9–12 is O(nps2), since for each scheduling activity, its predecessors (at most, nps) are considered. Therefore, the worst-case time complexity of Algorithm A.2 is O(c ×n× nt + nps2). Proposition A.5. If implemented properly, the worst-case time complexity of Algorithm A.1 is O(c×n×nt+nps2), where n is the number of Repeated Activities of the problem,ntis the maximum number of times that a repeated activity is executed,c is the number of constraints that appear in the definition of the problem, and nps is the number of scheduling activities in the optimized plan. Proof. The worst-case time complexity of line 1 is O(c ×n× nt + nps2), by Proposition A.3. The worst-case time complexity of line 3 is O(n), since #role ≤ n.The time complexity of line 4 is Θ(nps). The worst-case time complexity of lines 6 and 15 is O(nps). The time complexity of lines 7–13 is Θ(nps). Therefore, the worst-case time complexity of Algorithm A.1 is O(c × n × nt + nps2). 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 A.2. Equivalence between definitions in Sec. 5and algorithms in Appendix A The definitions which appear in Sec. 5define the generation of BPMN models from a formal point of view, while the algorithms in the appendix describe the same generation from an implementation point of view (e.g. some information has been duplicated and ordered in a different way to facilitate the implementation). Therefore, the types used in the appendix are not exactly the same than the definitions given throughout the paper. However, both Definition 5.6 and Algorithm A.1 generate the same BPMN model from the same input ConDec-R model and from the same solution, as explained in the following. Regarding the input parameters: (1) Definition 5.6 includes (i) a ConDec-R process model CR =(Acts,CBP,Res) and (ii) a solution Sto a CSP-ConDec problem as input parameters, while (2) Algorithm A.1 includes (i) a sorted set of objects of type P&SAct, acts, ordered by st; (ii) a set of objects of type Constraint, c; (iii) and a set of objects of type Role, r. The input parameters of Algorithm A.1 can be obtained from the input parameters of Definition 5.6 as follows: •the information for each P&SAct aiin acts (i.e. st,et and res, cf. UML diagram of Fig. 12) is taken so that ai·st =Sst(ai),ai·et =Set(ai),ai·res =Sres(ai) (i.e. from the CSP variables which are related to the scheduling activity aiin the solution to the CSP-ConDec problem, cf. Definition 4.3). •c=CBP, i.e. the set of objects of type Constraint, c, contains the same constraints which are included in the ConDec-R model. •r={role, (role, #role)∈Res, role.resources ={resk,k ∈[1 ...#role],res k· acts ={ai∈acts, ai·res =resk}}}, i.e. there is one object of type Role in rfor each role in Res. Moreover, for each object of type Role role,thereare #role objects of type Resource in the list resources of role. Each object of type Resource reskcontains, in turn, an ordered list of objects of type P&SAct which are related to the P&S activities which are allocated in that resource. Furthermore, the equivalence between Definition 5.6 and Algorithm A.1 is detailed as follows: •(1) in Definition 5.6 is equivalent to line 2 in Algorithm A.1, i.e. both include a pool for each role in the resulting BPMN model. •(2) in Definition 5.6 is equivalent to lines 3–5 in Algorithm A.1, i.e. both include a BPMN activity for each BP activity, plus one activity related to the start BPMN activity, plus one activity related to the end BPMN activity. •(3) in Definition 5.6 is equivalent to lines 6–20 in Algorithm A.1. The set predecessors in Definition 5.6 (cf. (3)) states the direct precedences between all the activities, including: the precedences between the P&S activities, and the precedences in which the BPMN start and end activities are involved. However, in Algorithm A.1, the precedences in which the BPMN start and end activities 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 are involved are handled differently from the rest of activities due to implementation reasons. The equivalence between (3) in Definition 5.6 and lines 6–20 in Algorithm A.1 is explained as follows: — (3)(i) in combination with (3)(a) in Definition 5.6 is equivalent to line 6 in Algorithm A.1, i.e. both include sequence flows between the BPMN start activity and all the activities whose start time is equal to 0 (i.e. are direct successors of the start activity). Specifically, in (3)(i) all the precedence relations in which the start activity is involved are included in the set P redecessors, and in (3)(a) sequence flows between the start activity and all its direct successors are included. However, in Algorithm A.1, these sequence flows are directly included in line 6. Note that the start activity is never involved in parallel merging gateways since this activity does not have any predecessor. — (3)(ii) in combination with (3)(a) and 3(b) in Definition 5.6 is equivalent to lines 15–20 in Algorithm A.1, i.e. both include either a sequence flow or a parallel merging gateway between the BPMN end activity and all its direct predecessors. Specifically, in (3)(ii) all the precedence relations in which the end activity is involved are included in the set P redecessors. In a similar way, in line 15 of Algorithm A.1, all the direct predecessors of the end activity are stored in the set finals. Then, if there is only one direct predecessor for the end activity, a sequence flow between this predecessor and the end activity is included (lines 16–18 in Algorithm A.1, (3)(a) in Definition 5.6). However, if there are more than one direct predecessor for the end activity, a parallel merging gateway between all predecessors and the end activity is included (lines 19 and 20 in Algorithm A.1, (3)(b) in Definition 5.6). Note that the end activity may be involved in parallel merging gateways since this activity may have more than one predecessor. — (3)(iii) in combination with (3)(a) and 3(b) in Definition 5.6 is equivalent to lines 7–14 in Algorithm A.1, i.e. both include either a sequence flow or a parallel merging gateway between each activity and all its direct predecessors. Specifically, in (3)(iii) all the precedence relations in which each activity is involved are included in the set P redecessors. In a similar way, in line 7 of Algorithm A.1, all the direct predecessors of each activity are stored in the map pred. For this, Algorithm A.2 (i.e. CreateDependencies) is used. Algorithm A.2 is equivalent to (3)(iii) since, as demonstrated in Proposition A.1, Algorithm A.2 returns a map which relates each activity with its direct predecessors (cf. Definition 5.4). Then, for each activity (line 8 in Algorithm A.1) if there is only one direct predecessor for that activity, a sequence flow between this predecessor and the activity is included (lines 9–11 in Algorithm A.1, (3)(a) in Definition 5.6). However, if there are more than one direct predecessor for that activity, a parallel merging gateway between all its predecessors and the activity is included (lines 12–14 in Algorithm A.1, 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 (3)(b) in Definition 5.6). Note that each activity may be involved in parallel merging gateways, since it may have more than one predecessor. References 1. M. Weske, Business Process Management: Concepts, Languages Architectures (Springer, Berlin, Germany, 2007). 2. M. Dumas, W. van der Aalst and A. ter Hofstede, Process-Aware Information Systems: Bridging People and Software Through Process Technology (Wiley-Interscience, Hoboken, NJ, 2005). 3. G. Group, Leading in Times of Transition: The 2010 CIO Agenda (EXP Premier Report No. January 2010), in Report,Gartner,Inc(2010). 4. W. van der Aalst, A. ter Hofstede and M. Weske, Business process management: A survey, in Proc. BPM (2003), pp. 1–12. 5. R. Aguilar-Sav´en, Business process modelling: Review and framework, Int. J. Prod. Econom. 90(2) (2004) 129–149. 6. J. Barjis and A. Verbraeck, The relevance of modeling and simulation in enterprise and organizational study, in Proc. EOMAS (2010), pp. 15–26. 7. H. Reijers, Design and Control of Workflow Processes (Springer-Verlag Berlin, Heidelberg, 2003). 8. N. Russell, W. van der Aalst, A. ter Hofstede and D. Edmond, Workflow resource patterns: Identification, representation and tool support, in Proc. CAiSE (2005), pp. 216–232. 9. H. M. Ferreira and D. R. Ferreira, An integrated life cycle for workflow management based on learning and planning, Int. J. Coop. Inform. Syst. 15(4) (2006) 485–505. 10. J. Wainer, F. Bezerra and P. Barthelmess, Tucupi: A flexible workflow system based on overridable constraints, in Proc. SAC (2004), pp. 498–502. 11. M. Pesic, M. Schonenberg, N. Sidorova and W. van der Aalst, Constraint-based workflow models: Change made easy, in OTM Conferences (1) (2007), pp. 77–94. 12. I. Rychkova, G. Regev and A. Wegmann, High-level design and analysis of business processes: The advantages of declarative specifications, in Proc. RCIS (2008), pp. 99–110. 13. D. Fahland, D. L¨ubke, J. Mendling, H. Reijers, B. Weber, M. Weidlich and S. Zugal, Declarative versus imperative process modeling languages: The issue of understandability, in Proc. BPMDS and EMMSAD (2009), pp. 353–366. 14. D. Fahland, J. Mendling, H. Reijers, B. Weber, M. Weidlich and S. Zugal, Declarative versus imperative process modeling languages: The issue of maintainability, in Proc. BPM Workshops (2010), pp. 477–488. 15. P. Pichler, B. Weber, S. Zugal, J. Pinggera, J. Mendling and H. Reijers, Imperative versus declarative process modeling languages: An empirical investigation, in Proc. ER-BPM (2011), pp. 383–394. 16. M. Ghallab, D. Nau and P. Traverso, Automated Planning: Theory and Practice (Morgan Kaufmann, Amsterdam, 2004). 17. P. Brucker and S. Knust, Complex Scheduling (GOR-Publications) (Springer-Verlag, New York, Inc., Secaucus, NJ, USA, 2006). 18. F. Rossi, P. van Beek and T. Walsh (eds.), Handbook of Constraint Programming (Elsevier, New York, USA, 2006). 19. M. Salido, Introduction to planning, scheduling and constraint satisfaction, J. Intell. Manuf. 21(1) (2010) 1–4. 2nd Reading October 9, 2013 9:20 WSPC/S0218-8430 111-IJCIS 1350009 20. Business Process Model and Notation (BPMN), Version 2.0., http://www.omg.org/ spec/BPMN/2.0/ (2011) [Online; accessed 3-October-2011]. 21. C. Ouyang, W. van der Aalst, M. Dumas and A. ter Hofstede, Translating BPMN to BPEL (2006). 22. Web Services Business Process Execution Language Version 2.0: OASIS Standard, http://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.html (2007) [Online; accessed 3October-2011]. 23. M. Reichert and B. Weber, Enabling Flexibility in Process-Aware Information Systems (Springer, 2012). 24. M. Pesic and W. van der Aalst, A declarative approach for flexible business processes management, in Proc. BPM Workshops (2006), pp. 169–180. 25. W. van der Aalst, M. Pesic and H. Schonenberg, Declarative workflows: Balancing between flexibility and support, Comput. Sci. — Res. Develop. 23(2) (2009) 99–113. 26. M. Montali, Specification and verification of declarative open interaction models: A logic-based approach, Ph.D. thesis, Department of Electronics, Computer Science and Telecommunications Engineering, University of Bologna, 2009. 27. P. Dourish, J. Holmes, A. MacLean, P. Marqvardsen and A. Zbyslaw, Freeflow: Mediating between representation and action in workflow systems, in Proc. CSCW (1996), pp. 190–198. 28. J. Wainer and F. De Lima Bezerra, Constraint-based flexible workflows, in Proc. CRIWG (2003), pp. 151–158. 29. R. Lu, S. Sadiq, V. Padmanabhan and G. Governatori, Using a temporal constraint network for business process execution, in Proc. ADC (2006), pp. 157–166. 30. W. M. P. van der Aalst and M. Pesic, DecSerFlow: Towards a Truly Declarative Service Flow Language, in LNCS 4184 (2006), pp. 1–23. 31. I. Barba and C. Del Valle, A constraint-based approach for planning and scheduling repeated activities, in Proc. COPLAS (2011), pp. 55–62 [Online; http://icaps11.icapsconference.org/proceedings/coplas/coplas2011-proceedings.pdf; accessed 3-October2011]. 32. Declare, http://www.win.tue.nl/declare/ (2013) [Online; accessed 11-February-2013]. 33. J. F. Allen, Maintaining knowledge about temporal intervals, in Communications of the ACM (1983), pp. 832–843. 34. I. Barba and C. Del Valle, Filtering Rules for ConDec Templates — Pseudocode and Complexity, http://www.lsi.us.es/∼quivir/irene/FilteringRulesforConDec Templates.pdf (2011) [Online; accessed 3-October-2011]. 35. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York, NY, USA, 1979). 36. C. Courbis and A. Finkelstein, Weaving aspects into web service orchestrations, in Proc. ICWS 2005 (2005), pp. 219–226. 37. S. Zugal, P. Soffer, J. Pinggera and B. Weber, Expressiveness and understandability considerations of hierarchy in declarative business process models, in Proc. BMMDS/EMMSAD 2012 (2012), pp. 167–181. 38. M. La Rosa, M. Dumas, R. Uba and R. Dijkman, Merging business process models, in Proc. OTM, Vol. 6426(1) (2010), pp. 96–113. 39. W. Nuijten and E. Aarts, Sequencing with earliness and tardiness penalties: A review, Eur. J. Oper. Res. 90(2) (1996) 269–284. 40. AristaFlow BPM Suite BPM09-Demo, http://www.uni-ulm.de/einrichtungen/arista flow-forum/screencasts.html (2009) [Online; accessed 05-February-2013]. 41. R. Bellman, Dynamic Programming (Princeton University Press, Princeton, NJ, 1957).