Generating Multi-objective Optimized Business Process Enactment Plans

Generating Multi-objective Optimized Business Process Enactment Plans Andr´es Jim´enez-Ram´ırez1, Irene Barba1, Carmelo del Valle1, and Barbara Weber2 1University of Seville, Dpto. Lenguajes y Sistemas Inform´aticos, Spain {ajramirez,irenebr,carmelo}@us.es 2University of Innsbruck, Department of Computer Science, Austria [email protected] Abstract. Declarative business process (BP) models are increasingly used allowing their users to specify what has to be done instead of how. Due to their flexible nature, there are several enactment plans related to a specific declarative model, each one presenting specific values for different objective functions, e.g., completion time or profit. In this work, a method for generating optimized BP enactment plans from declarative specifications is proposed to optimize the performance of a process considering multiple objectives. The plans can be used for different purposes, e.g., providing recommendations. The proposed approach is validated through an empirical evaluation based on a real-world case study. Keywords: Business Process Management, Constraint Programming, Planning and Scheduling, Constraint-based BP Models. 1 Introduction Nowadays, there exists a growing interest in aligning information systems in a process-oriented way [28] as well as in the effective and flexible management of business processes (BPs) [22]. A BP consists of a set of activities which are performed in coordination in an organizational and technical environment [28], and which jointly realize a business goal. Typically, BPs are specified in an imperative way. However, declarative BP models (e.g., constraint-based models) are increasingly used allowing their users to specify what has to be done instead of how [19]. Declarative specifications facilitate the human work involved, avoid failures, and allow to obtain a better optimization, since the tacit nature of human knowledge is often an obstacle to eliciting accurate BP models [10]. Due to their flexible nature, frequently several ways to execute declarative process models exist, i.e., there are several enactment plans related to a specific declarative model, each one presenting specific values for different objective functions, e.g., overall completion time or profit. The decision about the way to execute this model can be quite challenging since usually many constraints need to be obeyed, multiple instances of a process get concurrently executed within a particular timeframe, shared resources need to be allocated, and relevant objective functions should be considered. Temporal & Data Constraints obtains Constraint-based Approach Model Search Filtering Rules 1. ConDec-R Activity Attributes Number of Instances Resource Availabilities Basic constraint-based specification (ConDec) Recommendations Simulation Time Prediction Optimized BP Models 3. 3. Optimized Execution Plans 3. Optimized Execution Plans 2. Multi-objective Optimized Enactment Plans Resource Requirements Fig. 1. Overview of our Approach In this work, a method for generating optimized BP enactment plans from declarative specifications is proposed to optimize the performance of a process by considering multiple objectives. For this, we propose an extension of Con- Dec [19] motivated by requirements described in literature [18,29] (i.e., dealing with temporal and data constraints) and imposed by the case studies we have conducted (i.e., dealing with activity attributes, resource management), named ConDec-R. Specifically, we extend ConDec by considering (1) temporal and data constraints, (2) resource requirements for activity executions, and (3) estimates for some activity attributes (e.g., duration), number of process instances executed within a particular timeframe, and resource availabilities. Figure 1 provides an overview of our approach. Taking the ConDec-R specification as a starting point (cf. Fig. 1(1)), multi-objective optimized enactment plans can automatically be generated (cf. Fig. 1(2)). For this, activities to be executed have to be selected and ordered (planning problem [12]) considering all the constraints, resource requirements, and estimates regarding the number of instances executed within a particular timeframe, resource availabilities, and some activity attributes, e.g., activity durations (scheduling problem [5]). For planning and scheduling (P&S) the activities such that the process objective functions are optimized, a constraint-based approach is proposed. The generated plans can leverage the BP management (BPM) life cycle [28], since they can be used for different purposes (cf. Fig. 1(3)), e.g., recommendations [3], simulation [24], time prediction [27], and generation of optimized BP models [21]. The main contributions of this paper are: (1) the definition of a new language for the constraint-based specification of BPs (cf. Sect. 3, Fig. 1(1)), (2) the automatic generation of multi-objective optimized BP enactment plans from ConDec-R specifications through a constraint-based approach (cf. Sect. 4, Fig. 1(2)), (3) the application of the proposed approach to a case study (cf. Sect. 5), and (4) its empirical evaluation (cf. Sect. 6). Initial aspects of the proposed approach have been previously presented (cf. [14]). However, this paper significantly extends [14] by: (1) providing improved expressiveness through choice templates [19], metric temporal constraints [18,29], and data constraints [18], (2) extending the constraint-based approach by including new filtering rules (cf. Sect. 2) for the aforementioned constraints, (3) dealing with alternative resources to enable activities to be performed by different resources, (4) considering multiple objective functions in the optimization, and (5) evaluating the proposal in the context of an actual process, and therefore demonstrating that it can work in practice for managing realistic problems. Section 2 introduces backgrounds, Sect. 3 details the ConDec-R language, Sect. 4 shows the generation of optimized plans, Sect. 5 explains a real example, Sect. 6 deals with the evaluation, Sect. 7 presents a critical discussion, Sect. 8 summarizes related work, and Sect. 9 includes some conclusions and future work. 2 Background Different paradigms for process modelling exist, e.g., imperative and declarative. Imperative process models are well structured representations which specify exactly how things have to be done by explicitly depicting all possible behavior. A declarative model, in turn, is a loosely-structured representation focused on what should be done which specifies all forbidden behavior. Therefore, declarative models are commonly used for representing processes with high variability which can be executed in several ways. We use the declarative language ConDec [19] for specifying constraint-based models (cf. Def. 1) since it allows the specification of 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. Constraints can be added to a ConDec model to specify forbidden behavior, restricting the desired behavior (cf. [19]). ConDec templates are grouped into: 1. Existence constraints: unary relations concerning the number of times one activity is executed, e.g., Exactly(N,A) specifies that A must be executed exactly N times. 2. Relation constraints: positive binary relations used to impose the presence of a certain activity when some other activity is performed, e.g., Precedence(A,B) specifies that to execute activity B, activity A needs to be executed before. 3. Negation constraints: negative relations used to forbid the execution of activities in specific situations, e.g., NotCoexistence(A,B) specifies that if B is executed, then A cannot be executed, and vice versa. 4. Choice constraints: n-ary constraints expressing the need of executing activities belonging to a set of possible choices, e.g., ExactlyChoice(N,{A,B,C}) specifies that exactly N activities of the set {A,B,C}must be executed. Definition 1. Aconstraint-based process model S=(A, CBP )consists of a set of activities A, and a set of executing behavior constraints CBP .Each activity a∈Aare executed arbitrarily often if not restricted by any constraint. To support increased expressiveness of ConDec, several proposals for extensions have been made like metric temporal constraints [18,29] or data relations [18], which are all supported by our proposal. As an example, the temporal constraint Precedence(A,B,[5,10]) specifies that to start the execution of B, A needs to be finished between 5 and 10 time units before. Using data constraints, for example, the earliest and the latest start and end times of an activity, together with the selections of the choice template can be constrained through input data. As an example, the data constraint A.startTime≥Data.T specifies that A can only start after time T of input Data (for more examples see Sect. 5). Due to their flexible nature, there are frequently different ways to execute a constraint-based model in such a way that all constraints are fulfilled. The different valid execution alternatives, however, can vary significantly in how well different performance objective functions (cf. Def. 2) can be achieved. Definition 2. An objective function OF of a BP is a function to be optimized during the BP enactment, e.g., maximization of the profit. For generating plans optimizing the objective functions of constraint-based process models, activities to be executed have to be planned [12] and scheduled [5]. To do this, a constraint-based approach is proposed (cf. Sect. 4). The area of scheduling [5] includes problems in which it is necessary to determine an enactment plan for a set of activities related by constraints (in our context the control-flow constraints, together with the resource, data and temporal constraints). Several objective functions are usually considered to be optimized, e.g., minimization of the overal completion time. In a wider perspective, in planning [12], the activities to be executed are not established a priori, hence it is necessary to select them from a set of alternatives and to establish an ordering. Constraint Programming (CP) [23] supplies a suitable framework for modelling and solving P&S problems [26]. To solve a problem through CP, it needs to be modelled as a constraint satisfaction problem (CSP, cf. Def. 3). Definition 3. ACSP P=(V,D,CCSP )is composed of a set of variables V, a domain of values Dfor each variable in V, and a set of constraints CCSP between variables, so that each constraint represents a relation between a subset of variables and specifies the allowed combinations of values for these variables. To improve the modelling of the problems global constraints, i.e., constraints capturing a relation between a non-fixed number of variables, can be defined. A solution to a CSP consists of assigning values to CSP variables, being feasible when the assignments satisfy all the constraints. Since actual problems typically involve multiple conflicting objective functions (cf. Def. 2), multi-objective constraint optimization problems (MO-COPs, cf Def. 4) are considered in the current work. In MO-COPs, usually no unique optimal solution exists, but a set of Pareto optimal solutions (cf. Def. 5) can be found. Definition 4. AMO-COP Po=(V,D,CCSP ,OFs)is a CSP which also includes a set of objective functions OFs to be optimized. Definition 5. A solution for a MO-COP is Pareto optimal when it is not dominated by any other solution, i.e., for obtaining a better feasible solution in one of the objective functions, at least another objective needs to be deteriorated. To solve multi-objective optimization problems (for more information, the reader is referred to [9]), there are, basically, three approaches: (i) defining a new objective function (i.e., combining the original objective functions) which can be optimized with single objective solvers (e.g., the weighted-sum method [1]), (ii) optimizing one of the objective functions constraining the other ones (e.g., εconstraint method [13]), and (iii) working with a set of Pareto optimal solutions (e.g., evolutionary multi-objective optimization [6]). In this work, the εconstraint method [13] is applied since it appeared well suited for our purposes and typically provides good results. Regardless of the used search method, the global constraints can be implemented through filtering rules (i.e., rules responsible for removing values which do not belong to any solution) to efficiently handle the constraints in the search for solutions. 3 ConDec-R: A Constraint-Based BP Language To specify the processes in a declarative way, ConDec [19] is used as basis (cf. Sect. 2). Motivated by requirements described in literature [18,29] as well as the necessities of the case studies we have conducted (cf. Sect. 5) we extend ConDec to ConDec-R. Besides extending ConDec with resource reasoning and estimates for activity durations (which are partially covered in previous works [2,14]), ConDec-R supports activities with an open set of attributes and alternative resources (cf. Def. 6), and choice, temporal and data constraints. In a ConDec-R process model (cf. Def. 7), all the previously stated extensions are considered. Definition 6. ABP activity BPAct =(a, Res, Atts)represents a BP activity called a, which can be performed by any resource included in Res1,andwhich has a set of attributes associated (e.g., duration and profit) which is composed of tuples <att, val>(i.e., Atts). Definition 7. AConDec-R process model CR = (BPActs, Data, CBP ,Av- Res, OFs) related to a constraint-based process model S = (A,CBP ) (cf. Def. 1) is composed of (1)a set of BP activities (cf. Def. 6) BPActs, (2) problem data information Data, (3) a set of ConDec constraints CBP which relates activities included in BPActs and/or the data included in Data, (4) a set of available resources Res which is composed of tuples (role,#role) which includes for each role (i.e., role) the number #role of available resources2, and (5) a set of the objective functions OFs to be optimized (cf. Def. 2). Figure 2(A) shows a simple ConDec-R model3(cf. Def. 7) where: BPActs ={(A, < R1>, << att1,2>, < att2,6>>),(B,< R2>, << att1,2>, < att2,2>> ),(C, < R1,R2>, << att1,2>, < att2,3>>),(D,< R1,R2>, << att1,3>, < att2,2>>)};Data ={};CBP ={exactly(1,A), exactly(2,B), succession(A, B), response(A, B), negate-response(B,C),precedence(C, D)};Res ={(R1,2), (R2, 2)};andOFs ={OF1,OF2}. 1This allows activities to be performed by alternative resources, whereas in previous works (cf. [2,14]) only one resource can be assigned to each activity. 2The role-based allocation pattern [25] is considered. 3We extend Declare [7] (i.e, a workflow management system that can be used to specify ConDec models) to allow specifying ConDec-R models. R1:2 R2:2 Model and Estimates Constraint-based approach MO-COP Variables //number of sched. activities A:{nt:0..2},B:{nt:0..2},C:{nt:0..2},D:{nt:0..2} //1st and 2sd sched. activities A1:{st:0..26, et:0..26, res:1..2, sel:0..1}, A2:{st:0..26, et:0..26, res:1..2, sel:0..1}, B1:{st:0..26, et:0..26, res:1..2, sel:0..1}, … //B2,C1, C2, D1, D2have same definitions //Objective functions OF1={lbOF1..ubOF1} OF2={lbOF2..ubOF2} MO-COP Constraints et(A1)st(A2), et(B1)st(B2), et(C1)st(C2), et(D1)st(D2) //Relation between nt and sel sel(A1)==nt(A)1, sel(A2)==nt(A)2, sel(B1)==nt(B)1, sel(B2)==nt(B)2, sel(C1)==nt(C)1, sel(C2)==nt(C)2, sel(D1)==nt(D)1, sel(D2)==nt(D)2 //Global constraints exactly(A), exactly(C), succession(A, B), response(A, C), n-response(B,C), precedence(C, D) //Objective functions Max(OF1), Min(OF2) MO-COP Solutions (B) (C) ConDec-R model Gantt Chart Enactment Plan //number of sched. activities A:{nt:1},B:{nt:1}, C:{nt:2},D:{nt:1} //1st and 2sd sched. activities A1:{st:0, et:6, res:1, sel:1}, A2:{sel:0}, B1:{st:7, et:9, res:1, sel:1}, B2:{sel:0}, C1:{st:3, et:5, res:2, sel:1}, C2:{st:6, et:8, res:2, sel:1}, D1:{st:0, et:3, res:1, sel:1}, D2:{sel:0} OCT:{9}d (A) Resource Availability Enactment Plan //number of sched. activities A:{nt:1},B:{nt:1}, C:{nt:2},D:{nt:1} //1st and 2sd sched. activities A1:{st:0, et:6, res:1, sel:1}, A2:{sel:0}, B1:{st:7, et:9, res:1, sel:1}, B2:{sel:0}, C1:{st:3, et:5, res:2, sel:1}, C2:{st:6, et:8, res:2, sel:1}, D1:{st:0, et:3, res:1, sel:1}, D2:{sel:0} OCT:{9}d Enactment Plan //number of sched. activities A:{nt:1},B:{nt:1}, C:{nt:2},D:{nt:1} //1st and 2sd sched. activities A1:{st:0, et:6, res:1, sel:1}, A2:{sel:0}, B1:{st:6, et:9, res:1, sel:1}, B2:{sel:0}, C1:{st:3, et:5, res:2, sel:1}, C2:{st:6, et:8, res:2, sel:1}, D1:{st:0, et:3, res:1, sel:1}, D2:{sel:0} OF1:{9}, OF2: {21} Max(OF1) Min(OF2) Objective Functions Fig. 2. Generating Optimized Enactment Plans from ConDec-R Models 4 From ConDec-R to Optimized Enactment Plans To generate optimal (or optimized) execution plans for a specific ConDec-R model, we propose a constraint-based approach for P&S the BP activities. This includes: the modelling of the problem as a MO-COP, the use of global constraints implemented through filtering rules to improve the modelling of the problems and to efficiently handle the constraints in the search for solutions, and a search algorithm for solving the MO-COP. Representing the ConDec-R model as a MO-COP: Given a process modeled as a ConDec-R model (cf. Def. 7, Fig. 2(A)), it needs to be represented as a MO-COP (cf. Def. 4, Fig. 2(B)). Regarding the proposed MO-COP model, BP activities (repeated activities in the MO-COP model, cf. Def. 8), which can be executed arbitrarily often if not restricted by any constraint, are modelled as a sequence of optional scheduling activities (cf. Def. 9). This is required since each execution of a BP activity (i.e., a scheduling activity) is considered as one single activity which needs to be allocated to a specific resource and temporarily placed in the enactment plan, i.e., stating values for its start and end times. Definition 8. Arepeated activity ra =(a, Res, Att, nt)is a BP activity BPAct =(a, Res, Atts)(cf. Def. 6) which can be executed several times. It defines a CSP variable which specifies the number of times the BP activity is executed (i.e., nt). Definition 9. Ascheduling activity sa =(st, et, res, sel)related to a repeated activity ra =(a, Res, Att, nt), represents a specific execution of ra,wherest and et are CSP variables indicating the start and the end times of the activity execution, respectively, res ∈Res is a CSP variable representing the resource used for the execution, and sel is a CSP variable indicating whether or not the activity is selected to be executed (i.e., equal to 0 in the case that it is not executed andequalto1otherwise). For each repeated activity, ntMAX4scheduling activities exist, which are added to the CSP problem specification, apart from including a variable nt. Moreover, additional CSP variables representing the objective functions to optimize are also included in the MO-COP (cf. Fig. 2(B)). In this way, the ConDec- RmodelCR =(BP Acts, Data, CBP ,AvRes,OFs) (cf. Def. 7) is transformed intoaMO-COPPo= (V, D, CCSP ,OFs)(cf. Def. 4, Fig. 2(B)) where: 1. V={nt(a),a∈BPActs}∪{st(ai),et(ai),res(ai),sel(ai),i∈[1.. ntMAX(a)], a∈BPActs}∪OFs. 2. Dis composed of the domains of each CSP variable var,whereUB(var) and LB(var) represent the upper and lower bounds of the domain of var, respectively. In the example of Fig. 2, the domain [0..2] is used for nt since 2 is the maximum cardinality for the BP activities (established by existence relations in the constraint-based model). The domain [0..26] is used for et and st since 26 would be the completion time if all the scheduling activities were serially executed taking the maximum cardinality for the BP activities into account. 3. CCSP is composed of the resource constraints, the global constraints (implemented by the filtering rules, cf. Sect. 2) related to CBP , and the constraints which are inherent to the proposed model: (a) ∀a∈BPActs ∀i:1≤i<nt(a):et(ai)≤st(ai+1) (i.e., a specific execution of a repeated activity precedes the next execution of the same activity). (b) ∀a∈BPActs ∀i:1≤i≤UB(nt(a)) : sel(ai)==nt(a)>=i(i.e., the nt variable of the repeated activity is directly related to the sel variables of the associated scheduling activities). Resource constraints are not explicitly stated since most constraint-based systems provide a high-level constraint modeling specific to scheduling which includes an efficient management of shared resources. Besides the role-based allocation pattern, the CSP variables which are included in the model can be also used for specifying further resource constraints [25]. Filtering Rules: Many constraint-based approaches for modelling and solving P&S problems have been proposed [23]. Moreover, several proposals exist for filtering rules related to specialized scheduling constraints (e.g., [16,4]). Therefore, the considered problem could be managed by adapting existing constraint-based approaches. However, some ConDec-R templates entail complex reasoning about several combined innovative aspects, such as the alternating executions of activities together with the varying number of times which these activities are executed. Therefore, we implemented our own specific global constraints through innovative filtering rules to facilitate the specification of the problems and to 4ntMAX represents the maximum value for the initial domain of nt (cf. Fig 2(B)). TemporalPrecedence(A,B,[min, max]) -> If LB(nt(B)) > 0 then nt(A) <- nt(A) - {0} If LB(et(act(A,1))) + min > LB(st(act(B,1))))then LB(st(act(B,1)))) <- LB(et(act(A,1))) + min If UB(et(act(A,1))) - max > UB(st(act(B,1))) then UB(et(act(A,1))) <- UB(st(act(B,1))) - max Fig. 3. Propagator for Temporal Precedence Template in ConDec-R OF2 OF1 sol2 sol1 sol2.OF2 Legend sol2.OF1sol1.OF1 Solutions obtained from ܥܱܲ   ைி భ Solutions obtained from ܥܱܲ   ைி మ Solutions obtained from ܥܱܲ௦௢௟మ ைி భ Solutions obtained from ܥܱܲ௦௢௟భ ைி మ Pareto optimized solutions 1/2 1/2 sol1.OF2 Fig. 4. Example of a MO-COP with two objective functions which is solved through four single objective COPs increase the efficiency in the search for solutions. In this way, the constraints stated in the ConDec-R specification (cf. Def. 7) are included in the MO-COP model through the related global constraints (cf. Fig. 2(B)). In the MO-COP, initial estimates are made for upper and lower bounds of variable domains, and these values are refined during the search process by the developed filtering rules. In this work, filtering rules related to constraints which were not considered in previous works5(i.e., [2,14]) have been developed, i.e., choice, temporal and data. As an example, the T emporalPrecedence(A, B, [min, max]) rule is shown in Fig. 3, where the propagator that describes the pruning of domains appears after symbol →. This constraint means that between min and max units of time before the first execution of B, at least one execution of Amust be executed. Solving the MO-COP: Once the problem is modelled, several constraint-based mechanisms can be used to obtain the solutions for the MO-COP (cf. Def. 4), i.e., multi-objective optimized enactment plans (cf. Def. 10, Fig. 2(C)). As stated in Sect. 2, we implemented a multi-objective optimization search algorithm based on the ε-constraint method [13]. In Fig. 4 the search algorithm is applied over a problem with two objective functions (OF1and OF2). For this example, our approach performs the following steps: 5A detailed description of the developed basic ConDec-R filtering rules can be found at http://regula.lsi.us.es/MOPlanner/FilteringRules.pdf 1. Two single-objective constraint optimization problems (COPs) are generated (i.e., COPOF1and COPOF2) with the goal of optimizing (maximizing in this example) OF1and OF2respectively. 2. These two COPs are solved and therefore an optimized solution is found for each one (i.e., sol1and sol2respectively) along with a set of intermediate solutions. 3. Two new COPs (i.e., COPOF2 sol1and COPOF1 sol2) which include a constraint over the value of the objective function that is not optimized (i.e., OF2≥ |sol1.OF2−sol2.OF2|/2andOF1≥|sol2.OF1−sol1.OF1|/2 respectively6) are generated. 4. These two new COPs are solved and new solutions are obtained. 5. From all the obtained solutions, those solutions which are not Pareto optimal (cf. Def. 5) are removed. Definition 10. ABP enactment plan consist of: (i) the number of times each repeated activity is executed, (ii) the start and end times for each activity execution (i.e., scheduling activity), and (iii) the resource which is used for each scheduling activity. The generated enactment plans can be graphically represented by a Gantt chart (cf. Fig. 2(C)). This chart illustrates the activity schedules and allows users to understand the solution at a glance. Moreover, the relations between executions of activities are depicted in the Gantt chart due to the ConDec-R constraints of the model (e.g., the relation between the first execution of Dand the first execution of Cis due to the constraint precedence(C, D)). Since the generation of optimized plans presents NP-complexity [11], it is not possible to ensure the optimality of the generated plans for all the cases. The developed constraint-based approach, however, allows solving the considered problems in an efficient way (cf. Sect. 6). 5 A Real Example: A Beauty Salon of Seville Motivation: The considered business (i.e., a beauty salon) has grown considerably in the last years. It has expanded from a small salon with three employees to six and included additional facilities to be able to offer additional services. These changes, including the quick growth together with the complex constraints which need to be obeyed, resulted in problems related to the management of the salon. In particular, long waiting time for clients and missing schedules for employees are causing problems, affecting customer satisfaction and profit of the business. Improving the Management: The goal of the business is to improve the current situation by using a constraint-based approach for optimizing its BPs. Since our approach generates optimized enactment plans, optimized schedules for employees can be suggested, and therefore, the aforementioned problems can 6The symbol ≥is used since maximization of the objective functions is considered in the example of Fig. 4. The symbol ≤wouldbeusedforminimization. References 1. Athan, T.W., Papalambros, P.Y.: A note on weighted criteria methods for compromise solutions in multi-objective optimization. Eng. Optim. 27(2), 155–176 (1996) 2. Barba, I., Del Valle, C.: A Constraint-based Approach for Planning and Scheduling Repeated Activities. In: Proc. COPLAS, pp. 55–62 (2011) 3. Barba, I., Weber, B., Del Valle, C.: Supporting the Optimized Execution of Business Processes through Recommendations. In: Proc. BPI (2011) (in press) 4. Bartak, R., Cepek, O.: Incremental propagation rules for a precedence graph with optional activities and time windows. Trans. Inst. Meas. Control 32(1), 73–96 (2010) 5. Brucker, P., Knust, S.: Complex Scheduling (GOR-Publications). Springer-Verlag New York, Inc, Secaucus (2006) 6. Cheng, D., Li, F.Y.: Multiobjective optimization design with pareto genetic algorithm. J. Guid. Control Dyn. 19, 392–397 (1997) 7. Declare. Declare: Declarative Approach to Workflow Management Systems (2011), http://www.win.tue.nl/declare/ (accessed May 1, 2012) 8. Dynadec. Comet Downloads (2010), http://dynadec.com/support/downloads/ (accessed May 1, 2012) 9. Ehrgott, M., Gandibleux, X.: Multiobjective combinatorial optimization - theory, methodology, and applications. In: Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Int. Series in Op. Res. & Man. Sci, vol. 52, pp. 369–444 (2003) 10. Ferreira, H.M., Ferreira, D.R.: An integrated life cycle for workflow management based on learning and planning. Int. J. Cooper Inform. Syst. 15(4), 485–505 (2006) 11. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979) 12. Ghallab, M., Nau, D., Traverso, P.: Automated Planning: Theory and Practice. Morgan Kaufmann, Amsterdam (2004) 13. Haimes, Y.Y., Lasdon, L.S., Wismer, D.A.: On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans. on Syst. Man. Cybern. 1, 296–297 (1971) 14. Jim´enez-Ram´ırez, A., Barba, I., Del Valle, C., Weber, B.: OptBPPlanner: Automatic Generation of Optimized Business Process Enactment Plans. In: Proc. ISD. Springer (2012) (in press) 15. Krogt, R., Geraghty, J., Salman, M.R., Little, J.: On supporting lean methodologies using constraint-based scheduling. J. of Scheduling 13, 301–314 (2010) 16. Laborie, P., Rogerie, J., Shaw, P., Vilim, P.: Reasoning with conditional timeintervals. part ii: An algebraical model for resources (2009) 17. Lu, R., Sadiq, S., Governatori, G., Yang, X.: Defining adaptation constraints for business process variants. In: Abramowicz, W. (ed.) BIS 2009. LNBIP, vol. 21, pp. 145–156. Springer, Heidelberg (2009) 18. Montali, M.: Specification and Verification of Declarative Open Interaction Models: a Logic-Based Approach. PhD thesis, Department of Electronics, Computer Science and Telecommunications Engineering, University of Bologna (2009) 19. Pesic, M.: Constraint-Based Workflow Management Systems: Shifting Control to Users. PhD thesis, Eindhoven University of Technology, Eindhoven (2008) 20. Process Specification Language project (1977), http://www.nist.gov/psl/ (accessed May 1, 2012) 21. R-Moreno, M.D., Borrajo, D., Cesta, A., Oddi, A.: Integrating planning and scheduling in workflow domains. Expert Syst. Appl. 33(2), 389–406 (2007) 22. Reichert, M., Weber, B.: Enabling Flexibility in Process-Aware Information Systems. Springer (2012) 23. Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier (2006) 24. Rozinat, A., Wynn, M.T., van der Aalst, W.M.P., ter Hofstede, A.H.M., Fidge, C.J.: Workflow simulation for operational decision support. Data Knowl. Eng. 68(9), 834–850 (2009) 25. Russell, N., van der Aalst, W.M.P., ter Hofstede, A.H.M., Edmond, D.: Workflow resource patterns: Identification, representation and tool support. In: Pastor, ´ O., Falc˜ao e Cunha, J. (eds.) CAiSE 2005. LNCS, vol. 3520, pp. 216–232. Springer, Heidelberg (2005) 26. Salido, M.A.: Introduction to planning, scheduling and constraint satisfaction. J. Intell. Manuf. 21(1), 1–4 (2010) 27. van der Aalst, W.M.P., Schonenberg, M.H., Song, M.: Time prediction based on process mining. Inform. Syst. 36(2), 450–475 (2011) 28. Weske, M.: Business Process Management: Concepts, Languages, Architectures. Springer (2007) 29. Westergaard, M., Maggi, F.M.: Looking into the future: Using timed automata to provide a priori advice about timed declarative process models. In: Meersman, R., Panetto, H., Dillon, T., Rinderle-Ma, S., Dadam, P., Zhou, X., Pearson, S., Ferscha, A., Bergamaschi, S., Cruz, I.F. (eds.) OTM 2012, Part I. LNCS, vol. 7565, pp. 250– 267. Springer, Heidelberg (2012)