Abstract
Recent breakthroughs in predictive business process monitoring equip process analysts with predictions on running process instances, supporting the elicitation of proactive measures to mitigate risks that can be caused by the process instance. However, contrary to active research on providing various predictions and improving the accuracy of prediction models, the practical application of such predictions has been left to the subjective judgment of domain experts. In this work, we explore the exploitation of the insights from predictive information for the actual process improvement in practice. Concretely, we focus on improving resource allocation in business processes where the goal is to allocate appropriate resources to tasks at the proper time. Based on design science methodology, we develop a two-phase method to improve resource allocation by leveraging predictions. Based on the method, we instantiate an algorithm to optimize total-weighted completion time and evaluate its effectiveness and efficiency. From an academic standpoint, our work demonstrates the combination of predictions using machine learning and optimizations based on scheduling. From a practical standpoint, our work provides a general approach to optimize resource allocations for different objectives using predictions.
Practical problem
Hospitals, service centers, and other organizations must constantly decide which staff member handles which waiting case next, and a poor choice means urgent cases wait while a slow worker handles an easy one. Classical scheduling methods can compute good assignments, but only if they know each case’s upcoming steps and how long each worker would take, information that is simply not available while a patient is still being treated. Meanwhile, predictive process monitoring has become good at forecasting exactly such missing details, yet in practice its forecasts end up on a dashboard for a manager to interpret rather than driving any decision. Process owners therefore have predictions on one side and allocation algorithms on the other, with no systematic way to connect the two.
Research questions
- How can predictions about running process instances be used to optimize resource allocation when the information required by standard scheduling techniques is missing (non-clairvoyant instances)?
- Does prediction-enriched allocation improve total weighted completion time over the best allocation possible with only known information, and at what computational cost?
- How accurate do the predictions need to be before the allocation outperforms the no-prediction baseline?
Contributions
- A two-phase method, formalized through scheduling instances, work assignments, schedules and objective functions, that first trains prediction models offline and then predicts missing parameters online before optimizing the allocation.
- An uncertainty-aware prediction step based on Bayesian neural networks with Monte Carlo dropout and LSTM layers, which discards predictions whose uncertainty exceeds a threshold.
- An instantiation for minimizing total weighted completion time of weight-aware non-clairvoyant instances that casts allocation as a minimum cost maximum flow problem solved by the network simplex method.
- An evaluation protocol comparing against a maximum-weight baseline on a simulated emergency department and a real tertiary-hospital emergency log, including a controlled study of prediction accuracy.
- A public Python implementation on GitHub (
prediction_based_resource_allocation).
Key findings
- On the simulated emergency department (11 activities, 25 resources), the method yields lower total weighted completion time than the baseline for every patient set; with 100 patients the baseline is 14% higher (6,348 vs 5,420).
- Prediction adds computation, but the simulated 3-hour process is scheduled in under 80 seconds, which the paper judges suitable for real-time use.
- Scheduling quality jumps between 40% and 60% emulated prediction accuracy (with 110 patients, TWCT falls from 7670 to 6036); about 60% accuracy usually beats the baseline, with the worst case needing 80% and the best only 50%.
- On the real emergency log (421,995 events, 27,478 patients, 754 resources), the method beats the baseline on all 15 daily instance sets; on November 1, 2018 it reaches TWCT 4871 versus 5386, a 9.6% improvement.
- Limitations: on the real log almost all run time goes into predictions (710.4 of 721.6 seconds in one day), accuracy and objective are not monotonically related because the future sequence stays unknown, and alternative-resource service times had to be estimated rather than observed.