本文探讨了cpmpy库中累积约束（cumulative constraint）在使用ortools求解器时遇到的性能瓶颈，特别是在大规模非抢占式任务调度场景下，求解时间随任务数量呈指数级增长。文章揭示了问题源于累积约束的线性松弛实现，并指出cpmpy已通过更新解决了这一性能问题，显著提升了求解效率。
在约束编程（Constraint Programming, CP）领域，cpmpy 是一个强大且灵活的Python库，用于构建和求解各种优化问题。其中，Cumulative 约束是处理资源受限任务调度的核心工具，它允许我们定义一组任务，每个任务有开始时间、持续时间、结束时间、资源需求，并确保在任何时间点，所有正在运行任务的资源需求之和不超过给定容量。然而，在使用 cpmpy 结合 ortools 求解器处理大规模任务调度问题时，用户可能会遇到显著的性能瓶颈。
CPMpy中累积约束的性能挑战
我们以一个典型的非抢占式任务调度问题为例：目标是在给定时间范围内，确定完成一系列任务所需的最少机器数量。任务具有相同的持续时间和资源需求（例如，每台机器一次只能处理一个任务）。在实际测试中，当任务数量适度增加时，使用 cpmpy 的 Cumulative 约束与 ortools 求解器结合，求解性能会急剧下降，甚至出现无法在合理时间内找到解决方案的情况。
这种性能下降尤其在以下场景中表现突出：当部分机器已经满负荷运行，而剩余的少量未分配任务的总持续时间小于前几台机器的空闲时间总和时。这意味着求解器需要进行更复杂的推理来分配这些“零散”的任务，从而导致搜索空间急剧膨胀。
以下是用于模拟此问题的 cpmpy 代码示例：
import cpmpy as cp
import logging
from typing import List
class CumulativeTestModel:
def __init__(self, task_duration: int, nb_tasks: int, end_date: int):
self.model: cp.Model = cp.Model()
# 定义变量
self.objective: cp.IntVar = cp.intvar(0, nb_tasks) # 目标：最小机器数
starts: List[cp.IntVar] = [cp.intvar(0, end_date) for _ in range(nb_tasks)]
durations: List[int] = [task_duration] * nb_tasks
ends: List[cp.IntVar] = [cp.intvar(0, end_date) for _ in range(nb_tasks)]
demands: List[int] = [1] * nb_tasks # 每个任务需求1个资源
# 添加累积约束
self.model += cp.Cumulative(
start=starts,
duration=durations,
end=ends,
demand=demands,
capacity=self.objective, # 机器容量由目标变量决定
)
# 最小化目标变量
self.model.minimize(self.objective)
logging.info(f"Model created with {nb_tasks} tasks.")
def run(self):
solver = cp.model.SolverLookup.get("ortools", self.model)
has_solution = solver.solve()
if not has_solution:
logging.info("No solution found.")
else:
logging.info(f"Solution found: {solver.status()} -> {self.objective.value()}")
if __name__ == "__main__":
logging.basicConfig(level=logging.INFO)
# 示例用法
CumulativeTestModel(task_duration=10, nb_tasks=3, end_date=15).run()
CumulativeTestModel(task_duration=10, nb_tasks=5, end_date=25).run()
CumulativeTestModel(task_duration=10, nb_tasks=7, end_date=35).run()
CumulativeTestModel(task_duration=10, nb_tasks= 
