A Benchmark for ASP Systems: Resource Allocation in Business Processes

A Benchmark for ASP Systems: Resource Allocation in Business Processes Giray Havur Cristina Cabanillas Axel Polleres Arbeitspapiere zum Tätigkeitsfeld Informationsverarbeitung, Informationswirtschaft und Prozessmanagement Working Papers on Information Systems, Information Business and Operations Nr./No. 01/2019 ISSN: 2518-6809 URL: http://epub.wu.ac.at/view/p_series/S1/ Herausgeber / Editor: Department für Informationsverarbeitung und Prozessmanagement Wirtschaftsuniversität Wien · Welthandelsplatz 1 · 1020 Wien Department of Information Systems and Operations · Vienna University of Economics and Business · Welthandelsplatz 1 · 1020 Vienna 1 A Benchmark for ASP Systems: Resource Allocation in Business Processes∗ GIRAY HAVUR1,2, CRISTINA CABANILLAS1, AXEL POLLERES1 1Vienna University of Economics and Business, Vienna, Austria 2Siemens AG ¨ Osterreich, Corporate Technology, Vienna, Austria (e-mail: {name}.{surname}@wu.ac.at) Abstract The goal of this paper is to benchmark Answer Set Programming (ASP) systems to test their performance when dealing with a complex optimization problem. In particular, the problem tackled is resource allocation in the area of Business Process Management (BPM). Like many other scheduling problems, the allocation of resources and starting times to business process activities is a challenging optimization problem for ASP solvers. Our problem encoding is ASP Core-2 standard compliant and it is realized in a declarative and compact fashion. We develop an instance generator that produces problem instances of different size and hardness with respect to adjustable parameters. By using the baseline encoding and the instance generator, we provide a comparison between the two award-winning ASP solvers CLASP and WASP and report the grounding performance of GRINGO and I-DLV. The benchmark suggests that there is room for improvement concerning both the grounders and the solvers. Fostered by the relevance of the problem addressed, of which several variants have been described in different domains, we believe this is a solid application-oriented benchmark for the ASP community. KEYWORDS: answer set programming, benchmark, business process management, resource allocation 1 Introduction Business process management (BPM) is a discipline in operations management that aims at improving corporate performance by properly managing and optimizing a company’s business processes. A business process is a collection of related events, activities and decisions that involve a number of human and non-human resources and that collectively lead to an outcome that is of value to an organization or its customers (Dumas et al., 2018). Resources, as an integral part of business processes, have to be considered throughout all the stages of the BPM lifecycle, which iterates from process discovery and modeling to process execution and monitoring targeting continuous process improvement. At run time, a process execution engine creates instances of a business process and allocates specific resources to the tasks to be completed according to pre-defined criteria. Such criteria are defined in the form of constraints that comprise the characteristics as well as the number of resources needed for completing each process task. When referred to human resources, the characteristics are usually reflected in organizational models that contain all the relevant data about the resources, their roles, their skills and any other valuable ∗This work has been funded by the Austrian Research Promotion Agency (FFG) under the project grant 845638 (SHAPE) and the Austrian Science Fund (FWF) under the project grant V 569-N31 (PRAIS). 2Giray Havur, Cristina Cabanillas, Axel Polleres information. The Role-Based Access Control (RBAC) model is very often used for assigning resources to process tasks on the basis of the organizational roles they are associated with. As a result, during process execution, at the due time for each task only the required number of resources will be picked up from the set of candidates (i.e. suitable resources according to their roles) and allocated to the task. Therefore, we can define resource allocation in business processes as the assignment of resources and time intervals to the activities for the execution of a process. The complexity of resource allocation arises from coordinating the dependencies across a broad set of resources and process activities as well as from solving potential conflicts on the use of certain resources (e.g. certain roles are required to execute certain activities, particular resources cannot be used at the same time, or different resources have to be allocated to different activities to avoid conflicts of interest, i.e. separation of duties) (Russell et al., 2005). Process-oriented organizations are concerned with carrying out a proper resource allocation as they aim to optimize one or more process performance measures, which include time, cost, quality and flexibility (Dumas et al., 2018). Typically, among these objectives a subset of them is selected and each objective in this subset is assigned a relative priority that defines the respective optimization function. Such a problem is similar to a well-known scheduling problem called the Multi-mode Resource-constrained Project Scheduling Problem (MRCPSP) (Sprecher et al., 1994). One way of addressing this problem is describing it in a knowledge representation formalism. Answer Set Programming (ASP) appears as a good candidate for this purpose as it has been used to solve various hard computational problems and proved to maintain a balance between expressiveness, ease of use and computational effectiveness (Gebser et al., 2012). Moreover, any possible trade-off related to an allocated resource (e.g. duration of an activity given a resource) can be neatly represented using the defaults in the absence of complete information. As a matter of fact, we have previously used ASP as a flexible tool to encode the resource allocation problem and related complex constraints in prior research efforts (Havur et al., 2015, 2016), which allowes us to identify the problem-in-hand as a challenging task for the ASP systems, and therefore in this paper we describe this problem as a benchmark for the ASP systems. Earlier ASP competitions have led to the development of two scheduling-related benchmark entries. The first entry is called disjunctive scheduling (Denecker et al., 2009) and the problem addressed has generalized precedence relations, uniform activity durations, an overall deadline to be met with no resource aspect. The other entry is called incremental scheduling (Calimeri et al., 2014) and addresses a problem with one renewable resource set, uniform activity durations and deadlines imposed on activities. Unlike the problems involved in these two entries, the resource allocation problem has different numbers of resource sets, resource- and resource-set-specific time requirements, different resource demands per activity and a makespan1optimization function. For such a type of problems, a benchmark to compare the performance of existing ASP solvers and grounders is still missing. In the case of resource allocation in the area of BPM, this is also due to the lack of available data describing a variety of scenarios in which resource allocation is required. In this paper, we narrow this gap by extending former contributions on ASP-based resource allocation in business processes towards a common challenge benchmark for ASP solvers. In particular, our contribution is three-fold: 1The makespan is the distance in time that elapses from the start to the end of a process. 3 •We position the problem of resource allocation in the landscape of existing scheduling problems by characterizing their activity and resource environments. •Based on a declarative baseline encoding in ASP of the resource allocation problem with RBAC constraints2and a standardized encoding of problem instances, we develop an instance generator that produces both process instances and organizational resource models along with different parameters that can be used to adapt instance sizes. This sets up the benchmark as it provides all the inputs that are needed to test the performance of any ASP grounder/solver when dealing with the resource allocation problem in the BPM domain. •Lastly, by using our benchmark we present a detailed evaluation comparing two of the best performing ASP solvers (CLASP (Gebser et al., 2015) and WASP (Alviano et al., 2017)) and grounders (GRINGO (Gebser et al., 2011) and I-DLV (Calimeri et al., 2017)). Our benchmark implementation is configurable in the sense that any grounder/solver combinations can be added in. The results of our benchmark evaluation demonstrate that real-world instance sizes pose a considerable challenge on state-of-the-art ASP systems, which opens opportunities for further performance improvements in these systems. The paper is structured as follows: Section 2 provides necessary background by formally defining the problem of resource allocation in business processes and positioning it within the spectrum of scheduling problems already targeted by ASP experts. Section 3 describes the problem encoding in ASP and the problem instance generator. Section 4 presents the performance evaluation of different ASP systems using our problem encoding and the problem instances produced by our generator. Section 5 reflects on the related work. Section 6 concludes the paper with the gained insights and gives pointers for the future work. 2 Background The resource allocation problem deals with the assignment of resources and time intervals to the execution of activities, where the number of activities as well as the number of resources are assumed to be finite (Lombardi and Milano, 2012). The complexity of resource allocation in BPM arises from coordinating the explicit and implicit dependencies across a broad set of resources and activities of processes as well as from solving potential conflicts on the use of certain resources while minimizing the makespan (Havur et al., 2016). Before introducing our ASP encoding and benchmark setting, in this section we describe the elements involved in this problem and position the problem with respect to other (scheduling) problems. 2.1 Business Processes A business process is a finite set of activities whose executions are partially ordered. The execution of each activity in the process generally requires one or more (human or non-human) resources and produces some output that is of benefit for a customer, such as a service or a document (Burattin, 2015). Process models are defined to represent the different aspects of a business process, especially the functional (process activities) and the behavioral (control flow or execution order) perspectives. For instance, Figure 1 depicts the model of a process for publishing a book from the point of view of a publishing house, represented using Business Process 2To keep the encoding compact, in this paper we allocate only human resources but in prior research we developed a generalized ASP encoding covering different resource types (cf. Havur et al. (2016)). 4Giray Havur, Cristina Cabanillas, Axel Polleres Book publishing process Proofread manuscript Changes required? Revise text Revise visual Send press release Manuscript revised More changes required? Receive manuscript No No Yes Yes Fig. 1: BPMN model of the book publishing process Model and Notation (BPMN) (OMG, 2011). In this process, when the publishing entity receives a new textbook manuscript from an author, it must be proofread. If changes are required, the modifications suggested must be applied on text and figures, which can be done in parallel. This review-and-improvement procedure is repeated until there are no more changes to apply, and the improved manuscript is then sent back to the author for double-checking. Although BPMN is the de-facto standard process modeling notation due to its understandability and ease of use, in this work we rely on time Petri nets (Popova-Zeugmann, 2013) satisfying the workflow properties (van der Aalst, 1996) for process modeling because of their well-defined semantics and their analysis capabilities. Nonetheless, note that many process modeling notations, including BPMN, can be automatically mapped to Petri nets (e.g. by implementing the transformations defined by, e.g. Lohmann et al. (2009)). A Petri net is a directed graph with two kinds of nodes, interpreted as places and transitions, such that no arc connects two nodes of the same kind. The places of the Petri net might contain tokens, whose distribution might change over time, giving rise to the net behavior. Definition 1 (Petri net) APetri net is a 5-tuple PN = (P,T,F,M0,ν), where: P={p1,p2, ..., pn}is the set of places, represented graphically as circles, T={t1,t2, ...,tn}is the set of transitions, represented graphically as rectangles, F⊆(P×T)S(T×P)is the set of arcs (flow relations), represented as arrows and describing a bipartite graph, M0is the initial marking, where a marking (or state)M={µ(p1),µ(p2), ..., µ(p|P|)},µ: P→Z≥0, represents the distribution of tokens over the set of places. When it assigns a nonnegative integer kto place p, we say that pis marked with ktokens. Pictorially, we place k black dots (tokens) in place p; and ν:F→Z+is the arc weight mapping indicating cardinality constraints on the movement of tokens throughout the net. The input places and the output places of each transition t∈Tare •t={p∈P|(p,t)∈F}and t•={p∈P|(t,p)∈F}, respectively. Similarly, the input transitions and the output transitions of each place p∈Pare •p={t∈T|(t,p)∈F}and p•={t∈T|(p,t)∈F}, respectively. The initial marking of the Petri net M0, which represents the initial distribution of tokens over the places, can change into successor markings. These changes are described as firing rules. Such rules introduce a dynamic aspect to the Petri net by allowing the firings to modify the state of the Petri net. The minimum number of necessary tokens on the places for enabling a transition tis defined by ν(p,t). A transition tis enabled when there are at least as many tokens as ν(p,t)in each input place p∈•t. An enabled transition can therefore fire. The number of tokens which are added to each output place after firing of tis defined as ν(t,p). The firing of a transition changes 5 [1,∞] [4,∞] [10,∞] [5,∞] tRT (Revise Text) tRV (Revise Visual) [1,∞] pstart pend tSPR (Send Press Release) tPM (Proofread Manuscript) tRM (Receive Manuscript) ti Fig. 2: Petri net model of the book publishing process the current marking by subtracting ν(t,p)amount of tokens from each input place p∈•tand adding ν(p,t)amount of tokens to each output place p∈t•, and hence, it moves the net from a marking Mk−1to a new marking Mkdenoted as Mk−1 tk −→ Mk. A firing sequence of transitions σ=t1,t2, ...,tnchanges the state of the Petri net at each firing: M0 t1 −→ M1 t2 −→ ... tn −→ Mn. A marking Mkis reachable if there is a sequence σsuch that M0 σ −→ Mk(i.e. from the initial marking to Mk). Petri nets are classified according to several criteria, including cardinality and behavioral constraints. The Petri nets that represent the business processes addressed in this work have the following properties: They constitute a so-called workflow net (van der Aalst, 1996), which means that they contain a starting place pssuch that •ps=/0 and an ending place pesuch that p• e=/0; and they are connected, i.e. every node in the Petri net is on the path from psto pe. They are 1-safe, which means that each place contains at most one token at any state (i.e. for any place p∈P, 0 ≤µ(p)≤1). They are free-choice, which implies that the choice between multiple transitions can never be influenced by the rest of the net (i.e. for any two different places {pi,pj} ⊆ P,(p• i∩p• j) = /0 or p• i=p• j), Their transitions are labelled with a minimum and a maximum waiting time in order to be able to represent the temporal aspects related to activities needed for resource allocation, i.e. Time Petri nets (TPN) (Popova-Zeugmann, 2013). Definition 2 (Time Petri net) A time Petri net is a 6-tuple TPN = (P,T,F,M0,ν,∆), where: P,T,F,M0,νconstitute a Petri net, and ∆:T→Z≥0×(Z≥0∪{∞})is the interval function of the T PN, where ∆(t)=[δmin(t),δmax(t)]. δmin(t)and δmax(t)are the minimum and maximum waiting time to fire tin a use-case specific time unit (TU) (e.g. in minutes, hours or days). In time Petri nets, process activities correspond to timed transitions. The periods that timed transitions (we will call them activity transitions) are enabled (i.e. waiting times) represent activity durations and transition firings indicate activity completions. If the maximum waiting time of tis ∞, it means that the firing of tis not enforced to occur at any time. Figure 2 illustrates the time Petri net representation of the book publishing process described above, extended to reflect the minimum duration estimations of the process activities (i.e. δmin(t)). 6Giray Havur, Cristina Cabanillas, Axel Polleres The activity transitions are graphically represented by empty squares along with their minimum and maximum waiting times on top. On the contrary, the immediate transitions are shown as filled squares and they fire immediately (i.e. their earliest firing time and latest possible firing time are both equal to 0). These are used for representing concurrent activities in process executions (e.g. tiin Figure 2). Four types of ordering relations can be identified between transitions of a Petri net. Specifically, given two transitions tx,ty∈Tof a Petri net, then: txdirectly precedes ty, denoted as tx→ty, if the net contains a path with exactly two arcs (i.e. (tx,pi)∪(pi,ty)⊆F) leading from txto ty(e.g. tPM and tiin Figure 2). This precedence relation is reduced to cover activity transitions in the direct activity precedence relation, denoted as tx a −→ty, such that t0→t1→ ··· → tnwhere only t0and tnare activity transitions (e.g. tPM a −→tRT and tPM a −→ tRV in Figure 2). txprecedes ty, denoted as tx⇒ty, if the net contains a path with at least two arcs leading from txto ty(e.g. tRM and tSPR in Figure 2). txis in conflict with ty, denoted as tx#ty, if the net contains two paths leading to txand ty, respectively, which start at the same place and immediately diverge (e.g. tSPR and tiin Figure 2). txcan be executed parallelly with ty, denoted as tx||ty, if txand tyare neither in preceding nor in excluding relation (e.g. tRT and tRV in Figure 3). The conflicting transitions are necessary to describe a choice (or decision) point in process executions. For example, in Figure 2 it is not known before running the process if the manuscript will be ready to be sent for the press release or it will require (other) revision rounds. However, this kind of uncertainty that causally divides the search space prevents us from allocating resources and starting times to activities in a global time-optimal way. In order to avoid this, we first obtain an instance of the unfolding (i.e. a partial run of the net) of the process which contains no conflicts by making assumptions on these choices ahead of time, as explained next. Unfolding (Bonet et al., 2008) is a method used for developing processes with no conflicts. It generates possible firing sequences of the given Petri net PN = (P,T,F,M0,ν)while it maintains the partial order of transitions based on the precedence relation induced by the net. It produces a pair β= (ON,ϕ), where ON = (PB,TE,F0)is an occurrence net, which is a Petri net without conflicts and cycles, and ϕ:PB∪TE→P∪Tis a homomorphism from ON to PN. Definition 3 (Occurrence net) An Occurrence net ON = (PB,TE,F0)is a net where PBis the set of conditions (cf. places), TEis the set of events (cf. transitions) and F0are the arcs between PBand TEdefined as follows: ∀b∈PB,|•b| ≤ 1 and Nis acyclic, ∀e∈•PB, the set b∈•TEis finite, and 6 ∃e∈TE,e#e(i.e. there is no event in self-conflict). The process of unfolding breaks all reachable places in conflict by making independent copies of such places. For this reason, ON may contain multiple copies of the nodes in the original net. In most cases, βis infinite and cannot be built, therefore it requires a cut-off event to halt. We refer the reader to (Bonet et al., 2008) for further details. In order to rematch the conditions and events back to places and transitions, we introduce the concept of branching net (Couvreur et al., 2013). Definition 4 (Branching net) 7 pstart pend tRM (Receive Manuscript) tRT (Revise Text) [1,∞] tRV (Revise Visual) tPM (Proofread Manuscript) tPM2 (Proofread Manuscript 2) tSPR (Send Press Release) [4,∞] [10,∞] [5,∞] [4,∞] [1,∞] ti Fig. 3: Unfolded process to publish a book with the assumption that the loop is taken once A branching net of a Petri net system PN = (P,T,F,M0,ν)is a labeled occurrence net ONλ= (PB,TE,F0,λ)where the labeling function λsatisfies the following properties: λ(PB)⊆Pand λ(TE)⊆T, ∀p∈P,∃b∈PB,λ(p) = b(i.e. λis a surjection), |{b∈PB:µ0(λ(b)) = 1,λ(b) = p}| =1, ∀e1,e2∈TE, if •e1=•e2and λ(e1) = λ(e2), then e1=e2. After obtaining a branching net ONλfrom a given net, we lastly introduce assumption set to decompose ONλand thus generate the conflict-free instance of the net PN. An assumption set is described as A⊆2(T×Z≥0), which constraints the cardinality of events in the selected subnet that starts from bs∈PB,λ(bs) = psand ends at be∈PB,λ(be) = pe, that is, ON0 λ= (P0 B,T0 E,F00,λ) satisfies (1) ∀(ti,ni)∈A: |T0 Eti|=niwhere T 0 Eti=[ e∈T0 E,λ(e)=ti e(1) Moreover, in order to preserve the time intervals in the selected subnet for the duplicated transitions, we use the λfunction where any e∈T0 E, the minimum and the maximum waiting times are ∆(t) = [δmin(t),δmax(t)] where λ(e) = t. For example, we generate the Petri net in Figure 3 from the branching net of the time Petri net in Figure 2 using the assumption set A= {(tRT ,1)}that leads to the selection of the subnet where there is only one revise text activity. 2.2 The RBAC Model Different types of organizational structures give rise to different organizational models (Horling and Lesser, 2004). In most cases, the employees of the organization (i.e. its human resources) play one or more organizational roles according to their skills and characteristics. One of the most widely known models for capturing organizational structures based on roles is the Role-Based Access Control (RBAC) model (Colantonio et al., 2009). Definition 5 (RBAC Model) An RBAC Model is a 6-tuple O= (A,R,L,SAL,SRL,SLL), where: Ais the set of activities that corresponds to the activity transitions in a TPN = (P,T,F,ν,M0,∆), hence A⊆T, Ris the set of resources, Lis the set of roles, 8Giray Havur, Cristina Cabanillas, Axel Polleres Table 1: RBAC model of the publishing entity activity-to-role resource-to-role role-to-role Receive Manuscript Publisher Amy Publisher Publisher Copy Editor Proofread Manuscript Copy Editor Glen Copy Editor Revise Text Copy Editor Drew Copy Editor Revise Visual Graphic Artist Oliver Graphic Artist Send Press Release Administrative Assistant Evan Administrative Assistant SAL ⊆2(A×L)is the set of activity-to-role assignment tuples specifying which activity can be executed by the resources associated with which role(s) (commonly known as resource assignment in BPM), SRL ⊆2(R×L)is the set of resource-to-role assignment tuples identifying the roles of a resource, SLL ⊆2(L×L)is the set of role-to-role assignment tuples that creates a hierarchical (sub-role) structure. The symbol indicates the ordering operator. If l1l2, then l1 is referred to as the senior of l2. Conversely, l2 is the junior of l1. Let us assume that the book publishing process (cf. Figure 1 and Figure 2) is executed within an organization composed of five resources R={Amy,Glen,Drew,Oliver,Evan}that are assigned to four distinct roles L={Publisher,Copy Editor,Graphic Artist,Administrative Assistant}. Table 1 shows a possible RBAC model of such a publishing entity. For instance, within the activity-to-role relation, the first entry means that the activity Receive Manuscript can be executed by the members of the role Publisher; within the resource-to-role relation, the first entry means that the resource Amy has the role Publisher; and within the role-to-role relation, the first entry means that the resources with the role Publisher can execute the same activities as the resources with the role Copy Editor (specifically, Publisher Copy Editor). After we describe who can execute which activity in a RBAC model, now we can define which activity requires how many resources to be performed. Definition 6 (Activity Resource Demand Set) The activity resource demand set NAR ⊆2(A×Z≥0)represents the number of resources activity a demands to be executed. Like the minimum and maximum duration of activities, the activity resource demand values are also estimated by process managers. In our running scenario, all activities demand only one resource except Revise Text which demands two resources. 2.3 Temporal Knowledge In a real world scenario, the minimum and maximum duration of activities as well as the tentative deadlines for the completion of the process instances (i.e. each process execution) are estimated by the process managers. The process instances are usually managed with BPM Systems (BPMS) that provide functionality for defining and customizing process models, and for administrating and monitoring their executions. The execution data is stored in process execution (or event) logs or audit trails. The log entries comprise information about the events occurred during process execution, including resource-related properties (who executed each activity3) and temporal 3Within an organizational context, the resources that appear in the log are among those available according to the organizational model of the functional unit (e.g. an RBAC model). 15 Table 4: Parameters for generating resource allocation problem instances Petri net generator RBAC generator Temporal knowledge generator Number of activities nANumber of resources nRUpper bound u Degree of parallelism δpNumber of roles nLNumber of resource-activity duration ndRA Number of role-activity duration ndLA 3.2.2 Running Example The result of the running example described in Section 2 is computed by our program as follows: allocate(amy,tRM,0,1) allocate(glen,tPM,1,2) allocate(glen,tRT,2,8) allocate(amy,tRT,2,6) allocate(oliver,tRV,2,6) allocate(glen,tPM2,8,9) allocate(evan,tSPR,9,12) The optimized makespan is 12 hours. As Receive Manuscript can only be performed by the role Publisher, and therefore Amy is allocated to it. Glen is allocated to Proofread Manuscript due to the fact that the solver knows he can execute it faster than others (cf. raDuration(glen,aPR,1)). Glen and Amy are allocated to Revise Text as it requires two resources to be performed (cf. aDemand(aRT,2)). Revise Visual takes 4 hours because laDuration(graphicArtist,aRV ,4)overwrites the default duration minActDuration(aRV ,5). 3.3 Problem Instance Generator A formalized problem instance generator is necessary for a thorough evaluation of ASP systems against problems that have different sizes and properties. Our problem instance generator consists of three main parts: a Petri net generator; an RBAC model and activity resource demand generator; and a temporal knowledge generator. The required parameters for each of them are provided in Table 4. Petri net generator: For our benchmark we first generate conflict-free Petri nets using the Generate block-structured stochastic Petri net plug-in (Rogge-Solti, 2014) of the process mining tool ProM (van der Aalst, 2016). This generator performs a series of random structured insertion operations of new control-flow constructs resulting in a random Petri net that is by generation sound, free-choice and block-structured. The input of the Petri net generator is as follows: the number of activities nA∈Z+and the degree of parallelism of the generated net δp∈Z≥0, and 0 ≤δp≤100. The generated Petri net PN = (P,T,F,M0,ν)is described with the predicates: place(p)(i.e. p∈P), transition(t)(i.e. t∈T), aTransition(a)(i.e. a∈Aand A⊆T), iPlace(p,t)(i.e. p∈•t) and oPlace(p,t)(i.e. p∈t•). By changing the values of the input parameters, different sequentiality and parallelism degrees are realized in the generated Petri nets. For instance, in Figure 6 where nA=6, (a) has no parallel activities, (c) has no sequential activities, and (b) has both parallel and sequential activities. The generated Petri nets could be understood as being equivalent to the conflict-free Petri net that would arise from translating, e.g., a BPMN model to a Petri net first; and then deriving the branching net of this net and selecting a subnet that holds an assumption set. As the RBAC model requires the set of activities A, which is necessary for activity-to-role assignments, now we can further continue describing RBAC model generation. 16 Giray Havur, Cristina Cabanillas, Axel Polleres tA tBtCtD tE tF (a) δp=0 tB tC t0_split t1_join tD t2_split t3_jointE tF t4_split t5_join tA (b) δp=50 tA tB t0_split t1_join tC t2_split t3_join tD t4_split t5_join tE t6_split t7_join tF t8_split t9_join (c) δp=100 Fig. 6: Three generated Petri nets RBAC model and activity resource demand generator: We generate a RBAC model O= (A,R,L,SAL,SRL,SLL)where A⊆Tgiven a number of resources nR, a number of roles nLand the output of the Petri net generator by using the following ASP program: Input: aTransition/1, nR/1, nL/1 Output: alAC/2, rlAC/2, llAC/2, aDemand/2 34resource (1). role (1). 35resource ( R1) :- resource (R) , nR (N), R1 =R+1 , R1 <= N. 36role( L1) :- role (L), nL(N), L1=L +1, L1 <= N. 371 <={ alAC (A ,L): role ( L)} :- aTransition (A). 381 <={ rlAC (R ,L): role ( L)} :- resource (R ). 39{ llAC (L , L1 ): role ( L1 )} : - role ( L). 40:- llAC (L ,L). 41nrlAC (L ,N ):- N =# count {R: rlAC (R ,L )}, role ( L). 42{ aDemand (A,N )} <=N :- aTransition (A ), alAC (A ,L), nrlAC (L ,N ). Lines (34-36) generate R={r1,r2, ..., rnR}and L={l1,l2, ..., lnL}using the parameters nRand nL. Line (37) generates the set SAL (i.e. every activity ahas at least one assigned role l). Line (38) generates the set SRL (i.e. every resource rhas at least one assigned role l). Line (39) generates the set SLL and constraint (40) guarantees that a role lcannot be senior to itself. Lines (41,42) generate the activity resource demand set (i.e. NAR). Temporal knowledge generator: We generate the temporal knowledge (i.e. ψ(r,a)and ψ(l,a)) along with the default durations of activities (i.e. for each activity a,δmin(a)) given an upper bound u, a number of resource-activity duration ndRA , a number of role-activity duration ndLA and the output from the previously defined generators by using the following ASP program: Input: upperBound/1, ndRA/1, ndLA/1, aTransition/1, alAC/2, rlAC/2, llAC/2 Output: minActDuration/1, raDuration/2, laDuration/2 43nA(N) :- #count{A: activity (A) }= N. 44maxActivityDuration (U/N) :- upperBound (U) , nA(N). 45aDurationDomain (M) :- maxActivityDuration (M). 46aDurationDomain ( M1) :- aDurationDomain (M ), M >0 , M1=M -1. 471<={ minActDuration (A,D): aDurationDomain (D) } <=1 :- aTransition (A). 48N <={ raDuration (R ,A ,D): alAC (A ,L) , rlAC (R ,L) , aDurationDomain (D)} <= N :- ndRA (N). 49: - raDuration (R ,A ,D) , raDuration (R ,A , D1 ) ,D != D1 . 50alAC (A, L1 ) :- llAC (L1 ,L2), alAC (A, L2 ). 51N <={ laDuration (L ,A ,D): alAC (A ,L) , aDurationDomain (D )} <= N :- ndLA (N). 52: - laDuration (L ,A ,D) , laDuration (L ,A , D1 ) ,D != D1 . Lines (43-46) estimates the maximum value of activity duration from the upper bound uand derives a variable domain for the activity durations. Line (47) assigns one default duration per activity (i.e. δmin(a)). Lines (48,49) generates the resource-activity durations. Lines (50-52) generates the role-activity durations. 17 Table 5: Properties of problem instances id nAδpnRnLSAT u id nAδpnRnLSAT u id nAδpnRnLSAT u 18 50 2 1 yes 90 24 16 30 16 4 yes 90 47 32 90 16 8 yes 330 28 75 4 1 yes 70 25 16 30 16 4 yes 85 48 32 80 16 8 yes 260 38 100 4 1 yes 105 26 16 90 16 4 yes 140 49 32 90 16 8 yes 310 48 100 8 2 yes 70 27 16 30 37 8 yes 65 50 32 90 16 8 yes 360 516 90 2 1 yes 200 28 16 50 35 8 yes 75 51 32 50 17 4 yes 145 616 50 4 1 yes 75 29 16 75 35 8 yes 130 52 32 50 17 4 yes 145 716 90 8 4 yes 175 30 16 90 34 8 yes 190 53 32 50 32 16 yes 160 816 50 4 1 yes 120 31 32 90 2 1 yes 330 54 32 80 16 4 yes 330 916 90 4 1 yes 185 32 32 95 2 1 yes 360 55 32 50 33 8 yes 380 10 16 75 4 1 yes 145 33 32 30 4 1 yes 100 56 32 90 32 16 yes 345 11 16 90 4 1 yes 210 34 32 60 4 1 yes 210 57 32 90 17 4 yes 350 12 16 90 9 2 yes 205 35 32 75 8 4 no 210 58 32 50 32 16 yes 235 13 16 50 8 2 yes 130 36 32 60 4 1 yes 275 59 32 50 16 4 yes 360 14 16 75 8 2 yes 75 37 32 30 4 1 yes 270 60 32 80 32 16 yes 290 15 16 40 16 8 yes 85 38 32 85 4 1 yes 270 61 32 60 32 16 yes 520 16 16 40 8 2 yes 75 39 32 85 4 1 yes 300 62 32 50 33 8 yes 150 17 16 90 16 8 yes 190 40 32 90 4 1 yes 145 63 32 80 34 8 yes 317 18 16 90 8 2 yes 210 41 32 90 8 4 yes 355 64 32 90 33 8 yes 340 19 16 75 8 2 yes 115 42 32 90 8 4 yes 360 65 64 90 8 4 no 305 20 16 75 16 8 yes 120 43 32 30 8 2 yes 200 66 64 90 8 4 no 310 21 16 90 16 8 yes 165 44 32 75 16 8 yes 280 67 64 60 16 8 yes 295 22 16 90 9 2 yes 200 45 32 90 8 2 yes 315 68 64 90 16 8 yes 710 23 16 30 17 4 yes 75 46 32 50 16 8 yes 170 69 64 60 64 32 yes 320 70 64 90 64 32 yes 620 4 Benchmark for ASP Systems Our benchmark is configurable in the sense that any combinations of given ASP grounders and ASP solvers are compared against each other. In order to get a good idea of how challenging our problem is for the state-of-the-art ASP systems, we have selected the ASP grounders GRINGO (Gebser et al., 2011) and I-DLV (Calimeri et al., 2017), as well as the ASP solvers CLASP (Gebser et al., 2015) and WASP (Alviano et al., 2017). We have selected those grounders and solvers due to their top rankings in the latest ASP Competition (Gebser et al., 2017b). Every possible grounder+solver combination is competed against each other. Hence, our baseline benchmark run consists of four different ASP grounder+solver configurations: GRINGO+CLASP (i.e. CLINGO (Gebser et al., 2014)), GRINGO+WASP,I-DLV+CLASP, and I-DLV+WASP (i.e. DLV 2.0 (Alviano et al., 2017)). We use the most up-to-date versions of these grounders and solvers: GRINGO 5.3.0,I-DLV 1.1.1,CLASP 3.3.4,WASP 2.0. These tools are executed on their default options (i.e., no parameter is given). Platform: The benchmark has been run on an Ubuntu Linux server (64bit), equipped with 16 core 2.40 GHz Intel Xeon Processor and 128 GB RAM. Time and memory for each run were limited to 2 hours CPU clock time and 20 GB, respectively. Problem Instances: We have generated 70 problem instances using our instance generator. The details of these instances are provided in Table 5. In the table, id is the unique identifier of each instance, nAis the number of activities to which resources are going to be allocated, δpis the degree of parallelism of the generated Petri net, nRis the number of resources, and nLis the number of roles. The SAT column indicates if there exists a feasible solution for the problem instance, in other words, if there is a feasible makespan cmax where cmax ≤u.uis the upper bound for the makespan for the solutions as described in Section 3.3. Benchmark Results: We have summarized the benchmark results in Tables 6 and 7. Table 6 shows the performance statistics of two grounders while grounding the problem instances. time is the CPU time in seconds, mem is the memory used in MB, and |g(Π)|is the size of the ground program in MB. Table 7 presents the performance statistics of only the ASP solvers. CLASP(GRINGO) indicates the performance of the solver CLASP using the ground program from the grounder GRINGO.cmax is the makespan computed by the system, which is minimized by 18 Giray Havur, Cristina Cabanillas, Axel Polleres Table 6: Grounder statistics GRINGO I-DLV GRINGO I-DLV id time mem |g(Π)| time mem |g(Π)| id time mem |g(Π)| time mem |g(Π)| 13 7 29 3 74 20 36 1689 22 16323 960 4403 4526 27 8 74 4 86 25 37 1572 23 15544 1049 4272 4347 319 8 163 11 174 56 38 1459 18 15766 855 4284 4363 47 7 85 3 129 28 39 1860 20 19515 1107 5158 5422 568 9 527 76 598 330 40 460 15 4465 265 1300 1218 630 9 316 15 193 91 41 672 15 6743 1176 8736 3818 730 9 287 52 737 188 42 445 15 6939 925 8969 3927 877 9 752 46 439 239 43 513 18 8369 491 3552 2376 9192 10 1858 116 1024 570 44 233 16 4192 26 150 292 10 112 10 1129 66 643 350 45 1245 24 21315 1307 8285 6056 11 222 11 2301 137 1226 700 46 94 11 1519 10 92 115 12 291 13 2977 252 2003 809 47 356 15 5810 37 174 394 13 95 11 972 87 821 311 48 205 15 3593 23 142 252 14 29 9 297 5 179 46 49 291 14 5129 31 164 350 15 8 8 97 1 30 14 50 463 18 6912 44 187 465 16 27 9 307 5 180 46 51 290 13 5130 20 96 182 17 43 10 456 6 54 67 52 309 16 5530 21 97 191 18 259 11 2449 227 1870 751 53 78 11 1334 8 141 111 19 75 9 684 65 595 222 54 1283 25 23428 2266 14761 6651 20 21 8 184 3 39 27 55 2011 28 32896 120 373 1073 21 31 9 344 4 49 49 56 374 17 6341 35 293 447 22 242 11 2817 151 1869 735 57 1724 21 29670 1508 18263 8335 23 37 8 345 3 32 25 58 154 12 2900 16 207 217 24 45 9 438 3 34 32 59 1643 27 27747 1431 18011 8234 25 40 8 398 3 33 29 60 253 16 4495 25 251 325 26 87 10 1025 17 567 157 61 807 19 14386 83 456 993 27 29 9 308 2 42 26 62 282 13 5158 20 154 201 28 32 9 351 3 45 30 63 1461 26 24932 85 325 800 29 109 10 1161 8 74 84 64 1624 26 26446 102 335 871 30 244 11 2214 17 96 148 65 1120 26 19233 93 198 726 31 591 14 6122 489 3151 3320 66 1268 59 20685 114 204 768 32 814 15 6860 776 3688 3744 67 1094 26 18091 86 308 678 33 246 12 2278 159 717 638 68 - 37 93938 512 737 3847 34 1092 15 9483 669 2598 2582 69 1242 22 21228 78 981 925 35 232 12 2199 21 72 161 70 5118 45 80788 279 1907 3130 the weak constraint. Under this column, bold and italic numbers are the confirmed optima cases; other values are the instances for which a solution is found but the solution is not proven to be the optimal one (e.g. when the time or the memory limit is reached). For both of the tables “–” under time column means “out-of-time” and “–” under mem column means “out-of-memory”. The box plots in Figure 7 visually summarize Tables 6 and 7. We logarithmically scaled the yaxis of the plots for the sake of readability. 90% of the samples are in between the upper and lower whiskers. The solid green line represents the median, and the dashed green line represents the mean of the sample. Figure 7(a) and Figure 7(b) compare the CPU execution times of grounders and solvers. Fig. 7(c) and Figure 7(d) compare the memory usage of grounders and solvers. Figure 7(e) reports on the ground program sizes of the instances. By looking at Figure 7(a) and Figure 7(c), we find out that I-DLV grounds the problem instances much faster than GRINGO, however it has a larger memory footprint. The program rewriting (i.e. intelligent projections) feature of I-DLV is a vital optimization for this problem as the ground programs that are generated by I-DLV are way smaller than those generated by GRINGO (cf. Table 6 and Figure 7(e)). The cactus plots in Figure 8 separately compare the grounder and solver performances. Less steep curves (cf. Figure 8(b)) and smaller memory footprint (cf. Figure 7(d)) of CLASP(GRINGO) and CLASP(I-DLV)–in comparison to those of WASP(GRINGO) and WASP(I-DLV)–concludes that the ASP solver CLASP performs better than WASP for our benchmark problem. 19 Table 7: Solver statistics CLASP(GRINGO)WASP(GRINGO)CLASP(I-DLV)WASP(I-DLV) id u time mem cmax time mem cmax time mem cmax time mem cmax 190 315 279 69 533 680 69 345 169 69 465 415 69 270 73 581 54 107 1487 54 12 200 54 37 485 54 3105 720 1426 79 1535 3588 79 498 439 79 415 855 79 470 97 733 55 371 1875 55 21 257 55 50 702 55 5200 – 5964 200 – 14000 192 3923 1865 149 – 3639 179 675 – 2947 68 – 7220 68 – 543 68 3037 1109 68 7175 2305 3360 133 4788 7821 133 1217 1449 133 2971 3459 133 8120 – 7912 98 – 18600 101 – 1302 92 – 2650 92 9185 5302 – 192 19007 – 3196 – 6245 176 10 145 7146 12026 106 – 5279 1941 108 5014 3908 108 11 210 6646 – 207 – – 3876 – 7567 12 205 – 11788 315 – – 5156 192 – 10920 13 130 – 10487 134 96 – 2025 2042 104 2084 4368 104 14 75 1785 3190 59 2278 7411 59 84 467 59 133 983 59 15 85 115 951 64 148 2317 64 3 116 64 17 234 64 16 75 935 2985 56 432 6962 56 34 456 56 56 1003 56 17 190 5134 5547 144 7157 12500 160 68 432 144 279 418 144 18 210 – 10295 267 – – 4825 206 – 10081 19 115 – 8690 109 – 18098 100 377 1482 86 929 3162 86 20 120 479 2067 92 889 4860 92 13 205 92 33 279 92 21 165 1739 4026 124 4562 9450 124 37 344 124 111 373 124 22 200 – 11283 253 – – 4753 160 – 9817 195 23 75 1766 3395 64 1730 8062 64 10 202 64 25 283 64 24 90 4032 4319 64 2545 10498 64 25 234 64 57 299 64 25 85 1785 3793 67 2171 9018 67 14 217 67 30 289 67 26 140 – 11780 83 – 599 1571 106 1609 2888 106 27 65 1060 2995 48 388 7016 48 9 242 48 16 433 48 28 75 1433 3664 56 1013 8255 56 17 260 56 83 449 56 29 130 – 12586 122 101 – 91 609 99 183 803 99 30 190 – 9359 260 – 650 1026 143 933 1082 143 31 330 621 – 1010 – – 11872 284 – 32 360 670 – 1168 – – 13344 297 – 33 100 – 10537 258 – – 2467 – 5751 34 210 635 – 1006 – – 9483 287 – 35 210 5856 – 234 – 271 919 411 553 36 275 605 – 928 – – 16237 312 – 37 270 553 – 938 – – 15679 145 272 – 38 270 582 – 869 – – 15746 243 – 39 300 635 – 1070 – 997 – 221 – 40 145 618 – 555 – – 4612 – 10675 41 355 634 – 1017 – 796 – 161 – 42 360 406 – 795 – 565 – 145 – 43 200 366 – 628 – – 10440 76 170 – 44 280 – 17891 396 – 545 1770 210 1119 1258 210 45 315 366 – 660 – 803 – 124 – 46 170 – 17411 87 – 57 769 125 170 701 125 47 330 414 – 793 – 2194 2289 250 3650 2063 250 48 260 – 14796 307 – 499 1559 197 1034 1079 197 49 310 386 – 573 – 1241 2069 233 2896 1824 233 50 360 391 – 786 – 1998 2818 271 4946 2654 271 51 145 356 – 450 – 197 1142 110 288 954 110 52 145 347 – 506 – 469 1194 118 666 1017 118 53 160 – 15506 150 94 – 58 846 122 204 1076 122 54 330 414 – 757 – 790 – 132 – 55 380 397 – 755 – 2286 6601 163 2644 4370 163 56 345 415 – 723 – 1975 2953 258 4291 2695 258 57 350 369 – 672 – 456 – 47 – 58 235 6300 – 183 – 102 1522 132 553 1580 132 59 360 384 – 770 – 465 – 48 – 60 290 352 – 448 – 655 2120 215 1622 1962 215 61 520 399 – 812 – 677 5929 123 2685 3665 123 62 150 357 – 479 – 266 1437 126 366 1631 126 63 317 394 – 769 – 5339 4903 238 5881 4326 238 64 340 412 – 769 – – 5619 313 – 4394 274 65 305 414 – 783 – 1640 3865 2002 1933 66 310 396 – 713 – 2072 4057 2397 2091 67 295 416 – 769 – 2424 3908 221 3945 2545 221 68 710 481 – – 7885 69 320 395 – 760 – 5794 6307 238 – 7863 313 70 620 378 – 838 – 7152 – – 16188 20 Giray Havur, Cristina Cabanillas, Axel Polleres gringo idlv 100 101 102 103 Execution time (s) clasp (gringo) wasp (gringo) clasp (idlv) wasp (idlv) 101 102 103 gringo idlv 101 102 103 104 Memory (MB) clasp (gringo) wasp (gringo) clasp (idlv) wasp (idlv) 102 103 104 gringo idlv 101 102 103 104 105 Ground program size (MB) (a) (b) (c) (d) (e) Fig. 7: Box plots regarding the performance statistics of grounders and solvers 0 20 40 60 Number of grounded instances 0 10000 20000 30000 40000 Execution time (s) gringo idlv 0 10 20 30 40 Number of solved instances 0 10000 20000 30000 40000 50000 60000 Execution time (s) clasp(gringo) wasp(gringo) clasp(idlv) wasp(idlv) (a) Grounding times (b) Solving times Fig. 8: Sorted cactus plots Overall, I-DLV+CLASP completes 41 instances in given time and memory constraints whereas I-DLV+WASP,GRINGO+CLASP, and GRINGO+WASP complete 40, 16, and 15 instances, respectively. I-DLV+CLASP is clearly the most performant ASP system of our baseline benchmark. Our benchmark execution scripts, problem instance generator, and the instances described in Table 5 are available at https://goo.gl/Xrd2Hq. 5 Related Work The complexity of the resource allocation problem in domains similar to BPM has been widely acknowledged in other research areas, such as Constraint Programming (CP) and Operations Research (OR). The survey conducted in (Lombardi and Milano, 2012) studied resource allocation and scheduling separately and jointly. Pure scheduling problems (which traditionally assume static task network and resource requirements) have been mostly addressed with CP techniques (Baptiste et al., 2001). Resource allocation, on the contrary, has been typically tackled as a MRCPSP with OR techniques (Brucker et al., 1999). For addressing large problem instances in real-world scenarios in which scheduling and resource allocation have to be jointly considered, hybrid CP/OR approaches were developed, including Logic Based Benders Decomposition (Hooker and Ottosson, 2003) and Self-adaptive Large Neighborhood Search (Laborie, 2009). In (Drexl et al., 2000), the authors extended the MRCPSP to consider further temporal aspects like travel times between tasks that have to be performed at two different locations by 21 the same resources. New concepts, such as partially renewable resources, were introduced and incorporated to the ProGen problem instance generator (Kolisch et al., 1995). The work presented in this paper constitutes a realistic benchmark for declarative formalisms as our problem also involves the consideration of resource allocation and scheduling aspects. Specifically, the resource allocation problem in BPM is characterized by the essential ideas behind designing and managing business processes, and organizational models are crucial for extracting resource allocation requirements in BPM (Rosemann and vom Brocke, 2015). The extensive BPM literature with real use cases (Vom Brocke et al., 2010; Brocke and Rosemann, 2014; Dumas et al., 2018) is helpful for inferring those requirements. In our previous work, we addressed resource allocation in business processes with different problem configurations (i.e. Petri net semantics based encoding (Havur et al., 2015), extension of MRCPSP (Havur et al., 2016)). Nevertheless, Petri nets were encoded with ASP also in (Anwar et al., 2013), where the execution semantics of Petri nets is reflected for simulating biological pathways. However, in the work at hand, for improving the performance of our encoding we have eliminated these simulation-oriented aspects, which are redundant for resource allocation and scheduling purposes. We believe ASP is a powerful formalism for addressing such a hard problem based on our previous work and on results found in the ASP Programming Competition, a biennial event aimed at providing challenging benchmark collections and evaluating the advancement of the state of the art in ASP solving (Gebser et al., 2017b). According to the categories defined based on the ASP features required for the encoding of the problems, resource allocation in business processes is an optimization problem (Gebser et al., 2017b). ASP has been successfully used for addressing optimization problems in other domains, as demonstrated in the 6th ASP Programming Competition, including, among others, Crossing Minimization (Gange et al., 2010), Valves Location (Gavanelli et al., 2015), MaxSAT (Li and Many` a, 2009), Steiner Tree (Erdem and Wong, 2004), System Synthesis (Biewer et al., 2015) and Video Streaming (Toni et al., 2014). The problem of resource allocation in business processes will be subjected to analysis within the 7th edition of the ASP Programming Competition (Gebser et al., 2017a). 6 Conclusions We have modeled the resource allocation problem and provided an instance generator for benchmarking ASP systems. Our results show that this optimization problem is challenging for the current ASP systems which have received the highest performance scores in the 6th ASP Programming Competition held in 2015 (Calimeri et al., 2016). Future research on optimizing the problem encoding for improving its computational efficiency might extend the applicability of our approach in solving the resource allocation in BPM in large-scale by using ASP. Apart from it, it is also on our agenda to extend our benchmark towards a more detailed comparison of many formalisms, and their systems might prove quite beneficial to both the LP and the BPM communities: the LP community would be provided with an application-oriented problem domain for assessing the advances in formalisms (the ease of encoding the resource allocation problem, i.e., the compactness, readability, modularity and maintainability of problem encoding) and the computational performance of their solvers; and the BPM community would be given a solid evaluation of different approaches and encouraged to try these resource allocation methods out-of-the-box, preferably via an interface to already existing BPMSs. 22 Giray Havur, Cristina Cabanillas, Axel Polleres References ALVIANO, M., CALIMERI, F., DODARO, C., FUSC ` A, D., LEONE, N., PERRI, S., RICCA, F., AND VELTRI, P. 2017. The ASP System DLV2. In Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR), M. Balduccini and T. Janhunen, Eds. Vol. 10377. Springer, 215–221. ALVIANO, M., DODARO, C., LEONE, N., AND RICCA, F. 2015. Advances in WASP. In Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR), F. Calimeri, G. Ianni, and M. Truszczynski, Eds. Vol. 9345. Springer, 40–54. ANWAR, S., BARAL, C., AND INOUE, K. 2013. Encoding Petri Nets in Answer Set Programming for Simulation Based Reasoning. CoRR abs/1306.3542, 1–17. BAPTISTE, P., PAPE, C. L., AND NUIJTEN, W. 2001. Constraint-Based Scheduling. Kluwer Academic Publishers. BIEWER, A., ANDRES, B., GLADIGAU, J., SCHAUB, T., AND HAUBELT, C. 2015. A Symbolic System Synthesis Approach for Hard Real-time Systems Based on Coordinated SMT-solving. In Design, Automation & Test in Europe Conference & Exhibition (DATE), W. Nebel and D. Atienza, Eds. ACM, 357–362. BONET, B., HASLUM, P., HICKMOTT, S., AND THI ´ EBAUX, S. 2008. Directed unfolding of petri nets. In Transactions on Petri Nets and Other Models of Concurrency I. Springer, 172–198. BREWKA, G., EITER, T., AND TRUSZCZY ´ NSKI, M. 2011. Answer set programming at a glance. Communications of the ACM 54, 12, 92–103. BROCKE, J. V.AND ROSEMANN, M. 2014. Handbook on Business Process Management 2: Strategic Alignment, Governance, People and Culture. Springer. BRUCKER, P., DREXL, A., MHRING, R., NEUMANN, K., AND PESCH, E. 1999. Resourceconstrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112, 1, 3–41. BUCCAFURRI, F., LEONE, N., AND RULLO, P. 1997. Adding weak constraints to disjunctive datalog. In APPIA-GULP-PRODE. 557–568. BURATTIN, A. 2015. Introduction to Business Processes, BPM, and BPM Systems. In Process Mining Techniques in Business Environments. Vol. 207. Springer, 11–21. CALIMERI, F., FABER, W., GEBSER, M., IANNI, G., KAMINSKI, R., KRENNWALLNER, T., LEONE, N., RICCA, F., AND SCHAUB, T. 2013. ASP-Core-2: Input language format. Tech. rep., ASP Standardization Working Group. CALIMERI, F., FUSC ` A, D., PERRI, S., AND ZANGARI, J. 2017. I-DLV: the new intelligent grounder of DLV. Intelligenza Artificiale 11, 1, 5–20. CALIMERI, F., GEBSER, M., MARATEA, M., AND RICCA, F. 2016. Design and results of the fifth Answer Set Programming competition. Artificial Intelligence 231, 151–181. CALIMERI, F., IANNI, G., AND RICCA, F. 2014. The third open Answer Set Programming competition. Theory and Practice of Logic Programming 14, 1, 117–135. COLANTONIO, A., DIPIETRO, R., OCELLO, A., AND VERDE, N. V. 2009. A formal framework to elicit roles with business meaning in RBAC systems. In ACM symposium on Access control models and technologies (SACMAT), B. Carminati and J. Joshi, Eds. ACM, 85–94. COUVREUR, J.-M., POITRENAUD, D., AND WEIL, P. 2013. Branching processes of general petri nets. Fundamenta Informaticae 122, 1-2, 31–58. DENECKER, M., VENNEKENS, J., BOND, S., GEBSER, M., AND TRUSZCZY ´ NSKI, M. 2009. The second Answer Set Programming competition. In Int. Conf. on Logic Programming 23 and Nonmonotonic Reasoning (LPNMR), E. Erdem, F. Lin, and T. Schaub, Eds. Vol. 5753. Springer, 637–654. DREXL, A., NISSEN, R., PATTERSON, J. H., AND SALEWSKI, F. 2000. ProGen/x An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions. European Journal of Operational Research 125, 1, 59 – 72. DUMAS, M., ROSA, M. L., MENDLING, J., AND REIJERS, H. A. 2018. Fundamentals of Business Process Management (Second Edition). Springer. ERDEM, E. AND WONG, M. D. F. 2004. Rectilinear Steiner Tree Construction Using Answer Set Programming. In Int. Conf. on Logic Programming (ICLP), B. Demoen and V. Lifschitz, Eds. Vol. 3132. Springer, 386–399. GANGE, G., STUCKEY, P. J., AND MARRIOTT, K. 2010. Optimal k-Level Planarization and Crossing Minimization. In Int. Symposium on Graph Drawing (GD), U. Brandes and S. Cornelsen, Eds. Vol. 6502. Springer, 238–249. GAREY, M. R., JOHNSON, D. S., AND SETHI, R. 1976. The complexity of flowshop and jobshop scheduling. Mathematics of operations research 1, 2, 117–129. GAVANELLI, M., NONATO, M., AND PEANO, A. 2015. An ASP approach for the valves positioning optimization in a water distribution system. Journal of Logic and Computation 25, 6, 1351–1369. GEBSER, M., KAMINSKI, R., KAUFMANN, B., ROMERO, J., AND SCHAUB, T. 2015. Progress in clasp series 3. In Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR), F. Calimeri, G. Ianni, and M. Truszczynski, Eds. Vol. 9345. Springer, 368–383. GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2012. Answer set solving in practice. Synthesis Lectures on Artificial Intelligence and Machine Learning 6, 3, 1–238. GEBSER, M., KAMINSKI, R., KAUFMANN, B., AND SCHAUB, T. 2014. Clingo = ASP + Control: Extended Report. Tech. rep., University of Potsdam, Germany. GEBSER, M., KAMINSKI, R., K ¨ ONIG, A., AND SCHAUB, T. 2011. Advances in gringo series 3. In Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR), J. P. Delgrande and W. Faber, Eds. Vol. 6645. Springer, 345–351. GEBSER, M., MARATEA, M., AND RICCA, F. 2017a. The Design of the Seventh Answer Set Programming Competition. In Int. Conf. on Logic Programming and Nonmonotonic Reasoning (LPNMR), M. Balduccini and T. Janhunen, Eds. Vol. 10377. Springer, 3–9. GEBSER, M., MARATEA, M., AND RICCA, F. 2017b. The Sixth Answer Set Programming Competition. Journal of Artificial Intelligence Research 60, 41–95. HAVUR, G., CABANILLAS, C., MENDLING, J., AND POLLERES, A. 2015. Automated Resource Allocation in Business Processes with Answer Set Programming. In BPM Workshops (BPI). Vol. 256. Springer, 191–203. HAVUR, G., CABANILLAS, C., MENDLING, J., AND POLLERES, A. 2016. Resource Allocation with Dependencies in Business Process Management Systems. In Int. Conf. on Business Process Management (BPM) - Forum. Vol. 260. Springer, 3–19. HOOKER, J. AND OTTOSSON, G. 2003. Logic-based Benders decomposition. Mathematical Programming 96, 1, 33–60. HORLING, B. AND LESSER, V. 2004. A Survey of Multi-agent Organizational Paradigms. Knowledge Engineering Review 19, 4, 281–316. KOLISCH, R., SPRECHER, A., AND DREXL, A. 1995. Characterization and Generation of a General Class of Resource-constrained Project Scheduling Problems. Management Science 41, 10, 1693–1703. 24 Giray Havur, Cristina Cabanillas, Axel Polleres LABORIE, P. 2009. IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems. In Int. Conf. on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR), W.-J. van Hoeve and J. N. Hooker, Eds. Vol. 5547. Springer, 148–162. LI, C. M. AND MANY ` A, F. 2009. MaxSAT, Hard and Soft Constraints. In Handbook of Satisfiability, A. Biere, M. Heule, H. van Maaren, and T. Walsh, Eds. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, 613–631. LOHMANN, N., VERBEEK, E., AND DIJKMAN, R. 2009. Petri Net Transformations for Business Processes - A Survey. Trans. on Petri Nets and Other Models of Concurrency II 2, 46–63. LOMBARDI, M. AND MILANO, M. 2012. Optimal methods for resource allocation and scheduling: a cross-disciplinary survey. Constraints 17, 51–85. OMG. 2011. BPMN 2.0. Recommendation, OMG. POPOVA-ZEUGMANN, L. 2013. Time Petri Nets. In Time and Petri Nets. Springer, 139–140. ROGGE-SOLTI, A. 2014. Block-structured stochastic Petri net generator (ProM plug-in). http: //www.promtools.org/. Accessed: 2018-01-01. ROSEMANN, M. AND VOM BROCKE, J. 2015. The six core elements of business process management. In Handbook on Business Process Management 1. Springer, 105–122. RUSSELL, N., VAN DER AALST, W. M., TER HOFSTEDE, A. H., AND EDMOND, D. 2005. Workflow resource patterns: Identification, representation and tool support. In Int. Conf. on Advanced Information Systems Engineering (CAiSE), O. Pastor and J. F. e Cunha, Eds. Vol. 3520. Springer, 216–232. SCH ¨ ONIG, S., CABANILLAS, C., JABLONSKI, S., AND MENDLING, J. 2016. A Framework for Efficiently Mining the Organisational Perspective of Business Processes. Decision Support Systems 89, 87–97. SPRECHER, A., HARTMANN, S., AND DREXL, A. 1994. Project scheduling with discrete timeresource and resource-resource tradeoffs. Tech. rep., Instituten f¨ ur Betriebswirtschaftslehre der Universit¨ at Kiel, Germany. TONI, L., APARICIO-PARDO, R., SIMON, G., BLANC, A., AND FROSSARD, P. 2014. Optimal Set of Video Representations in Adaptive Streaming. In ACM Multimedia Systems Conference (MMSys), R. Zimmermann, Ed. ACM, 271–282. VAN DER AALST, W. M. 1996. Structural characterizations of sound workflow nets. Computing Science Reports 96, 23, 18–22. VAN DER AALST, W. M. P. 2016. Process Mining - Data Science in Action (Second Edition). Springer. VOM BROCKE, J., ROSEMANN, M., ET AL. 2010. Handbook on business process management. Springer.