Planning and Scheduling of Business Processes in Run-Time: A Repair Planning Example

Planning and Scheduling of Business Processes in Run-Time: A Repair Planning Example Irene Barba and Carmelo Del Valle Abstract Over the last decade, the efficient and flexible management of business processes has become one of the most critical success aspects. Furthermore, there exists a growing interest in the application of Artificial Intelligence Planning and Scheduling techniques to automate the production and execution of models of organization. However, from our point of view, several connections between both disciplines remains to be exploited. The current work presents a proposal for modelling and enacting business processes that involve the selection and order of the activities to be executed (planning), besides the resource allocation (scheduling), considering the optimization of several functions and the reach of some objectives. The main novelty is that all decisions (even the activities selection) are taken in run-time considering the actual parameters of the execution, so the business process is managed in an efficient and flexible way. As an example, a complex and representative problem, the repair planning problem, is managed through the proposed approach. 1 Introduction In the last years, the effective management of business processes (BP) in organizations became more important, since they need to adapt to the new commercial conditions, as well as to respond to competitive pressures, considering the business environment and the evaluation of their information systems. BP Management (BPM) can be seen as supporting BP using methods, techniques, and software to design, enact, control and analyze operational processes involving humans, organizations, applications, and other sources of information [2]. Similarly, Workflow Management Systems [1, 11] consist of methods and technologies for managing the flow of work in organizations. In a related way, BPM Systems (BPMS) are software tools that support the management of the BP. In some cases, they use temporal information and ignore, in some ways, the required resources, considering them unlimited. This may not be adequate in different situations, for example when limited resources can be required by different activities at overlapped periods of time. The area of Scheduling [8] includes problems in which it is necessary to determine an execution plan for a set of activities related by temporal constraints. Moreover, the execution of each activity requires the use of resources so they may compete for limited resources. In general, the objective is to find a feasible plan so that temporal and resource constraints are satisfied, usually optimizing objective functions related to temporal measures. In a wider perspective, in Artificial Intelligence (AI) planning [12], the activities to be executed are not established a priori, so it is necessary to select and to order them from a set of alternatives. In most cases, the specification of planning problems includes the initial state of the world, the goal (a predicate representing to a set of possible final states) that must be reached, and a set of operators (actions) that can be applied to one state to reach another one, allowing the evolution of the system. In order to solve this kind of problems, it is necessary to select a suitable set of actions that must be executed in a correct order, in some cases allowing parallelism. Furthermore, in several planning problems, the optimization of some objectives functions is pursued. Currently, there is an increasing interest in integrating the application ofAI Planning and Scheduling (P&S) techniques, some of them are maintenance and repair planning [10], where there may be a cascading set of choices for actions, facilities, tools or personnel, which affect different features of the plan, such as duration or cost [24]. Also, connection and disconnection planning involve the identification, selection and sequencing of operations, which can be specified by their effects on the components. In other context, disconnection planning has been object of different studies, such as maintenance or repair purposes [17]. Many problems can involve multiple conflicting objectives at the same time (multi-objective optimization [9]). The And/Or graphs [15] (Sect. 3) can be used as a basis of representing most problems that involve both P&S, including the repair planning problem (Sect. 3), that is studied in the current work.A similar representation for this kind of problems can be found in [6], that proposes an extension of temporal networks by parallel and alternative branching to represent some kinds of P&S problems. Also, in [3] it is proposed the concept of blocks that can classify BP flows into several patterns: iterative block, serial block and parallel block including AND and OR structures. BPM andAI P&S are two disciplines with many parallels, but which have largely been pursued by disjoint communities. BPMS are responsible for goals specification, design, implementation, enactment, monitoring and evaluation of BP [18], so they must deal with the anticipated P&S of processes. In general, automated P&S has not been integrated in business environments due to, between others, the lack of friendly modelling tools. There are several points where AI P&S tools can be effectively applied to BPMS, as it is explained in Sect. 2. In the last years, there exists a growing interest in the application ofAI P&S techniques to automate the production and execution of models of organization, as shown by the existence of a Technical Coordination Unit of the European research network on P&S, PLANET [20], and Fig. 1 AI P&S techniques for optimal business process enactment several related research projects (SWIM system [7], the MILOS project [19], the TBPM project [16], etc). However, from our point of view, several connections between both disciplines remains to be exploited. This work is based on modelling and enacting a problem involving both AI planning (selection and order of the activities) and scheduling (temporal resources allocation) through BP tools, using AI techniques in run-time for the optimization of several objective functions regarding the resulting execution plan, specifically duration and cost. The repair planning problem has been selected for being a complex and representative problem involving P&S. The most important contribution of this paper is the automatic management of the enactment of BP representing complex P&S problems, selecting and ordering the activities execution and allocating the resources in run-time, in order to avoid the drawbacks of taking these decisions during the design phase. Figure 1shows a graphic representation of this work: first, the user introduces the information about the P&S problem, in this case, the repair problem. This information can be modelled through anAnd/Or graph or a BP model language, where all the execution alternatives are included, also containing the estimated values of several parameters, such as activity durations, resource availability, etc. This graph is translated to a BP model, that still represents a P&S problem since the selection and the order of the activities, together with the temporal resources allocation, are carried out in the enactment phase. The resulting BP model includes a pool composed by web services based on AI P&S techniques, that drives the execution considering the optimization functions and the actual values of the parameters. From this specification, the workflow engine can enact the plan in an optimized way. In the BP enactment, the P&S decisions are taken considering the actual execution values instead of the estimated ones, optimizing the objective functions, so a flexible and dynamic BP is got. On the other hand, the decision-making in run-time provides the problem with a high spatial and temporal complexity. It is necessary to find a good balance between flexibility–optimality and complexity of the BP. The main contributions of this paper can be summarized as: • Optimal execution of BP that, in run-time, require: first, the selection and the order of the activities to be executed, due to the existence of several possible alternatives (planning) expressed through exclusive data-based gateways; and secondly, the resources allocation involving temporal reasoning due to the use of shared resources (scheduling), both considering the optimization of functions. • Optimal execution ofAI P&S problems that can be represented byAnd/Or graphs through BP tools, considering both P&S of the activities, and taking into account the optimization of objective functions. • Translation from AI P&S problems that can be modelled through And/Or graphs, to BP models, focused on a complex and representative P&S problem: the repair planning problem. In the following, Sect. 2 describes the BPM life cycle, Sect. 3 details the considered repair planning problem, Sect. 4 states the translation from the And/Or graph to a BP model, Sect. 5 summarizes the more related work and, finally, Sect. 6 presents some conclusions and future work. 2 AI Planning and Scheduling for BPM The integration of AI P&S techniques with Workflow Management Systems can improve overall system functionality and can help to automate the definition of BP. As follows, the different stages of a typical BPM Life Cycle [2] are briefly presented: • Process design: This stage involves designing, modelling, optimizing and simulating the organization processes. It is basically a human activity. • System configuration: In this stage a schedule must be generated, taking into account the information given by the customer, such as the target end date, dependencies between activities or activity durations. The resources are assigned to activities for the appropriate time slots (scheduling), considering the finite capacity and/or non-sharable resources and, generally, taking into account the optimization of objective functions, such as process duration or cost. • Process enactment: In this phase, the plan is carried out so that the activities have tobe coordinated to ensurecorrect sequencing.Atthe same time, resourceswill be involved in enacting multiple processes and instances of the same process. When the same resource is required by several activities at the same time, generally, rules for prioritizing activities must act on the conflict. • Diagnosis: As execution proceeds, the enactment information must be analyzed due to the possible appearance of unexpected incidents, such us unavailability of resources, actual activity durations different from expected ones, fails, etc. Minor incidents may require updating of the plan. More significant differences may require great changes in the plan, even a re-planning. This work is based on automating the resource allocation and the selection and order of the activities, in both system configuration and process enactment phases, considering AI P&S techniques for optimizing several objective functions. 3 The Repair Planning Problem Maintenance and repair planning is becoming a more important issue in many systems, according to the increasing problem of their complexity, the limitations of the technology used to maintain it and the problem of its ageing. In some studies, repair activities are integrated into the diagnosis process [10]. In order to repair some (previously diagnosed) faulty components, a sequence of disconnection activities must be executed to get it. After that, a repair action would substitute or repair the component, and then a set of connection activities must reconnect the system. And/Or graphs have been used for the planning of assembly and repair processes [15]. This graph has been adapted for the representation of the proposed repair problem due to the existing similarities between both problems. The And/Or graph allows to represent the set of all feasible connection/disconnection plans in a natural way, depicting the system structure and including the alternative activities and the precedence constraints between them (Fig. 2a). It represents the disconnection (top part) and connection (bottom part) activities that can be selected in order to repair a faulty component (D in this case), in a system made of five components (ABCDE). In this representation two kinds of nodes can be distinguished: • Or nodes: Correspond to subsystems, i.e., AC in Fig. 2. The top node corresponds to the complete system, and the leaf ones correspond to the components. • And nodes: Correspond to the connection activities joining the subsystems of its two Or nodes below it producing the subsystem corresponding to the Or node above it, i.e., T3; and the disconnection activities, that decomposes the subsystem above it to obtain the two subsystems below it, i.e., T1. For the same Or node, there can be several And nodes (activities) below it, representing different alternatives to connect/disconnect the corresponding subsystem. In these graphs, each disconnection plan is associated to a tree, that is an And/Or path starting at the root node and ending at the nodes representing components (also, each connection plan is associated to a tree in a similar way). An important advantage is that the And/Or graph shows the activities that can be executed in parallel (Fig. 2). Furthermore, both precedence constraints and those related to the selection of activities, can be easily obtained from this representation. A feasible repair plan can be seen as a (minimum) set of activities that starts with the disconnection of the complete system, repairs the faulty component, and finishes with the connection of the complete system. In this work, two kinds of activities are considered, each one presenting an associated duration and cost: • Connection/disconnection activities: are executed on an established resource with a particular configuration to obtain the different subsystems. Fig.2 ExampleofAnd/Orgraph andanextensionincluding resourceconstraints. aOriginalAnd/Or graph. bExtended And/Or graph • Auxiliary activities: due to the use of shared and different resources. Two kinds of operations are considered: set-up operations, that change the configuration of a resource when two successive activities with different configuration use that resource; and transportation operations, that transport the subsystems between locations when the location where the subsystem is obtained after a connection/disconnection activity is different from the location where is required before a connection/disconnection activity. In order to manage the shared resources with different configurations, the original And/Or graph has been extended, so that the new representation includes all the constraints involved in the problem, adding new types of links between the And nodes (Fig. 2b). The new links represent non-precedence constraints: due to the use of shared resources (i.e., T5and T11) and due to the change of configurations in the resources (i.e., T5and T1). The reasoning with resources, specifically temporal resources allocation, lead to NP completeness due to disjunctive constraints. It is important to emphasize that theAnd/Or graph represents the system structure through components relations, that remains permanent despite of different required resources or faulty components. Consequently, for the same graph there can be several repair problems varying the faulty components or the required resources. TheAnd/Or graph can be used as a base representation of mostAI P&S problems, since it allows to represent important P&S aspects, such as alternative activities or precedence relations. In general, this representation can be easily extended in order to include other aspects, i.e., shared resources in the repair planning problem. 4 The Repair Planning Problem as a Business Process Once the problem in modelled as an And/Or graph, it can be translated to a BP language model, as instance BPMN [26], in order to be deployed and executed. It is important to emphasize that the And/Or graph contains all the possible alternative activities to be selected, and during the enactment phase,AI P&S methods are used to select and to order the suitable activities automatically, in order to obtain an optimal execution plan. As stated before, the And/Or graph represents the system structure through components relations, so different required resources and faulty components leads to different problems. The BP model for the repair planning problem (Fig. 4) contains three pools: 1. Client: Abstract pool that acts as intermediary between the user and the BP. The user must specify the faulty components, that starts the BP enactment. At the end of the enactment, a message containing the selected activities together with their temporal allocation, is sent to the client. 2. Repair module: Executable pool that contains all the activities of the problem, from the And/Or graph specification. 3. Planner and dispatcher: Abstract pool that contains the web services. These web services are based onAI P&S techniques and are responsible for the optimal P&S of the activities. Each time that the repair plan execution (Repair Module) reaches OR branches, the Planner and Dispatcher pool decides the way that must be followed (planning). Furthermore, for the tasks requiring the same resources to be executed, this pool establishes the execution order (scheduling). During the execution of the repair plan, the Repair Module and the Planner and Dispatcher pool are interchanging information. When the Repair Module reaches an exclusive data-based gateway, the decision to take is established by the information previously received from the Planner and Dispatcher pool. Different AI P&S techniques can be used in order to obtain an optimal execution plan. In previous works, we have developed proposals for solving the optimal P&S for the proposed repair planning problem, taking into account the minimization of both duration and cost. Specifically, in [4] it is explained a constraint based proposal [23] and in [5]itis shown a PDDL specification for generic planners [12], both considering multimode Fig. 3 Example of extended And/Or graph for a system made of three components when faulty component is B activities and multi-objective optimization (duration and cost). In both, several experimental results are shown, demonstrating that these proposals are successful at solving this kind of problems. These tools have been used for developing the web services related to P&S in the current work. As follows, the BP model generation from the And/Or graph is explained. As an example, the BPMN corresponding to the repair problem of Fig. 3can be seen in Fig. 4. For the sake of clarity, in Fig. 4a the activities corresponding to connection/disconnection tasks appear collapsed, while in Fig. 4b its expanded representation is shown. Regarding to the proposed BP model, first of all, a message containing the faulty components is sent from the Client pool to the Repair Module. After that, an initial plan is generated trying to obtain a good start point (optimizing the objective functions). This initial plan, in most cases, will be iteratively improved during the BP enactment, as explained later. After the initial plan generation, two branches are executed in parallel in the Repair Module: • Optimization process (Branch 1 in Fig. 4a): The initial plan can be non-optimal. Also, the actual parameters can be different from the estimated ones. Considering both reasons, it is proposed a loop updating activity that is continuously trying to improve the current solution, taking the actual values of the parameters. In order to do this, a web service based on AI techniques (Update plan) is invoked. Each time a better solution is found, the current plan is updated and these information Fig. 4 BPMN diagram of the repair problem of Fig. 3.aBPMN diagram with collapsed activities. bBPMN diagram for the expanded activity