Planning and Scheduling Business Processes Under Control-Flow Uncertainty

Summary

Scheduling business-process activities is difficult because the sequence required to complete a case may depend on data revealed during execution. The paper uses probabilistic information derived from historical execution logs to anticipate likely paths and formulates the task as a chance-constrained optimization problem. It considers both the probability of successful completion and the expected number of planned activities that will ultimately be unnecessary. The decomposed formulation first chooses a plan that limits unnecessary activities subject to a feasibility constraint, then schedules those activities to reduce makespan. The integrated formulation optimizes planning and scheduling together. Tests on two real-world datasets and one synthetic dataset show that the integrated approach achieves better makespans, but becomes intractable at scale. The decomposed approach is less tightly optimized but scales to large problem settings.