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

# 使用 OR-Tools CP-SAT 解决调度问题 来源: https://atalaykutlay.com/or-tools-cp-sat-for-scheduling-problems.html 2026-05-12 我一直致力于改进 Akamai 云基础设施中的维护调度方式，特别是针对服务于数十万客户虚拟机（VM）的 Hypervisor 宿主机进行的破坏性维护。这个问题相当复杂，涉及多种相互竞争的限制条件，例如容量、客户干扰服务等级协议（SLA）以及跨主机、机架和数据中心并发性限制。 在原型开发解决方案时，我尝试了多种优化工具，包括商业和开源的混合整数规划（MIP）求解器。在探索了不同的选项后，我发现 Google 的 OR-Tools 库，特别是其 CP-SAT 求解器，非常适合解决调度问题。在本文中，我将演示 OR-Tools 中的一个简单调度模型，并解释为什么它适合这类问题。 ## 云基础设施中的维护调度 首先，让我解释一下我要解决的问题。云服务提供商管理称为“Hypervisor 宿主机”的物理服务器，这些服务器为客户运行虚拟机（VM）。这些主机需要定期维护以确保安全性和可靠性。其中一些维护任务可以通过无需重启的实时补丁来完成。处理实时补丁相对简单，主要挑战在于安全地部署更新。然而，有些维护任务需要重启主机。在重启之前，主机上的所有 VM 都需要迁移到其他主机。这一过程会对客户造成干扰，因此需要仔细的调度，以便在合理的时间范围内完成所有维护任务的同时，将影响降至最低。 为多个主机疏散以进行维护的过程涉及一个具有多个约束的复杂调度问题。主要挑战可以概括为“3C”： **容量（Capacity）**：疏散主机需要数据中心中有足够的备用容量来容纳迁移的 VM。 **并发性（Concurrency）**：迁移是资源密集型操作。它们消耗 CPU、磁盘 I/O 和网络带宽。为了不使主机或网络过载，只能同时执行有限数量的迁移。 **冲突（Conflict）**：客户在维护期间可以容忍一定程度的干扰，但计划内的维护不应造成过多的干扰。这意味着任何特定客户的 VM 在同一时间只能有少部分进行迁移。 考虑到这些挑战，调度问题的目标是找到维护任务的调度方案，在遵守这些约束的同时，最小化完成所有维护所需的总时间。 如果您对这个问题感兴趣，欢迎查看我在 SRECon26 上的演讲：以最小的客户干扰保持 Hypervisor 集群的最新状态 (https://www.usenix.org/conference/srecon26americas/presentation/kutlay) ## 如何建模问题 运筹学（OR）是一个成熟的领域，它使用算法和数学模型来解决复杂的决策问题。OR 研究人员几十年来一直致力于调度问题，并提出了各种“问题类型”，以捕捉不同调度挑战的本质。一些著名的问题类型包括作业车间调度、流水车间调度和资源受限项目调度。了解适合您调度问题的正确问题类型，有助于您利用针对该问题类型已开发的现有研究和算法。 云中的维护调度接近于没有前置约束的资源受限项目调度问题（RCPSP）。在 RCPSP 中，有一组需要调度的任务，每个任务都有自己的持续时间和资源需求。目标是找到一个调度方案，在遵守资源约束的同时，最小化项目的总体持续时间。类似地，在维护调度中，每个 VM 迁移可以被视为一个需要特定资源（见上述 3C）的任务，目标是 minimize 完成所有维护任务所需的总时间。 OR-Tools 是由 Google 开发的开源软件套件，提供了一组用于解决组合优化问题的工具。其关键组件之一是 CP-SAT 求解器，这是一种多功能的组合求解器，可以处理各种调度问题。对于任何给定的问题，CP-SAT 都会尝试一系列算法，并在它们之间共享信息。 CP-SAT 特别适合调度问题，因为它具有用于建模时间的专用变量和约束，这使得建模调度问题更加直观和高效。 让我用代码示例来说明这一点。首先，让我们为自己设置一个玩具问题，其中我们有一个需要维护的 Hypervisor 主机，并且有 3 个 VM 需要从中迁移出来。假设每次迁移需要 10 个时间单位，我们希望考虑可以在 100 个时间单位内完成的解决方案。 ```python hosts = ["host_1"] vms = {"host_1": ["vm_1", "vm_2", "vm_3"]} migration_duration = 10 planning_horizon = 100 ``` 问题的核心是在遵守与容量、并发性和冲突相关的约束的同时，调度这些 VM 的迁移。因此，我们需要建模这些迁移的时序以及它们消耗的资源。这正是 CP-SAT 的区间变量（interval variables）派上用场的地方。在 CP-SAT 中，您可以使用区间变量来表示具有开始时间、结束时间和持续时间的任务。让我们为每个 VM 迁移创建一个区间变量，并将它们保存在字典中，以便稍后轻松访问。 ```python vm_interval_vars = {} # 用于保存每个 VM 区间变量的字典 for host in hosts: vm_interval_vars[host] = {} for vm in vms[host]: start_var = model.new_int_var(0, planning_horizon, f"{vm}_start") end_var = model.new_int_var(0, planning_horizon, f"{vm}_end") migration_duration = 10 vm_interval_var = model.new_interval_var( start=start_var, size=migration_duration, end=end_var, name=f"{vm}_interval" ) vm_interval_vars[host][vm] = vm_interval_var ``` 执行上述代码将生成一个字典 `vm_interval_vars`，其中包含每个 VM 迁移的区间变量。每个区间变量都有一个开始时间、结束时间和固定的 10 个时间单位的持续时间。 ```python { 'host_1': { 'vm_1': vm_1_interval(start = vm_1_start, size = 10, end = vm_1_end), 'vm_2': vm_2_interval(start = vm_2_start, size = 10, end = vm_2_end), 'vm_3': vm_3_interval(start = vm_3_start, size = 10, end = vm_3_end) } } ``` 区间变量使得表达与并发性和资源使用相关的约束变得容易。例如，您可以使用 `AddNoOverlap` 约束来确保任何两个需要相同资源（如网络带宽）的迁移在时间上不重叠。 ```python for host, vms_dict in vm_interval_vars.items(): vm_intervals = list(vms_dict.values()) model.AddNoOverlap(vm_intervals) ``` 或者更好的是，您可以使用 `AddCumulative` 约束来建模有限的资源容量，并确保在任何给定时间的总资源使用量不超过可用容量。下面的约束限制了可以同时进行的迁移数量。为了匹配上面的 `AddNoOverlap` 约束，我们可以将最大并发迁移数设置为 1： ```python maximum_migrations_per_host = 1 for host, vms_dict in vm_interval_vars.items(): vm_intervals = list(vms_dict.values()) model.AddCumulative( vm_intervals, # 区间变量列表 [1] * len(vm_intervals), # 每个区间变量的资源使用量 maximum_migrations_per_host # 最大资源容量 ) ``` `AddCumulative` 的第二个参数是每个区间变量的资源使用量列表，在这种情况下，每次迁移仅为 1，因为每次迁移消耗一单位资源。`AddCumulative` 更强大的用法是为不同的迁移分配不同的资源使用量，这对于建模真实约束（如吞吐量）更有用。如果某些 VM 可以以比其它 VM 更高的吞吐量进行迁移，那么您可以限制任何给定时间的总吞吐量，而不是限制并发迁移的数量： ```python migration_throughput = {"vm_1": 5, "vm_2": 3, "vm_3": 2} host_maximum_throughput = 5 for host, vms_dict in vm_interval_vars.items(): vm_intervals = list(vms_dict.values()) vm_throughputs = [migration_throughput[vm] for vm in vms_dict.keys()] model.AddCumulative(vm_intervals, vm_throughputs, host_maximum_throughput) ``` 由于最大吞吐量为 5，我们预计调度方案将同时迁移 VM 2 和 VM 3，但不会将 VM 1 与其他任何 VM 一起迁移，因为仅 VM 1 就消耗了所有可用吞吐量。 此时，我们有了一个微小的模型，它捕捉了维护调度问题的一个方面，即并发约束。让我们求解这个模型，看看解决方案是什么样子的： ```python solver = cp_model.CpSolver() status = solver.Solve(model) print(status) # 打印调度方案 if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: for host, vms_dict in vm_interval_vars.items(): print(f"Schedule for {host}:") for vm, interval_var in vms_dict.items(): start = solver.Value(interval_var.StartExpr()) end = solver.Value(interval_var.EndExpr()) print(f" {vm}: Start at {start}, end at {end}") else: print("No solution found.") ``` 该解决方案打印了每个 VM 迁移的开始和结束时间，从而为您提供一个遵守并发约束的调度方案。 ```text CpSolverStatus.OPTIMAL Schedule for host_1: vm_1: Start at 10, end at 20 vm_2: Start at 0, end at 10 vm_3: Start at 0, end at 10 ``` 正如预期的那样，我们看到 VM 2 和 VM 3 同时迁移，而 VM 1 单独迁移，以遵守最大吞吐量约束。 要理解为什么 OR-Tools 是一个很好的选择，了解替代方案很有帮助。解决调度问题的另一种常见技术是混合整数规划（MIP）。市面上有很多开源 MIP 求解器，但没有任何一种能像 OR-Tools 那样提供自然的工具来建模时间和调度约束。 使用 MIP 解决此调度问题有两种方法：基于时间索引的公式和时间连续的公式。基于时间索引的公式很直观，但随着任务数量和规划范围的增加，其扩展性不佳。时间连续的公式更高效，但不那么直观，并且需要大量工作才能正确实现。 ### “简单”的 MIP 方法：基于时间索引的公式 使用 MIP 实现调度问题的简单方法是使用基于时间索引的公式，其中创建二进制变量以指示任务在特定时间是否处于活动状态。例如，您可以创建一个二进制变量 `active[i, t]`，如果任务 `i` 在时间 `t` 处于活动状态，则为 1，否则为 0。然后，您可以添加约束以确保任何给定时间的总资源使用量不超过可用容量。 为了演示一个小例子，我将使用 Pyomo 以基于时间索引的公式建模上述相同的问题。 首先，让我们定义集合和变量。与上面类似，我们需要每个 VM 开始时间的变量。此外，我们还需要一个二进制变量来指示 VM 在时间 `t` 是否正在迁移。 ```python model = pyo.ConcreteModel() # 集合 model.VMS = pyo.Set(initialize=vms["host_1"]) model.TIME = pyo.RangeSet(0, planning_horizon) # 变量 # 每次 VM 迁移的开始时间 model.start = pyo.Var( model.VMS, domain=pyo.NonNegativeIntegers, bounds=(0, planning_horizon) ) # 二进制变量：VM 在时间 t 是否在迁移？ model.vm_active = pyo.Var(model.VMS, model.TIME, domain=pyo.Binary) # 目标：最小化完工时间（最后一次迁移的完成时间） model.makespan = pyo.Var(domain=pyo.NonNegativeReals, bounds=(0, planning_horizon)) model.obj = pyo.Objective(expr=model.makespan, sense=pyo.minimize) ``` 然而，这种方法可能导致大量的变量和约束，特别是如果规划范围很长或有很多任务的话。这会使模型难以求解，并且可能无法良好扩展。 下图显示了随着 VM 数量和规划范围的增加，基于时间索引的公式的求解时间如何增长。如您所见，求解时间呈指数增长，这使得它对于较大问题来说不切实际。 显示基于时间索引公式求解时间指数增长的图表 ### MIP 的时间连续公式 表述相同问题的另一种方法是时间连续公式。与其跟踪任务在每个离散时间步长中是否处于活动状态，不如完全删除时间索引，并在任务对之间引入二进制**排序**变量。提出这种公式并不简单，而且不如 CP-SAT 公式直观，但对于具有大规划范围的小问题，它可能更高效。 核心思想是这样的：对于共享资源的任意两个任务 `i` 和 `j`，必须恰好有一个先完成。我们用二进制变量 `y[i, j]` 对此进行编码，如果任务 `i` 在任务 `j` 开始之前完成，则等于 1。 ```python model = pyo.ConcreteModel() M = planning_horizon # Big-M 常数 model.VMS = pyo.Set(initialize=vms["host_1"]) model.VM_PAIRS = pyo.Set(initialize=[ (i, j) for i in vms["host_1"] for j in vms["host_1"] if i != j ]) # 每次 VM 迁移的开始时间 model.start = pyo.Var(model.VMS, domain=pyo.NonNegativeIntegers, bounds=(0, planning_horizon)) # 排序变量：y[i,j] = 1 表示任务 i 在任务 j 开始前完成 model.y = pyo.Var(model.VM_PAIRS, domain=pyo.Binary) # 完工时间 model.makespan = pyo.Var(domain=pyo.NonNegativeReals, bounds=(0, planning_horizon)) model.obj = pyo.Objective(expr=model.makespan, sense=pyo.minimize) ``` 对于无重叠约束（相当于 CP-SAT 中的 `AddNoOverlap`），我们需要两件事：一个在 `y[i,j] = 1` 时强制排序的约束，以及一个确保每对之间恰好选择一个排序的约束： ```python # 如果 i 在 j 之前 (y[i,j]=1)，则 j 必须在 i 结束后开始 model.precedence = pyo.Constraint( model.VM_PAIRS, rule=lambda model, i, j: model.start[j] >= model.start[i] + migration_duration - M * (1 - model.y[i, j]) ) # 必须恰好满足一个排序 model.one_ordering = pyo.Constraint( model.VM_PAIRS, rule=lambda model, i, j: model.y[i, j] + model.y[j, i] == 1 ) # 完工时间必须 >= 所有结束时间 model.makespan_constraint = pyo.Constraint( model.VMS, rule=lambda model, i: model.makespan >= model.start[i] + migration_duration ) ``` 变量数量现在是 VM 数量的 $O(n^2)$。如果问题的 VM 数量较少且规划范围较长，这可能比基于时间索引公式的 $O(n \times T)$ 有显著改进。例如，对于 1440 分钟（一天）的规划范围，基于时间索引的模型每个任务创建多 1440 倍的变量，这会迅速压倒求解器。 然而，为了在 CP-SAT 中实现 `AddCumulative` 约束，我们需要更复杂的约束。挑战在于，在每个任务 `i` 的开始时间，您需要确保所有并发任务的总吞吐量不超过主机的限制。 “当任务 `i` 开始时任务 `j` 处于活动状态”本身是一个复合条件（`start[j] <= start[i]` **且** `start[i] < start[j] + duration[j]`），线性化它需要每对再加上另一个二进制变量以及每对再加两个 Big-M 约束。这很快就变得笨拙且难以理解。我无法...