An appropriate resource utilization is crucial for organizations in order to avoid, among other things, unnecessary costs (e.g. when resources are under-utilized) and too long execution times (e.g. due to excessive workloads, i.e. resource over-utilization). However, traditional process control and risk measurement approaches do not address resource utilization in processes. We studied an often-encountered industry case for providing large-scale technical infrastructure which requires rigorous testing for the systems deployed and identi ed the need of projecting resource utilization as a means for measuring the risk of resource underand over-utilization. Consequently, this paper presents a novel predictive model for resource utilization in decision-intensive processes, present in many domains. In particular, we predict the utilization of resources for a desired period of time given a decision-intensive business process that may include nested loops, and historical data (i.e. order and duration of past activity executions, resource pro les and their experience etc.). We have applied our method using a real business process with multiple instances and presented the outcome.
Human resource utilization in an organization can be seen as the proportion of
time a person spends on working on allocated tasks. Poor utilization of human
resources2 relates to having resources unnecessarily idle or overloaded. This has a
very negative e ect on process performance measures such as process completion
time, execution costs, and quality [
In a scenario where the process model has no decision nodes, given a
baseline schedule and resource allocation [
In this paper we address that problem and describe a mathematical method for quantifying resource utilization with respect to the structural properties of non-deterministic processes and the historical executions of these proceses. The input values that are used for our prediction model are intrinsically of a stochastic nature, i.e. in the form of probability density functions (PDF). They include, among others, the activity duration PDFs and the resource utilization PDFs. We propagate these input values towards the accumulated utilization function. This function provides a visual overview on the level of future resource utilizations. Therefore, an upcoming over- or under-utilization of resources can be observed. Moreover, we have de ned two metrics which characterizes resource over-utilization and under-utilization. We have implemented our approach and demonstrated it with a real process related to large-scale technical infrastructure development and deployment.
We believe that our approach enhances the assessment of process behaviour with the resource perspective. It is especially useful for organizations who need to evaluate the utilization of resources for which they are accountable. With the help of our approach they can automatically get an answer to questions such as whether they have enough resources for the robust execution of their processes, in which periods of time they should expect a delay in the process execution, and when they can safely grant vacations to particular resources, among others.
The paper is structured as follows: Section 2 presents a scenario that motivates this work as well as related work. Section 3 formally de nes the input required for our approach. Section 4 describes our approach for predicting resource utilization in decision-intensive business processes. Section 5 applies our method to a real process and presents the outcome, and Section 6 concludes the paper and outlines the future work. In the following, we describe an example scenario that motivates this work and shows the problems to be addressed, and then we outline related work.
A company that provides large-scale technical infrastructure requires rigorous testing for the systems deployed. Each system consists of di erent types and number components that are developed and tested in parallel. In order to provide concise and clear examples while describing our method, we use the simple example process shown in Fig. 1. In this process, the Develop activity is followed by a Test activity, and this may repeat if the test fails. There is also the activity Manage which abstracts the potential contractual work running in parallel. There are two resources, namely Jack and Jill, who execute this process. A more complex process from a real scenario is used later in Section 5 for demostrating the applicability of our method.
The approach presented in this paper is mostly related to resource-related risk
monitoring and prediction. This risk occurs \due to the high variability that may
a ect operational processes in real world scenarios" [
Information systems support processes by recording information about their
executions in event logs [
Our method requires extracting durations of activities, and experience of
resources for each activity from the event logs for providing realistic resource
utilization predictions. Durations can be obtained in a similar way to described
by van der Aalst et al. [
Within the context of quantifying the resource perspective, our method draws
parallels with [
Folino et al. [
The following input is required for resource utilization prediction in decisionintensive business processes: Input 1 (Business Process Model). A business process model P is represented as a directed, connected graph (N; E) with N = A [ G [ fnstart; nendg denoting a nite set of nodes consisting of activities A, gateways G, and two respective start and end events nstart and nend, and E N N representing a set of edges connecting the nodes.
We assume that our model consists of activities, XOR-gateways (decision points), AND-gateways (parallel execution gateways), a start-event, and an endevent. The process always terminates (i.e., it contains no livelocks or deadlocks).
In a real life application, an input process can be composed of the processes that are planned to be executed in the future, and of the unexecuted fragments of the already executing processes.
Input 2 (Edge Execution Probability). Given a process model P = (A [ G [ fnstart; nendg; E), each edge e 2 E leaving a XOR-gateway g 2 GXOR G of P is annotated with an edge execution probability pe 2 [0; 1]. Additionally edge execution probabilities pe must satisfy
P pe = 1; 8g 2 GXOR. e2E\(g N)
The outgoing edges of XOR-gateways are annotated with edge execution probabilities (see Fig. 6).
Input 3 (Activity Duration PDF). For each activity a 2 A, Da : R 0 ! R 0 denotes the PDF representing the duration PDF of activity a.
Example 1. For clari cation, we provide the process in Fig. 1. A single loop of two consequent activities Develop and Test is presented in parallel with the activity Manage. The duration PDFs for Manage and Develop are normally distributed while Test has a xed duration represented as a solid dot (i.e., a time shifted dirac delta function 3). The duration of Test is deterministically 3 time-units (TU) whereas the duration of Manage is on average 2 TU.
Input 4 (Resource Utilization PDF). Given a set of activities A of a business process B and a set of resources R, the resource utilization PDF is Ua;r : R 0 ! R 0 for activity a 2 A and resource r 2 R. U de nes the PDFs of the probable additional utilization the execution of an activity causes for all resources.
The resource utilization PDFs describe which resources are utilized to what extent while executing an activity. Intuitively, one can think of Ua;r(x)dx as being the probability of r's utilization falling in the in nitesimal interval [x; x + dx]. We assume that utilization values are normalized so that Ua;r(0) represents the probability of resource r being 0% utilized by the activity a. Ua;r(1) speci es the probability of resource r's being utilized 100% by the activity a. The notion of utilization can be considered as \the percentage of the work day spent on a task" in our running example.
Example 2. See Fig. 2 for an example visualizing the de nition of resource utilization PDF. For instance, UDevelop;Jill(0:5) = 0:3 means with 0.3 probability Input 1
Input 2
Resource Input 4
Input 5 Time Input 3
Def. 1 Def. 2,3,4,5
Def. 6 Output 3
Output 2
Output 1 Develop utilizes Jill 50%, and UDevelop;Jack(0) = 1 means that Jack is never occupied by Develop.
Input 5 (Experience Matrix). Given a set of activities A of a process model, and a set of resources R, the experience value Xa;r : R>0 where a 2 A and r 2 R is a multiplication factor (a scalar) for activity durations.
The experience of each resource r in every activity a is re ected in this matrix. This value theoretically has a range between zero to in nity which is extracted from activity execution durations of resources. Resources that execute activities faster than average have an experience value greater than 1:0.
We assume that the edge execution probabilities pe, activity duration PDFs Da, resource utilization PDFs Ua;r, and experience matrix X (Input 2{5 ) are extracted from the event logs obtained from the past executions of the process P (Input 1), where the resources and the durations of the past activity executions are recorded. A solution to this prediction problem is total utilization PDFs over time for each resource. Each function provides a utilization prediction for its respective resource.
Following the problem de nition, we rst introduce intermediary functions that would allow us to compute the ultimate total utilization PDF, and afterwards we introduce quality metrics that would quantify the risk of abnormal resource utilization that may occur in the future. Fig. 3 is an overview of \used by " relation between input values and de ned functions of our method (e.g., Input 3 is used by De nition 1 ). Background colors blue, green and yellow indicates process-related, time-related and resource-related elements.
De nition 1 (Dependent Activity Duration PDF). Given an independent activity duration PDF Da, allocation PDF Ua;r, experience values Xa;r for activities a and resources r, the (utilization-and-experience) dependent activity duration PDF Dadep : R 0 ! R 0 is de ned as follows:
For each activity, an experience value xa is derived from the experiences of all the resources that are potentially participants in a (i.e., 9x 2 R>0 : Ua;r(x) > 0). xa is used as a division factor for Da, therefore the experience values above 1:0 reduce the width of Da (i.e., they act as speed-up factor for execution times), and the opposite holds for the values smaller than 1:0. 4.1 Edge Transition Probability Function In order to compute how often an activity is being executed, we need to extract the probability values of edge traversals over time. Only activities can create time delays via their duration PDFs. Edge transitions are always instantaneous. De nition 2 (Edge transition probability function). fe(t) : R 0 ! R 0 denotes the probability that an edge e 2 E is traversed at time t 2 R 0.
P (An edge is traversed between t1 and t2) = P (Edge is traversed before t2) P (Edge is traversed before t1) Zt2 0
Zt1 0 = f (t0) dt0
f (t0) dt0
Note that in general fe is not a PDF. However, if the process contains no XOR-gateways all fe are PDFs since 8e 2 E : R fe(t) dt = 1.
De nition 3 (f for AND-Gateway). Given g 2 Gand G with incoming edges fin1; : : : ; inng = E \ (N g) and outgoing edges fout1; : : : ; outmg = E \ (g N ), the edge transition probability function fe(t) for outgoing edges e is de ned as
Having a generic analytical result about the edge transition behavior of the process is di cult unless the input is in form of time-shifted dirac delta functions or PDFs of an exponential distribution. finn (t) (t) . .
.
fout1 f outm(t) foutj (t) = n t Q R fini (t0) dt0 i=1 d dt ; 1 j
m De nition 4 (f for XOR-Gateway). Given g 2 GXOR G with incoming edges fin1; : : : ; inng = E \ (N g), outgoing edges fout1; : : : ; outmg = E \ (g N ), and edge execution probabilities fpout1 ; : : : ; poutm g, the edge transition probability function fe(t) for outgoing edges e is de ned as . . . finn (t) fout1 (t) . .
. f outm(t) n
P fini (t) ; 1 foutj (t) = poutj i=1 j m De nition 5 (f for Activities). Given an activity a 2 A with one incoming edge ein, one outgoing edge eout, and activity duration PDF Dadep, the edge transition probability function fout(t) is de ned as fin(t)
fout(t) Dadep(t) fout(t) = fin(t)
Dadep(t)
Note that the convolution operator for two functions f and g is de ned as (f g)(t) = R f (t0)g(t t0) dt0.
We compute edge transition probability functions directly on the process.
Another way of doing this is described in [
De nition 6 (Activity execution probability function). The function Fa(t) : R 0 ! R 0 denotes the probability density that an activity a 2 A is executed at time t 2 R 0.
Fa(t) = P (Activity is currently being executed at t) = P (Activity is entered before t)
P (Activity is left before t) = fin(t0) dt0 fin(t0)
Dadep(t0) dt0 = fin(t0) dt0 fout(t0) dt0 t Z 0
t Z 0
t Z 0
t Z 0 Example 3. Our running example with the activity duration PDFs Da in Fig. 1 would then result into the activity execution probability functions Fa presented in Fig. 4. Manage is immediately executed once. As Develop and Test repeat
t
Output 1 (Total utilization PDF over time). Or is the utilization PDF of a resource r 2 R at time t 2 R 0, where A = fa1; : : : ; ang. A value Or(t; u) represents the probability density that r is utilized by an amount of u percent of his/her time (e.g. u = 1 means full time, u > 1 means over-utilization) at time t. The operator u is the convolution over the parameter u.
Or : (R 0
R 0) ! R 0 Or(t; u) = (u) : : : u (Ua1;r(u)Fa1 (t) + (u)(1
Fa1 (t))) u (Uan;r(u)Fan (t) + (u)(1
Fan (t)))
For each resource, there is one total utilization PDF over time. In these PDFs, the activity execution probability functions and resource utilization PDFs of the respective resources are combined.
Example 4. In Fig. 5, the total utilization PDF over time for Jack OJack is based on (1) our running example with the activity execution probability functions F as seen in Fig. 4, and (ii) the resource utilization PDFs U as seen in Fig. 2. OJack;T est(t; u) = (WJack;T est(u)FT est(t) + (u)(1 FT est(t))) is the probable utilization of Jack by the activity Test shown in top-left corner. In a similar way, OJack;Manage is on the top-right corner. We do not show OJack;Develop, since it has no in uence on Jack's total utilization (see Fig. 2). We can clearly observe in OJack;Manage that the activity Manage is non-repeating. The combined total utilization PDF for Jack OJack is shown in bottom of the Figure. It shows how the probable utilizations of Jack's activities combine into a period of over-utilization as shown in the red region. Such region representing overutilization are of special interest for the decision makers (e.g., project managers) who are also responsible for time and resource management. time F
Test utilization iliab UJack,Manage y t b o r p
time OJack(t, u)
F over-utilization utilization
Based on resource utilization PDFs Or, we can de ne various metrics for quantifying abnormal resource utilization. These metrics can be used as optimization criteria for managing organizations and their schedules.
Output 2 (Resource over-utilization metric). The resource over-utilization metric m+r : R 0 for a resource r 2 R is the volume of utilization larger than 1.
oOr(t; u) du dt
Develop Component A
Develop Component B
Develop Component C
Test Component A
Test Component B
Test Component C pjoin-A p B pjoin-B p C pjoin-C
Integrate Components
Test pend p * Output 3 (Resource under-utilization metric). The resource under-utilization metric m r for a resource r 2 R is the accumulated volume under the optimal resource occupancy threshold on the occupancy axis (cf. 1:0).
t Z
We tested our method in a setting where the utilization of 10 resources is forecasted in 10 process instances of the process shown in Fig. 6. In this realistic process, each system consists of di erent types and number of components that are developed and tested in parallel. All Develop activities must be tested independently, and repeated development e ort is expected. Additionally, a nal Integrate and Test phase is mandatory for the combined system, which may cause additional repetitions of the entire process. It is expected for resources to work on multiple processes in parallel.
Table 1 describes the properties of 10 process instances with di erent starting times and resource utilizations: The process name (id), the starting time (ts), the initial letter of the resource allocated to a certain activity (r), mean duration of the activity (@), repetition probability of the iteration \Develop and Test " for component X (p X ) are given (cf. p is the edge execution probability of restarting the process). The di erent components of each process have di erent failure rates and duration distributions.
In order to generate the utilization functions for each resource, we simulate the process instances with respect to their properties (cf. Table 1) and apply the methods described previously. Note that we leave out the process execution paths with a probability lower than 0.1%.
Fig. 7 shows the visualization of the utilization functions for each resource. For instance, Boris is overoccupied most of the times because he is allocated to 5 Develop, 3 Test, and 4 Integration activities which are overlapping. Grace becomes overoccupied due to the start of project-6 at day 70. Edgar, Florence, and Henry are also expected to be visibly overoccupied in some periods during the execution of these 10 projects, though their situations are not as critical as Boris's, because their activities are not as many times overlapping as the activities of Boris. David's utilization looks exceptionally low. Moreover, by using the quality metrics de ned in Section 4.3, we are informed that there is a 10 times greater risk of resource under-occupancy (m = 2665:45) than resource over-occupancy (m+ = 273:44). This can be intuitively con rmed by comparing the amount of blue and red areas on Fig. 7.
Fig. 7 and the quality metrics suggest that: (i) There are more resources than needed in this setting, and (ii) demand for resources can still be balanced, especially those of Boris's for a more robust execution.
The computational complexity of our method is equivalent to the complexity
of numerical integration which is P-complete [
In this paper we have introduced a novel method for predicting resource utilization in decision-intensive business processes. Our approach facilitates to obtain a resource utilization overview for the whole organization where the processes have a stochastic nature. As a result, the decision makers are provided with actual Boris Casey David Edgar Grace Henry Ingrid
Jack Florence 40 70 100
120 utilization 0-50% 50-100% 100-150% 170 >150% days insights about their organizational feasibility. One advantage of our approach is that it can be readily used in practice, and it can be incorporated in BPM systems as a supplementary risk monitoring element.
Our future work primarily involves conducting exhaustive evaluations to assess the applicability of the approach in more real settings and compare the performance results. We also aim at integrating the approach into a BPM system as well as at adapting the current design-time method to be used at run time too, i.e. to make it more dynamic such that the resource utilization predictions are updated during the execution of the process instances.