第9章計画エンジン

計画とは「依存関係」を整理すること

黒板の前の口論は、実は答えの出せる問題です。必要なのは、作業ごとの日数と、作業同士の前後関係だけ。これを図にすると、第1章で崩壊の連鎖を読んだときと同じ依存グラフになります。

点（ノード）が作業、矢印が「左が終わらないと右を始められない」という関係です。第5章の技術ツリーが「何を作れるようになるか」の地図だったとすれば、こちらは「今月、誰が何をするか」の地図です。

flowchart TD
  S[断熱調査 3日] --> M[断熱材の回収 8日]
  M --> I[断熱工事 10日]
  S --> ST[ストーブ設置 6日]
  ST --> CO[CO警報器 2日]
  S --> P[水タンク凍結対策 7日]
  S --> B[蓄電池の保温箱 4日]
  H[収穫 14日] --> F[保存食 10日]
  W[薪集め 12日] --> MV[冬季居住区へ移動 3日]
  I --> MV
  CO --> MV
  F --> MV
  P --> MV
  B --> MV

このグラフには大事な性質があります。矢印をどうたどっても、元の場所に戻ってこない。こういうグラフを有向非巡回グラフ（DAG）と呼びます。DAGであれば、必ず「前提を守った順番」が少なくとも一つ存在します。

順番を決める：トポロジカルソート

前提を守った並べ方を求める操作をトポロジカルソートといいます。代表的な方法のひとつが、1962年にアーサー・カーン（Arthur B. Kahn）が学術誌 Communications of the ACM に発表したアルゴリズムです。考え方は、黒板の前でも実行できるほど単純です。

1. 各作業について「まだ終わっていない前提の数」を数える。
2. 前提の数がゼロの作業（すぐ着手できる作業）を「着手可能リスト」に入れる。
3. リストから一つ取り出して順番に加え、それを前提にしていた作業の数を1減らす。ゼロになったらリストに入れる。
4. リストが空になるまで繰り返す。

未完了の前提数 = 各作業の前提の数
着手可能 = [前提数が0の作業]
順番 = []
while 着手可能が空でない:
    a = 着手可能から1つ取り出す
    順番に a を加える
    for b in (a を前提にしている作業):
        b の前提数 -= 1
        if b の前提数 == 0: 着手可能に b を加える
if 順番の長さ < 作業の数:
    循環依存がある（どこかで堂々巡りしている）

計算量は作業の数と矢印の数の合計に比例します（O(V+E)）。数千の作業でも、アカリのような小さな計算機で一瞬です。

最後の2行に注目してください。もし「AにはBが先、BにはAが先」という循環依存があると、どちらも前提数がゼロにならず、リストが途中で空になります。つまりこのアルゴリズムは、計画が論理的に不可能なことも検出してくれるのです。

どこが遅れると全体が遅れるか：クリティカルパス

順番がわかっても、「何日で終わるか」はまだわかりません。人手が無限にあって、着手できる作業をすべて同時に進められるとしましょう。それでも全体は、依存の連なりの中で日数の合計がいちばん長い道筋より早くは終わりません。この道筋をクリティカルパスと呼びます。

図9-1では、収穫（14日）→ 保存食（10日）→ 移動（3日）の27日がクリティカルパスです。断熱の道筋（調査3＋回収8＋工事10＋移動3＝24日）は、3日の余裕（フロート）を持っています。

• クリティカルパス上の作業が1日遅れれば、全体が1日遅れる。
• フロートのある作業は、その日数までは遅れても全体に影響しない。

この考え方は、1950年代後半にデュポン社のモーガン・ウォーカーとレミントン・ランド社のジェームズ・ケリーが開発したクリティカルパス法（CPM）として体系化されました。ほぼ同じ時期に、米海軍とブーズ・アレン・ハミルトンがPERTという手法を作っており、二つは今もよく組み合わせて使われます。

人手が足りないとき：優先度つきの割り当て

現実には人手に限りがあります。2チームしかいなければ、着手可能な作業が4つあっても、同時に進められるのは2つだけです。このとき、どの作業から手をつけるかで、終わる日が変わります。

アカリが使っているのは、リスト・スケジューリングと呼ばれる単純な方法です。着手可能な作業のうち、「そこから最後までの残りの道のりがいちばん長いもの」を優先して、空いたチームに割り当てます。クリティカルパスに近い作業ほど先に始める、という発想です。必ず最適な答えを出す方法ではありませんが、速くて、なぜその順番なのかを人に説明できます。

表の最後の2行を見比べてください。3チームから6チームへ人手を倍にしても、2日しか縮みません。27日というクリティカルパスの壁より早くは、何人いても終われないからです。人を足すなら、クリティカルパスが詰まっている間だけ。これが、限られた人手で計画を立てるときのいちばん大事な直感です。

外れ方を設計する：再計画

レイのノートの「計画は外れる」は、悲観ではなく工学的な前提です。雨が降れば断熱材の回収は遅れるし、収穫は天気しだいです。プランナーで試すと、3チームの場合でも次のように変わります。

• 雨で断熱材の回収が6日延びる → 全体は31日目に。断熱の道筋がクリティカルパスに入れ替わる。
• 収穫が5日遅れる → 全体は32日目に。食料の道筋がさらに伸びる。

大事なのは、遅れが起きたときにクリティカルパスが入れ替わることです。昨日まで余裕のあった作業が、今日から最優先になるかもしれない。だから計画は一度立てて終わりではなく、次のループで回します。

1. 毎朝、各作業の進み具合と残り日数を更新する。
2. 依存グラフで計算し直し、クリティカルパスと各作業の余裕を出す。
3. クリティカルパスが変わったら、人手の配置を変える。
4. 締め切りを越えそうなら、早めに知らせる。作業を削る、外から人を借りる、締め切りそのものを疑う。

人間の頭でこれを毎朝やるのは大変ですが、計算機には得意な仕事です。アカリの役目は計画を当てることではなく、外れたときにすぐ計算し直して、どこに手を打てばいいかを示すことです。

循環依存が見つかったら

プランナーで「循環依存を入れる」を押すと、「ストーブ設置には断熱工事が先」「断熱工事には（作業場を暖める）ストーブが先」という二つの条件が同時に入ります。Kahnのアルゴリズムは途中で止まり、どの作業も始められなくなります。

こうなったら、計算では解決できません。人間がどちらかの依存を切る必要があります。たとえば「仮設の暖房で断熱工事を先に進める」。循環は、計画の間違いというより前提の思い込みであることが多く、それを見つけてくれるだけでも計算には価値があります。