Planning human activities within business processes often happens based on the same methods and algorithms as are used in the area of manufacturing systems. However, human resources are more complex than machines. Their performance depends on a number of factors, including stress, personal preferences, etc. In this paper we describe an approach for planning activities of people that takes into account business rules and optimises the schedule with respect to one or more KPIs. Taking a task list, a set of rules or constraints and a KPI calculation model as input, we automatically create an executable model that captures all the possible scheduling scenarios. The state space of this executable model is explored to nd an optimal schedule.
Scheduling is a well-known type of optimisation problem that occurs in many
di erent contexts, e.g. exible manufacturing systems, transportation and
personnel planning [
An aspect that is often not taken into account when planning human
activities is that, unlike machines, human performance changes depending on a
number of factors [
It has been shown that there are strong relations between work-related stress
and deterioration of productivity, absenteeism and employee turnover [
As an example, Fig. 1 shows a scheduled workday for two employees working in a hardware maintenance process, whose stress is being monitored. Both employees have each been assigned to work on two cases, but the activities have been scheduled di erently. John's schedule in Fig. 1a results in a shorter workday, while Anna's schedule in Fig. 1b results in less stress. Which personal schedule is better depends on the desired tradeo between time and stress. Of course, due to the e ect of stress on performance, the last two activities in John's schedule may actually take longer than usual, so this information also has to be taken into account in the planning.
In this paper we present an activity planning approach to nd optimal schedules with respect to one or more key performance indicators (KPIs), e.g. stress or workday length. We focus on exible environments, where planning can be adjusted to people's needs.
The structure of the rest of this paper is as follows: In Sect. 2 we explain our planning approach. Then we discuss our rst implementation in Sect. 3 and evaluate it in Sect. 4. Finally, in Sect. 5 we conclude the paper and state several areas for future work. 2
A graphical overview of our approach is shown in Fig. 2. We rst discuss the input required and then we describe the approach itself. 2.1
We take a task list, the time period in which the activities should take place, a constraint model and a KPI calculation model as input.
The task list tells us what activities should be scheduled together with the available resources to divide the activities over. Instead of listing planned activities, the task list can also be extracted from a historical event log. This can be Hardware Maintenance (x4 cases, 8 hours) • Problem Intake • Repair Product • Document Issue Resources • Anna • John
If caseType = complex then Repair Product before Document Issue Stress = Stress − 1 +
Effect(Activity ,
Stress( − 1))
1. Build Executable Model 2. Find Optimal Schedule
done to see how to improve on a previous execution according to one or more given KPIs. The task list de nes the size of the scheduling problem.
The constraint model is a collection of rules that have to be upheld for a
schedule to be viable. They may describe the order in which activities are
executed, specify which people may do what activities, or impose other restrictions
on activity executions, e.g. an activity can only be done at a certain location or
time. An example of such a rule is \For complex cases, Repair Product has to
be done before Document Issue". Therefore, the schedule in Fig. 1b is only valid
if case 4 is a simple case. Rules can even specify that additional activities, not
mentioned in the task list, have to be executed. For example, if two activities
from the task list are scheduled to be executed sequentially by the same person
but at di erent locations, then that person will need to travel between the
locations. To specify which people may do what activities the constraint model can
de ne each employee's skills and the competencies needed for each activity [
The KPI calculation model de nes the quality metrics for schedules. It
speci es how the value of one or more speci c KPIs can be calculated for a given
(part of a) schedule. Examples of KPIs are the length of a working day of people
involved, the maximal stress level, and the stress level at the end of the working
day. If more than one KPI is speci ed then a tradeo needs to be made. This
can be done by giving each KPI an importance weight and normalising the KPI
values, or by constructing a Pareto front of schedules and allowing the end-user
to make the tradeo [
The goal of the planning approach is to take the input described above to produce an optimal schedule, or a set of optimal schedules. This approach should ideally not require the end-user to have scheduling expertise or to provide additional input.
Simply generating all permutations of activities divided over time and resources is not practically feasible because there are too many possibilities, while most result in invalid schedules due to violated constraints. A common scheduling technique is to use integer programming, which explores the solution space without explicitly enumerating all possible schedules. However, setting up an integer program is a complex task, especially because of history-dependent variables such as the location of a person, stress level and stress-dependent performance.
Therefore, we propose a planning approach consisting of two stages. First, an executable model that generates valid schedules is automatically constructed from the input described above. Second, this model is used to nd the optimal schedule(s).
This approach is similar to the ones in [
We have created a preliminary implementation of the proposed activity planning
approach as a plug-in in the process mining tool ProM [
The executable model is created by combining the inputs described in Sect. 2. It represents the search space of schedules, which is then the input for nding the optimal schedule. To create an executable model, the rules of the constraint model have to be combined and translated to the representation of the executable model.
There are many di erent ways to express rules or constraints in constraint
models [
We choose to model the individual rules of the constraint model as CPNs. One reason for this choice is that CPNs are expressive, but single rules are easier to model than entire processes. Another reason is that CPNs provide us directly with executable models, so we only need to combine them. Two examples of constraints modelled as CPNs are shown in Fig. 3. Activities can be supplied with guards that restrict the conditions relevant to the activity execution, e.g. caseType referring to the complexity of a case. When combing rules and creating the schedules we also take into account these guards.
Combining the rules in the constraint model is done using an adapted form of
the synchronous product de ned for PNs [
In our implementation we choose to merge the KPI calculation model with the executable model. Each KPI is tracked separately and their value is updated upon each activity execution. This makes measuring the KPI explicit, even for partial schedules, which helps when nding an optimal schedule. However, the main reason for merging the KPI calculation is that some KPIs, like stress, need to be modelled anyway because they a ect the duration of activities. 3.2
The state space of the executable model described above contains all valid
schedules as a nal state. The state space is nite, due to the limitation on the number
of activities that need to be scheduled as well as the bound on the available time
to schedule them in. Therefore, one way to nd the optimal schedule is to use
existing state space exploration techniques to nd all nal states or deadlocks [
Due to the explicit tracking of KPIs and time in each state of the executable model, both constructing a schedule and nding the optimal schedule are straightforward. Given a set of nal states, the optimal schedule is the one with the best KPI score or the best tradeo between KPIs, shown to the user e.g. by creating a Pareto front. Constructing the schedule for a state means traversing the explored state space back to the initial state and recording which activities were executed at what time. 4
We have performed a limited experimental evaluation for the implementation of our approach. A stress monitoring scenario was created, where two employees work at two possible locations on a simple hardware maintenance process. A model explaining the e ect of executing activities on the stress of the employees was assumed to be known. Our implementation automatically combined the business rules of the scenario, modelled as CPNs, and scheduled a number of activities, searching for a good tradeo between stress levels and working time. Two versions of the scenario were tested, one where activity duration did not depend on the stress level and one where stress levels a ected performance.
The experimental results are shown in Fig. 5. It is clear from Fig. 5a and Fig. 5b that the number of possible schedules increases exponentially with an increasing number of activities to plan. This also means that the time needed to explore the state space increases exponentially and it quickly reaches a point where the optimal schedule cannot be found within reasonable time. However, it should be noted that the current state space exploration implementation is Nr. of cases Shortest Nr. of valid Computation (activities) work time schedules time 1 (3) 3 hours 18 0.5 min. 2 (6) 6 hours 160 12.5 min. 3 (9) 7.5 hours 1001 8 hours 4 (12) ? ? 24 hours (a) Planning results with uniform activity durations. The shortest work time is the smallest possible workday length in which all activities can be executed.
Nr. of cases Shortest Nr. of valid Computation (activities) work time schedules time 1 (3) 3 hours 18 0.5 min. 2 (6) 6 hours 130 12 min. 3 (9) 9 hours 396 7 hours 4 (12) ? ? 24 hours
(c) The Pareto front of optimal schedules (b) Planning results when the e ects of with 3 cases. The shaded solutions are only stress on performance are considered. valid with uniform activity durations. not very e cient. Another observation is that considering the e ects of stress on performance imposes additional restrictions on the solutions, so the state space is smaller and the number of valid schedules is reduced. This also means that the computational complexity of nding the optimal schedule is lower.
Fig. 5c contains a Pareto front of optimal schedules when planning 3 cases. The Pareto front shows that a tradeo can be made in terms of dividing the work over the available people, as well as the available time. Performing the required work in less time causes higher stress levels. The shaded points indicate schedules that are infeasible if the e ect of stress on performance is considered. 5
In this paper we have described an activity planning approach that can nd an optimal schedule with respect to one or more KPIs. The approach takes a task list, a set of rules or constraints, and a KPI calculation model to create an executable model that can generate schedules. The state space of this executable model is explored to nd an optimal schedule.
Unfortunately, evaluation has shown that the current implementation is not suitable for practical purposes. The implementation allows for a lot of freedom in the types of constraints that can be speci ed and it can automatically construct an executable model out of these constraints. However, exploring the state space of the resulting executable model is very expensive. Due to the large number of possible ways to schedule activities, the state space becomes too big to explore. There are still multiple areas of future work that can make the suggested approach suitable for practical purposes.
One direction of future work is the use of heuristics during the state space exploration. As the stress of people is highly variable and dependent on many factors, it is di cult to model and predict. Searching for an optimal schedule on a awed stress model will probably not result in an optimal schedule in practice, so a focus on nding good instead of optimal schedules may be more suitable. The use of state space reduction techniques could also speed up the exploration.
Another direction of future work is the use of a di erent method to nd the optimal schedule. The executable model represents the space of valid schedules, and it might be more e cient to translate this model to a di erent formalism, e.g. a constraint program. While de ning a constraint program directly might be error-prone and challenging, the translation is possible, and would enable the use of many optimisation techniques that exist in constraint programming.
Additionally, more research is needed on learning personalised models that predict people's stress in practical situations and how that a ects performance.