CP-SATは制約プログラミングとSATを組み合わせた無償ソルバー
OR-Toolsは、Googleが公開しているオープンソースの最適化ツール群です。その中のCP-SATは、制約プログラミング（CP）と、論理式の充足可能性を解くSAT技術を組み合わせたソルバーで、スケジューリングのように「区間（作業の開始と終了）」と「重なってはいけない」という制約が多い問題に強い特徴があります。
VU Amsterdamの研究者が開発したスケジューリング用ライブラリPyJobShopの論文（arXiv 2502.13483）では、CP-SATと商用のIBM ILOG CP Optimizerを9,000以上のインスタンスで比べています。
最適性ギャップとは、得られた解が理論上の最適解からどれだけ離れているかの目安です。ジョブショップ問題では、無償のCP-SATが商用ソルバーと同等以上の水準にあることを示しています。ただし問題の種類によって結果は変わり、すべての問題でCP-SATが優位というわけではありません。
解ける規模を左右する要因
「何ジョブまでなら解ける」と一律には言えません。計算時間は、ジョブ数だけでなく、次の要因で大きく変わります。
| 要因 | 計算時間への影響 | 対処 |
|---|---|---|
| ジョブ数×工程数×設備数 | 増えるほど探索空間が急増 | 期間・工程で分割 |
| 計画期間の長さと時間刻み | 長く細かいほど重い | 刻みを粗くする（分→15分） |
| 順序依存の段取り | 品目の組み合わせで制約が増える | 品目をグループ化して段取りを近似 |
| 代替設備の数 | 選択肢が増えるほど重い | 主設備・代替設備に優先度を付ける |
| 人員・治具など副資源 | 資源制約が増えるほど重い | 本当に制約になる資源だけ入れる |
| 多目的（納期・段取り・平準化） | 重み付けの調整が要る | 優先順位をつけて段階的に最適化 |
実務上の判断は、「計画に許される計算時間内に、現行計画より良い解が出るか」です。夜間バッチで数時間使えるなら、かなり大きな問題も扱えます。日中の再計画で数分しか使えないなら、規模を絞る必要があります。CP-SATは時間制限を設定でき、その時点の最良解を返すので、最適解に届かなくても実用解として使えます。
解けない規模の問題を分割する
- 階層分割：まず「どの日にどの品目を作るか」を粗く決め、次に「日内の順序」を詳細に決める。上位の問題は時間刻みを粗くできるので軽くなる
- 期間分割（ローリング）：直近1週間だけを詳細に最適化し、それ以降は粗い計画にとどめ、毎日ずらして解き直す
- 工程分割：ボトルネック工程の順序を先に最適化し、前後の工程はそれに合わせて割り付ける
分割すると全体最適からは離れますが、現場の計画業務も実際にはこのように階層的に行われているため、運用上の違和感は小さいことが多いです。
制約をどう書くか：区間変数の考え方
CP-SATでスケジューリングを書くときの中心は「区間変数」です。各作業を、開始時刻・所要時間・終了時刻を持つ区間として表し、次のような制約を加えます。
| 現場の制約 | CP-SATでの表現 |
|---|---|
| 1台の設備で同時に1作業 | 同じ設備の区間が重ならない（NoOverlap） |
| 工程の順序 | 前工程の区間の終了 ≦ 後工程の区間の開始 |
| 代替設備のどれか1台で加工 | 設備ごとの任意区間を作り、どれか1つだけ有効にする |
| 人員・治具の数 | 同時に使う量の合計が上限以下（Cumulative） |
| 段取り時間 | 区間の間に遷移時間を入れる |
| 設備の計画停止 | 停止時間帯を固定の区間として置く |
| 納期 | 終了時刻と納期の差を遅れとして目的関数に入れる |
PyJobShopのようなライブラリは、こうした典型的な制約を部品として提供しており、ゼロから書くより短期間でモデルを作れます。とはいえ、どの制約を入れ、どれを省略するかの判断は、問題を理解した人にしかできません。
実装で詰まりやすい点
最適化ソルバーを使う場合、プログラムを書くこと自体より、制約を正しく定式化することのほうが難しい作業です。「この設備は午前中に高温品を流さない」といった現場のルールを、すべて式に書き下す必要があります。暗黙ルールの扱いは熟練計画者の暗黙ルールをモデル化する、入力データは生産計画AIに必要なマスタ7種を参照してください。
よくある質問
CP-SATとMIP（混合整数計画）はどちらを使うべきですか？
作業の順序や重なりの制約が中心のスケジューリングにはCP系が向き、数量の配分やロットサイズの決定が中心の問題にはMIPが向くことが多いです。問題に応じて使い分けるか、両方試して比べます。
Pythonが書ける人がいれば内製できますか？
簡単な問題なら可能ですが、現場の制約を正しく定式化し、計算時間を管理し、計画担当者が使える画面を作るまでを考えると、最適化の経験者か外部の支援があるほうが安全です。
この記事を書いた人
DELMIA Apriso を中核とした MES / 製造DX の導入・運用・人材育成と、製造業向けAIの調査・開発・教育を手がけるITコンサルティング企業。ISO 9001:2015 / ISO 27001:2022 認証取得。 日本・中国・米国で製造業のMES・データ基盤・AI導入を手がけた実務者が、欧米・中国の一次情報にあたって書いています。
