メタヒューリスティクスと
生産計画スケジューリング
金曜の夜、駅前の小さなラーメン屋。カウンター8席、厨房は店主ひとり。 土曜のランチに「予約だけ」で 30 人。 お客さんを どの順番で呼び、どの注文を先に作るか で、最後の人の食べ終わりが 14時になるか、16時になるかが決まる。
店主の頭の中では、毎週この計算が走っている。 本書はその計算の話だ。
この本でやること
「順番を決める」「割り当てを決める」「経路を決める」 —— こういう問題を 組合せ最適化 と呼ぶ。 意外なほど、世界はこれで動いている。
- 工場のジョブをどの機械でいつ流すか
- 配達トラックがどの順で店を回るか
- シフトを誰にどう割り当てるか
- クラウドのコンテナをどのサーバに置くか
- パズル、スケジュール、ナップサックに何を詰めるか
全部「並べ替えの問題」だ。そして全部、まじめにやると 宇宙が終わるまで計算しても答えが出ない くらい難しい。
じゃあ人類はどうしているのか? 「そこそこ良い答えを、現実的な時間で出す」工夫が、半世紀かけて積み上がっている。 それが本書の主役、 メタヒューリスティクス だ。
この本の物語の流れ
本書は 1冊の長い物語 として読めるようにした。 最初に「順番なんてカンタンじゃん？」というところからスタートして、 痛い目に遭いながら強力な道具を一つずつ手に入れていく構成だ。
| 章 | たどり着く理解 |
|---|---|
| 第1章 | 「えっ、こんな単純な問題が解けないの?」と組合せ爆発を体感する |
| 第2章 | 「とりあえず一番安いやつから」= 貪欲法 を試して、どこまで通用するかを見る |
| 第3章 | 「ちょっと入れ替えてみる」= 局所探索 。そして局所最適という壁にぶつかる |
| 第4章 | 壁を乗り越える 5 つの戦略 (SA / Tabu / ILS / VNS / GRASP) |
| 第5章 | もっと豪快に壊して作り直す LNS / ALNS 。現代の主役 |
| 第6章 | 厳密に解くという反対側の世界 (MIP / CP-SAT)。両者を混ぜると最強 |
| 第7章 | 生産スケジューリングの語彙 (α|β|γ, JSP, FJSP)。地図を読めるようになる |
| 第8章 | 現実の工場は教科書とどう違うのか。Rolling Horizon の運用 |
| 第9章 | 本番に投入する設計と落とし穴 |
三つの「合言葉」
この本を読むときに、頭の片隅に置いておくと迷子にならない合言葉が三つある。
① 「そもそも何の問題?」
アルゴリズムの名前を覚える前に、 状態 と 操作 を絵に描けるかを問う。 ここをサボると、どんな道具を使っても刺さらない。
② 「攻めるか、守るか」
今ある良さそうな解を磨く (活用) のか、まだ見ぬ領域に飛ぶ (探索) のか。 すべてのメタヒューリスティクスは、このバランスを取る工夫だ。
③ 「ベンチマークで勝つ ≠ 現場で動く」
論文のチャンピオンアルゴリズムが、実工場で動くとは限らない。 むしろ現場では、説明できない解は使ってもらえない。これを第III部で扱う。
こんな人向け
- 業務で「スケジューリング」「割当て」「配送計画」をやるハメになった人
- OR-Tools とか触ったが、中で何が起きているか 気持ち悪い 人
- ML で全部解けると思っていたが、組合せ最適化に出会って戸惑っている人
- APS パッケージを評価・導入するけど、設計判断の軸がほしい人
逆に、「組合せ最適化の理論の最先端」を求めている研究者向けではない。 本書は 実務でこの分野を使う人 のための、なるべく腑に落ちる入門書として書いた。
前提知識
Python の擬似コードが読めれば OK。数学は高校レベル + 計算量の O(n²) くらいの感覚があれば十分。
たまに出てくる数式は、出てきたところで言葉で補足する。
本の中で使う「目印」
落とし穴 ハマりやすい罠。実装時の注意。
実務メモ 本番に投入するときの経験則。
さあ、はじめよう
最初の第1章では、冒頭のラーメン屋のような 小さな問題 が、なぜそんなに難しいのかを見る。 たぶん想像より遥かに難しい。そこから本当の旅が始まる。