使用 Google OR-Tools CP-SAT 解決複雜排程問題

排程雲端基礎設施的維護是一項高風險的平衡工作。當管理服務數十萬個客戶虛擬機的虛擬機監控主機時，簡單的重新啟動不僅僅是伺服器重啟——它是一個巨大的協調挑戰。為了將客戶中斷降至最低，工程師必須在「3C」之間取得平衡：Capacity（可供遷移虛擬機的可用空間）、Concurrency（網路與 I/O 限制）以及Conflict（單一客戶的虛擬機同時遷移數量的 SLA 限制）。

對於此類組合優化問題，求解器的選擇可能決定模型是能在數秒內求解，還是因指數複雜度而崩潰。雖然混合整數規劃（MIP）是傳統的首選，Google 的 OR-Tools CP-SAT 求解器則提供更直觀且效能更佳的框架，專門針對排程而設計。

排程挑戰：RCPSP

雲端的維護排程本質上是 Resource-Constrained Project Scheduling Problem (RCPSP) 的變體。在標準的 RCPSP 中，您有具有特定持續時間與資源需求的任務，目標是最小化整體專案持續時間（即完工時間），同時不超過資源上限。

在雲端維護的情境下，每一次虛擬機遷移即為一個任務。資源則是可用的網路頻寬與主機 CPU。目標是在遵守 3C 的前提下，以最短時間完成整個 fleet 所需的所有維護工作。

使用 CP-SAT 建模

CP-SAT 特別強大，因為它引入了專門的變數與約束，直接對應時間概念。CP-SAT 不再將時間視為一系列二元旗標，而是使用 interval variables。

區間變數

區間變數封裝了開始時間、結束時間與持續時間。這使得求解器能將任務視為連續的時間區塊，而非離散的時間點集合。

# 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 成為更佳的選擇。它減輕了開發者的認知負擔，且通常在時間相關約束上提供更佳效能。想深入了解的讀者，可參考 Dr. Dominik Krupke 所著的 CP‑SAT Primer，這是掌握求解器細節的高度推薦資源。

Sources