Google OR-Tools CP- SAT を用いた複雑なスケジューリング問題の解決

クラウドインフラストラクチャのメンテナンススケジューリングは、ハイリスクなバランス調整です。数十万台のゲストVMを提供するハイパーバイザホストを管理する際、単純な再起動はサーバーの再起動だけでなく、大規模なオーケストレーション課題です。顧客への影響を最小限に抑えるため、エンジニアは「3C」―― Capacity（移行先VMの利用可能な容量）、Concurrency（ネットワークおよびI/Oの制限）、Conflict（単一顧客のVMが同時に移行できる数に関するSLA制限）を考慮しなければなりません。

この種の組合せ最適化問題では、ソルバーの選択が数秒で解けるモデルと指数的な複雑性でクラッシュするモデルの違いを生むことがあります。従来は Mixed Integer Programming（MIP）が主流でしたが、Google の OR-Tools CP-SAT ソルバーはスケジューリングに特化した、より直感的で高性能なフレームワークを提供します。

スケジューリング課題：RCPSP

クラウドにおけるメンテナンススケジューリングは、本質的に Resource-Constrained Project Scheduling Problem（RCPSP） の変形です。標準的な RCPSP では、特定の期間とリソース要件を持つタスクがあり、リソース制限を超えないように総プロジェクト期間（メイクスパン）を最小化することが目標です。

クラウドメンテナンスの文脈では、各 VM 移行がタスクに相当します。リソースは利用可能なネットワーク帯域とホスト CPU です。目的は、3C を遵守しつつ、フリート全体の必要なメンテナンスを可能な限り短時間で完了させることです。

CP-SAT でのモデリング

CP-SAT は、時間の概念に直接マッピングできる特殊な変数と制約を導入するため、特に強力です。時間をバイナリフラグの列として扱う代わりに、CP-SAT は interval 変数 を使用します。

インターバル変数

インターバル変数は開始時刻、終了時刻、期間をひとまとめにします。これにより、ソルバーはタスクを離散的な点の集合ではなく、連続した時間ブロックとして扱うことができます。

# 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"
)

同時実行の管理

インターバルが定義されると、リソース制限の適用は以下の 2 つの主要制約を使うだけで簡単になります。

  1. AddNoOverlap：リスト内のタスクが重ならないことを保証します。単一スレッドのリソース（例：ホストあたり同時に 1 つの移行）に最適です。
  2. AddCumulative：特定の容量を持つリソースをモデル化します。例えば、ホストの総ネットワークスループットが 5 ユニットで、VM ごとに必要なスループットが異なる場合、AddCumulative は全アクティブな移行の合計が 5 を超えないようにします。
# Limiting total throughput across concurrent migrations
model.AddCumulative(vm_intervals, vm_throughputs, host_maximum_throughput)

CP-SAT と Mixed Integer Programming（MIP）の比較

多くの開発者は最初に MIP ソルバーでスケジューリング問題に取り組みます。しかし、MIP では通常、次の 2 つの定式化のいずれかが必要で、どちらも重大な欠点があります。

1. 時間インデックス形式

この手法は、可能なすべての時間ステップに対してバイナリ変数（例：active[task, time]）を作成します。直感的ではありますが、スケーラビリティが低いです。計画期間やタスク数が増えると変数数が指数的に増加し、実際の時間枠（例：分単位で測る 24 時間ウィンドウ）では問題が解けなくなることが多いです。

2. 時間連続形式

時間インデックスの爆発を回避するために、タスク A がタスク B の開始前に終了するかどうかを示すバイナリの「順序」変数を使用できます。大規模な時間枠では効率的ですが、数学的に扱いにくいです。MIP でスループットのような累積リソース制約を実装するには、複雑な「Big‑M」制約とタスクのペアごとの追加バイナリ変数が必要となり、記述・デバッグ・保守が困難なモデルになります。

実務上の考慮点とトレードオフ

CP-SAT は表現力が高いものの、万能ではありません。コミュニティの見解では、これらのソルバーを実装する際に考慮すべき重要な点がいくつか挙げられています。

スケーラビリティの限界

数百万のシャードを数万のタスクに割り当てるような極めて大規模な問題では、CP‑SAT でも遅くなることがあります。そのような場合、エンジニアは最適ではないが迅速に割り当てられる「手作り」ヒューリスティックへ移行する必要があります。

メタヒューリスティックの代替手段

Vehicle Routing Problem（VRP）などの特定の問題では、メタヒューリスティックソルバー（例：シミュレーテッド・アニーリングやタブーサーチ）が CP‑SAT を上回ることがあります。これらのソルバーは問題の正式な数式モデルを必要とせず、2 つの解のコスト関数だけで比較します。Timefold のようなツールは、最適解よりも速く「十分良い」解が必要な場合の代替手段としてしばしば言及されます。

「AI」誤解

興味深いことに、これらのソルバーを「AI」と呼ぶ傾向が高まっています。OR‑Tools は Google AI の下で提供されていますが、CP‑SAT は制約プログラミングと SAT ソルビングに基づく技術で、1960 年代に遡ります。LLM とは異なり、これらのソルバーはハード制約に基づく決定的な保証と最適解を提供し、「幻覚」が許容できないインフラストラクチャにとって不可欠です。

まとめ

ほとんどのスケジューリング問題において、CP‑SAT のインターバル変数と累積制約が提供する抽象化は MIP よりも優れた選択肢です。開発者の認知負荷を軽減し、時間ベースの制約に対して一般により高いパフォーマンスを提供します。さらに深く学びたい方には、Dr. Dominik Krupke の CP‑SAT Primer がソルバーの微妙な点を習得するための強く推奨されるリソースです。

Sources