Scheduling activities in business processes can improve efficiency, e.g., by reducing the makespan, yet the exact order of activities is often uncertain because decisions depend on data that emerges during execution. Probabilistic estimates of these decisions can be derived from historical logs, allowing us to anticipate which execution paths are more likely to succeed.
Choosing particular execution paths influences two aspects: the feasibility, i.e., the probability of successful completion, and the expected number of superfluous activities that are planned but never executed. We model the problem as a chance‑constrained optimization and propose two formulations.
The first is a decomposed two‑stage approach: a planning stage minimizes the expected number of superfluous activities under a feasibility constraint, followed by a scheduling stage that minimizes the makespan over the planned activities. The second is an integrated approach that combines planning and scheduling into a single model, optimizing both objectives simultaneously.
Evaluation on two real‑world datasets and one synthetic dataset shows that the integrated approach yields shorter makespans but becomes intractable at scale, whereas the decomposed approach scales well while delivering acceptable makespans.
Review