現場の声をモデルにする — 翻訳問題が本丸

8章までで道具は揃っている。CP-SAT もある、ALNS もある、Rolling Horizon もある。
だがこの5つを残らずモデルに入れられるかが、本物の現場では勝負を決める。

この章は、その翻訳カタログだ。

9.1 アルゴリズムは揃った。残ったのは翻訳問題

第7章までで見てきた通り、メタヒューリスティクスの主要流派は1980〜2000年代でほぼ出揃った。CP-SAT のような厳密ソルバーも、Gurobi 級の MIP も、手が届く道具になった。LNS × CP-SAT という現代の王道アーキテクチャ (第7章 / 9章の hybrid_lns) を組めば、教科書 JSP を現代の現場規模で叩ける。

ところが APS パッケージ導入の9割は失敗する (第8章)。原因はアルゴリズムではない。

そして翻訳には型がある。これから5つを順に見ていく。

9.2 要件は3層に分ける — hard / soft / preference

翻訳の前に、要件を3つに仕分ける癖をつけたい。これを混ぜると LNS の近傍設計が破綻する。

致命的アンチパターン

preference をハード制約にしてしまうと、ちょっとした故障で INFEASIBLE が出て計画が止まる。
逆に hard を soft にすると、ソルバーが「払えるなら払う」とコストで違反してくる (例: 安全規制違反)。
3層の仕分けが、本番運用の最初の一歩。

LNS × CP-SAT の世界では、この3層が役割分担にも対応する:

• hard は CP-SAT が常に守る。LNS の destroy で壊しても、repair で必ず復元される。
• soft は CP-SAT の目的関数項。LNS の destroy で「悪化している領域」を狙い撃ちにする手がかりになる。
• preference は LNS の neighborhood の偏りで誘導する (= ソルバーには弱く伝える)。

9.3 翻訳カタログ — 5つの典型要件

ここからが本論。冒頭の5要望を、順にモデルに落とす。

① 注文の優先順 — 「他より先に」

第一手: 辞書順最適化

業務の優先順位がそのまま数式になる、最も説明しやすい型。

# 1段目: 総遅れを最小化
model.Minimize(sum(tardiness[j] for j in jobs))
solver.Solve(model)
tard_best = solver.ObjectiveValue()

# 2段目: 総遅れを上限に固定して、makespan を最小化
model.Add(sum(tardiness[j] for j in jobs) <= int(tard_best))
model.Minimize(makespan)
solver.Solve(model)

第二手: 重み付き目的関数

「A 社は他の10倍重い」を w_j で表す。辞書順より柔軟だが、重みの校正が難しい。

model.Minimize(sum(weight[j] * tardiness[j] for j in jobs))

LNS との接続

注文 j の destroy 優先度を w_j · tardiness[j] でランキングすると、悪化に効いているジョブから抜けてくれる。

def priority_aware_removal(state, rng, frac=0.2):
    scored = [(j, weight[j] * state.tardiness(j)) for j in state.jobs]
    scored.sort(key=lambda x: -x[1])
    k = int(len(scored) * frac)
    targets = [j for j, _ in scored[:k * 2]]
    return state.remove(rng.choice(targets, size=k, replace=False))

② 工程をまとめたい — 「赤と白を交互に流さないで」

これは 段取り時間 (Sequence-Dependent Setup Time, SDST) として翻訳するのが王道。色の切替に30分かかるなら、それをそのままモデルに入れる。

CP-SAT 上の置き方: AddCircuit

機械 m 上のジョブ列を 巡回路 として表現する (ダミー始点/終点を入れる)。エッジ (i, j) を選ぶと、i の後に j を流す = 切替コスト setup[i][j] を払う。

# 各機械 m について
arcs = []
for i in jobs_on(m):
    arcs.append((SRC, i, lit_start[i]))
    arcs.append((i, SINK, lit_end[i]))
    for j in jobs_on(m):
        if i == j: continue
        arcs.append((i, j, lit_next[i][j]))
        # i の end + setup[i][j] <= j の start
        model.Add(end[i] + setup[i][j] <= start[j]).OnlyEnforceIf(lit_next[i][j])

model.AddCircuit(arcs)
total_setup = sum(setup[i][j] * lit_next[i][j] for i in ... for j in ...)
model.Minimize(makespan + 0.1 * total_setup)

setup[赤][白] = 30、setup[赤][赤] = 0 と置くと、ソルバーは自発的に同色をまとめる。明示的に「まとめろ」と命令しなくていい。これが状態設計の威力。

LNS との接続: family-based destroy

同色ジョブを 一括で抜いて挿し直す 近傍を入れると、まとめ替えが進む。

def family_removal(state, rng, frac=0.15):
    families = group_by(state.jobs, key=lambda j: j.color)
    chosen_family = rng.choice(list(families.keys()))
    targets = families[chosen_family]
    return state.remove(rng.choice(targets, size=int(len(targets)*frac)))

③ ラインを指定したい — 「M3 固定」

機械適合 (machine eligibility) $M_j \subseteq M$ の話。CP-SAT では OptionalInterval と適合機械集合で書く。

# ジョブ j を機械 m に割り当てるかどうか
present = {}
intervals_per_machine = {m: [] for m in machines}
for j in jobs:
    for m in eligible[j]:    # eligible = ジョブごとに使える機械の集合
        p = model.NewBoolVar(f"present_{j}_{m}")
        s = model.NewIntVar(0, H, f"start_{j}_{m}")
        e = model.NewIntVar(0, H, f"end_{j}_{m}")
        iv = model.NewOptionalIntervalVar(s, dur[j][m], e, p, f"iv_{j}_{m}")
        present[(j, m)] = p
        intervals_per_machine[m].append(iv)
    # ちょうど1つの機械に割り当てる
    model.AddExactlyOne(present[(j, m)] for m in eligible[j])

for m in machines:
    model.AddNoOverlap(intervals_per_machine[m])

固定なら eligible[j] = {M3} と1要素にするだけ。複数候補から選ばせたいなら集合を広げる。

LNS との接続

destroy で 特定機械の負荷を一掃 する近傍が効く。ボトルネック機械を空にして詰め直す。

def machine_removal(state, rng):
    loads = state.machine_loads()
    bottleneck = max(loads, key=loads.get)
    return state.remove_all_on(bottleneck)

④ サブロット (lot streaming) — 「半分できたら次工程へ」

教科書 JSP はジョブを 不可分 の塊として扱う。だが現場では、ロット100個のうち50個できた時点で次工程を流し始めたい。これは変数の解像度の問題で、ジョブを子タスク (サブロット) に分解する以外に解決策はない。

# ジョブ j を K 個のサブロットに分割
sub = {}
for j in jobs:
    for k in range(K[j]):
        for op in ops[j]:        # 工程 (op1 -> op2 -> ...)
            s = model.NewIntVar(0, H, f"s_{j}_{k}_{op}")
            e = model.NewIntVar(0, H, f"e_{j}_{k}_{op}")
            iv = model.NewIntervalVar(s, dur_sub[j][op], e, f"iv_{j}_{k}_{op}")
            sub[(j, k, op)] = (s, e, iv)
        # 同じサブロット内: 工程間の precedence
        for op_prev, op_next in zip(ops[j], ops[j][1:]):
            model.Add(sub[(j, k, op_prev)][1] <= sub[(j, k, op_next)][0])

ここまでだとサブロット同士は独立に流れる。転送ロット (一度に次工程に渡す数) と 処理ロット (まとめて処理する数) を分けて扱いたい場合は、サブロット間の precedence を追加する。

# サブロット k の op を、サブロット k-1 の op が始まった後に開始可
for k in range(1, K[j]):
    model.Add(sub[(j, k, op_next)][0] >= sub[(j, k - 1, op_next)][0])

サブロット数の暴発

K を10とかにすると変数が10倍に膨らむ。ホライズン全部でこれをやるとソルバーが沈黙する。
Rolling Horizon の詳細ゾーンだけ K を上げる、ボトルネック工程の前後だけ細かく刻む、など解像度を場所で変える設計が現実解。

LNS との接続: lot-streaming destroy

サブロット単位で抜いて挿し直す。K を動的に変える destroy も効く (合体させる/分割する)。

def lot_split_or_merge(state, rng):
    j = rng.choice(state.jobs)
    if rng.random() < 0.5 and state.K[j] > 1:
        return state.merge_sublots(j)
    else:
        return state.split_sublot(j)

⑤ 前段取り — 「木曜のうちに済ませておく」

これも変数の解像度の問題。段取りを処理タスクの一部に閉じ込めず、独立タスクとして切り出す。SMED でいう外段取り (external setup) の世界。

# 段取りタスクを独立に
setup_iv = model.NewIntervalVar(s_setup, dur_setup, e_setup, "setup_j")
proc_iv  = model.NewIntervalVar(s_proc,  dur_proc,  e_proc,  "proc_j")

# 段取りは処理より前に終わっていればよい (= 直前接続を強制しない)
model.Add(e_setup <= s_proc)

# 段取りは「段取り人員」のリソースを取る
model.AddCumulative(
    [setup_iv_j for j in jobs],
    [1 for j in jobs],
    capacity_setup_workers
)

# 処理は機械リソースを取る
model.AddNoOverlap([proc_iv_j for j in jobs_on(m)])

これだけで、段取りは「処理の直前」から解放され、人員に空きがあれば前日にも回せる。

LNS との接続: setup-only destroy

段取りタスクだけを抜いて、人員カレンダーに対して挿し直す近傍。前段取り化が一気に進む。

def setup_only_removal(state, rng, frac=0.2):
    setups = [j for j in state.jobs if state.has_setup(j)]
    k = int(len(setups) * frac)
    targets = rng.choice(setups, size=k, replace=False)
    return state.remove_setups(targets)

9.4 矛盾する要件をどう捌くか

5つを並べると、確実にぶつかる。

• 営業「A 社の納期最優先」
• 製造「同色まとめたい」
  → A 社が赤、その後の最重要ジョブが白なら、まとめれば遅れる、遅れを取れば段取りが増える。

これは技術問題ではなく政治問題だ。モデラーが勝手に重みを決めてはいけない。

これだけで、LNS × CP-SAT は階段の上から順に守る。説明も「納期はこの順位だから、ここで段取りを犠牲にしました」と一発で出る。

9.5 安定性も目的関数に入れる — 前計画距離

第8章で触れた 「毎日解が変わる」 問題は、目的関数で吸収する。

# 前計画のジョブ j の機械割当て prev_machine[j]、開始時刻 prev_start[j]
dev_machine = []
for j in jobs:
    same = model.NewBoolVar(f"same_m_{j}")
    model.Add(present[(j, prev_machine[j])] == 1).OnlyEnforceIf(same)
    dev_machine.append(1 - same)

dev_start = []
for j in jobs:
    d = model.NewIntVar(0, H, f"dev_s_{j}")
    model.AddAbsEquality(d, start[j] - prev_start[j])
    dev_start.append(d)

model.Minimize(
    primary_objective
    + α * sum(dev_machine)
    + β * sum(dev_start)
)

LNS は 凍結ゾーン外 を全部破壊する近傍を持っていても、dev_* がブレーキになって前計画を大きく崩す解を抑える。現場が混乱しない。

9.6 対話ループ — 「現場が直した範囲」を近傍にする

完璧な要件ヒアリングは存在しない。だから運用フェーズに 「現場が解を直す → 直した範囲を学ぶ」 ループを組み込む。

実装としては、現場が修正した解 $x'$ と提案解 $x$ の差分から、LNS の近傍の偏りと目的関数の重みを更新する:

• 「いつも同じ機械にジョブを動かされる」 → eligibility か preference が間違っている
• 「いつも特定の品種を後ろに回される」 → 重みが間違っている
• 「いつもそのジョブの段取りが消される」 → 段取りモデルが粗い

そして、LNS の destroy で「現場が直した範囲」を高確率で含める 仕掛けにすると、再最適化の質が一気に上がる。

def user_edit_aware_removal(state, rng, edit_history, frac=0.2):
    recent_edits = edit_history.last_n(50)
    hot_jobs = collections.Counter(e.job for e in recent_edits)
    weights = [hot_jobs[j] + 1 for j in state.jobs]
    k = int(len(state.jobs) * frac)
    return state.remove(rng.choice(state.jobs, size=k, replace=False, p=normalize(weights)))

これは ML を入れる前の、ルールベース の最も投資対効果が高い学習機構だ (第9章 9.9 の「パターン3」と地続き)。

9.7 失敗例ベースで要件を獲得する

「制約と目的を全部前もって列挙してください」と言って出てくる組織は存在しない。
正しいやり方は 反例の蓄積だ。

このサイクルが回り始めると、要件はドキュメントから生まれずに、運用から自然に獲得される。APS 導入失敗の主因 (= 業務側の要件整理不足) は、これでかなり緩和できる。

9.8 段階導入 — 一番痛い1工程から

要件カタログを揃えても、全工程を同時に最適化対象にしない。失敗確率が跳ね上がる。

最初の対象を絞ると、その工程の要件だけ深掘りできる。残りは人間が触る余地として残す。CP-SAT のスコープを狭めるだけで、LNS の近傍設計もシンプルに保てる。

成果が出てから次の工程に拡げる。最初から「全工場最適化」を目指すと、たいてい12ヶ月後に死ぬ (第8章のAPSパッケージ失敗率の話)。

9.9 翻訳の責任は誰のものか

最後に、組織の話。

最適化システムを 「OR エンジニアが作る」「業務が要件を出す」 の二分業にすると、ほぼ確実に失敗する。要件は翻訳されながら確定するものだからだ。OR エンジニアが「これは hard ですか soft ですか」と聞かないと、業務側は preference を hard に書いてしまう。

このスキルは育てるのに時間がかかる。だがここを諦めると、どんなに良い CP-SAT モデルもどんなに高度な ALNS も、現場に届かないまま終わる。

9.10 この章の振り返り

• 組合せ最適化の未解決問題は、もうアルゴリズムよりも翻訳問題に残っている
• 要件は hard / soft / preference の3層に仕分ける。混ぜると LNS の近傍設計が破綻する
• 5つの典型要件 → CP-SAT の翻訳カタログ:
  • 優先順 = 辞書順最適化 + 重み付き目的 + LNS の destroy 優先度
  • まとめ = SDST + AddCircuit + family-based destroy
  • ライン指定 = eligibility + OptionalInterval + machine-clear destroy
  • サブロット = ジョブを子タスクに分解 + 工程内 precedence + lot-streaming destroy
  • 前段取り = setup と process を独立 interval に分離 + 人員 AddCumulative
• 矛盾は政治問題。辞書順の階段を業務側に決めてもらう
• 安定性も目的関数に入れる。前計画との距離を α · dev_machine + β · dev_start で
• 対話ループで近傍と重みを学習する。現場が触った範囲 = 不満領域
• 要件は反例の蓄積から獲得する。回帰テストとして残す
• 段階導入で「一番痛い1工程」から。全工場最適化はたいてい12ヶ月で死ぬ
• モデラーという第三の職能を組織に置く。これが APS 失敗率9割の主因への解