使用 OR-Tools CP-SAT 解决调度问题

2026-05-12 使用 OR-Tools CP-SAT 解决计划问题 我一直致力于改进 Akamai 云基础设施中的维护计划，特别是对为数十万来宾虚拟机提供服务的虚拟机管理程序主机进行中断性维护。这个问题相当复杂，存在容量、客户中断 SLA 以及主机、机架和数据中心之间的并发限制等相互竞争的限制。在制作解决方案原型时，我尝试了多种优化工具，包括商业和开源 MIP 求解器。在探索了不同的选项之后，我发现 Google 的 OR-Tools 库，特别是它的 CP-SAT 求解器，非常适合解决调度问题。在这篇文章中，我将介绍 OR-Tools 中的一个简单的调度模型，并解释为什么它能够很好地解决此类问题。云基础设施中的维护计划首先，让我解释一下我想要解决的问题。云提供商管理称为“虚拟机管理程序主机”的物理服务器，这些服务器为客户运行虚拟机 (VM)。这些主机需要定期维护以确保安全性和可靠性。其中一些维护任务可以使用实时补丁来完成，无需重新启动。处理实时补丁相对简单，主要挑战是安全地推出更新。但是，某些维护任务需要重新启动主机。主机重启前，需要将主机上的所有虚拟机迁移到其他主机上。此过程会对客户造成干扰，因此需要仔细安排，以尽量减少影响，同时仍确保所有维护任务在合理的时间范围内完成。疏散多台主机进行维护的过程涉及一个复杂的调度问题，并受到多种限制。主要挑战可概括为“3C”： 容量：撤离主机需要数据中心的备用容量来容纳迁移的虚拟机。并发：迁移是资源密集型操作。它们使用 CPU、磁盘 I/O 和网络带宽。在不使主机或网络超载的情况下，只能同时执行有限数量的迁移。冲突：客户可以容忍维护期间一定程度的中断，但计划内维护不应造成太多中断。这意味着任何给定客户的虚拟机中只能同时迁移一小部分。考虑到这些挑战，调度问题的目标是找到维护任务的调度表，在尊重这些约束的同时最大限度地减少完成所有维护的总时间。如果您对此问题感兴趣，请随时查看我的 SRECon26 演示：以最小的客户干扰保持虚拟机管理程序队列最新如何对问题进行建模 运筹学 (OR) 是一个成熟的领域，它使用算法和数学模型来解决复杂的决策问题。 OR 研究人员几十年来一直致力于研究调度问题，他们提出了各种“问题类型”，捕捉了不同调度挑战的本质。一些众所周知的问题类型包括作业车间调度、流水作业调度和资源受限项目调度。了解适合您的调度问题的问题类型有助于您利用已为其开发的现有研究和算法。云中的维护调度接近于没有优先级约束的资源受限项目调度问题（RCPSP）。在 RCPSP 中，您有一组需要计划的任务，每个任务都有自己的持续时间和资源要求。目标是找到一个时间表，在尊重资源限制的同时最大限度地缩短整个项目的持续时间。同样，在维护调度中，每个虚拟机迁移都可以看作是一个需要一定资源的任务（参见上面的3C），目标是最小化完成所有维护任务所需的总时间。使用 OR-Tools 进行问题建模 CP-SAT Solver OR-Tools 是 Google 开发的开源软件套件，提供了解决组合优化问题的工具集合。其关键组件之一是 CP-SAT 求解器，它是一种多功能组合求解器，可以处理各种调度问题。对于任何给定的问题，CP-SAT 都会尝试一系列算法并在它们之间共享信息。 CP-SAT 特别适合调度问题，因为它具有专门的建模时间变量和约束，这使得建模调度问题更加直观和高效。让我举一些代码示例来说明这一点。首先，让我们为自己设置一个玩具问题，其中我们有一个需要维护的虚拟机管理程序主机，并且有 3 个虚拟机需要从中迁移。假设每次迁移需要 10 个时间单位，并且我们希望考虑可以在 100 个时间单位内完成的解决方案。主机= [“host_1”] vms = {“host_1”：[“vm_1”，“vm_2”，“vm_3”]}迁移持续时间= 10 p