在流程执行路径不确定时，优化任务计划与调度以提升成功率并减少冗余操作。
Planning and Scheduling Business Processes under Control-Flow Uncertainty
- 分阶段规划：先最小化冗余活动，再优化时间
- 集成方法使完成时间更短但难以扩展
- 分阶段方法可处理大规模实际场景
业务流程中的活动调度能提高效率（如缩短完工时间），但因执行中数据驱动的决策导致路径不确定而具挑战性。然而，可通过历史日志估算决策的概率信息，预测可能成功完成的执行路径。针对特定路径进行规划会影响可行性（即成功完成的概率）和预期冗余活动数量（计划了但未执行）。本文将问题建模为机会约束优化问题，提出两种方案：分阶段方法包含规划阶段（在可行性约束下最小化冗余活动期望值）和调度阶段（在已规划活动上最小化完工时间）；以及将规划与调度整合为单一公式的方法。在两个真实世界数据集和一个合成数据集上的评估表明，集成方法获得更优的完工时间，但在大规模下不可行；而分阶段方法可扩展至大规模设置。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。