ガントが主役、最適化が裏方 — 小工場のための計画設計

この章は、その違和感に正面から答える話。
教科書 JSP は「ジョブ × 機械」の二項関係しか持たない。だが現実の小工場は、設備・作業者・タクト の三つ巴で動く。そして、計画の主役を人間に置く設計が、実は LNS × CP-SAT でいちばん筋がいい。

10.1 教科書 JSP の外側 — 三つ巴の世界

まず、対象問題が JSP よりずっと複雑だという事実から始める。

この差は本質的だ。NoOverlap ひとつで済む世界ではない。

10.2 リソースの二重制約をモデルに置く

設備と作業者を 両方 リソースとして立てる。CP-SAT の AddCumulative を二段に重ねるのが定石。

# ジョブ j の interval (設備 m を使う / 作業者 w を使う)
iv_machine = {}  # (j, m) -> OptionalInterval
iv_worker  = {}  # (j, w) -> OptionalInterval

for j in jobs:
    # 適合設備
    machine_present = []
    for m in eligible_machines[j]:
        p = model.NewBoolVar(f"m_{j}_{m}")
        s = model.NewIntVar(0, H, f"sm_{j}_{m}")
        e = model.NewIntVar(0, H, f"em_{j}_{m}")
        iv = model.NewOptionalIntervalVar(s, dur[j][m], e, p, f"ivm_{j}_{m}")
        iv_machine[(j, m)] = iv
        machine_present.append(p)
    model.AddExactlyOne(machine_present)

    # 適合作業者 (スキルマトリクス × 機械適合の積集合)
    worker_present = []
    for w in eligible_workers[j]:
        p = model.NewBoolVar(f"w_{j}_{w}")
        s = model.NewIntVar(0, H, f"sw_{j}_{w}")
        e = model.NewIntVar(0, H, f"ew_{j}_{w}")
        iv = model.NewOptionalIntervalVar(s, dur[j][w], e, p, f"ivw_{j}_{w}")
        iv_worker[(j, w)] = iv
        worker_present.append(p)
    model.AddExactlyOne(worker_present)

    # 同期: 設備と作業者の interval は同じ時間帯
    for m in eligible_machines[j]:
        for w in eligible_workers[j]:
            # 両方選ばれたとき、開始・終了を一致させる
            both = model.NewBoolVar(f"both_{j}_{m}_{w}")
            model.AddBoolAnd([machine_present[m], worker_present[w]]).OnlyEnforceIf(both)
            model.Add(iv_machine[(j, m)].StartExpr() == iv_worker[(j, w)].StartExpr()).OnlyEnforceIf(both)

# リソースの NoOverlap
for m in machines:
    model.AddNoOverlap([iv_machine[(j, m)] for j in jobs if m in eligible_machines[j]])
for w in workers:
    model.AddNoOverlap([iv_worker[(j, w)] for j in jobs if w in eligible_workers[j]])

ペア変数の爆発

ジョブ数 × 機械数 × 作業者数 で both_* のペア変数が三乗で増える。
実務では 「設備が決まれば動かせる作業者は数人」 のスパース性を使い、適合ペア (m, w) だけを enumerate するのが必須。

スキルマトリクスは集合演算で

# スキル: worker -> machines を動かせる
skill = {
    "田中": {"A", "B", "C"},
    "佐藤": {"A", "C"},
    "鈴木": {"B"},       # B 専任
    "高橋": {"C", "D"},
    "伊藤": {"A", "D"},
}
# ジョブ j を動かせる作業者: そのジョブの適合機械を動かせる人
eligible_workers[j] = {w for w in workers if eligible_machines[j] & skill[w]}

10.3 タクトタイム × 数量 = 所要時間

教科書 JSP は dur[j][m] を定数で持つが、現場では タクト × 数量 で決まる。さらに作業者のスキルで揺れる。

dur[j][m, w] = ceil(takt[j][m] * qty[j] * skill_factor[w][m])
# 例: 製品 X (タクト30秒) を 100個、設備 A、田中
#     dur = 30 * 100 * 1.0 = 3000 秒 = 50 分
#     同じく鈴木がやるなら skill_factor = 1.3 で 65 分

これだけで、ソルバーは**「スキルの高い人をボトルネックに優先配置する」**を自然に選ぶ。重み付けで誘導する必要がない。

バッチを分けると所要時間も変わる

サブロット (第9章 9.3 ④) と組み合わせると、

• 100個を50個×2サブロットに分けると、各サブロットの dur は半分
• 段取りは2回必要
• 後工程は最初のサブロットが終わった時点で開始可

このロットストリーミング × タクトの組合せが、小工場では一番効く。バッチサイズ自体を最適化変数にすると、変数が膨らむのでホライズン詳細ゾーン (第8章) に絞るのがコツ。

10.4 規模で最適化の意味が変わる — 3つの設計圏

ここまでで分かるのは、現場の複雑さは「制約が多い」ことより**「文脈情報の量が多い」**こと。これに対する設計は、規模で大きく分かれる。

判別の目安:

10.5 エディタ派の中核 — 役割を逆転させる

エンジン派の設計:

最適化エンジン → 解 → 人間がレビュー (たいてい不満)

エディタ派の設計:

人間がガントを動かす → 最適化が「触られていない範囲」を再最適化 + 警告 + サジェスト

この逆転を成立させるには、ガントの操作を CP-SAT のハード制約として翻訳するだけでいい。

def freeze_user_decisions(model, schedule, edits):
    """ユーザーが手で動かしたジョブは、固定変数として CP-SAT に渡す"""
    for j, e in edits.items():
        # ユーザー指定の機械と作業者をハード化
        model.Add(present_machine[(j, e.machine)] == 1)
        model.Add(present_worker[(j, e.worker)] == 1)
        # 開始時刻も固定 (またはタイムウィンドウで)
        if e.pin_time:
            model.Add(start[j] == e.start)
        else:
            model.Add(start[j] >= e.start - tol)
            model.Add(start[j] <= e.start + tol)

これだけで、ユーザーが「鈴木さん、金曜午前 B でこの仕事」とドラッグした瞬間、その3要素 (機械・作業者・時刻) は固定変数になり、CP-SAT は残りだけを最適化する。

10.6 ピン留め LNS — LNS の近傍が「触られなかった範囲」

第7章で見た LNS × CP-SAT のハイブリッドアーキテクチャは、エディタ派ではこう書き換わる:

def editor_lns(problem, current, user_edits, time_budget):
    end = time.time() + time_budget
    while time.time() < end:
        # destroy: ユーザーが触っていない範囲をランダムに抜く
        free = [j for j in current.jobs if j not in user_edits]
        targets = random.sample(free, k=int(len(free) * 0.2))
        partial = current.remove(targets)

        # repair: CP-SAT で targets を厳密に挿し直す
        #         このとき user_edits は固定変数として与える
        model = build_cp_model(problem, fixed=user_edits | partial.fixed)
        solver = cp_model.CpSolver()
        solver.parameters.max_time_in_seconds = 5   # エディタは応答性が命
        solver.Solve(model)
        candidate = extract_schedule(model, solver)
        if better(candidate, current):
            current = candidate
    return current

10.7 警告・サジェスト・KPI ライブ — 3つの裏方仕事

エディタ派で最適化が果たす仕事は、エンジン派と全く違う。

警告: INFEASIBLE になる前に

ユーザーがジョブを動かした瞬間、部分モデルを解いて整合性をチェック。

def validate_edit(current, edit, time_limit=0.5):
    model = build_cp_model_around(current, edit, scope="local")
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = time_limit
    status = solver.Solve(model)
    if status == cp_model.INFEASIBLE:
        return Warning("鈴木さんはその時間、B 設備で別ジョブ稼働中です")
    if status == cp_model.FEASIBLE and solver.ObjectiveValue() > current.objective * 1.2:
        return Warning("この配置だと総遅れが 20% 悪化します")
    return None

時間制限は 0.5 秒 がエディタとしての応答性ライン。これを超えるとユーザーは「もたつく」と感じる。範囲を狭めて部分検査にするのがコツ。

サジェスト: 「ここに置くと切替が30分減ります」

LNS の destroy/repair を ユーザーの注目領域 に限定して動かし、改善候補を出す。

def suggest_improvements(current, focus_region, k=3):
    suggestions = []
    for _ in range(k * 5):
        candidate = lns_step(current, scope=focus_region, time_limit=0.3)
        delta = current.objective - candidate.objective
        if delta > significance_threshold:
            suggestions.append(Suggestion(
                description=describe_change(current, candidate),
                improvement=delta,
            ))
    return top_k(suggestions, k)

UI には:

💡 ジョブ J5 を田中さんから佐藤さんに変えると、切替が25分減ります (総遅れ -10分, makespan -5分)

のように、Δ で表現する。「最適です」ではなく「ここを変えるとこれだけ良くなる」と差分で示すのが、人間が受け取りやすい言語。

KPI ライブビュー

ユーザーがガントを動かすたびに、目的関数の値を即時計算する。最適化はしない。値を出すだけ。

def compute_kpis(schedule):
    return {
        "total_tardiness": sum(max(0, schedule.end[j] - due[j]) for j in jobs),
        "makespan": max(schedule.end[j] for j in jobs),
        "total_setup": sum(setup_cost(schedule, m) for m in machines),
        "worker_overtime": sum(max(0, schedule.worker_load[w] - shift[w]) for w in workers),
        "deviation_from_prev": sum(1 for j in jobs if schedule.machine[j] != prev.machine[j]),
    }

これだけで「ガントを動かす感覚」がぐっと変わる。意思決定の物差しが手に入る。

10.8 重みの校正 — 過去判断ログから学習する

エンジン派の最大の壁が「重みを誰が決めるか」だが、エディタ派なら 人間の編集ログそのものが正解データになる。

記録された人間の操作:
  「ジョブ J3 を手で午前から午後に動かした」
  → 自動最適化はそれを午前に置きたがった
  → 人間の知っている情報 (午前 J3 と相性悪い客先のクレーム履歴)
  → この情報を「重み」にすると、自動最適化が次回その動きを再現できる

実装は 逆強化学習 のような大層なものではなく、重みのスライダー で良い:

• 「納期遵守」 重み 1.0
• 「切替削減」 重み 0.3
• 「前計画からのブレ」 重み 0.5
• 「特定客先優先」 重み 客先別

UI でスライダーを動かすと、裏で CP-SAT を再走させて結果を可視化する。ユーザーは数式を書かないが、直感で重みを校正できる。重みのプリセットを「平常モード」「繁忙モード」「年末モード」と保存しておくのも実務的に効く。

10.9 「急ぎは切替を外す」は目的関数で書ける

最後に、冒頭の Scene の問いに答える。

基本は切替コスト最小化、でも急ぎはそれを外れる

これはルールベースの追加ではなく、目的関数の重みで自然に出る:

model.Minimize(
    sum(weight[j] * tardiness[j] for j in jobs)   # 急ぎは weight[j] が大きい
  + lambda_setup * total_setup
)

weight[j] >> lambda_setup なら、ソルバーは急ぎを通すためなら切替を払うを自発的に選ぶ。「急ぎフラグを立てたら weight が10倍になる」をスライダーかフラグで実装すれば、ユーザーから見ると「ルールベース」と同じ操作感だが、裏では一貫した最適化問題が解かれている。

10.10 最適化を諦める勇気

最後にもう一つ、エディタ派でも諦めるべき場面の話。

10.11 この章の振り返り

• 小工場の問題は教科書 JSP の外側 — 設備 × 作業者 × タクト の三つ巴 (Dual-Resource Constrained Scheduling)
• 設備と作業者は AddCumulative を二段 に重ねる。ペア変数の爆発はスパース性で抑える
• タクトタイム × 数量で所要時間が決まる。スキルファクタで作業者ごとに揺れる
• 3つの設計圏: Excel 派 / エディタ派 / エンジン派。小工場の本命はエディタ派
• エディタ派の中核は 役割の逆転 — ガントが主役、最適化が裏方
• 人間の編集を CP-SAT の 固定変数 に翻訳すると、LNS の近傍が自然に「触られなかった部分」になる
• 裏方の仕事は3つ — 警告 / サジェスト / KPI ライブビュー。応答性0.5秒が境界線
• 重みの校正は操作ログから。スライダーとプリセットで人間が直感的に触れる
• 「急ぎは切替を外す」は目的関数の重みで自然に出る。ルールベースに見えるものの大半は重みで書ける
• 最適化を諦める勇気も大事。ナレッジ管理問題を最適化で解こうとしない