将动态规划与约束编程结合，提升部分车间调度问题的求解灵活性。
CP or DP? Why Not Both: A Case Study in the Partial Shop Scheduling Problem
- 用动态规划为主框架，约束编程做子程序，利用全局约束传播加速搜索。
- 支持任意优先级图和即时求解策略，可复用模型设计大邻域搜索方案。
- 适合需要灵活建模和渐进求解的调度场景，为混合求解提供新思路。
动态规划（DP）和约束编程（CP）是求解组合优化问题的经典范式，通常独立使用。本文展示两者可有效融合：以动态规划为主搜索框架，约束编程作为子程序，利用全局约束传播。针对部分车间调度问题（PSSP），该方法在已有纯动态规划算法和高效约束编程过滤算法基础上，实现更灵活的求解。该方法支持任意优先级约束，兼容即时列搜索等任意时间策略，不再局限于分层执行。同时，其灵活的建模能力便于设计大邻域搜索（LNS）机制，通过重启时施加部分序调度改进当前解。虽然在该问题上未超越顶尖纯约束编程求解器，但核心贡献在于验证了此类混合集成的可行性。
原文摘要 · Abstract (English)
Dynamic Programming (DP) and Constraint Programming (CP) are well-established paradigms for solving combinatorial optimization problems. Usually, these two approaches are used separately. This paper aims to show that the two can be combined effectively and elegantly, with DP serving as the primary search framework and CP used as a subroutine to leverage global constraint propagation. This paper presents such an approach for the Partial Shop Scheduling Problem (PSSP), for which a pure DP method has previously been proposed, and efficient CP filtering algorithms are available. The PSSP is a general scheduling problem where each job consists of a set of operations with arbitrary precedence constraints. The approach is flexible enough to accommodate anytime DP strategies, such as anytime column search, whereas the original DP algorithm operated in a strictly layer-wise manner. Moreover, the flexibility of the CP modeling makes it straightforward to incorporate arbitrary precedence constraints. As a result, the model naturally handles any precedence graph and even enables the design of a Large Neighborhood Search (LNS) scheme, in which the DP model is reused, and partial-order schedules are imposed across restarts to improve the incumbent solution. While not competitive with state-of-the-art pure CP solvers for this specific problem, our primary contribution is demonstrating the viability of this hybrid integration.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。