使用 Google OR‑Tools CP‑SAT 解决复杂调度问题

为云基础设施安排维护是一项高风险的平衡工作。当管理为数十万虚拟机提供服务的 hypervisor 主机时，简单的重启不仅仅是服务器的重启——它是一项巨大的编排挑战。为了将客户中断降到最低，工程师必须在 “3C” 中进行权衡：容量（迁移虚拟机的可用空间）、并发（网络和 I/O 限制）以及 冲突（单个客户的虚拟机一次可迁移数量的 SLA 限制）。

对于此类组合优化问题，求解器的选择可能决定模型是几秒钟内求解成功，还是因指数级复杂度而崩溃。虽然混合整数规划（MIP）是传统的首选，但 Google 的 OR‑Tools CP‑SAT 求解器提供了更直观且性能更佳的框架，专门针对调度进行优化。

调度挑战：RCPSP

云中的维护调度本质上是 资源受限项目调度问题 (RCPSP) 的一种变体。在标准的 RCPSP 中，任务具有特定的持续时间和资源需求，目标是在不超出资源限制的前提下，最小化项目的总工期（即 makespan）。

在云维护的场景中，每一次虚拟机迁移都是一个任务。资源包括可用的网络带宽和主机 CPU。目标是在遵循 3C 的前提下，以最短时间完成整个集群的所有必要维护工作。

使用 CP‑SAT 建模

CP‑SAT 之所以特别强大，是因为它引入了专门的变量和约束，能够直接映射到时间的概念上。CP‑SAT 并不是将时间视为一系列二进制标记，而是使用 区间变量。

区间变量

区间变量封装了开始时间、结束时间和持续时间。这使得求解器能够将任务视为一个连续的时间块，而不是离散的时间点集合。

# Example: Creating an interval variable for a VM migration
start_var = model.new_int_var(0, planning_horizon, f"{vm}_start")
end_var = model.new_int_var(0, planning_horizon, f"{vm}_end")

vm_interval_var = model.new_interval_var(
    start=start_var, size=migration_duration, end=end_var, name=f"{vm}_interval"
)

管理并发

一旦定义了区间，使用两种主要约束来强制资源限制就变得直观简单：

  1. AddNoOverlap：确保列表中的任务不会相互重叠。它非常适用于单线程资源（例如，每台主机一次只能进行一次迁移）。
  2. AddCumulative：对具有特定容量的资源进行建模。例如，如果一台主机的总网络吞吐量为 5 单位，而不同的虚拟机需要不同的吞吐量，AddCumulative 能确保所有活跃迁移的总和永不超过 5。
# Limiting total throughput across concurrent migrations
model.AddCumulative(vm_intervals, vm_throughputs, host_maximum_throughput)

CP‑SAT 与混合整数规划 (MIP) 的对比

许多开发者最初会尝试使用 MIP 求解器来解决调度问题。然而，MIP 通常需要采用以下两种模型之一，而这两种模型都有显著的缺点：

1. 时间索引模型

这种方法为每一个可能的时间步（例如 active[task, time]）创建二进制变量。虽然直观，但可扩展性差。随着规划时域或任务数量的增加，变量数量呈指数增长，往往导致在实际时域（例如以分钟为单位的 24 小时窗口）下问题不可求解。

2. 连续时间模型

为避免时间索引的爆炸式增长，可以使用二进制的“顺序”变量来指示任务 A 是否在任务 B 开始之前完成。虽然在大时域下更高效，但在数学上相当繁琐。在 MIP 中实现累计资源约束（如吞吐量）需要复杂的 “Big‑M” 约束以及每对任务的额外二进制变量，导致模型难以编写、调试和维护。

实际考虑与权衡

虽然 CP‑SAT 表达能力很强，但并非万能。社区的见解指出了在实现这些求解器时需要注意的几个关键点：

可扩展性限制

对于极大规模的问题——例如将数百万个分片分配到数万任务——即使是 CP‑SAT 也可能变得过慢。在这种情况下，工程师可能需要转向“手工”启发式算法，以提供次优但及时的分配方案。

元启发式替代方案

对于某些问题，例如车辆路径问题（VRP），元启发式求解器（如模拟退火或禁忌搜索）可能优于 CP‑SAT。这类求解器不需要问题的正式数学模型，只需一个成本函数来比较两个不同的解。当需要比最优解更快的“足够好”解时，像 Timefold 这样的工具常被作为替代方案。

“AI” 误解

有趣的是，越来越多的人将这些求解器标记为 “AI”。虽然 OR‑Tools 隶属于 Google AI，但 CP‑SAT 基于约束编程和 SAT 求解——这些技术可以追溯到 1960 年代。与大语言模型不同，这些求解器提供基于硬约束的确定性保证和最优解，使其在“幻觉”不可接受的基础设施场景中不可或缺。

总结

对于大多数调度问题，CP‑SAT 的区间变量和累计约束所提供的抽象使其相较于 MIP 成为更优的选择。它降低了开发者的认知负担，并通常在基于时间的约束上提供更好的性能。想要深入学习的读者，可参考 Dominik Krupke 博士的 CP‑SAT Primer，这是掌握该求解器细节的强力资源。

Sources