Replacement planning is critical to guarantee continuity of operations in business processes in case of personnel unavailability. In this work, we propose a data-driven approach for supporting resource replacement that makes use of logs of past process executions to model a social network of resources. On this top, a similarity measure among resources is exploited to assign tasks of unavailable resource to the available ones through an Integer Linear Model.
In organization management, replacement planning consists in addressing shortterm lack of workforce that may be due to temporary or permanent unavailability of personnel for several reasons, including for instance vacation, resignation or illness. This issue has a larger impact on organizations when the unavailability cannot be predicted in advance, such as during strikes or emergencies. A recent example of the latter case is the COVID-19 outbreak, which is severely a ecting continuity of operations in many public administrations and private companies worldwide.
Traditional approaches in the literature for resource scheduling and replacement planning address the problem typically through business rules modeled by domain experts. On the other hand, nowadays information systems (e.g., ERPs, Work ow Management Systems, CRMs) are capable to track and monitor every event occurring during a business process, such as what activities have been executed, when and by whom. This valuable information can be exploited to support more reliable kinds of data-driven analysis, e.g. through Process Mining techniques.
This paper discusses a data-driven framework for planning of resource replacement. Through the analysis of past executions of business processes the approach is aimed to model a sociogram, i.e. a social network describing how Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). This volume is published and copyrighted by its editors. SEBD 2020, June 21-24, 2020, Villasimius, Italy. resources collaborate with each other. Several metrics have been devised in the literature to analyse di erent social relations among resources, including those focusing on how work moves among performers and those considering that people doing similar tasks have stronger relations than people doing completely di erent things [5]. Here we focus on the both aspects, using a handover of work metric (measuring how frequently work is transferred between two resources) and taking into account capabilities of resources, to evaluate the costs for assigning those activities that should have been performed by the unavailable resource(s), to others. Finally, on the basis of this information, an Integer Linear Programming (ILP) model is de ned with the aim of selecting the set of candidate resources to minimize the total cost of replacement.
The work ts into the eld of organizational mining [4], focusing on the resources (or actors) that performed events and their mutual cooperation in the ful llment of a process. In [3] an organizational mining framework has been proposed for the discovery, rather than the enforcement, of patterns related to resource assignment using declarative process modelling languages based on rule templates. Our approach shares also the exploitation of an ILP model for task assignment with [2], although the work has a di erent purpose, namely proposing a recommendation system to support process participants to take a risk-informed decision in choosing the next task to execute out of a set of assigned tasks.
The novel contributions of this work are as follows: (
We propose here an example related to a phone repair process for a company, that will be used throughout the paper. As shown in Figure 1, the process starts with the registration of the repair request (A) and is followed by analysis of defects (B). Then, the user is informed about the outcome (C) and in parallel the repair subprocess is performed. This is achieved by executing either a simple repair (D) or a complex one (E), and is ended by a test to verify whether the repair solved the issues (F). In the negative case, the repair subprocess is reexecuted. Finally, if the test succeeds, the request is archived (G) and the process ends. Let us assume the process involves 6 users, named James, Carrie (in charge of administration activities A, C and G), Mark, Alec, Harrison and Peter (in charge of analysis, repair and test, i.e. activities B, D, E and F). Every record in the log refers to a speci c case and is a sequence of events, each of which described in terms of activity, resource and duration in a certain time unit (minutes in the example), as shown in Table 1.
The example is inspired to the ProM 6 tutorial by H.M.W. (Eric) Verbeek at http://www.promtools.org/prom6/downloads/prom-6.0-tutorial.pdf
The rest of this work is structured as follows: the next section presents a novel handover of work metric and the sociogram model. Section 3 discusses the proposed methodology for resource replacement. Finally, Section 4 reports preliminary results and draws future research extension. 2
In this section we introduce the terminology and a model of social network for handover of work that is used in the rest of the paper.
Hereby we refer to the term activity as a task (or portion thereof) performed to achieve a goal, and to resource as any member of personnel that is capable to perform some activity.
Let A be a set of activities and R a set of resources. V = A R is the set of possible event s, i.e., combinations of an activity and a resource. Given a resource r, V (r) V is the set of events in which r can take part. A trace is a possible sequence of events, where C = V is the set of all possible traces. An event log L is a subset of all bags (multi-sets) over C.
In our scenario, we assume the event log includes as attributes at least the case id, the executed activity, the resource name and the timestamp when each event has been performed. For convenience, we introduce the function a( ) which returns the set of activities related to events of a trace .
From the event log, it is possible to characterize a resource r 2 R in terms of his/her capabilities, i.e. the set A(r) of activities that is able to perform. To make an example, from the log in Table 1 we derive A(M ark)=fB, Dg and A(Harrison)=fB,D,Eg.
Among the various relations that can be recognized in an event log between two resources, we focus here on relations of possible causality, and speci cally to handover of work. Within a case there is a handover of work from a resource r1 to a resource r2 if there are two subsequent activities a1 and a2 where a1 is completed by r1 and a2 by r2. The metric can be de ned and computed in multiple ways [5], according to the degree of causality (direct or indirect), the existence of multiple succession from a resource to itself (multiple self-transfer), and the kind of succession, i.e. arbitrary succession between two subsequent events in a trace or casual dependency. In this last case, a process model is needed to recognize which is the correct ow of activities in a trace. To make an example, with reference to the case 3, between events (A,Carrie) and (B,Peter) there is a direct and casual succession, while between (F,Alec) and (C,Carrie) there is a direct but arbitrary succession. Indeed, if we compare the log to the process model in Figure 1, there is a causal relation between activities A and B, but this does not hold between activities F and C.
In this work, we refer to the handover of work relation (
Given r1; r2 2 R, ax 2 A(r1); ay 2 A(r2), an event log L, a process model P and a trace 2 L, the function r1 ax;ay r2 returns how many times r1 and r2 executed respectively activity ax 2 a( ) and ay 2 a( ) such that a causal relation between them in P exists. For the whole event log L, the function is computed as: qxy = r1 aLx;ay r2 =
X r1 ax;ay r2 2L
Finally, the metric handover of work between r1; r2 for activities ax; ay in L is computed as: hxy = r1 aLx;ay r2 = r1 aLx;ay r2=
X X ri aLx;ay rj ri2R rj2R
The metric is computed for a couple of resources r1; r2 and with respect to a couple of activities ax; ay by dividing the total number of proper casual (F,G,0.25,1) (B,C,0.25,1) (F,G,0.25,1)
Harrison (B,D,0.3,1) (A,B,0.25,1) (F,E,1.0,1)
Alec (D,F,0.25,1) (D,F,0.25,1)
Peter (A,B, 0.25,1) (D,F,0.25,1) (E,F,0.5,1) (E,F,0.5,1) (D,F,0.25,1) succession (with no self-transfer) by the total number of casual succession of ax; ay between any two resources ri, rj , with i 6= j.
As for the running example, given resources J ames and Carrie, and activities C and G, J ames LC;G Carrie= 24 = 0:5, because the casual succession between them happens 2 times (case 1 and case 4), but the casual succession of C and G between any two resources occurs 4 times.
This information can be represented as a handover matrix, that is a matrix N N , where N < jRj is the number of active resources (i.e. resources that executed at least 1 activity in the event log). Given two resources ri; rj 2 R active in L, the cell (i; j) of the handover matrix includes a tuple (ax; ay; hxy; qxy), with ax 2 A(ri) and ay 2 A(rj ), if and only if hxy > 0. In Table 2 we report the handover matrix for the running example.
From the matrix, a sociogram can be de ned, i.e. a graph of social relations where nodes are resources and an edge linking two resources is de ned if a certain social relation is recognized between them. We refer to the following de nition of a sociogram as a labeled multidigraph, i.e. a directed multigraph where two nodes may be linked by multiple labeled edges.
Given a N N handover matrix M , a sociogram G is de ned as an 8-tuple G = ( R0 ; E ; R0; E; s; t; `R0 ; `E ) where: { R0 R is the nite set of N resources in M and E is a set of arcs representing a handover of work relation; { R0 and E are nite alphabets of the available vertex and arc labels, s : E ! R0 and t : E ! R0 are two maps indicating the source and target vertex of an arc; { `R0 : R0 ! R0 and `E : E ! E are two maps describing the labeling of the vertices and arcs.
In the following, for the sake of simplicity, we refer to a sociogram G as a tuple G = (R0; E), with E as a multi-set of arcs. Each arc e 2 E will be shortly represented as a tuple e = (ri; rj ; (ax; ay; hxy; qxy)) linking two nodes ri; rj 2 R0, being ri the source and rj the target of e, and (ax; ay; hxy; qxy) the arc label. For convenience, we introduce the operations h(ri; rj ; ax) = fhxy : 9e = (ri; rj ; (ax; ay; hxy; qxy)) 2 Eg and q(ri; rj ; ax) = fqxy : 9e = (ri; rj ; (ax; ay; hxy; qxy)) 2 Eg which respectively return the values of handover of work between ri (after ax has been completed) and rj , and the numbers of times ax has been executed by ri before rj . Furthermore, the set Gri (ax) = fr0 2 R0 : 9(ri; r0; (ax; ay; hxy; qxy)) 2 Eg is introduced to return the subset of resources for which an handover of work relation from ri after completing ax exists.
Please note that, di erently from the organizational mining literature, we refer to a labeled multidigraph with multiple edges between two nodes. This enables a greater expressiveness as we can encode not only the handover of generic work between two resources, but also take into account which speci c activities one resource has handed over the other. 3
We assume an organization relying on a Business Process Management system with monitoring capabilities of process execution. Execution traces are made available as event logs, which are then analysed and elaborated through organizational mining techniques to derive the sociogram as described in Section 2. This information is used to drive the resource replacement, that returns the set of speci c resources that are selected to replace the missing ones, and their allocation to activities.
Given a sociogram G = (R0; E), an unavailable resource r 2 R to replace and a multi-set T = fa1; : : : ; ahg of activities assigned to r that must be performed by some other resources, the goal is to determine a set of resources fr1; : : : ; rng R that is collectively capable to replace r to perform activities in T . We take into account a similarity factor such that resources being more compatible to the one to replace are preferred. This takes into account handover of work relations, capabilities of resources, performance and experience.
Similarity measure. Given a resource r 2 R to replace, a candidate resource
ri 2 R and an activity aj , the similarity between the r and rj for the speci c
activity aj is de ned as follows:
sim(r; ri; aj ) = !1 coll(r; ri; aj ) + !2 perf (r; ri; aj ) + !3 exp(r; ri; aj )
The function sim(r; ri; aj ) returns the degree of a nity between the two
resources on the basis of (
In details, Gr(aj ) and Gri (aj ) (see Section 2) are the sets of resources to whom respectively r and ri handed over work after performing activity aj . Let h^(rx; ry; aj ) = j h(rx1;ry;aj)j Phi2 h(rx;ry;aj) hi be the average handover of work T is a multi-set because an activity may need to be performed multiple times in a process. coll(r; ri; aj ) = . It ranges in [0; 1], between rx, executing aj , and ry. Finally, we introduce the function (x) which returns x if x 1, and 1 otherwise. The coll function is de ned as: 1 X h^(ri; r0; aj ) ! jGr(aj )j r02Gr(aj)\Gri (aj) h^(r; r0; aj ) returning 0 when the two resources do not share any collaborations, 1 if ri interacts with all collaborators of r with the same handover of work. The coll function is introduced under the assumption that replacing a resource with someone acquainted to work in the same team and with similar handover relations is preferable.
The perf (r; ri; aj ) function compares the time taken by the two resources to carry out the activity aj . Let tr and tri be the average time respectively taken by r and ri to perform aj , the perf function is de ned as perf (r; ri; aj ) = ttrri . The perf function ranges in [0; 1], values close to 0 mean that r is much faster than ri. When ri is on average faster then r, assigning aj to ri is also better than having it performed by r, hence the value of perf is set to the maximum. The average times to perform an activity, if not available in the event log, can be estimated from the model by considering the di erence in time between two causally related events.
Finally, the exp(r; ri; aj ) function compares the experience of the two resources to perform aj , computed as the number of times the resource has carried out the activity (qr(aj ) and qri (aj ) respectively). The exp function is de ned as exp(r; ri; aj ) = qqrri , where qr0 (aj ) = rx2GPr0 (aj) q(r0; rx; aj ). This function ranges in [0; 1]. Values close to 0 mean that the experience of ri is much smaller than that of r, while the function takes the maximum value when the experience of ri is greater than or equal to that of r.
Model speci cation. An Integer Linear Programming (ILP) model is aimed to select the set of assignments of activities to resources in order to minimize the total cost of resource replacement.
Given a sociogram G = (R0; E) and a resource r 2 R0 to replace, let C = fri 2 R0 : 9aj 2 A(ri) such that aj 2 T g be the set of candidate resources having at least one capability equal to one activity in T . Finally, Let jCj and jT j be equal to k and h respectively.
We introduce the decision variable xij ; 8ri 2 C and 8aj 2 T , equal to 1 if the resource ri is selected for replacement of r to perform activity aj , 0 otherwise.
k h The objective function min P P cij xij represents the total cost of replacing i=1 j=1 the resource r, taking into account the cost factor cij = 1 sim(r; ri; aj ). An additional constraint is set to impose that each activity in T is assigned to only one resource of C to avoid multiple assignments. Finally, a further constraint de nes the binary nature of the decision variables, according to a 0-1 Integer Linear Programming model.
In this work we propose a data-driven approach to support resource replacement in organizations, based on a notion for handover of work that is capable to model collaboration among resources on the basis of causal relations between activities. Although we referred mostly to human-centric processes, the approach is general enough to be applied in cases where a mix of users and machines cooperate together, provided additional constraints on which resources cannot be selected for replacement.
We report some preliminary results of an early experimentation done on the real-world dataset published for the BPI Challenge 2012, referring to an application process for personal loan. From the log we extracted the conform subset, including 7974 traces and 47634 events, with an average number of 6 events per trace (from 3 to 41) and belonging to 8 event types (corresponding to activity names), with 62 resources. We randomly selected a resource and a day in the last 10 days of the log. The procedure is then repeated for all resources. The average number of daily activities that needs to be reassigned per resource is 6.9. On average, in our setting the replace phase took around 6 milliseconds on average per resource to achieve a solution (with an ILP model including up to 1000 variables). The most demanding phase, on the other hand, is the creation of the sociogram, which takes 285 seconds for the whole dataset. Further analysis are not reported here for lack of space and will be deepened in future work. We also plan to extend the model to take into account further social relations among resources and the case of organisations that evolve over time [1]. Furthermore, the average execution time for each activity and the current resource workload will be considered as they can be exploited to add load-balancing constraints in the replacement planning.
The experiments run on a 4-core 2.2GHz processor, 16 GB RAM. IBM ILOG CPLEX API (version 12.9) was used for ILP model solving.