Resource Allocation with Dependencies using Answer Set Programming

Resource Allocation with Dependencies using Answer Set Programming? Giray Havur, Cristina Cabanillas, Jan Mendling, and Axel Polleres Vienna University of Economics and Business, Austria {firstname.lastname}@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 scheduling 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. Keywords: Answer Set Programming, resource allocation, timed Petri net, 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 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. We extend prior research on BPMS integration with calendars [4] to take dependencies and resource ?

Funded by the Austrian Research Promotion Agency (FFG) grant 845638 (SHAPE).

2

Havur et al.

t1start

TEST-1

t2start

TEST-2

S E T a1 [2] a2 [2] a3 [2] a4 [5] a6 [5] a7 [5] a8 [5] a9 [6] a10 [6] a11 [6] U P

R U N

t1end

a5

[8]

t2end

a12

[10]

Fig. 1: Workflow for two projects

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]. 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 2 presents and analyzes an industry scenario. Section 3 explains our ASP-based solution applied to the industry scenario.

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 technicians specialized in the different types of hardware. Afterwards, a team of engineers supervises the simulation run. Figure 1 depicts 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

Resource Allocation with Dependencies using ASP

3

brackets next to the activities indicates their (default maximum) duration in generic time units (TU). 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. For completing tests, the non-human resources available in the organization include 13 units of space distributed into 2 laboratories (Fig. 1) and several units of 3 types of hardware (Fig. 2). The human resources of the company are specialized in the execution of specific phases of the two testing projects, whose activities they are able to complete in a specific time (Fig. 3 shows TU in square brackets for the phases that each employee can perform). The requirements on the use of such resources in the activities of the processes are collected in Table 4. In particular, 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 problem deals 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 across a broad set of resources and activities of processes as well as from solving potential conflicts on the use of certain resources. As can be observed in the industry scenario, such dependencies comprise, among others: (i) resource requirements, i.e., the characteristics of the resources that are involved in an activity (e.g., roles 1 or skills) ; (ii) temporal requirements. For instance, the duration of the activities may be static or may depend on the characteristics of the set of resources 1

For simplicity, that information is omitted in Section 2.1. Table 3 is provided instead.

Space

LAB − 1 LAB − 2 4 9

Table 1: Available space in labs T ype HW 1 HW 2 HW 3

U nits hw1a, hw1b, hw1c hw2a, hw2b, hw2c, hw2d hw3a, hw3b, hw3c

Table 2: Available hardware (HW)

Glen[7] Drew[7] Evan[3] Mary[5] Kate[6] Amy[8]

T est − 1 T est − 2 Setup Run Setup Run X X X X X X X X X X X

Table 3: Specialization of employees

4

Havur et al.

involved in it, especially for collaborative activities in which several employees work together (such us for the activities of the run phase of a testing process). Furthermore, resource availability may not be unlimited (e.g., the working time of human resources is defined in 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 the control flow defined in the process model, and (2) each activity is assigned to at least exactly one start time and its required resources. This combinatorial problem for finding a feasible resource allocation 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 P the resource allocation problem becomes ∆2 [8].

3

Implementation with ASP

Answer Set Programming (ASP) [9,10] is a declarative (logic-programming-style) paradigm for solving (primarily NP-hard ) combinatorial search problems. An ASP program Π is a finite set of rules of the form: A0 ← A1 , . . . , Am , not Am+1 , . . . , not An .

(1)

Test-2

Test-1

where n ≥ m ≥ 0 and each Ai ∈ σ are (function-free first-order) atoms; if A0 is empty in a rule r, we call r a constraint, and if n = m = 0 we call r a fact. Whenever Ai is 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

Activities a1 − a3 a4 a5 a6 − a8 a9 − a11 a12

1 1 4 1 1 2

Requirements Employee:Setup-1, 1 Hardware:HW-1, 1 Lab:a1 -a4 same lab Employee:Setup-1, 1 Hardware:HW-2, 1 Lab:a1 -a4 same lab Employee:Run-1, after execution(a.e.) release the lab for a1 -a4 Employee:Setup-2, 1 Hardware:HW-2, 1 Lab:a6 -a11 same lab Employee:Setup-2, 1 Hardware:HW-3, 1 Lab:a6 -a11 same lab Employee:Run-2 (hasExp>5), a.e. release the lab for a6 -a11

Table 4: Activity requirements


5

answer sets), that is subset-minimal Herbrand models, we again refer to [9] and references therein 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. There are various solvers [11, 12] for ASP problem specifications. We use clasp [10] for our experiments herein, as it has proved to be one of the most efficient implementations available. As syntactic extension, in place of atoms, clasp allows set-like choice expressions of the form E = {A1 , . . . , Ak } which are true for any subset of E; that is, when used in heads of rules, E generates many answer sets, and such rules are often referred to as choice rules. For instance, Π4 = {lights on.{shop open, door locked}:-lights on.} has both answer sets of Π3 plus the answer set {lights on}. Note that in the presence of choice rules, answer sets are not necessarily subset-minimal (cf. [10] for details). Another extension supported in clasp are optimization statements [10] to indicate preferences between possible answer sets: #minimize {A1 : Body1 = w1 , . . . , Am : 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. ReaP soning problems including such weak constraints are ∆2 -complete. Finally, many problems conventiently modelled in ASP require a boundary parameter k that 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. However, re-processing repeatedly the entire problem is a redundant approach, which is why incremental ASP (iASP) [10] 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. An iASP program is a triple (B, A[k], Q[k]), where B describes static knowledge, and A[k] and Q[k] are ASP programs parameterized by the incremental + parameter k ∈ N . In the iterative answer set computation of iASP, while the knowledge derived from the rules in A[k] accumulates as k increases, the knowledge obtained from Q[k] is only considered for the latest value of k. A[k] and Q[k] are called cumulative knowledge and volatile knowledge, resp. More formally, an iASP solver computes in each iteration i Π[i] = B ∪

S

1≤j≤i

A[k/j] ∪ Q[k/i]

6

Havur et al.

A[k] : {fire(T, B, I, k) : inPlace(P, T, B), bpInstance(B, I)}. :-fire(T, B, I, k), bpInstance(B, I), inPlace(P, T, B), not tokenAt(P, B, I, k). tokenAt(P, B, I, k):-fire(T, B, I, k − 1), outPlace(P, T, B), bpInstance(B, I). :-inPlace(P, T1, B), inPlace(P, T2, B), T16=T2, fire(T1, B, I, k), fire(T2, B, I, k), bpInstance(B, I). consumeToken(P, B, I, k):-inPlace(P, T, B), fire(T, B, I, k), bpInstance(B, I). tokenAt(P, B, I, k):-tokenAt(P, B, I, k − 1), not consumeToken(P, B, I, k − 1). Q[k] : :-not tokenAt(pg , B, I, k), bpInstance(B, I).

Fig. 2: 1-safe Petri net formulation in iASP

until an answer set for some (minimum) integer i ≥ 1 is found. We will demonstrate next how iASP can be successfully used to model and solve various variants of resource allocation problems in business process management. 3.1

Customizable Resource Allocation

A former version of our program is detailed in [5]. We enhance our encoding in three folds: (1) the allocation of resources in multiple business processes with multiple running instances, (2) the definition of resource sets, and (3) the enforcement of requirements that lead the reasoner to allocate a certain number of resources to activities from resource sets, including cardinality, advanced time management and advanced resource management requirements. Our customizable resource allocation program consists of three parts. Petri net Dynamics The first part of the program (cf. Fig. 2) finds a firing sequence between initial and goal markings of a 1-safe Petri net. Given the factual representation of Test-1 in Fig. 1, the output describes the firing sequence using the predicate fire(t,b,i,k), which means that an activity t of business process b in instance i is fired at step k. The firing sequence of Test-1 is computed as → − σ test−1 =< t10 , t11 |t12 |t13 |t14 , t15 , t16 >. Scheduling of Activities The scheduling extension (cf. Fig. 3) extends the 1-safe Petri net formulation by considering the estimated duration of activities indicated in the timed Petri net and hence, it computes the overall execution time at each place. Given the factual representation of Test-1 in Fig. 1, the starting − time of each activity in the firing sequence → σ test−1 =< a1 , a2 |a3 |a4 |a5 , a6 > is → − computed as c( σ test−1 ) =< 0, 0|0|0|0, 5 >. Resource Requirements of Activities. The last part of our program (cf. Fig. 4) adds the rules and constraints for allocating resources to activities. We start by describing resource sets whose members satisfy some properties. These properties can be class memberships or resource attributes that are defined in


7

B: firingDelay(A, D):-activityDuration(A, D). firingDelay(A, 0):-not activityDuration(A, ), activity(A). A[k] : greTimeInPlace(P1, T, B, I, k):-inPlace(P1, T, B), inPlace(P2, T, B), P16=P2, timeAt(P1, C1, B, I, k), timeAt(P2, C2, B, I, k), C1 < C2, fire(T, B, I, k), bpInstance(B, I). maxTimeInPlace(P, T, B, I, k):-inPlace(P, T, B), not greTimePlace(P, T, B, I, k) , fire(T, B, I, k), bpInstance(B, I). timeAt(P2, C, B, I, k):-not activity(T), fire(T, B, I, k − 1), outPlace(P2, T, B), maxTimeInPlace(P, T, B, I, k − 1), timeAt(P, C, B, I, k − 1), bpInstance(B, I). timeAt(P2, C2, B, I, k):-activity(T, B), fire(T, B, I, k − 1), outPlace(P2, T, B), alloc(R, T, C1, C2, B, I, k − 1), bpInstance(B, I). timeAt(P, C, B, I, k):-not consumeToken(P, B, I, k − 1), inPlace(P, T, B), timeAt(P, C, B, I, k − 1), bpInstance(B, I). 0

Q[k] : #minimize{C, timeAt : timeAt(pg , C, B, I, k), bpInstance(B, I)}

(2)

Fig. 3: Scheduling extension

Section 2. We have two kinds of resource sets defined for two different types of resources. A set of discrete resources that can be assigned to an activity as a unit resource is represented in our program with the predicate resourceSet(R,id ), where R is a set of resources and id is the identifier of the set. We explain the following sets of discrete resources following our industry scenario: All human resources that can take part in the setup phase of Test-1: resourceSet(R,rs set1):-humanResource(R), hasRole(R,setup1).

All human resources that can take part in the run phase of Test-2 and have a working experience greater than 5 years: resourceSet(R,rs ex2):-humanResource(R), hasRole(R,run2), hasExp(E), E>5.

All hardware resources of type HW2: resourceSet(R,rs h2):-hardware2(R).

A set of cumulative resources that can be consumed and generated by an activity requires one more term for representing the available amount of such resources. Such resources are described by the predicate resourceSet(R,V,id ), where R is the set of cumulative resources, V is the set of their initial amount and id is the identifier of the resource set. For example: Lab space set: resourceSet(R,V,lab space):-lab(R),hasSpace(R,V).

8

Havur et al.

After defining resource sets, we define resource requirements of an activity by the predicate requirement(a,id,n) where a is the activity, id refers to a specific resource set and n is the number/amount (resp., for discrete/cumulative resources) of resources that activity a requires from this set. For instance, requirement(a12 ,rs ex2,2) means that activity a12 requires 2 resources from the resource set rs ex2. Respectively, requirement(a1 ,lab space,−1) consumes 1 unit of lab space when a1 is allocated, whereas requirement(a12 ,rs ex2,6) releases 6 units of space by the time a12 is executed. Activity Durations Default durations of activities are defined in the process model, i.e. associated durations of transitions in timed Petri nets, and represented as activityDuration(T,B,D) (Activity a of the process b has duration d ) in our program. This default duration can be overwritten by a new value d when a certain resource r is assigned to a certain activity a of the process b by using the predicate resActDuration(r ,a ,b ,d ). In a similar fashion, this duration can be overwritten by d when any resource r that belongs to a resource set rs is assigned to a certain activity a of the process b by using the predicate rSetActDuration(rs ,a ,b ,d ). The order (>) preferred in activity time is resActDuration>rSetActDuration>activityDuration. Rules (3-5) in Fig. 4 take care of this preference handling. As one activity can be allocated to a group of resources, an aggregation method might be needed. Our default aggregation method identifies the maximum duration within the group and uses it for allocation (Rule (6) and (7)). This method can be modified with different aggregation options that fit in the purpose of allocation scenario. Deadlines For business process instances and their activities, (optionally, max. or min.) starting or ending times can be defined using the following predicates in Fig. 6: actStarts(o ,a ,b ,i ,d ), i.e. activity a in business process b of instance i , starts at d ; actEnds(o ,a ,b ,i ,d ), i.e. activity a in business process b of instance i , ends at d ; bpiStarts(o ,b ,i ,d ), i.e. business process b of instance i , starts at d ; bpiEnds(o ,b ,i ,d ), i.e. business process b of instance i , ends at d ; where o ∈ {strictly,earliest,latest}. Resource blocking The capability of resource blocking during the execution of two activities in a process is provided with our extension in Fig. 5. The predicate block(a1 ,a2 ,id ,n) blocks n amount of resources in the resource set id from the beginning of a1 to beginning of a2 . Break calendar In many real-life projects, certain resources are only available during the working periods (e.g. working hours). We model this by break(rs, c1 ,c2 ) in Fig. 6 that forbids allocation of resources in the resource set rs between time c1 and c2 , where c1 < c2 . Separation of Duties (SoD) and Binding of Duties (BoD) are important concepts when it comes to resource allocation in business processes [13]. We provide this capability in our extension in Fig. 5. They are implemented in our program by using the predicate separateDuties(a1 ,b1 ,a2 ,b2 ), which separates the re-


9

B: (3)

defRABD(R, A, B, D, k):-resActDuration(R, A, B, D). defRABD(R, A, B, D, k):-resourceSet(R, ID), rSetActDuration(ID, A, B, D), not resActDuration(R, A, B, D1) defRABD(R, A, B, D, k):-not resActDuration(R, A, B, D1), not roleActDuration(L, A, B, D2), firingDelay(A, B, D). greaterDExists(A, B, D, k):-defaultRABD(R, A, B, D, k), R6=R1, D < D1, defaultRABD(R1, A, B, D1, k). defaultD(A, B, D, k):-not greaterDExists(A, B, D, k), defRABD(R, A, B, D, k).

(4) (5) (6) (7)

A[k] : N{alloc(R, A, C, C + D, B, I, k) :resourceSet(R, ID), defaultD(A, B, D, k)}N:requirement(A, ID, N), consumeToken(P, B, I, k), timeAt(P, C, B, I, k), bpInstance(B, I). :-alloc(R, A, C, C1, B, I, K), alloc(R, A1, C, C2, B, I, S1), C < C1, C < C2, A6=A1. :-alloc(R, A, C, C1, B, I, K), alloc(R, A1, C, C2, B, I1, S1),C < C1, C < C2, A6=A1, I6=I1. :-alloc(R, A, C, C1, B, I, K), alloc(R, A1, C, C2, B1, I1, S1), C < C1, C < C2, B6=B1. :-alloc(R, A, C, C1, B, I, K), alloc(R, A, C, C2, B, I1, S1), C < C1, C < C2, I6=I1. :-alloc(R, A, C, C1, B, I, K), alloc(R, A, C, C2, B1, I1, S1), C < C1, C < C2, B6=B1. :-alloc(R, T, Y, Y1, B, I, K), alloc(R, T1, X, X1, B1, I1, S1), X > Y, X < Y1. :-alloc(R, T, Y, Y1, B, I, K), alloc(R, T1, X, X1, B1, I1, S1), X1 < Y1, X1 > Y. :-alloc(R, A, C, C1, B, I, k), alloc(R1, A, C2, C3, B, I, k), R6=R1, C6=C2. stepChange(ID, N, A, B, I, k):-requirement(A, ID, N), inPlace(P1, A, B), consumeToken(P1, B, I, k), timeAt(P1, C, B, I, k), bpInstance(B, I). 1{valueChange(A, B, I, R, N, k) :resourceValueSet(R, V, ID, k)}1:stepChange(ID, N, A, B, I, k). resourceValueSet(R, V + N, ID, k):-resourceValueSet(R, V, ID, k − 1), N = #sum{M, A, R, valueChange : valueChange(A, B, I, R, M, k − 1)}. :-resourceValueSet(R, V, ID, k), V < 0. :-resourceValueSet(R, V, ID, k), valueChange( , B, I, R, M, k), M < 0, −M > V.

Fig. 4: Allocation extension

sources allocated to the activity a1 of process b1 from the resources allocated to a2 of b2 ; and bindDuties(a1 ,b1 ,a2 ,b2 ), which binds the resources allocated to the activity a1 of process b1 with the resources allocated to a2 of b2 .

10

Havur et al.

A[k] : N{blocked(A, R, C1, s) : resourceSet(R, ID)}N:-block(A, A1, ID, N), consumeToken(P1, B, I, s − 1), inPlace(P1, A, B), timeAt(P1, C1, B, I, s − 1). unblocked(A1, R, C2, s):-blocked(A, R, C, s − 1), block(A, A1, ID, ), allocate( , A1, C1, C2, B, I, s − 1), resourceSet(R, ID). :-blocked(A1, R, C1, s), block(A1, A3, ID, N), not unblocked(A3, R, C3, s), blocked(A2, R, C2, s), A16=A2, C3 = C1..C2, C2≥C1. :-blocked(A1, R, C1, s), block(A1, A2, ID, N), not unblocked(A2, R, C2, s), allocate(R, A3, C3, , B, I, s), C3 < C2. blocked(A, R, C1, s):-block(A, A1, ID, N), blocked(A, R, C1, s − 1), not unblocked(A1, R, , s − 1). unblocked(A1, R, C1, s):-block(A, A1, ID, N), unblocked(A1, R, C1, s − 1), not blocked(A, R, , s − 1). separateDutiesR(R, A1, B1, C2, s):-separateDuties(A, B, A1, B1), allocate(R, A, , C2, s − 1, B, I). :-allocate(R, A, C1, C2, K, B, I), separateDutiesR(R, A, B, C, S1), C1 >= C. bindDutiesR(R, A1, B1, C2, s):-bindDuties(A, B, A1, B1), allocate(R, A, , C2, s − 1, B, I). :-allocate(R1, A, C1, C2, K, B, I), separateDutiesR(R, A, B, C, S1), C1 >= C, R16=R.

Fig. 5: Advanced resource management extension (Resource blocking, SoD, BoD)

Objectives As aforementioned, the ASP solver clasp allows us to define some objectives as cost functions that are expressed through a sequence of #minimize (and #maximize) statements. In our encoding, we ensure time optimality of our solutions using the minimization statement (Rule (2) in Fig. 3). In a similar way, any objective that is quantified with an integer value (e.g. cost objectives, resource levelling, etc.) could be introduced. When there is more than one objective, they are prioritized with respect to their order p. After introducing our extensions, we provide the following constraints additionally for our running example. Activity Durations: resActDuration(Mary,a5 ,10),rSetActDuration(rs ex2,a12 ,5).

Break calendar: break(all resources,0,7), break(all resources,19,31), break(all resources,43,55), break(all resources,67,79).

Resource blocking for hardware: block(a1 ,a5 ,rs h1,1), block(a2 ,a5 ,rs h1,1), block(a3 ,a5 ,rs h1,1), block(a4 ,a5 ,rs h2,1), block(a6 ,a12 ,rs h2,1), block(a7 ,a12 ,rs h2,1), block(a8 ,a12 ,rs h2,1), block(a9 ,a12 ,rs h3,1), block(a10 ,a12 ,rs h3,1),


11

B: :-alloc(R, A, C1, C2, B, I, K), resourceSet(R, ID), break(ID, C3, C4), C3 >= C1, C3 =< C2. :-alloc(R, A, C1, C2, B, I, K), resourceSet(R, ID), break(ID, C3, C4), C4 > C1, C4 < C2. :-actStarts(strictly, A, B, I, C), alloc( , A, C1, , B, I, K), C16=C. :-actStarts(earliest, A, B, I, C), alloc( , A, C1, , B, I, K), C1 < C. :-actStarts(latest, A, B, I, C), alloc( , A, C1, , B, I, K), C1 > C. :-actEnds(strictly, A, B, I, C), alloc( , A, , C1, B, I, K), C16=C. :-actEnds(earliest, A, B, I, C), alloc( , A, , C1, B, I, K), C1 < C. :-actEnds(latest, A, B, I, C), alloc( , A, , C1, B, I, K), C1 > C. :-bpiStarts(strictly, B, I, C), C1 = #min{C1 : alloc( , C1, , , B, I, K)}, C16=C. :-bpiStarts(earliest, B, I, C), C1 = #min{C1 : alloc( , C1, , , B, I, K)}, C1 < C. :-bpiStarts(latest, B, I, C), C1 = #min{C1 : alloc( , C1, , , B, I, K)}, C1 > C. :-bpiEnds(strictly, B, I, C), C1 = #max{C1 : alloc( , , C1, , B, I, K)}, C16=C. :-bpiEnds(earliest, B, I, C), C1 = #max{C1 : alloc( , , C1, , B, I, K)}, C1 < C. :-bpiEnds(latest, B, I, C), C1 = #max{C1 : alloc( , , C1, , B, I, K)}, C1 > C.

Fig. 6: Break and deadlines

................................. a a a 18 32

1

a4

2

a5

3

a9 a10 a11

66

42 56

a6 a8

a7

a12

lab-2 lab-1

test-2 test-1

8

Fig. 7: Optimal resource allocation for our industry scenario

block(a11 ,a12 ,rs h3,1).

Separation of duties: separateDuties(a1 ,test-1,a4 ,test-1), separateDuties(a6 ,test-2,a9 ,test-2).

Deadlines: actStarts(strictly,a2 ,10), bpStarts(earliest,test-2,12).

Fig. 7 shows the result of the implementation of the industry scenario with ASP. The final allocation of resources to each activity ai is as follows:

12

Havur et al.

a1 a2 a3 a4 a5 a6

{Amy,hw1a,lab-1(-1)} {Amy,hw1b,lab-1(-1)} {Glen,hw1c,lab-1(-1)} {Glen,hw2b,lab-1(-1)} {Glen,Drew,Ewan,Mary,lab-1(4)} {Kate,hw2c,lab-2(-1)}

a7 a8 a9 a10 a11 a12

{Mary,hw2a,lab-2(-1)} {Amy,hw2d,lab-2(-1)} {Amy,hw3c,lab-2(-1)} {Mary,hw3b,lab-2(-1)} {Kate,hw3a,lab-2(-1)} {Kate,Amy,lab-2(6)}

References 1. G. A. Rummler and A. J. Ramias, “A framework for defining and designing the structure of work,” in Handbook on Business Process Management 1, pp. 81–104, Springer, 2015. 2. H. A. Reijers, I. T. P. Vanderfeesten, and W. M. P. van der Aalst, “The effectiveness of workflow management systems: A longitudinal study,” Int J. Information Management, vol. 36, no. 1, pp. 126–141, 2016. 3. M. Rosemann and J. vom Brocke, “The six core elements of business process management,” in Handbook on Business Process Management 1, pp. 105–122, Springer, 2015. 4. R. Mans, N. C. Russell, W. M. P. van der Aalst, A. J. Moleman, and P. J. M. Bakker, “Schedule-aware workflow management systems,” Trans. Petri Nets and Other Models of Concurrency, vol. 4, pp. 121–143, 2010. 5. G. Havur, C. Cabanillas, J. Mendling, and A. Polleres, “Automated Resource Allocation in Business Processes with Answer Set Programming,” in BPM Workshops (BPI), p. In press, 2015. 6. L. Popova-Zeugmann, “Time Petri Nets,” in Time and Petri Nets, pp. 139–140, Springer Berlin Heidelberg, 2013. 7. D. S. Johnson and M. R. Garey, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” WH Free. Co., San Fr, 1979. 8. F. Buccafurri, N. Leone, and P. Rullo, “Enhancing disjunctive datalog by constraints,” Knowledge and Data Engineering, IEEE Transactions on, vol. 12, no. 5, pp. 845–860, 2000. 9. G. Brewka, T. Eiter, and M. Truszczy´ nski, “Answer set programming at a glance,” Communications of the ACM, vol. 54, no. 12, pp. 92–103, 2011. 10. M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub, Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2012. 11. F. Calimeri, M. Gebser, M. Maratea, and F. Ricca, “The Design of the Fifth Answer Set Programming Competition,” CoRR, 2014. 12. M. J. Heule and T. Schaub, “What’s Hot in the SAT and ASP Competitions,” in Association for the Advancement of Artificial Intelligence (AAAI), 2015. 13. C. Cabanillas, M. Resinas, A. del R´ıo-Ortega, and A. Ruiz-Cort´es, “Specification and Automated Design-Time Analysis of the Business Process Human Resource Perspective,” Inf. Syst., vol. 52, pp. 55–82, 2015.