スケジューリング問題の地図

ここから第III部「スケジューリング実戦」に入る。
理論よりも、現場で必要な語彙と直感を優先する。

7.1 共通言語: α | β | γ 表記

1979 年に Graham らが提案した、スケジューリング問題の共通の書き方がある。
バーで囲んだ三つのフィールドで、問題をひとことに記述する。

α: 機械の世界

β: ジョブの事情

γ: 最小化対象

7.2 ガントチャートで見る JSP

スケジュールを見える化する最強の道具がガントチャート。
横軸が時間、縦軸が機械。タスクは長方形。

3 ジョブ × 3 機械の JSP の例を見てみよう。

7.3 対立グラフ — JSP の構造を見抜く道具

JSP の解を「グラフ」として表現する強力な道具がある。対立グラフ (disjunctive graph)。

工程をノード、確定の順序を実線、「どっちが先か未決」の対立辺を破線。
解くこととは、破線の向きを全部決めることに等しい。

7.4 主要モデルざっくり整理

7.5 やってみよう: CP-SAT で JSP を 30 行で書く

ここで第6章で予告した CP-SAT を、JSP に適用する。

from ortools.sat.python import cp_model

# 各ジョブ = [(machine_id, duration), ...]
jobs = [
    [(0, 3), (1, 4), (2, 2)],   # J1: M1→M2→M3
    [(2, 5), (0, 4), (1, 4)],   # J2: M3→M1→M2
    [(0, 2), (1, 3), (2, 4)],   # J3: M1→M2→M3
]
horizon = sum(d for job in jobs for _, d in job)
m = cp_model.CpModel()

intervals, ends, by_machine = {}, {}, {}
for j, job in enumerate(jobs):
    for o, (mc, dur) in enumerate(job):
        s = m.NewIntVar(0, horizon, f"s_{j}_{o}")
        e = m.NewIntVar(0, horizon, f"e_{j}_{o}")
        iv = m.NewIntervalVar(s, dur, e, f"iv_{j}_{o}")
        intervals[(j, o)] = (s, e, iv)
        ends[(j, o)] = e
        by_machine.setdefault(mc, []).append(iv)

# 同じ機械の interval は重ならない
for mc, ivs in by_machine.items():
    m.AddNoOverlap(ivs)

# ジョブ内の工程順序
for j, job in enumerate(jobs):
    for o in range(len(job) - 1):
        m.Add(intervals[(j, o+1)][0] >= intervals[(j, o)][1])

# makespan を最小化
C_max = m.NewIntVar(0, horizon, "C_max")
m.AddMaxEquality(C_max, [ends[(j, len(job)-1)] for j, job in enumerate(jobs)])
m.Minimize(C_max)

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
solver.parameters.num_search_workers = 8       # 並列で 8 倍速
solver.Solve(m)
print("makespan =", solver.ObjectiveValue())

7.6 FJSP — 機械の選択肢があるバージョン

現実の工場に近いのは、FJSP (Flexible Job Shop)。
各工程に「この機械でもいい、こっちの機械でもいい」と選択肢がある。
当然、難易度は跳ね上がる。

CP-SAT には OptionalIntervalVar という強力な道具がある。
「選ばれたときだけ存在する区間変数」だ。これで FJSP が綺麗に書ける。

# jobs[j][o] = [(machine, duration), ...]  ← 工程ごとに選択肢
for j, job in enumerate(jobs):
    prev_end = None
    for o, choices in enumerate(job):
        presences = []
        for k, (mc, dur) in enumerate(choices):
            p = m.NewBoolVar(...)
            s = m.NewIntVar(...); e = m.NewIntVar(...)
            iv = m.NewOptionalIntervalVar(s, dur, e, p, ...)
            by_machine.setdefault(mc, []).append(iv)
            presences.append(p)
        m.Add(sum(presences) == 1)   # ちょうど 1 つだけ選ぶ
        # ... 開始/終了をマージしてジョブ順序の制約を貼る

7.7 目的関数の選び方は、業務そのもの

αとβは「問題の構造」だが、γ (目的関数) は**「あなたが何を大事にしたいか」**そのもの。 ここを決めるのが、最も業務理解を求められる部分だ。

現実には、これらを同時に最小化したいことが多い。
これは次章 (第8章) で「多目的問題」として扱う。

7.8 ベンチマークインスタンス (お試し問題集)

ベンチマークは半世紀の蓄積。
新しい手法を試すときは、これに対して既存手法と比べる。

• Lawrence (la01〜la40): JSP の小〜中サイズ、初心者向け
• Taillard (ta01〜ta80): JSP 大規模、研究の defacto 標準
• Brandimarte / Hurink: FJSP の定番
• OR-Library: 古典問題の宝庫 (ナップサック、VRP、シフトなど)

7.9 この章の振り返り

• スケジューリング問題は α | β | γ で網羅的に分類できる。
• シングル機械の単純な目的は多項式時間。並列・JSP・FJSP は NP困難。
• ガントチャートと対立グラフが、解を見るための 2 つの眼鏡。
• CP-SAT は30 行で JSP、optional interval で FJSP が書ける。
• 目的関数の選択は業務の優先順位そのもの。

次の章では、いよいよ現実の工場に入る。
教科書の世界と何がどう違うのか。Rolling Horizon という運用パターンの話だ。