OR-Tools CP-SAT 调度优化实战：从约束建模到搜索策略

在工业排产、人员排班和项目调度场景中，传统的启发式算法往往难以平衡多目标优化与硬约束满足。Google OR-Tools 的 CP-SAT（Constraint Programming - SAT）求解器提供了一种声明式的建模方式，让开发者专注于 "什么是一个合法调度" 而非 "如何构造调度"。本文从核心原语出发，逐步展开到复杂场景的性能调优策略。

三大核心原语：Interval、No-Overlap、Cumulative

CP-SAT 的调度建模建立在三个基础组件之上。理解它们的语义边界是正确使用的前提。

区间变量（Interval Variable） 封装了任务的三元组 (start, duration, end)，并自动维护约束 end = start + duration。创建方式如下：

from ortools.sat.python import cp_model

model = cp_model.CpModel()
horizon = 100  # 调度时间窗口上限

start = model.new_int_var(0, horizon, 'start')
end = model.new_int_var(0, horizon, 'end')
duration = 8   # 固定时长，也可使用变量实现弹性工时

interval = model.new_interval_var(start, duration, end, 'task')

对于可选任务（如可选订单、弹性排班），使用 new_optional_interval_var，通过布尔变量 is_present 控制任务是否被调度。

No-Overlap 约束 确保一组区间互斥，即同一时刻至多一个任务执行。这是单机调度的直接建模：

intervals = []
for i, dur in enumerate(durations):
    s = model.new_int_var(0, horizon, f's{i}')
    e = model.new_int_var(0, horizon, f'e{i}')
    iv = model.new_interval_var(s, dur, e, f'iv{i}')
    intervals.append(iv)

model.add_no_overlap(intervals)  # 单机互斥

Cumulative 约束 处理可共享资源（如工人池、并行机器组）。它要求任意时刻，活跃任务的需求总和不超过容量上限：

demands = [2, 2, 3]  # 各任务资源需求
capacity = 4         # 资源池总容量
model.add_cumulative(intervals, demands, capacity)

经验法则：单机排他用 No-Overlap，资源池共享用 Cumulative。

典型调度模式的建模映射

单机调度与目标函数

单机场景下，不同优化目标导向完全不同的求解策略：

• 最小化 Makespan（完工时间）：model.minimize(max(end_times))，适用于压缩总工期
• 最小化总完工时间：model.minimize(sum(end_times))，CP-SAT 会自动发现 SPT（最短处理时间优先）规则
• 最小化加权延迟：引入延迟变量 tardiness[i] = max(0, end[i] - due_date[i])，适用于订单优先级场景

并行机调度（Parallel Machines）

当存在多台相同机器时，需要同时决策 "分配到哪台" 和 "何时执行"。标准做法是创建可选区间矩阵：

num_jobs, num_machines = 5, 2
presences = [[model.new_bool_var(f'p{j}_{m}') 
              for m in range(num_machines)] for j in range(num_jobs)]

for j in range(num_jobs):
    model.add_exactly_one(presences[j])  # 每个任务恰好分配一台机器

若机器同质，添加对称性破缺约束 model.add(starts[0] <= starts[1]) 可削减约一半的搜索空间。

作业车间（Job Shop）与资源约束项目调度（RCPSP）

作业车间的核心特征是每道工序有特定工艺路线。建模时需叠加两类约束：

1. 机器维度的 No-Overlap：同一机器上的工序互斥
2. 工序维度的 Precedence：同一工件内工序按工艺顺序执行

RCPSP 在此基础上引入 Cumulative 约束描述资源容量限制。关键路径（最长依赖链）给出 Makespan 下界，而资源约束可能迫使实际工期更长 —— 这正是 RCPSAT 求解器的优化空间。

高级建模：序列相关准备时间与 Circuit 约束

当换线时间依赖于前后工序组合（如颜色切换需清洗、模具更换），简单的 No-Overlap 不足以表达。此时需引入 Circuit 约束 将调度建模为哈密顿回路：

arcs = []
n = len(durations)

for i in range(n):
    # 虚拟节点 0 表示调度起点/终点
    arcs.append((0, i+1, model.new_bool_var(f'first_{i}')))
    arcs.append((i+1, 0, model.new_bool_var(f'last_{i}')))
    
    for j in range(n):
        if i != j:
            lit = model.new_bool_var(f'succ_{i}_{j}')
            arcs.append((i+1, j+1, lit))
            # 若选择弧 i→j，则强制准备时间
            model.add(starts[j] >= ends[i] + setup[i][j]).only_enforce_if(lit)

model.add_circuit(arcs)

Circuit 约束会生成 O (n²) 个布尔变量，当任务数超过 50 时求解时间急剧上升。此时建议先用贪心算法（如最近邻）生成初始解，通过 model.add_hint(var, value) 提供热启动。

性能调优的工程化参数

生产环境部署时，以下参数组合可显著提升求解效率：

对于需要流式获取中间解的场景，实现 CpSolverSolutionCallback 子类可在求解过程中捕获改进解：

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self, makespan_var):
        super().__init__()
        self._makespan = makespan_var
        
    def on_solution_callback(self):
        print(f"Found makespan: {self.value(self._makespan)}")

solver.solve(model, SolutionPrinter(makespan))

生产环境检查清单

• 整数域验证：CP-SAT 仅支持整数变量，浮点时长需先缩放（如 1.5 小时 → 90 分钟）
• Horizon 设置：过松的边界会膨胀搜索空间，建议用启发式算法预计算紧上界
• 可选任务处理：使用 only_enforce_if 条件约束，避免未调度任务污染目标函数
• 求解状态判断：区分 OPTIMAL（证明最优）与 FEASIBLE（可行解），后者在时限内可用
• 日志分析：开启 solver.parameters.log_search_progress = True 观察冲突传播效率

OR-Tools CP-SAT 将调度问题从算法实现层提升到约束声明层，使团队能快速实验不同业务规则。其底层结合了 CP 的约束传播与 SAT 的冲突驱动学习，在中小规模（数百任务）的排产、排班场景中已展现出工业级求解能力。

参考资料

• Google OR-Tools Scheduling Recipes: https://github.com/google/or-tools/blob/main/ortools/sat/docs/scheduling.md
• Scheduling with CP-SAT — A Practical Tutorial: https://nexmindai.org/cp-sat-tutorial/

systems