Resource Allocation with Dependencies in Business Process Management Systems

Resource Allocation with Dependencies in Business Process Management Systems Giray Havur, Cristina Cabanillas, Jan Mendling, and Axel Polleres Vienna University of Economics and Business, Vienna, Austria {giray.havur,cristina.cabanillas,jan.mendling,axel.polleres}@wu.ac.at Abstract. Business Process Management Systems (BPMS) facilitate the execution of business processes by coordinating all involved resources. Traditional BPMS assume that these resources are independent from one another, which justifies a greedy allocation strategy of offering each work item as soon as it becomes available. In this paper, we develop a formal technique to derive an optimal schedule for work items that have dependencies and resource conflicts. We build our work on Answer Set Programming (ASP), which is supported by a wide range of efficient solvers. We apply our technique in an industry scenario and evaluate its effectiveness. In this way, we contribute an explicit notion of resource dependencies within BPMS research and a technique to derive optimal schedules. Keywords: Answer Set Programming ·Optimality ·Resource allocation ·Resource requirements ·Work scheduling 1 Introduction Business Process Management Systems (BPMS) have been designed as an integral part of the business process management (BPM) lifecycle by coordinating all resources involved in a process including people, machines and systems [1]. At design time, BPMS take as input a business process model enriched with technical details such as role assignments, data processing and system interfaces as a specification for the execution of various process instances. In this way, they support the efficient and effective execution of business processes [2]. It is an implicit assumption of BPMS that work items are independent from one another. If this assumption holds, it is fine to put work items in a queue and offer them to available resources right away. This approach of resource allocation, can be summarized as a greedy strategy. However, if there are dependencies between work items, this strategy can easily become suboptimal. Some domains like engineering or healthcare have a rich set of activities for which various Funded by the Austrian Research Promotion Agency (FFG) grant 845638 (SHAPE). resources, human and non-human, are required at the same time. Resource conflicts have often the consequence that working on one work item blocks resources such that other work items cannot be worked on. This observation emphasizes the need for techniques to make better use of existing resources in business processes [3]. In this paper, we address current limitations of BPMS with respect to taking such resource constraints into account. We extend prior research on the integration of BPMS with calendars [4] to take dependencies and resource conflicts between work items into account. We develop a technique for specifying these dependencies in a formal way in order to derive a globally optimal schedule for all resources together. We define our technique using Answer Set Programming (ASP), a formalism from logic programming that has been found to scale well for solving problems as the one we tackle [5]. We evaluate our technique using an industry scenario from the railway engineering domain. Our contribution to research on BPMS is an explicit notion of dependence along with a technique to achieve an optimal schedule. The paper is structured as follows. Section 2presents and analyzes an industry scenario. Section 3conceptually describes the resource allocation problem. Section 4explains our ASP-based solution and how it can be applied to the industry scenario. Section 5evaluates the solution. Section 6discusses related work. Section 7summarizes the conclusions of the work and the future steps. 2 Motivation In the following, we describe an industry scenario that leads us to a more detailed definition of the resource allocation problem and its complexity. 2.1 Industry Scenario A company that provides large-scale technical infrastructure for railway automation requires rigorous testing for the systems deployed. Each system consists of different types and number of hardware that are first set up in a laboratory. This setup is executed by some employees specialized in different types of hardware. Afterwards, the simulation is run under supervision. Figure 1depicts two process models representing the setup and run phases of two tests. We use (timed) Petri nets [6] for representing the processes. The process activities are represented by transitions (ai). The number within square brackets next to the activities indicates their (default maximum) duration in generic time units (TU). The numbers under process names indicate the starting times of the process executions: 8 TU for Test-1 and 12 TU for Test-2. The processes are similar for all the testing projects but differ in the activities required for setting up the hardware as well as in the resource requirements associated with them. Certain resources can only be allocated to activities during working periods, i.e., we want to enforce time intervals (so called breaks) where Fig. 1. Workflow for two projects some resources are not available. In our scenario, no resource is available in the intervals [0,8), [19,32), [43,56), and [67,80). For completing tests, the available non-human resources in the organization include 13 units of space distributed into 2 laboratories (Table 1) and several units of 3 types of hardware (Table 2). The human resources of the company are specialized in the execution of specific phases of the two testing projects, whose activities are able to complete in a specific time. Table 3shows available resources in different process phases and therefore, their ability to conduct certain activities along with their years of experience in the company in square brackets. The requirements on the use of such resources in the process activities are showninTable4. Each process activity requires a specific set of resources for its completion. For instance, three of the activities involved in the setup of Test-1 require 1 employee working on 1 unit of the hardware HW-1 in a laboratory; 1 setup activity requires 1 employee working on 1 unit of the hardware HW-2 in a laboratory; and the run activity requires 4 employees. Besides, a test can only be executed if the whole setup takes place in the same laboratory. The aim in this scenario is to optimize the overall execution time of simultaneous tests and consequently, the space usage in the laboratories. 2.2 Insights The resource allocation problem1deals with the assignment of resources and time intervals to the execution of activities. The complexity of resource allocation in BPM arises from coordinating the explicit and implicit dependencies 1Commonly referred as scheduling. across a broad set of resources and activities of processes as well as from solving potential conflicts on the use of certain resources. As we observe in our industry scenario, such dependencies include, among others: (i) resource requirements, i.e., the characteristics of the resources that are involved in an activity (e.g., roles or skills) (cf. Table 3); (ii) temporal requirements. For instance, the duration of the activities may be static or may depend on the characteristics of the set of resources involved in it, especially for collaborative activities in which several employees work together (such as for the activities of the run phase of a testing process). Furthermore, resource availability may not be unlimited (e.g., break calendars). In addition, resource conflicts may emerge from interdependencies between requirements, e.g., activities might need to be executed within a specific setting which may be associated with (or share resources with) the setting of other activities (e.g., all the setup activities of a testing process must be performed in the same laboratory). A resource allocation is feasible if (1) activities are scheduled with respect to time constraints derived from activity durations and control flow of the process model, and (2) resources are allocated to scheduled activities in accordance with resource availability and resource requirements of activities. This combinatorial problem for finding a feasible resource allocation under constraints is an NP-Complete problem [7]. However, organizations generally pursue an optimal allocation of resources to process activities aiming at minimizing overall execution times or costs, or maximizing the usage of the resources available. In presence of objective functions the resource allocation problem becomes ΔP 2[8]. 3 Conceptualization of the Resource Allocation Problem Figure 2illustrates our conceptualization of the resource allocation problem. We divide it into three complexity layers related to the aforementioned dependencies and resource conflicts. Optimization functions can be applied to all types of allocation problems. This model has been defined from the characteristics identified in our industry scenario as well as in related literature [9]. Table 1. Available space in labs LAB −1LAB −2 Space 4 9 Table 2. Available hardware (HW) Type Units HW1 hw1a, hw1b, hw1c HW2 hw2a, hw2b, hw2c, hw2d HW3 hw3a, hw3b, hw3c Table 3. Specialization of employees Test −1Test −2 Setup Run Setup Run Glen[7]   Drew[7]  Evan[3]  Mary[5]   Kate[6]   Amy[8]    Table 4. Activity requirements Activities Requirements Test-1 a1−a31Employee:Setup-1, 1 Hardware:HW-1, 1 Lab:a1-a4same lab a41Employee:Setup-1, 1 Hardware :HW-2, 1 Lab:a1-a4same lab a54Employee:Run-1, after execution(a.e.) release the lab for a1-a4 Test-2 a6−a81Employee:Setup-2, 1 Hardware:HW-2, 1 Lab:a6-a11 same lab a9−a11 1Employee:Setup-2, 1 Hardware :HW-3, 1 Lab:a6-a11 same lab a12 2Employee:Run-2 (hasExp>5), a.e. release the lab for a6-a11 Fig. 2. Resource allocation in business processes Fig. 3. Resource ontology and example instantiation 3.1 Basic Resource Allocation Three elements are involved in a basic resource allocation, namely: a model that stores all the information required about the resources available, information about the expected duration of the process activities, and a language for defining the restrictions that characterize the allocation. Resource Ontology. As a uniform and standardized representation language, we suggest the use of RDF Schema (RDFS) [10] to model organizational information and resources. Figure 3illustrates a sample RDFS ontology, in which aresource is characterized by a type and can have one or more attributes. In particular, any resource type (e.g. Employee) is a subclass of rdfs:Resource. The attributes are all of type rdf:Property; domain (rdfs:domain) and range of attributes are indicated with straight arrows labeled with the attribute name, whereas dashed arrows indicate an rdfs:subclassOf. There are three different types of resources: Employee,Hardware and Lab, where Hardware has three resource subtypes. Employees have attributes for their name (hasName), role(s) (hasRole) and experience level (hasExp) in the organization (number of years). Labs provide a certain amount of space for experiments (hasSpace). An instantiation of the ontology is described at the bottom of the figure using the RDF Turtle syntax [11]. This instantiation represents Tables 1,2and 3of the industry scenario. Activity Duration. Resource allocation aims at properly distributing available resources among running and coming work items. The main temporal aspect is determined by the expected duration of the activities. The duration can be predefined according to the type of activity or calculated from previous executions, usually taking the average duration as reference. This information can be included in the executable process model as a property of an activity (e.g. with BPMN [12]) or can be modelled externally. In either case, it has to be accessible by the allocation algorithm. Resource Allocation. Resource allocation can be seen as a two-step definition of restrictions. First, the so-called resource assignments must be defined, i.e., the restrictions that determine which resources can be involved in the activities [13] according to their properties. The outcome of resource assignment is one or more2resource sets with the set of resources that can be potentially allocated to an activity at run time. The second step assigns cardinality to the resource sets such that different settings can be described, e.g. for the execution of activity a1, 1 employee with role setup-1, 1 hardware of type HW2, and 1 unit space of a laboratory are required. There exist languages for assigning resource sets to process activities [13– 16]. However, cardinality is generally disregarded under the assumption that 2Since several sets of restrictions can be provided, e.g. for activity a1resources with either role r1or skill s1are required. only one resource will be allocated to each process activity. This is a limitation of current BPMS that prevents the implementation of industry scenarios like the one described in Sect. 2.1. 3.2 Advanced Time Management This layer extends the temporal aspect of resource allocation by taking into account that: (i) resource availability affects allocation, and that (ii) the resource sets allocated to an activity may affect its duration. Regarding resource availability, calendars are an effective way of specifying different resource availability status, such as available, unavailable, occupied/busy or blocked [9]. Such information must be accessible by the resource allocation module. As for the variable activity durations depending of the resource allocation, three specificity levels can be distinguished: –Resource-set-based duration, i.e., a triple (activity, resourceSet, duration) stating the (minimum/average) amount of time that it takes to the resources within a specific resource set (i.e., cardinality is disregarded) to execute instances of a certain activity. For instance, (a1, technician, 6) specifies that people with the role technician need (at least/on average) 6 TU to complete activity a1, assuming that technician is an organisational role. –Resource-based duration, i.e., a triple (activity, resource, duration) stating the (minimum/average) amount of time that it takes to a concrete resource to execute instances of a certain activity. For instance, (a1,John,8) specifies that John needs (at least/on average) 8 TU to complete activity a1. –Aggregation-based duration, i.e., a triple (activity, group, duration) stating the (minimum/average) amount of time that it takes to a specific group to execute instances of a certain activity. In this paper, we use group to refer to a set of human resources that work together in the completion of a work item, i.e., cardinality is considered. Therefore, a group might be composed of resources from different resource sets which may not necessarily share a specific resource-set-based duration. An aggregation function must be implemented in order to derive the most appropriate duration for an activity when a group is allocated to it. The definition of that function is up to the organization. For instance, a group might be composed of (John,Claire), where John has an associated duration of 8 TU for activity a1and Claire does not have a specific duration but she has role technician, with an associated duration of 6 TU for activity a1. Strategies for allocating the group to the activity could be to consider the maximum time needed for the resources involved (i.e., 8 TU), or to consider the mean of all the durations (i.e., 7 TU) assuming that the joint work of two people will be faster than one single resource completing all the work. 3.3 Advanced Resource Management The basic resource allocation layer considers resources to be discrete, i.e. they are either fully available or fully busy/occupied. This applies to many types of resources, e.g. people, software or hardware. However, for certain types of nonhuman resources, availability can be partial at a specific point in time. Moreover, they may have other fluent attributes. For instance, cumulative resources are hence characterized by their dynamic attributes and they can be allocated to more than one activity at a time, e.g. in Fig. 2there is a resource room 1 whose occupancy changes over time. We use the ASP solver clasp [17] due to its efficiency for our experiments. This allows us to use integer variables as attributes. There are also other extensions of ASP such as FASP [18] that adds the power to model continuous variables. 3.4 Optimization Function Searching for (the existence of) a feasible resource allocation ensures that all the work items can eventually be completed with the available resources. However, typically schedules should also fulfill some kind of optimality criterion, most commonly completion of the schedule in the shortest possible overall time. Other optimization criteria may involve for instance costs of the allocation of certain resources to particular activities, etc. Given such an optimization criterion, there are greedy approaches [19]providing a substantial improvements over choosing any feasible schedule, although such techniques depend on heuristics and may not find a globally optimal solution for complex allocation problems. We refer to [20] for further information on various optimization functions, but emphasize that our approach will in principle allow arbitrary optimization functions and finds optimal solutions – similar in spirit to encodings of cost optimal planning using ASP [21]. 4 Implementation with ASP Answer Set Programming (ASP) [17] is a declarative (logic-programming-style) paradigm. Its expressive representation language, ease of use, and computational effectiveness facilitate the implementation of combinatorial search and optimization problems (primarily NP-hard). Modifying, refining, and extending an ASP program is uncomplicated due to its strong declarative aspect. An ASP program Πis a finite set of rules of the form: A0←A1,...,A m,notA m+1,...,notA n.(1) where n≥m≥0 and each Ai∈σare (function-free first-order) atoms; if A0is empty in a rule r, we call ra constraint, and if n=m= 0 we call ra fact. Whenever Aiis a first-order predicate with variables within a rule of the form (1), this rule is considered as a shortcut for its grounding ground(r), i.e., the set of its ground instantiations obtained by replacing the variables with all possible constants occurring in Π. Likewise, we denote by ground(Π) the set of rules obtained from grounding all rules in Π. Sets of rules are evaluated in ASP under the so-called stable-model semantics, which allows several models, so called answer sets (cf. [22] for details). ASP Solvers typically first compute a subset of ground(Π) and then use a DPLL-like branch and bound algorithm to find answer sets for this ground program. We use the ASP solver clasp [17] for our experiments as it has proved to be one of the most efficient implementations available [23]. As syntactic extension, in place of atoms, clasp allows set-like choice expressions of the form E={A1,...,A k}which are true for any subset of E; that is, when used in heads of rules, Egenerates many answer sets, and such rules are often referred to as choice rules. Another extension supported in clasp are optimization statements [17] to indicate preferences between possible answer sets: #minimize{A1:Body1=w1,...,A m:Bodym=wm@p} associates integer weights (defaulting to 1) with atoms Ai(conditional to Bodyi being true), where such a statement expresses that we want to find only answer sets with the smallest aggregated weight sum; again, variables in Ai:Bodyi=wi are replaced at grounding w.r.t. all possible instantiations. Several optimization statements can be introduced by assigning the statement a priority level p. Reasoning problems including such weak constraints are ΔP 2-complete. Finally, many problems conventiently modelled in ASP require a boundary parameter kthat reflects the size of the solution. However, often in problems like planning or model checking this boundary (e.g. the plan length) is not known upfront, and therefore such problems are addressed by considering one problem instance after another while gradually increasing this parameter k. Re-processing repeatedly the entire problem is a redundant approach, which is why incremental ASP (iASP) [17] natively supports incremental computation of answer sets; the intuition is rooted in treating programs in program slices (extensions). In each incremental step, a successive extension of the program is considered where previous computations are re-used as far as possible. A former version of our technique is detailed in [5]. We enhance our encoding in three folds: (1) basic resource allocation supporting multiple business processes with multiple running instances, (2) definition of advanced resource management concepts, and (3) definition of advanced time management concepts. The entire ASP encoding can be found at http://goo.gl/Q7B2t4. 4.1 Basic Resource Allocation This program schedules the activities in business processes described as timed Petri nets (cf. the generic formulation of 1-safe Petri Nets [5, Sect. 4]) and allocates resources to activities with respect to activity-resource requirements. To achieve this, the program finds a firing sequence between initial and goal places of given processes, schedules the activities in between, and allocates resources by complying with resource requirements. In our program, a firing sequence is represented as predicates fire(a,b,i,k), which means that an activity aof a References 1. Rummler, G.A., Ramias, A.J.: A framework for defining and designing the structure of work. In: vom Brocke, J., Rosemann, M. (eds.) Handbook on Business Process Management 1, pp. 81–104. Springer, Heidelberg (2015) 2. Reijers, H.A., Vanderfeesten, I.T.P., van der Aalst, W.M.P.: The effectiveness of workflow management systems: a longitudinal study. Int. J. Inf. Manage. 36(1), 126–141 (2016) 3. Rosemann, M., vom Brocke, J.: The six core elements of business process management. In: vom Brocke, J., Rosemann, M. (eds.) Handbook on Business Process Management 1, pp. 105–122. Springer, Heidelberg (2015) 4. Mans, R., Russell, N.C., Aalst, W.M.P., Moleman, A.J., Bakker, P.J.M.: Scheduleaware workflow management systems. Trans. Petri Nets Other Models Concurrency 4, 121–143 (2010) 5. Havur, G., Cabanillas, C., Mendling, J., Polleres, A.: Automated resource allocation in business processes with answer set programming. In: Reichert, M., Reijers, H. (eds.) BPM Workshops 2015. LNBIP, vol. 256, pp. 191–203. Springer, Heidelberg (2016). doi:10.1007/978-3-319-42887-1 16 6. Popova-Zeugmann, L.: Time Petri Nets, pp. 139–140, Springer, Heidelberg (2013) 7. Johnson, D.S., Garey, M.R.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Free. Co., San Fr. (1979) 8. Buccafurri, F., Leone, N., Rullo, P.: Enhancing disjunctive datalog by constraints. IEEE Trans. Knowl. Data Eng. 12(5), 845–860 (2000) 9. Ouyang, C., Wynn, M.T., Fidge, C., ter Hofstede, A.H., Kuhr, J.-C.: Modelling complex resource requirements in Business Process Management Systems. In: ACIS (2010) 10. Brickley, D., Guha, R.: RDF Schema 1.1. W3C Recommendation, February 2014. http://www.w3.org/TR/rdf-schema/ 11. Beckett, D., Berners-Lee, T., Prud’hommeaux, E., Carothers, G.: Turtle - Terse RDF Triple Language. W3C Candidate Recommendation, February 2014. https:// www.w3.org/TR/turtle/ 12. OMG, BPMN 2.0, recommendation, OMG (2011) 13. Cabanillas, C., Resinas, M., R´ıo-Ortega, A., Ruiz-Cort´es, A.: Specification and automated design-time analysis of the business process human resource perspective. Inf. Syst. 52, 55–82 (2015) 14. Aalst, W.M.P., Hofstede, A.H.M.: YAWL: yet another workflow language. Inf. Syst. 30(4), 245–275 (2005) 15. Stroppi, L.J.R., Chiotti, O., Villarreal, P.D.: A BPMN 2.0 extension to define the resource perspective of business process models. In: CIbS 2011 (2011) 16. Cabanillas, C., Resinas, M., Mendling, J., Cort´es, A.R.: Automated team selection and compliance checking in business processes. In: ICSSP, pp. 42–51 (2015) 17. Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer Set Solving in Practice. Morgan & Claypool Publishers, San Rafael (2012) 18. Van Nieuwenborgh, D., De Cock, M., Hadavandi, E.: Fuzzy answer set programming. In: Fisher, M., van der Hoek, W., Konev, B., Lisitsa, A. (eds.) JELIA 2006. LNCS (LNAI), vol. 4160, pp. 359–372. Springer, Heidelberg (2006) 19. van der Aalst, W.: Petri net based scheduling. Operations-Research-Spektrum 18(4), 219–229 (1996) 20. Roose, R.: Automated Resource Optimization in Business Processes. MSc. Thesis 21. Eiter, T., Faber, W., Leone, N., Pfeifer, G., Polleres, A.: Answer set planning under action costs. J. Artif. Intell. Res. (JAIR) 19, 25–71 (2003) 22. Brewka, G., Eiter, T., Truszczy´nski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011) 23. Calimeri, F., Gebser, M., Maratea, M., Ricca, F.: Design and results of the fifthanswer set programming competition. Artif. Intell. 231, 151–181 (2016) 24. Eiter, T., Ianni, G., Krennwallner, T., Polleres, A.: Rules and ontologies for the semantic web. In: Baroglio, C., Bonatti, P.A., Maluszy´nski, J., Marchiori, M., Polleres, A., Schaffert, S. (eds.) Reasoning Web 2008. LNCS, vol. 5224, pp. 1–53. Springer, Heidelberg (2008) 25. Castro, P.M., Marques, I.: Operating room scheduling with generalized disjunctive programming. Comput. Oper. Res. 64, 262–273 (2015) 26. Silva, T.A., Souza, M.C., Saldanha, R.R., Burke, E.K.: Surgical scheduling with simultaneous employment of specialised human resources. Eur. J. Oper. Res. 245(3), 719–730 (2015) 27. Riise, A., Mannino, C., Burke, E.K.: Modelling and solving generalised operational surgery scheduling problems. Comput. Oper. Res. 66, 1–11 (2016) 28. Siu, M.-F.F., Lu, M., AbouRizk, S.: Methodology for crew-job allocation optimization in project and workface scheduling. In: ASCE, pp. 652–659 (2015) 29. Menesi, W., Abdel-Monem, M., Hegazy, T., Abuwarda, Z.: Multi-objective schedule optimization using constraint programming. In: ICSC15 (2015) 30. Sprecher, A., Drexl, A.: Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm1. Eur. J. Oper. Res. 107(2), 431–450 (1998) 31. Senkul, P., Toroslu, I.H.: An architecture for workflow scheduling under resource allocation constraints. Inf. Syst. 30, 399–422 (2005) 32. Arias, M., Rojas, E., Munoz-Gama, J., Sep´ulveda, M.: A framework for recommending resource allocation based on process mining. In: BpPM Workshops (DeMiMoP) (in press) (2015) 33. Lombardi, M., Milano, M.: Optimal methods for resource allocation and scheduling: a cross-disciplinary survey. Constraints 17, 51–85 (2012) 34. Rieck, J., Zimmermann, J.: Exact methods for resource leveling problems. In: Schwindt, C., Zimmermann, J. (eds.) Handbook on Project Management and Scheduling, vol. 1. Springer, Switzerland (2015) 35. Lohmann, N., Verbeek, E., Dijkman, R.: Petri Net transformations for business processes - a survey. Trans. Petri Nets Other Models Concurrency II (2), 46–63 (2009)