Proactive Data-driven Scheduling of Business Processes

Francesca Meneghello, Arik Senderovich, Massimiliano Ronzani, Chiara Di Francescomarino, Chiara GhidiniIJCAI 2025 · DOI

TL;DR

This paper tackles the complex challenge of scheduling business processes, which are often plagued by unpredictable activity durations and fluctuating resource availability. They introduce a novel framework that combines process mining to learn from historical data, deterministic transformations to handle uncertainty, and constraint programming with Monte Carlo simulation to generate robust, proactive schedules that minimize overall completion time.

What Problem Does This Paper Address?

Scheduling business processes, especially in service-oriented domains like healthcare and finance, is significantly more challenging than in traditional manufacturing. Unlike predictable manufacturing tasks, business processes are rife with uncertainty. Activity durations can vary wildly due to human factors, and resource availability is dynamic, influenced by shift schedules, overlapping responsibilities, and planned absences. Existing scheduling methods often struggle with this inherent variability and the practical issue of incomplete or missing data on key scheduling parameters like activity durations and resource calendars. This paper aims to bridge this gap by developing a proactive scheduling approach that leverages data-driven insights and accounts for both duration uncertainty and resource unavailability.

Methods

The authors propose a framework that integrates several key techniques:

  • Process Mining: To address the lack of readily available data, they use process mining to extract crucial BPSP parameters (activity types, durations, precedence constraints, resource requirements, and availability) from historical event logs.
  • Deterministic Transformation: To handle the stochastic nature of activity durations, they employ a transformation method (based on Beck and Wilson, 2007) that converts random durations into deterministic ones by adding a buffer proportional to the standard deviation. This allows for the application of deterministic scheduling techniques.
  • Constraint Programming (CP): A CP model is constructed to generate deterministic schedules for the transformed BPSP. This model incorporates precedence constraints, resource requirements, and planned resource unavailability (resource calendars).
  • Monte Carlo Simulation: After obtaining a set of candidate deterministic schedules from the CP solver, Monte Carlo simulations are used to evaluate these schedules using the original stochastic activity durations. This allows them to identify the schedule that probabilistically minimizes the global Makespan (overall completion time) with a high degree of confidence. They also introduce a refined method for selecting the deterministic parameter q (used in the transformation) that better correlates with the probabilistic Makespan.

Datasets

  • Synthetic Data: The authors generated synthetic datasets to systematically test their framework's performance under varying levels of uncertainty, problem sizes, and the presence or absence of resource calendars. They used benchmarks from publicly available JSP (Job Shop Scheduling) problem sets, scaled to small, medium, and big sizes.
  • Real-World Data: The approach was validated on a real-world dataset from a hospital process (DayHospital), using a full year of event log data to learn parameters and then optimizing schedules for the subsequent five months.

Key Insights and Ideas

  • Process Mining is Crucial for Real-World Applicability: The paper highlights that without process mining to infer parameters from event logs, advanced scheduling techniques would be impractical for many real-world business processes due to data scarcity.
  • The Challenge of Combined Uncertainty: The core contribution lies in addressing both uncertain activity durations and planned resource unavailability, a combination often overlooked in prior work.
  • Deterministic Transformation Needs Careful Calibration: While the deterministic transformation is a powerful tool, the paper shows that the choice of the uncertainty coefficient q significantly impacts the quality of the resulting schedule. Their refined approach for selecting q leads to better correlation with the probabilistic Makespan.
  • Proactive Scheduling Yields Tangible Benefits: The results demonstrate that proactive scheduling, by accounting for future uncertainties, can lead to significant improvements in key performance indicators like the Makespan.

Key Results

  • Synthetic Data: The approach showed effectiveness in optimizing schedules across different uncertainty levels and problem sizes. The inclusion of resource calendars improved performance, particularly for larger problem instances.
  • Real-World Hospital Data: The framework achieved a significant reduction in the global Makespan for the DayHospital process, with improvements ranging from 5% to 14% (approximately 4 hours for larger days). This demonstrates the practical utility of the approach in a complex healthcare setting.

Limitations and Future Work

  • Scalability: While the approach shows promise, the authors acknowledge the need for further work to enhance scalability for even larger and more complex business processes.
  • Real-time Adaptability: The current framework focuses on offline scheduling. Future work could explore integrating adaptive, real-time rescheduling capabilities.
  • Multi-Objective Optimization: The current work focuses solely on minimizing the global Makespan. Future research could explore multi-objective optimization to balance trade-offs with other organizational goals like cost and resource utilization.
  • Data Quality: The effectiveness of process mining relies on complete and accurate event logs. Future work could investigate methods to handle incomplete or noisy data.
  • Stochastic Programming: The authors suggest exploring stochastic programming as a more structured approach to handling uncertainty, though they note its current limitations with a vast number of possible scenarios.

Summary updated

BibTeX
@inproceedings{meneghello2025proactive,
  author = {Francesca Meneghello and Arik Senderovich and Massimiliano Ronzani and Chiara Di Francescomarino and Chiara Ghidini},
  title = {{Proactive Data-driven Scheduling of Business Processes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/953},
}
Figure