Source-linked AI summary
Planning and Scheduling Business Processes under Control-Flow Uncertainty
Michel Kunkler, Stefanie Rinderle-Ma
TL;DR
The paper studies how to plan and schedule business-process activities when control-flow decisions make the required completion path uncertain. It formulates activity selection and scheduling as chance-constrained optimization through decomposed and integrated approaches. The integrated approach achieves superior makespans but is intractable at scale, while the decomposed approach scales to large settings.
Problem
Control-flow uncertainty makes the activities required to complete a business-process case unknown in advance, complicating scheduling until case completion.
Method
The paper uses chance-constrained optimization with either sequential planning and scheduling or an integrated formulation that jointly selects activities and minimizes makespan.
Results
The integrated approach yields superior makespans but is intractable at scale, whereas the decomposed approach scales to large settings.
Takeaways & Limitations
The evaluation reveals a trade-off between solution quality and scalability between the integrated and decomposed formulations.
Takeaways & Limitations
Both formulations assume uniform branch selection across loop iterations, which can produce suboptimal plans; future work includes iteration-dependent branch selection and processing-time uncertainty.
Abstract
from arXiv · showhide
Scheduling activities in business processes can improve efficiency (e.g., reduce makespan), but is challenging because the exact sequence of activities required to complete a case is often uncertain due to decisions based on data that emerges during execution. Nevertheless, probabilistic information regarding such decisions can often be estimated or derived from historical execution logs, and can help anticipate which execution paths are likely to lead to successful completion. Planning with particular execution paths affects feasibility, i.e., the probability of successful completion, and the expected number of superfluous activities that are planned but never executed. We frame the problem as a chance-constrained optimization problem and present two formulations: A decomposed approach with two stages, a planning stage that minimizes the expected number of superfluous activities subject to a feasibility constraint, and a scheduling stage that minimizes the makespan over the planned activities; and an integrated approach that combines planning and scheduling into a single formulation. Evaluation on two real-world and one synthetic dataset shows that the integrated approach yields superior makespans but is intractable at scale, while the decomposed approach scales to large settings.
1 Introduction
Business-process scheduling can improve efficiency and visibility, but control-flow uncertainty makes the activities required for case completion unknown in advance. The paper addresses this by selecting and scheduling activities under a feasibility constraint, using decomposed and integrated approaches.
- Motivation: Scheduling can reduce case makespan, improve resource utilization, and help identify upcoming capacity bottlenecks.Schedules also provide visibility that supports resource preparation and management decisions.
- Control-flow uncertainty: Control-flow uncertainty arises because runtime constraints or data-dependent decisions can make the required activity sequence unknown beforehand.Consequently, the exact set of activities to schedule for a case is uncertain.
- Control-flow uncertainty: Existing strategies either schedule only until the process becomes highly predictable or allocate resources online, limiting preparation for later activities.These strategies therefore undermine some benefits of advance scheduling.
- Approach: The paper uses chance-constrained optimization to select activities that meet a predefined feasibility threshold while minimizing an objective.Feasibility means scheduled activities are sufficient to complete the case, while unnecessarily scheduled activities may be skipped as superfluous.
- Approach: The decomposed approach first minimizes expected superfluous activities subject to feasibility, then schedules the selected activities to minimize makespan.The integrated approach combines planning and scheduling in one formulation that directly minimizes makespan subject to feasibility.
- Results: The integrated approach yields superior makespans but is intractable at scale, whereas the decomposed approach scales to large settings.The evaluation covers two real-world and one synthetic dataset.
2 Decomposed Planning and Scheduling
The decomposed approach first selects branches and loop counts under a case-feasibility threshold while minimizing expected superfluous activities, then schedules the resulting activities to minimize makespan. It extends this planning and scheduling process to multiple cases using a shared selection and an expected feasible-case constraint.
- Planning problem: Stochastic process trees represent sequential, parallel, exclusive-choice, and redo-loop structure together with branch and loop probabilities.The formulation assumes stationary exclusive-choice probabilities p_i,j and redo probabilities q_i across loop iterations.
- Planning problem: Planning minimizes expected superfluous activities subject to a case-feasibility threshold θ.Expected superfluous activities sum planned counts minus expected execution counts across activities, while feasibility is computed from selected branches and loop probabilities.
- Planning problem: The planning problem selects exclusive-choice branches x_i,j and planned loop iterations r_i as decision variables.A loop planned for r_i iterations includes r_i do-part executions and r_i −1 redo-part executions.
- Scheduling problem: Scheduling removes non-selected branches, unrolls loops, and preserves process-tree precedence and mutual-exclusivity constraints.Mutually exclusive activities may overlap on a shared resource because at most one exclusive-choice branch executes at runtime.
- Multi-case planning and scheduling: For n concurrent cases, the decomposed approach applies one selection uniformly and constrains the expected number of feasible cases.The resulting schedule uses the union of the n unrolled process trees; per-case planning could reduce superfluous activities but becomes intractable for large n.
3 Integrated Approach
The integrated approach combines activity planning and scheduling under control-flow uncertainty, allowing selections and overlaps to be optimized jointly while accounting for their effects on case feasibility.
- 3 Integrated Approach: The integrated approach addresses two decomposed-approach limitations by jointly selecting activities and scheduling them, including overlaps among non-exclusive activities.Selecting additional activities can improve makespan by avoiding bottleneck resources, while cross-case overlaps can shorten schedules with limited feasibility impact.
- 3 Integrated Approach: The integrated model represents planned activities, precedence relations, intervals, and resource assignments over variable-size sets induced by each case’s selection.Activity sets and precedence relations are derived from the selected, unrolled process trees.
- 3 Integrated Approach: For each case, the formulation deletes unselected exclusive-choice branches and unrolls loops according to the selected iteration counts.The resulting unrolled-and-selected process trees retain precedence, exclusivity, and original branch or loop probabilities.
- 3 Integrated Approach: Overlapping activities on a shared resource require priority rules because only the higher-priority activity can execute when non-exclusive allocations conflict.The model defines overlapping activities, priority orders, threats, and intra-case feasibility to characterize these conflicts.
- 3 Integrated Approach: The feasibility calculation uses per-case execution scenarios to capture correlated overlapping activities rather than treating each overlap as an independent threat.The approach exploits independent scenarios across cases, mutual exclusivity of exclusive activities, and deterministic executions within each scenario.
- 3 Integrated Approach: The integrated formulation minimizes makespan subject to an expected-feasible-case threshold, but its scenario space grows exponentially with loop-nesting depth.Runtime loop realizations beyond the plan are incorporated through tail-absorbing scenario weights so threat probabilities and feasibility bounds remain valid.
4 Evaluation
The evaluation compares the approaches on three business processes using constraint-programming implementations and reports feasibility, makespan, workload, and solver performance. The integrated approach can shorten makespans where it solves, whereas the decomposed approach is substantially more scalable.
- 4 Evaluation: Three processes—Repair Shop, BPIC-14I, and BPIC-17W—were selected to vary process complexity, resource requirements, and event-log availability.The evaluation includes one synthetic process and two real-world processes.
- 4 Evaluation: The implementations use Google OR-Tools CP-SAT, with probabilities converted to fixed-point integers for integer-only solving.The decomposed approach precomputes geometric-series coefficients up to rmax = 10, while the integrated approach limits loop unrolling to rmax = 10.
- 4 Evaluation: The evaluation reports expected feasible cases, makespan, scheduled activities, planning and scheduling durations, optimality indicators, and integration duration.The feasibility threshold and workload measures distinguish reliability from resource commitment and runtime cost.
- 4 Evaluation: The integrated approach yields shorter makespans where it solves, typically at the cost of more scheduled activities, but scales poorly on larger configurations.It mostly fails to find feasible solutions within the time limit for larger configurations.
- 4 Evaluation: The decomposed approach finds feasible schedules for every tested configuration except BPIC-17W with N=50 and remains the more reliable scalable option.Its planning phase is trivially fast and always optimal, while scheduling is the main bottleneck.
- 4 Evaluation: The single-path baseline has process-dependent feasibility: it matches the decomposed approach for BPIC-14I at the 60% constraint but performs extremely poorly for BPIC-17W.For Repair Shop, it has lower feasibility than the other approaches while matching the decomposed approach’s makespan.
5 Related Work
Related work spans business-process scheduling, resource-constrained project scheduling, and AI planning under uncertainty. The paper differs by treating branch selection as stochastic and planning sufficiently many paths to meet a feasibility target.
- 5 Related Work: The related literature spans business process management, operations research, and AI planning, but the problem setting combines planning and scheduling until case completion under stochastic control flow.This distinguishes the paper from approaches that stop at the next uncertain decision point or assume a fixed activity network.
- 5 Related Work: Business-process scheduling studies often select a single best path by treating exclusive-choice branches as decision variables.This work instead treats branch selection as a stochastic outcome and plans for sufficiently many paths to satisfy a feasibility level.
- 5 Related Work: Standard RCPSP schedules a fixed activity network with known durations and precedence constraints, unlike this paper’s uncertain network structure.RCPSP with alternative subgraphs is closer because it includes alternative execution paths, but its alternatives are decision choices rather than stochastic outcomes.
- 5 Related Work: Conformant probabilistic planning addresses uncertain outcomes, while chance-constrained variants commonly model uncertain durations without uncertain control flow.The paper applies chance-constrained optimization to control-flow-induced uncertainty in business-process activities.
6 Discussion and Conclusion
The paper presents decomposed and integrated chance-constrained approaches for scheduling business processes through case completion under control-flow uncertainty. The integrated approach can improve makespan but scales poorly, while the decomposed approach reliably scales across nearly all tested settings.
- 6 Discussion and Conclusion: The integrated approach can yield superior makespans, whereas the decomposed approach reliably finds feasible schedules across nearly all tested configurations.This reflects a trade-off between solution quality and scalability.
- 6 Discussion and Conclusion: Scheduling through case completion lets resources prepare for upcoming activities and supports reliable commitments toward customers.The feasibility threshold balances rescheduling risk against reserved but potentially unused capacity.
- 6 Discussion and Conclusion: Both formulations assume uniform branch selection across loop iterations, which can produce suboptimal plans when later iterations have lower execution probabilities.Future work could use iteration-dependent branch selection and incorporate processing-time uncertainty.