Decision-making support for input data in business processes according to former instances

Computer Science and Information Systems 18(3):835–865 https://doi.org/10.2298/CSIS200522051P Decision-Making Support for Input Data in Business Processes according to Former Instances Jos´ e Miguel P´ erez ´ Alvarez1, Luisa Parody2, Mar´ ıa Teresa G´ omez-L´ opez3, Rafael M. Gasca3, and Paolo Ceravolo4 1NAVER LABS Europe 6 Chemin de Maupertuis, 38240 Meylan, France [email protected] 2Universidad Loyola Andaluc´ ıa Avda. de las Universidades s/n. 41704 Dos Hermanas (Sevilla), Espa˜ na [email protected] 3Universidad de Sevilla Av. Reina Mercedes s/n, 41012 Sevilla, Espa˜ na {maytegomez,gasca}@us.es 4Universita’ degli Studi di Milano Via Festa del Perdono, 7, 20122 Milano, Italy paolo.cerav[email protected] Abstract. Business Processes facilitate the execution of a set of activities to achieve the strategic plans of a company. During the execution of a business process model, several decisions can be made that frequently involve the values of the input data of certain activities. The decision regarding the value of these input data concerns not only the correct execution of the business process in terms of consistency, but also the compliance with the strategic plans of the company. Smart decision-support systems provide information by analyzing the process model and the business rules to be satisfied, but other elements, such as the previous temporal variation of the data during the former executed instances of similar processes, can also be employed to guide the input data decisions at instantiation time. Our proposal consists of learning the evolution patterns of the temporal variation of the data values in a process model extracted from previous process instances by applying Constraint Programming techniques. The knowledge obtained is applied in a Decision Support System (DSS) which helps in the maintenance of the alignment of the process execution with the organizational strategic plans, through a framework and a methodology. Finally, to present a proof of concept, the proposal has been applied to a complete case study. Keywords: Business processes, Input Data, Decision-making support, Evolution Models of variables, Constraint Programming, Process Instance Compliance 1. Introduction The operational plans of organizations are documents that include in detail all technical and organizational aspects related to the development of their products or services. Organizations frequently perform their operations by using Business Processes to support the services offered. A Business Process consists of a set of activities that are performed in 836 Jos´ e Miguel P´ erez ´ Alvarez et al. coordination within an organizational and technical environment to achieve an objective [43]. In process orientation, business processes are the main instrument for the organization [18], where commercial Business Process Management Systems are incorporated to facilitate the automation and monitoring of their daily processes, and that they are aligned with their objectives and data at the same time [32]. These systems support the implementation, coordination, and monitoring of the business process executions, and produce a great quantity of data that can be stored for its later application in deriving a data evolution pattern temporal variation. In order to maintain the correct management defined in the strategy plans, companies evaluate the status of the organization by analyzing the suitability of their Key Process Indicators (henceforth referred to as KPI) [34]. However, some of the decisions made during the process instances take into account information not available when the decisions are made, because it depends on the activities that will be executed later in the process and how the KPIs will evolve in the future. The process model describes activities that will be executed until the process instance ends. However, to know how the KPIs will evolve, it is necessary to analyze former instances, and the values of the variables that represent the measurements concerning the evolution of the process instances. This data allows a target value to be monitored over specific periods through extraction this value from the execution of business processes. For this reason, this set of observational variables represents the stage of the business, in terms of measurements. In this paper, we propose a methodology to support the decisions about the values of input variables in business process instances introduced by the business experts at runtime. Frequently, these decisions are made by the expert experience, that can be partial and subjective. But, what can be done when the process instance evolution is not aligned with the KPIs defined. For this reason in this paper, we support the decision-making for the alignment of the execution of the processes with the KPIs, guided by how previous instances of the same process evolved. To clarify our contribution, the application of our proposal will be illustrated using an example. In the organization of a scientific conference, a set of decisions must be made. Months before the celebration and the attendees are registered, the business experts must decide the early and late registration fees, the venue, or the number of proceedings to print. These decisions affect the successful execution of the conference. Usually, to make these decisions, experts consult previous editions of the same or similar conferences. The analysis of how the number of registrations evolves, and how it is affected by the proximity to the end of the early registration period can avoid making incorrect decisions. Furthermore, the decision-makers can check if the information obtained is aligned with the business goals and organizational constraints. 1.1. Challenges A methodology to guide decision point during process instantiation was addressed in previous work [15,14]. That methodology was based on modeling the restrictions extracted from the operational plans, by using a special type of Business Rules called Business Data Constraint [16]. However, the previous approximations fail in the following aspects, which are tackled in the current paper: Decision-Making Support for Input Data in BP according to Former Instances 837 –Analyze the temporal variation of the relevant data during the process instances by consistently incorporating the fluctuating patters, their trends and recurring behavior. –Incorporate into the decision point results obtained by cases with analog contextual patterns. The activities executed during each instance describe the stage of an instance, although other factors can influence the temporal variation of the data involved. –The degree of uncertainty of the variables handled at the decision points, was not accounted in the previous methodology. It is essential to include this uncertainty since it is not the same to decide the value of a variable in an initial stage of the business process instance, in which its uncertainty is very high, as is in an advanced stage, in which the uncertainty is reduced. 1.2. Objectives Taking into account the above challenges, in this paper we propose an extension of the previous study to achieve the objective: The creation of a methodology that supports the decisions made during the process model execution about the input data values. The basis of the methodology is to provide the proper range of values taking into account the stage of the instance and the possible evolution of the variables in the future according to analog models, i.e. related former-instances. This objective implies the achievement of the three following sub-objectives: 1. Problem Modeling: During modeling time, the different parts of the problem are incorporated using the business Expert Knowledge. The elements that must be modeled are: The Business Process Model,Dictionary,Stages and Business Rules. 2. Creation of evolution patterns of variables: Before starting the instance in which decisions have to be made, it is necessary to create the the patterns of the data temporal variation, by analyzing how they evolved in analog models. 3. Decision-making support for input data at runtime: For each decision, the system uses the knowledge extracted from data temporal variation in previous instances, adapted to the current stage of the Process-Observational Variables in the decisionmaking moment. This is performed by using the Constraint Programming paradigm that provides different techniques to solve constraint problems. Thanks to this new approach, the board and executive team of an enterprise can compare the current status of an instance with previous statuses, thereby helping to maintain the alignment of all business processes with the defined KPIs. On the other hand, thanks to the base of knowledge obtained, we will have the capacity to predict how the business instance will evolve, and how undesirable variation can be detected at an earlier stage. The paper is organized as follows: Section 2 introduces a real world case study, used throughout the paper to illustrate the various aspects. Section 3 presents a graphical overview of the basic aspects of the methodology. The subsequent three sections describe the three phases of the methodology: Problem Modeling in Section 4, creation of variable evolution pattern in Section 5, and Decision-making support for the input data phase in Section 6. Section 7 describes related work. Finally, conclusions are drawn and future work is proposed in Section 8. 838 Jos´ e Miguel P´ erez ´ Alvarez et al. 2. Case Study In order to describe our proposal, a case study is presented to make the methodology accessible. The case study is a sample extracted from an event organization company focused on conferences. The company offers the service by using a web-based application, through which the customers can manage the conferences that they organize. Thanks to this service, the company has a large database of past events that can be consulted in order to improve decisions regarding conferences of the future. Figure 1 shows the process that support a conference organization that follows the operational business plans of the company. The example represents a research conference where participants can present a research work that has been previously reviewed and accepted. The process has been simplified to illustrate the example. Conference Chair Attendees Authors Select available conference Make payment (1) Conference management process (3) Registration Management process Select available conference with open submission process Register paper data (2) Submission process review Receive notification Configure conference and publicity Print proceedings Book dinner Contact partners Book lunch Hold conference Prepare final report and make payment Review of papers Submission closes lunchPrice Hire venue venueCost earlyRegFee lateRegFee publicity income – expenses < 4000 Invite speakers numberOfProceedings galaDinnerPrice speakersCost Fig. 1. Example of processes for Conference Organization. The process Conference management is performed by the Conference Chair, and supports the operations for the establishment and management of the conference organization. The first task is to Configure conference and publicity, where the conference chair decides to set up the parameters of the conference, by defining the initial data values. Some of this data, represented by means of variables in the process, is related to registration fees at different times, available budgets, and the important dates. There is a data element associated with the activity Configure conference and publicity where the input variables, whose values must be established, are depicted (e.g. early registration fee, late registration fee, date of submission closes, date of early registration closes, etc.). Once the conference is configured, some values of the input variables cannot be changed, for example, the early registration fee, this is why to take into account how the process instance can evolve is so relevant. Afterwards, Contact partners is performed in parallel with the Review of papers, as shown in Figure 1. These two latter activities can start once the Submission time has expired. Subsequently, the Print proceedings and Hire venue tasks are executed in parallel. The subsequent steps are Book gala dinner and in parallel Book lunch. In the case where a profit of more than 4,000 euros is expected, speakers can be invited. This is performed in the task Invite speakers. Finally, the conference takes place Decision-Making Support for Input Data in BP according to Former Instances 839 when the task Hold conference is executed, and payments and final reports are performed in the task Prepare final reports and make payments. The second process, (2) Submission, is carried out by Authors. The first task is Select available conference with open submission process, since several conferences can be available for the submission of contributions at the same time. The next task consists of collecting information on the author and the contribution in Register the paper data. The author must subsequently wait until the revision is completed. Finally, the author is notified once the task Receive notification is executed. The third process is (3) Registration management, which is in a pool assigned to the Attendees for their registration in a conference. This case study is challenging for several reasons: (1) it includes several actors in the process: organizers, authors, reviewers, and attendees; (2) there is a relationship between various processes with a significant number of shared variables, such as conference id, number of attendees, etc.; and (3) there are many decisions about variable values needed throughout the process that are key to the success of the process: registration fees, venue cost, lunch and gala dinner prices, etc. One of the main problematic issues of the conference organization is that several decisions must be made before a specific value is known. Many activities include decisions on the value of variables that are key to the successful celebration of the conference. For example, in the Configure conference and publicity activity, the values of registration fees are established without knowing the number of participants. A low registration fee and few attendees could mean that no speakers can be invited to give the keynotes or there may not be enough money to hire the gala dinner. In order to avoid this type of problems, these decisions tend to be made according to the previous experiences of the organizers, but frequently based on subjective aspects. The evolution of the number of papers sent, or the number of early registered can give clues about how the process instance can evolve in the future, making the current decisions more proper and accurate. Without the use of a decision-making support system, the organizer of a conference cannot come ahead of time when the number of attendance are not evolved as expected (in comparison with previous instances), and how the decisions of the future can be made to avoid an unwanted situation. Thanks to our proposal, the organizers can obtain information of previous instances and make decisions according to this information at runtime. Following with the keynotes problem and let’s assume that income is only dependent on registrations. When the organizers have to decide who to invite to give a keynote, they are going to have available not only the number of people registered up to that moment, but also how that value is evolving with respect to previous instances. If the evolution is very negative (many less registered), our framework will let the organizers know how much money they will have available approximately according to that evolution. How the framework is integrated in the business process and in which points the decisions are made are explained in the following sections. 3. Methodology for Decision-Making Support of Input Data The main objective of our proposal is to assist the business experts in the decision-making during process execution. Figure 2 graphically summarizes our methodology. The summary is introduced in this section, and details are provided in the following sections. 840 Jos´ e Miguel P´ erez ´ Alvarez et al. Problem Modelling Business Processes Model (M) Former instances (FI) BPMS Creation of pattern behaviour BPMS Decision maker variable DSS CSP instance CSP engine Range of values Decision-making support for input data Instance under decision Business expert step Automatic step Decision maker Dictionary Subsection 4.2 Business Policies Subsection 4.3 CSP template DSS Subsection 5.3 Comparable instances DSS DSS Evolution of the POVar Filter executions Subsection 5.1 Subsection 5.2 Section 6 # # Subsection 4.4 State description Decision Points Subsection 4.5 Fig. 2. Steps of the Methodology proposed. 1. Problem Modeling: This takes place during the definition of the business process by the business expert as detailed in Section 4: –The Business Process Model must be included to describe the behavior of the organization (Subsection 4.1). –The Dictionary of Process-Observational Variables is defined, with the objective of maintaining a common language that facilities the following steps of the methodology, explained in Subsection 4.2. –Business Rules enrich the Business Process Model to describe the business rules involving Process-Observational Variables as described in Subsection 4.3. –The set of relevant Stages (S), in which the Business Process Instances (BPI) can be, must be defined. Based on the strategic plans of the company and the business experts’ knowledge, in Subsection 4.4 we propose a mechanism to model and compute the Sthat represents the BPI temporal variation. –Identify activities where decisions will be made, so that different decision points can be pinpointed in the business process (Subsection 4.5). 2. Creation of the evolution pattern of the variables: The temporal variation of the relevant variables and how each stage can affect them is fundamental in the later decision-making process. Since the BPI works in various ways, the selection of a subset of instances similar to the instance subject to a decision is essential. Section 5 details the following information: –A mechanism enables business experts to specify the Comparable Instance criteria, to select the former instances that are more related to the instance under decision. These aspects are discussed in Subsection 5.1. –According to the Comparable Instance and by analyzing the former instances, the temporal variations of the Process-Observational Variables are obtained as Decision-Making Support for Input Data in BP according to Former Instances 841 detailed in Subsection 5.2. The discovery of the evolution pattern is crucial for the understanding of how the business works, thereby helping in the decisionmaking process. –A model template is automatically created by traversing Business Process Models and combining the Business Rule associated with each activity. Once the evolution patterns are created, we propose the use of the Constraint Programming Paradigm, thereby creating a Constraint Satisfaction Problem template that contains the temporal variation patterns obtained and the structure of the process, as detailed in Subsection 5.3. 3. Decision-making support for input data: During the execution of each Decision Point in an instance under decision, decisions regarding input data can be made. In order to determine the correct input domain, we propose the combination of the current stage with the Constraint Satisfaction Problem created in the previous step, as discussed in Section 6. 4. Problem Modeling The model of the problem is composed of a Business Process Model, a Dictionary of Process-Observational Variables, the Business Rules, the Stage descriptions, and the Decision Points. Each component is described in the following subsections. 4.1. Business Process Model Business Process Models permit the description of the activities developed by an organization. The standard BPMN 2.0 [31] is usually employed for this purpose. The example of Figure 1 includes three business processes. Business Processes can include: a start event, end events, activities, gateways, and conditions associated with the gateway branches (OR and XOR). These components are combined in a control flow structure that manages the order of execution of the activities. 4.2. Dictionary (D) In order to describe the relevant control variables that will be involved in the business rules and in the KPIs, the business experts must describe the Dictionary of terms. A Dictionary is formed of a set of Process-Observational Variables {POVar1,. . ., POVarn}, whose values are relevant for the organization to know whether their policies comply and their KPIs are reached or not. Each Process-Observational Variable is composed of a name of the variable and its description (hname, descriptioni). The description contains information that enables its value to be extracted from the Business Process Management System for each instance. In our case study, examples of the Process-Observational Variables include: –earlyRegFee: Cost in the early registration period. –lateRegFee: Cost in the late registration period. –maxPapers: Maximum number of papers that can be accepted. –submissionOpen: Date when the paper submission opens. 842 Jos´ e Miguel P´ erez ´ Alvarez et al. –regOpen: Date when the registration opens. –earlyRegClose: Date when the early registration closes. –submissions: Number of submissions to the conference. –earlyReg: Number of registrations in the early registration period. –totalReg: Number of attendees. –sponsorship: Total amount reached by sponsors. –acceptedPapers: Number of accepted papers. In order to describe the meaning of the Process-Observational Variables and to automatically evaluate and monitor these variables, the use of Process Instance Query Language (PIQL) [33] is proposed. PIQL enables business experts to extract information from the process instances that match with specified criteria, and includes a set of operations over the selection. Not only does PIQL allow the selection of instances under execution, but also that of former instances. PIQL is oriented to business experts, offering a naturallanguage-like specification. It should be borne in mind that although PIQL is the language selected to specify Process-Observational Variables, the study of PIQL itself remains outside of the scope of this paper. Certain details are provided below for a better understanding, but the formal syntax, and in-depth details are available in [33]. The types of operations that can be performed over processes and task instances can be seen in Table 1. Table 1. Operations over a set of process and task instances. Operation PIQL Syntax Count all selected instances The number of instances of processes Obtain the value of a variable of the data-flow if just one instance matches The value of variable of the process p Obtain the average of values of a variable of the data-flow for the selected instances of a process The average value of variable of the process p Obtain the maximum value of a variable of the dataflow for the selected instances of a process The maximum value of variable in the process p Obtain the minimal value of a variable in data-flow for the selected instance of a process The minimum value of variable in the process p Count the task instances for all the selected instances The number of instances of task t Additionally, the attributes of Table 2 can be used for the filtering of processes and task instances. Moreover, certain arithmetical, logical, and comparison operators can be used. Moreover, a set of predicates can also be used as detailed in Table 3. By using PIQL, several of the Process-Observational Variables specified above can be modeled as follows: –maxPaper: The value of maxPaper of the process “Conference Management”. –regOpen: The value of regOpen of the process “Conference Management”. –submissions: The number of instances of “Submission process” that are finalized. –earlyReg: The number of instances of “Registration Management process” that end before earlyRegClose. Decision-Making Support for Input Data in BP according to Former Instances 843 –totalReg: The number of instances of “Registration Management process” that are finalized. –acceptedPapers: The number of instances of “Submission process” with “accepted” =“true”. –notified: The number of instances of “Author notifications” task of process “Conference Management process”. Table 2. Attributes of process and task instances. Attributes PIQL Syntax idCase with a case id idCase Process Name with a name process name Task Name with a name task name Start with a start date date End with an end date date Cancelled cancelled Who executed by the user user Table 3. Predicates allowed Predicates Transformed pattern are finalized end date is not equal to Null are not finalized end date is equal to Null are cancelled cancelled is not equal to Null are not cancelled cancelled is equal to Null executed by {name}the user is equal to {name} start before {date}a start date is less than {date} end before {date}an end date is less than {date} start after {date}a start date is greater than {date} end after {date}an end date is greater than {date} 4.3. Business Rules The strategic plan of a company is commonly a set of documents written in natural language. These documents must be translated into something computable in order to know whether a Business Process Instance has finalized correctly or not, according to the policies of the companies. Numerous studies propose a variety of taxonomies to classify the definition of business rules [7,19]. One of the most frequent definitions is: A specification, a policy or a standardized procedure, that represents a natural step towards the inclusion of semantic requirements between business functionality and data. However, if the relations between the variables that delineate the Stages of the business have to be described, then Business Rules have the capacity to describe Business Compliance Rules [5]. This is 850 Jos´ e Miguel P´ erez ´ Alvarez et al. Therefore, the normalization process consists of two phases: (1) Displace the start instant of all Comparable Instances to the same instant, Start=1; and (2) Set the different duration of Business Process Instances to a common scale to compare the temporal variation of each variable involved in the various instances. Thanks to this normalization, every instance is scaled to the same duration, where this duration is the maximum duration of the former instances (12 units of time for this example), as shown in Figure 3.b. Once normalized, the Business Process Instances can be compared, and the degree of similarity among the temporal variations can be observed. Table 4 shows an application of the Stages defined by business experts over the set of data shown in Figure 3.a. In this case, we can observe three possible Stages represented with three colors. Three sets of data are obtained (because three stages have been reached), and the results once the stage is started are shown graphically in Figure 4. Table 4. Variable Registrations with the stages colored in each instance t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 P1 0 0 0 0 0 0 0 0 0 0 1 3 4 5 7 8 9 10 12 13 P2 0 2 3 5 6 8 10 11 13 14 16 18 19 21 22 28 35 43 54 67 P3 00000000000000000000 t 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 P1 14 16 17 18 20 21 22 23 25 26 29 31 35 38 42 46 51 56 61 67 P2 P3 2 3 5 6 8 12 19 29 44 67 Finding out the Envelopment Temporal Variation of Process-observational variables Once the temporal variation of the variables is normalized, techniques of knowledge extraction can be applied. For every detected possible combination of Stages and all variables in these Stages, this step consists of computing the minimum and maximum slope of the Process-Observational Variable. It represents the degree by which the variable increases or decreases, from the Stages understudy, to the final value of the variable, at the point of finalization. This implies the computing of the maximum and minimum percentage of increment or decrement of the variable from the Stages to the end of the process. Slopes for early stages contain more uncertainty than those for late stages; however, this information will be beneficial in the estimation of the potential final range of values of the Decision Variable. There exist numerous references in the literature, where methodologies and techniques are proposed for the creation of models by using the observations, such as curve fitting [24], linear regression [29], and non-linear regression [30]. These models are needed for the computation of the potential increase or decrease of the variable, and hence, our proposal is based on the calculation of the slopes, although other techniques, such as those described below, could be applied. The slopes are computed by dividing the difference between the final and initial value by the duration of the process. Minimum and Maximum slopes are calculated by taking Decision-Making Support for Input Data in BP according to Former Instances 851 -2 8 18 28 38 48 58 68 0 5 10 15 20 P1 P2 P3 (a) Stage: Not started -2 8 18 28 38 48 58 68 0 5 10 15 20 P1 P2 P3 (b) Stage: Started, not notified -2 8 18 28 38 48 58 68 0 2 4 6 8 10 P1 P2 P3 (c) Stage: Started, notified Fig. 4. Variable normalized according to the stage minimum and maximum values into account, as shown in Figure 5 where the Stages is “started, not notified”. This consists of calculating the slopes by using the lowest value for any instance at the beginning of the stage, and the lowest final value of an instance for the computation of the minimal slope. On the other hand, by using the highest values at the beginning of the stage for any instance and the highest values at the end of the process, the maximum slope is computed. 5.3. Combination of the element of the Models by means of a CSP template Once the different elements of the model have been described or derived from former instances, they must all be combined for overall reasoning. This implies to link the business rules to the activities, along with the Decision Points and the possible envelopment variation according to the stages. We propose to use an approximation similar to [15], where 852 Jos´ e Miguel P´ erez ´ Alvarez et al. State “started, not notified” Units of time (time) Registration (reg) 𝑀𝑎𝑥𝑆𝑙𝑜𝑝𝑒 = * MaxFreg - MaxIreg MaxFtime*−MaxItime Max final value (MaxFtime, MaxFreg) Min final value (MinFtime, MinFreg) Min initial value (MinItime, MinIreg) Max initial value (MaxItime, MaxIreg) 𝑀𝑖𝑛𝑆𝑙𝑜𝑝𝑒 = * MinFreg -MinIreg MinFtime*−MinItime Fig. 5. Graphical representation of the max and min slope for one stage the elements were associated to the business process model according to the control-flow structure of the process. The various business rules associated to each activity or set of activities (as explained in 4.3) can be combined in a Constraint Satisfaction Problem to ascertain how the Process-Observational Variables variation can affect each decision. Since the Business Process Model contains elements that route the execution flow of the process (such as gateways), it is necessary to analyze the control-flow structure and its associated business rules. The problem of analyzing the structure of the business process has been addressed in [15], which tackles how to obtain the set of Business Rules in accordance with the control-flow. The basic principles of how the Constraints are combined following the control flow are depicted in Figure 6. The set of patterns to combine the constraints are: –Sequence (Figure 6.a). All the instances must execute these activities, hence all the Business Rules must be satisfied. Therefore they are put together with an AND Boolean relation between them. –AND Split (Figure 6.b). Similarly with the AND split control flow, all the instances have to execute all the activities of the different branches, although the order is unknown. Therefore, the business rules of all these activities will be combined by means of an AND Boolean combination. –XOR Split (Figure 6.c). In the case of the XOR control flow, where only one branch can be executed for an instance, the condition associated with each branch will be combined with the Business Constraints of the activities for each branch. The Business Constraints of the activities of a branch have to be satisfied only if the branch is executed. Therefore, the Business Rules of the activities of the different branches will have an OR Boolean relation between them, and the conditions are combined with an AND Boolean relation with the Business Rules of the activities for each branch. A special treatment is performed for the default branch, where the conditional flow of execution implies the non-compliance of the condition for the rest of the branches, thereby implying the negation of the rest of the conditions. Decision-Making Support for Input Data in BP according to Former Instances 853 A1A2A3 Ca...CkCl...CmCn...Cp (Ca...Ck) ˄ (Cl...Cm)˄ (Cn...Cp) (a) A1A2 Ca...Ck Cl...Cm (Ca...Ck) ˄ … ˄ (Cl...Cm) (b) Branchn + + Branch1 ... A1A2 Ca...Ck Cl...Cm (Ci ˄ (Ca...Ck)) ˅ (Cj ˄ (Cl...Cm)) ˅...˅ ((⌐Cj ˄ ⌐Cj ˄ ...) ˄ (Cp...Cr)) Branch2 X X Branch1 ... (c) Ci Cj Cp...Cr Branchn A1A2 Ca...Ck Cl...Cm (Ci ˄ (Ca...Ck)) ˅...˅ (Cj ˄ (Cl...Cm)) (d) Branchn o o Branch1 ... // Ci Cj Fig. 6. Combination of Business Rules in terms of the control flows and their conditions –OR Split (Figure 6.d). OR control flow is very similar to XOR, the only difference being that more than one branch can be executed, and hence the default option negating the rest of the branches does not appear since this would make no sense. Invar (Start) Config. S1 S2 Review Partner J1 Venue S3J2 Speaker J3 PaymentHold END Print Legend Constraint AND Split JoinEvent XOR Split Fig. 7. BPMN Graph for Conference Organization. These algorithms enable to approach a Business Processes as a BPMN-graph that is traversed to build a Constraint Satisfaction Problem that guides during the decisionmaking process. For example, the BPMN-graph created for the process used in the paper is shown in Figure 7. Each node represents: start event (with the invariant constraints associated); an activity with the associated constraint, if correspond; gateways (and-split, and-join, xor-split, xor-join), and; end event. 854 Jos´ e Miguel P´ erez ´ Alvarez et al. The problem obtained has the following form: CInvariant ∧(CConfig∧(CReview∧CP artner)∧(CP rint∧CV enue)∧(¬(Income− expenses < 4,0000) ∧CSpeak)∧CHold ∧CP aym) The details about the traverse algorithm can be found in [15]. AConstraint Satisfaction Problem (CSP) represents a reasoning framework that consists of of variables, domains, and constraints. Formally, it is defined as a tuple hX,DO, Ci, where X={x1,x2,. . .,xn}is a finite set of variables, DO ={do(x1),do(x2), . . .,do(xn)}is a set of domains of the values of the variables, and C={C1,C2,. . ., Cm}is a set of constraints. Each constraint Ciis defined as a relation Ron a subset of variables V={xi,xj,. . .,xl}, called the constraint scope. The relation Rmay be represented as a subset of the Cartesian product do(xi)×do(xj)×. . . ×do(xl). A constraint Ci= (Vi,Ri)simultaneously specifies the possible values of the variables in Vin order to satisfy R. Let Vk={xk1,xk2,. . .,xkl}be a subset of X. An l-tuple (xk1,xk2,. . ., xkl)from do(xk1),do(xk2),. . .,do(xkl)can therefore be called an instantiation of the variables in Vk. An instantiation is a solution if and only if it satisfies the constraints C. In order to solve a CSP, a combination of search and consistency techniques is commonly used [9]. The consistency techniques remove inconsistent values from the domains of the variables during or before the search. During the search, a propagation process is executed which analyzes the combination of values of variables where the constraints are satisfiable. Several local consistency and optimization techniques have been proposed as ways of improving the efficiency of search algorithms. In a CSP, the inclusion of a constraint in the set Chas the same effect as including this constraint with an AND (∧) relation with the set C. For this reason, the CSP template is composed of: –X:{Related variables defined in the Dictionary }∪{Decision Variables} –DO: Estimated ranges for each variable in X, in the Stages in which the decisions are going to be taken –C:{Business Rules defined for the whole Business Process} ∪ {BDC obtained by traversing the Business Process} Not all Process-Observational Variables defined in Dictionary are included in the CSP template. Only those variables in the intersection between the Process-Observational Variables defined in Dictionary and the set of variables that have been used to define the Business Rules, are included in the CSP template. The reason is that, if Process-Obser- vational Variable is defined in Dictionary but is not used in any Business Rules, then it implies that the variable exerts no affect, and therefore its inclusion can be omitted. This CSP template represents the whole process since the template contains all relevant Process-Observational Variables, and the combined Business Rules are in accordance with the control flow. The only element in the preceding template that needs to be specified is the specific value of the DO of each Process-Observational Variable at the specific moment at which the decision must be made. For the example, the CSP pattern built to analyze the possible valid values of a Decision Variable is presented in Figure 8. The orange parts can be defined with the business process analysis, although the green parts (instantiation of min and max ranges and definition of the input variable to be decided) will depend on the execution decision-making points. Decision-Making Support for Input Data in BP according to Former Instances 855 Instantiation of Min and Max ranges Define the input variables to decide (Decision Variable) Relevant variables of the dictionary maxPapers, submissions, totalReg, … Integer Range of the data-flow variables obtained from the pattern evolution of former instances maxPapers [MINmaxPaper...MAXmaxPaper] Integer submissions [MINsubmissions...MAXsubmissions] Integer ... totalReg [MINtotalReg...MAXtotalReg] Integer Business Constraints obtained by traversing the business model income – expenses >4000 -> speakersCost <= sponsorship*0.3 ... Global Business Policies expenses <= income numberOfProceedings >= totalReg ... Fig. 8. Pattern of CSP for input-data decision-dmaking. Constraint Satisfaction Problems provide possible tuples of variables that satisfy the constraints. On the other hand, Constraint Optimization Problems provide the tuple of values that optimize a function. We can consider the utilization of an optimization in this context, however, it was dismissed for avoiding the reduction of the domain of the decision variables, necessary in uncertain scenarios. For the example, to minimize the outcomes, the person in charge of the decision can always select the lowest quantity of expenses and the highest of revenue. However, these decision could reduce the domain of the future decision provoking possible unsatisfiable business rules. This is why the proposal provides the possible range instead of a single value. 6. Decision-Making Support for Input Data in Decision Points In this section, the whole DSS process is followed using a real set of Process-Obser- vational Variable values applied to the example presented in Section 2. In the example, the number of copies of the Proceedings (numberOfProceedings) is an input variable whose value must be decided before the registration process is closed. However, our methodology can help in the decision-making regarding input data once the execution of an instance reaches a Decision Point, in this case, to decide the number of copies of proceedings to print in the activity Print Proceeding. 6.1. Ascertaining the current Stage Table 5 shows the temporal variation of the most relevant Process-Observational Variables defined in the Dictionary of Section 4.2 for one simple former instance. This data has been processed with the aim of showing an understandable dataset, and, for this reason, every row has been summarized into weekly data, and several less relevant weeks have been removed. Several interesting aspects can be seen in this former instance, including aspects such as: The income for sponsorship remains unchanged from week 6; the submissions start in week 6, and their number remain unchanged after week 19; and the total number of registrations is 121 and this remains unchanged from week 36. 856 Jos´ e Miguel P´ erez ´ Alvarez et al. Table 5. Temporal variation of the main POVars in the Dictionary week sponsorship submissions totalReg earlyReg lateReg acceptedPapers 00 0 0 0 0 0 1100 0 0 0 0 0 210000 0 0 0 0 0 ... 625000 1 0 0 0 0 725000 5 1 1 0 0 825000 5 4 4 0 0 925000 10 6 6 0 0 10 25000 25 8 8 0 0 ... 19 25000 50 54 54 0 20 20 25000 50 66 66 0 20 21 25000 50 66 66 0 20 22 25000 50 67 66 1 20 23 25000 50 69 66 3 20 ... 35 25000 50 114 66 48 20 36 25000 50 121 66 55 20 ... 40 25000 50 121 66 55 20 6.2. Estimation of the ranges for each Process-Observational Variable The estimation of the ranges will be performed based on the current Stage at the moment of the decision, and the knowledge extracted regarding Process-Observational Variable temporal variation patterns. These ranges involve the possible ranges of potential final values of each Process-Observational Variable, based on the variation of Process-Obser- vational Variables extracted from former instances of the business processes, as explained in Subsection 5. The Stages defined by business experts in Section 4.4 are applied with the experimentation data, and the data in each possible set of Stages that can be matched together are normalized to be comparable (shown in Section 5). The evolution patterns found are shown in Table 6. In order to create a comprehensible sample, only the most relevant Process-Observational Variables are shown. Table 6. Knowledge extracted from Minimum and Maximum slopes for each POVar. Stages POVar \sponsor. submi. totalReg earlyReg lateReg accepted papers earlyReg 0.00 - 625.00 1.25 -1.25 1.55 - 3.00 1.00 - 1.62 0.55 - 1.37 0.50 - 0.75 earlyReg paperSub 0.00 - 405.40 0.00 - 1.32 1.67 - 2.78 1.08 - 1.30 0.59 - 1.49 0.54 - 0.81 earlyReg notified 0.00 - 0.00 0.00 - 0.00 1.68 - 2.68 0.48 - 0.80 0.88 - 2.20 0.00 - 0.00 lateReg notified 0.00 - 0.00 0.00 - 0.00 0.00 - 1.10 0.00 - 0.00 0.00 - 1.10 0.00 - 0.00 lateReg notified confer. 0.00 - 0,00 0.00 - 0.00 0.00 - 0.00 0.00 - 0.00 0.00 - 0.00 0.00 - 0.00 Decision-Making Support for Input Data in BP according to Former Instances 857 6.3. Instantation of the CSP template When the possible ranges of the Process-Observational Variables have been obtained from the previous step, it is the moment to incorporate the obtained values into the CSP- template and to include the decision variable as the goal of the CSP. The way in which the template is instantiated is presented below. Table 7. Predicted minimum and maximum values for the related Process-Observational Variables in stage “earlyReg and notified” Variable Min Max Current Estimated Estimated Slope slope value min value max value earlyReg 0.48 0.80 24 35.52 43.20 lateReg 0.88 2.20 0 21.12 52.80 totalReg 1.68 2.68 24 64.32 88.32 acceptedPapers 0.00 0.00 19 19 19 maxPapers 0.00 0.00 20 20 20 sponsorship 0.00 0.00 20000 20000 20000 earlyRegFee 0.00 0.00 300 300 300 lateRegFee 0.00 0.00 400 400 400 publicity 0.00 0.00 20000 20000 20000 venueCost 0.00 160.00 0 0 3840 venueCapacity 0.00 3.20 0 0 76.80 numberOfProceeding 0.00 2.80 0 0 67.20 proceedingPrice 0.00 3.20 0 0 76.80 galaDinnerPrice 1.60 2.80 0 38.40 67.20 lunchPrice 0.60 1.00 0 14.40 24 speakersCost 200.00 400.00 0 4800 9600 Table 6 presents the knowledge regarding the temporal variation of Process-Observa- tional Variables that has been extracted by analyzing the Comparable Instances. In Table 6, it can be observed how certain variables leave the value unchanged in certain stages, for instance, earlyReg has positive slopes when the set of stages defined by business experts is: earlyReg (Min: 1.00, Max: 1.65), earlyReg and paperSubmission (Min: 1.08, Max: 1.30), earlyReg and notified (Min: 0.48, Max: 0.80). This means that, in this situation, the variable has increased minimal and maximal values. However, in the stages lateReg and notified, and lateReg and notified and conference, the slopes are Min: 0.00, Max: 0.00, which means that, in these stages, the variable earlyReg remains unmodified. Thanks to this information, once a decision regarding data has to be made, it is possible to estimate the final range of values of each variable, and a Constraint Satisfaction Problem can be built in order to verify that all constraints in the process are satisfied, and to inform the decision maker of the range of values of the Decision Variable. In the aforementioned conference example, one instance of a decision is given in the establishment of the value of the variable numberOfProceedings, which is decided upon in the task Print Proceedings. For this example, the decision has been made at moment t= 16 weeks, and with the current values for the process following the current Stages of the Process-Observational Variables defined in the Dictionary:{submissions: 53, earlyReg: 24, lateReg: 0, totalReg: 24, acceptedPapers: 19, notified: 1, holdConference: 0, maxPapers: 20, submissionClose: 11, regOpen: 4, earlyRegClose: 23, regClose: 858 Jos´ e Miguel P´ erez ´ Alvarez et al. 38, sponsorship: 20000, earlyRegFee: 300, publicity: 20000, lateRegFee: 400, venueCost: 0, numberOfProceedings: 0, proceedingPrice: 0, galaDinnerPrice: 0, lunchPrice: 0, speakersCost: 0}. Therefore, by mapping this information with Dictionary, it is possible to observe that the stages activated are earlyReg and notified. As can be seen in Table 7, by using the previous knowledge extracted from former instances, it is possible to know how these variables will probably evolve. For instance, current totalReg is 24, and since the minimum slope and maximum slope calculated for these stages are: Min 1.68 and Max 2.68. Thereby, the final values will probably lie between: -EstimatedMinV alue = (40t−16t)×1.68totalReg t+ 24totalReg = 64.32 totalReg -EstimatedMaxV alue = (40t−16t)×2.68totalReg t+ 24totalReg = 88.32 totalReg Other Process-Observational Variables, such as sponsorship, have a Min and Max slope of 0.00 in this set of stages and hence we consider that this value is fixed, in this case, to 20,000. With this information, the CSP-template is instantiated according to the envelopers and the current stage, as shown in Figure 9. The instantiation of the Min and Max Ranges of the variables that evolve, and the input variable under decision is included (green part). maxPapers, submissions, totalReg, … Integer maxPapers [MINmaxPaper...MAXmaxPaper] Integer ... totalReg [MINtotalReg...MAXtotalReg] Integer income – expenses >4000 -> speakersCost <= sponsorship*0.3 ... numberOfProceedings >= totalReg ... Instantiation of Min and Max ranges MINearlyReg=35 MAXearlyReg=44 MINlateReg=21 MAXlateReg=54 MINtotalReg=64 MAXtotalReg=89 Define the input variables to decide (Decision Variable) Goal for branching(numberOfProceedings) Fig. 9. Pattern of CSP for input at decision time. The domain of the Process-Observational Variables depends on the stage of the variables when the decision is made, and how the value of the variables can evolve according to the envelopment temporal variation obtained in the previous subsection. The stage of the variables is known at decision time, and therefore the specific domain of the variables cannot be included in the CSP template, for the example MINmaxPaper,MAXmaxPaper, MINsubmission,MAXsubmission,MINtotalReg and MAXtotalReg. Since the CSP solver returns all the possible values of the variables, it is necessary to limit it further to present only the values of the Decision Variables. To this end, the decision variables are defined as objectives during the propagation process where the variables are instantiated. This limitation enables the search to stop the propagation in Decision-Making Support for Input Data in BP according to Former Instances 859 those branches where no new values of decision variables can be found, thereby halting the unnecessary combinations of values. For each solution found, each value of the Decision Variables is stored in a sorted list. Each of these sorted lists is conditioned to return the list of intervals for each variable of decision. For example, if the values {1, 2, 3, 5, 8, 9, 10}are found for the variable x, then the list of intervals built is {[1, 3],[5, 5],[8, 10]}. 6.4. Solution of the Constraint Satisfaction Problem In order to compute the range of the Decision Variable to guarantee a successful execution, a Constraint Programming solver must solve the CSP, and obtain the possible range of the decision variable, numberOfProceedings for the example of the CSP above. Numerous commercial solvers are available. In this case, we have selected ChocoSolver [36]. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 earlyRegFee lateRegFee numberOfProceedings lunchPrice galaDinnerPrice speakersCost submissions earlyReg totalReg Configure conference ... Review of pap.. Contact partners Print proceed… Hire venue Book dinner Book lunch Invite speakers Hold confer.. Prepare final rep… + + + + + + x x incomes-expenses<400 earlyReg earlyReg paperSubmission earlyReg notified notified lateReg notified lateReg conference Stages decision decision decision decision decision decision Decision variables Evolution variables from 61 to 68 Fig. 10. Decisions and support system. Figure 10 describes a possible process instance where the activities are executed and the decision are made, in accordance with the evolution of the evolution of the variables. For example, several decisions are made before the task print proceedings is executed, where the numberOfProceedings to print out has to be decided. Moreover, there is a set of evolution variables that are changing during the process instance. Following