用通用全局约束实现条件时间区间的累积函数，解决调度建模难题
Implementing Cumulative Functions with Generalized Cumulative Constraints
- 提出通用累积约束，统一建模条件时间区间
- 新时表过滤算法支持生产者-消费者调度，性能媲美商业求解器
- 开源实现填补空白，适合大规模调度问题研究者使用
使用现代商业约束求解器建模包含生产者与消费者的时间区间调度问题已成为常见方法。该范式可有效处理多种调度场景，但现有开源求解器尚不支持，且实现细节未公开。本文提出一种基于单一通用全局约束——广义累积约束的实现方案，并设计了一种专为条件时间区间任务优化的新时表过滤算法。实验结果表明，该方法结合新过滤算法后，在性能上可与现有求解器竞争，能有效建模生产者-消费者调度问题，并具备良好的大规模扩展能力。
原文摘要 · Abstract (English)
Modeling scheduling problems with conditional time intervals and cumulative functions has become a common approach when using modern commercial constraint programming solvers. This paradigm enables the modeling of a wide range of scheduling problems, including those involving producers and consumers. However, it is unavailable in existing open-source solvers and practical implementation details remain undocumented. In this work, we present an implementation of this modeling approach using a single, generic global constraint called the Generalized Cumulative. We also introduce a novel time-table filtering algorithm specifically designed to handle tasks defined on conditional time-intervals. Experimental results demonstrate that this approach, combined with the new filtering algorithm, performs competitively with existing solvers enabling the modeling of producer and consumer scheduling problems and effectively scales to large-scale problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。