スケジューリングとジョブショップ｜オペレーションズマネジメント

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：プロセス分析とリトルの法則（フロータイム $T$ ・フローの3指標）　|　関連：線形計画による生産計画（最適化のもう一つの顔・連続変数の配分）　|　次：総合生産計画（集約計画）

要点（BLUF）

スケジューリング＝順序付け（sequencing）。同じジョブの集合でも、処理する順番で平均フロータイム・遅れ・メイクスパンが変わります。「何をつくるか」を決めるのが線形計画による生産計画なら、こちらは「どの順でこなすか」。
単一機械：SPT（最短処理時間順）は平均フロータイムを最小化します（短い仕事を先に片付けると、待たされる仕事が減る）。EDD（納期順）は最大遅れ（最大ラテネス）を最小化します。どの目的を最適化するかで、最適順序が変わるのが核心です。
メイクスパン（全ジョブが終わる時刻）は、単一機械・遊休なしなら順序によらず一定（＝総処理時間）。順序が効くのは複数機械のときです。
2機械フローショップ（全ジョブが機械1→機械2の順に通る）では、ジョンソン法がメイクスパンを最小化します。「最小処理時間が機械1にあるジョブは前へ、機械2にあるジョブは後ろへ」並べるだけ。
一般のジョブショップ（多機械・ジョブごとに経路が違う）はNP困難。厳密最適は現実規模で解けず、ディスパッチ規則（SPT・EDD などの優先規則）で良い解を発見的に得ます。

1. 指標：フロータイム・遅れ・メイクスパン

$n$ 個のジョブがあり、ジョブ $i$ の処理時間を $p_i$ とします。ある順序で1台の機械が休まず処理するとき、ジョブ $i$ の完了時刻 $C_i$ は「自分より前のジョブの処理時間の合計＋自分の処理時間」。着手を時刻0とすればフロータイム（系内滞在時間）は $F_i=C_i$ です（プロセス分析とリトルの法則のフロータイム $T$ と同じもの）。納期 $d_i$ があるなら、

遅れ（ラテネス） $L_i=C_i-d_i$ （負なら早い・正なら遅れ）
ターディネス $T_i=\max(0,\,L_i)$ （遅れた分だけ。早くてもマイナスにはしない）
メイクスパン $C_{\max}=\max_i C_i$ （最後のジョブが終わる時刻）

評価したい目的はいくつもあります——平均フロータイム $\frac1n\sum_i C_i$ （仕掛りの少なさ・速さ）、最大遅れ $\max_i L_i$ （納期遵守の最悪値）、総ターディネス $\sum_i T_i$ 、メイクスパン。目的が違えば最適な順序も違うのが、スケジューリングの面白さであり難しさです。

2. SPT が平均フロータイムを最小にする理由

順序を位置 $[1],[2],\dots,[n]$ で表すと、位置 $k$ のジョブの完了時刻は前から積み上げた $C_{[k]}=\sum_{j=1}^{k}p_{[j]}$ 。完了時刻の総和は

\sum_{k=1}^{n} C_{[k]}=\sum_{k=1}^{n}\sum_{j=1}^{k} p_{[j]} =\sum_{j=1}^{n}(n-j+1)\,p_{[j]}

——位置 $j$ のジョブの処理時間 $p_{[j]}$ は、自分自身と後ろのジョブの完了時刻すべてに効くので、係数 $(n-j+1)$ がかかります（先頭 $j=1$ は $n$ 回、最後 $j=n$ は1回）。この重み付き和を最小化したい。重み $(n-j+1)$ は前ほど大きい（先頭が $n$ 、最後が1）から、大きい重みには小さい $p$ を当てるのが最小（並べ替え不等式）。すなわち処理時間の短い順＝SPT が $\sum C_i$ を、したがって平均フロータイムを最小化します。直感は単純で、短い仕事を先に終わらせると、その後ろで待たされる仕事の待ち時間がいちばん小さくなるからです。

一方、EDD（納期順）は最大遅れ $\max_i L_i$ を最小化します（ジャクソンの規則）。証明は隣接交換：最適順序の中で「納期が遅いジョブが、納期が早いジョブより前」に並んでいる隣り合った対があれば、その2つを入れ替えても最大遅れは増えません。よって納期の早い順に整列した EDD が最大遅れを最小にできます。速さ（フロータイム）を取るか、納期遵守（最大遅れ）を取るかで、並べ方が変わるわけです。

3. 単一機械で SPT・FCFS・EDD を比べる（コード）

6ジョブを FCFS（到着順）・SPT（最短処理時間順）・EDD（納期順）で並べ、平均フロータイム・最大遅れ・総遅れ・メイクスパンを比べます。SPT が平均フロータイム最小・EDD が最大遅れ最小になること、そしてメイクスパンはどの順序でも同じになることを数値で確認します。

import numpy as np
import pandas as pd

# 6ジョブ：処理時間 p（単位=時間）と納期 d（着手時刻0からの経過時間）
jobs = ["A", "B", "C", "D", "E", "F"]
p = np.array([7, 3, 8, 2, 5, 4])     # 処理時間
d = np.array([12, 8, 25, 6, 15, 18])  # 納期

def evaluate(order):
    """順序 order（インデックス列）でのフロータイム・遅れ指標を返す"""
    idx = np.array(order)
    C = np.cumsum(p[idx])               # 完了時刻＝それまでの処理時間の累積
    flow = C                            # 単一機械・着手0なのでフロータイム＝完了時刻
    lateness = C - d[idx]               # 遅れ（負なら早い）
    tardiness = np.maximum(0, lateness)
    return {
        "mean_flow": flow.mean(),
        "max_lateness": lateness.max(),
        "sum_tardiness": tardiness.sum(),
        "makespan": C[-1],
    }

# 3つの規則で順序を作る
order_fcfs = list(range(len(jobs)))             # 到着順（与えられた順）
order_spt = list(np.argsort(p, kind="stable"))  # 最短処理時間順（SPT）
order_edd = list(np.argsort(d, kind="stable"))  # 納期順（EDD）

rows = []
for name, order in [("FCFS(到着順)", order_fcfs), ("SPT(最短処理時間順)", order_spt),
                    ("EDD(納期順)", order_edd)]:
    seq = "-".join(jobs[i] for i in order)
    m = evaluate(order)
    rows.append({"規則": name, "順序": seq,
                 "平均フロータイム": m["mean_flow"],
                 "最大遅れ": m["max_lateness"],
                 "総遅れ": m["sum_tardiness"],
                 "メイクスパン": m["makespan"]})
df = pd.DataFrame(rows)
print(df.to_string(index=False, float_format=lambda x: f"{x:.4f}"))
print()
print(f"平均フロータイム最小 -> {df.loc[df['平均フロータイム'].idxmin(), '規則']}"
      f"（{df['平均フロータイム'].min():.4f}）")
print(f"最大遅れ最小       -> {df.loc[df['最大遅れ'].idxmin(), '規則']}"
      f"（{df['最大遅れ'].min():.4f}）")
print(f"メイクスパンは全規則で同じ = {df['メイクスパン'].iloc[0]:.0f}"
      f"（単一機械・遊休なしなら順序によらず総処理時間）")

出力：

          規則          順序  平均フロータイム  最大遅れ  総遅れ  メイクスパン
   FCFS(到着順) A-B-C-D-E-F   18.1667    14   37      29
SPT(最短処理時間順) D-B-F-E-A-C   13.3333     9   13      29
    EDD(納期順) D-B-A-E-F-C   14.3333     4    9      29

平均フロータイム最小 -> SPT(最短処理時間順)（13.3333）
最大遅れ最小       -> EDD(納期順)（4.0000）
メイクスパンは全規則で同じ = 29（単一機械・遊休なしなら順序によらず総処理時間）

出力の意味：3つの規則で最適になる指標が違います。SPT は平均フロータイム 13.33 で最小——短い仕事を先にこなすので、平均すると一番速く片付く。同じ仕事でも到着順（FCFS）の18.17より4.83短いのは、長いジョブ C・A を後ろに回した効果です。EDD は最大遅れ 4 で最小——納期の迫った順に処理するので、最悪の遅れがいちばん小さい（FCFS の14、SPT の9に対して4）。総遅れも EDD が9で最小です。一方でメイクスパンはどの規則も29で同じ：単一機械で休まず流す限り、終わる時刻は処理時間の合計（ $7+3+8+2+5+4=29$ ）で、順序に依りません。「速さ重視なら SPT、納期重視なら EDD」——目的を決めて初めて最適順序が決まる、という教訓がそのまま数字に出ています。

4. 2機械フローショップとジョンソン法（コード）

機械が2台あり、全ジョブが機械1→機械2の順に通る（フローショップ）と、話は一気に難しくなります。機械2はそのジョブの機械1が終わるまで着手できず、機械2が空いていても前のジョブを待つ遊休が生じうるからです。このときメイクスパンを最小化するのがジョンソン法です。

ジョンソン法の手順はシンプルです——全ジョブの処理時間（両機械を通して）の中で最小のものを探し、それが機械1にあれば先頭から、機械2にあれば末尾から詰める。決めたジョブを除いて繰り返す。直感は「機械1が短いジョブは早く流して機械2を早く動かし始める／機械2が短いジョブは最後に回して終盤の遊休を減らす」。5ジョブで実装し、全120通りの総当たりと比べてジョンソン法が本当に最小メイクスパンを与えることを検証し、ガント図を描きます。

import numpy as np
from itertools import permutations
import matplotlib.pyplot as plt
import japanize_matplotlib

# 2機械フローショップ：各ジョブは機械1 -> 機械2 の順に通る
jobs = ["J1", "J2", "J3", "J4", "J5"]
p1 = np.array([8, 2, 5, 3, 7])   # 機械1の処理時間
p2 = np.array([2, 8, 6, 9, 3])   # 機械2の処理時間

def schedule(order):
    """順序 order での各ジョブの (M1開始,M1終了,M2開始,M2終了) とメイクスパンを返す"""
    t1 = 0.0  # 機械1が空く時刻
    t2 = 0.0  # 機械2が空く時刻
    info = []
    for j in order:
        s1, e1 = t1, t1 + p1[j]
        s2 = max(e1, t2)             # 機械2はM1完了とM2の空きの遅い方から
        e2 = s2 + p2[j]
        t1, t2 = e1, e2
        info.append((j, s1, e1, s2, e2))
    makespan = t2
    return info, makespan

def johnson(p1, p2):
    """ジョンソン法：最小処理時間が機械1なら前へ、機械2なら後ろへ"""
    remaining = list(range(len(p1)))
    front, back = [], []
    while remaining:
        # 残りジョブの中で最小の処理時間（両機械を通して）を探す
        best_j, best_t, best_machine = None, np.inf, None
        for j in remaining:
            if p1[j] < best_t:
                best_j, best_t, best_machine = j, p1[j], 1
            if p2[j] < best_t:
                best_j, best_t, best_machine = j, p2[j], 2
        if best_machine == 1:
            front.append(best_j)     # 機械1が最小 -> 前から詰める
        else:
            back.insert(0, best_j)   # 機械2が最小 -> 後ろから詰める
        remaining.remove(best_j)
    return front + back

order_naive = list(range(len(jobs)))       # 素朴な順（与えられた順）
order_johnson = johnson(p1, p2)

# 全順列を総当たりして最小メイクスパンを確認（ジョンソン法の最適性チェック）
best_ms = np.inf
for perm in permutations(range(len(jobs))):
    _, ms = schedule(list(perm))
    best_ms = min(best_ms, ms)

_, ms_naive = schedule(order_naive)
info_j, ms_johnson = schedule(order_johnson)

print("機械1の処理時間 p1 =", p1.tolist())
print("機械2の処理時間 p2 =", p2.tolist())
print()
print(f"素朴な順    {'-'.join(jobs[i] for i in order_naive)} : メイクスパン = {ms_naive:.0f}")
print(f"ジョンソン法 {'-'.join(jobs[i] for i in order_johnson)} : メイクスパン = {ms_johnson:.0f}")
print(f"総当たり最小（120通り）            : メイクスパン = {best_ms:.0f}")
print(f"-> ジョンソン法は総当たり最小と一致：{ms_johnson == best_ms}"
      f"（素朴順より {ms_naive - ms_johnson:.0f} 短縮）")

# ガント図：ジョンソン法のスケジュール
fig, ax = plt.subplots(figsize=(9.5, 3.6))
colors = plt.cm.tab10(np.linspace(0, 1, len(jobs)))
for (j, s1, e1, s2, e2) in info_j:
    ax.broken_barh([(s1, e1 - s1)], (10, 8), facecolors=colors[j], edgecolor="black")
    ax.text((s1 + e1) / 2, 14, jobs[j], ha="center", va="center", fontsize=9)
    ax.broken_barh([(s2, e2 - s2)], (0, 8), facecolors=colors[j], edgecolor="black")
    ax.text((s2 + e2) / 2, 4, jobs[j], ha="center", va="center", fontsize=9)
ax.axvline(ms_johnson, ls="--", color="red")
ax.text(ms_johnson - 0.5, 9, f"メイクスパン={ms_johnson:.0f}", color="red",
        ha="right", va="center", fontsize=10,
        bbox=dict(boxstyle="round", fc="white", ec="red", alpha=0.85))
ax.set_yticks([4, 14]); ax.set_yticklabels(["機械2", "機械1"])
ax.set_ylim(-1, 19)
ax.set_xlabel("時刻"); ax.set_xlim(0, ms_naive + 1)
ax.set_title("ジョンソン法による2機械フローショップのガント図")
plt.tight_layout()
plt.show()

出力：

機械1の処理時間 p1 = [8, 2, 5, 3, 7]
機械2の処理時間 p2 = [2, 8, 6, 9, 3]

素朴な順    J1-J2-J3-J4-J5 : メイクスパン = 36
ジョンソン法 J2-J4-J3-J5-J1 : メイクスパン = 30
総当たり最小（120通り）            : メイクスパン = 30
-> ジョンソン法は総当たり最小と一致：True（素朴順より 6 短縮）

出力の意味：ジョンソン法は順序 J2-J4-J3-J5-J1 を選び、メイクスパン 30。これは全120通りを総当たりした最小値30と一致——つまりジョンソン法は2機械フローショップで証明付きの最適です。与えられた順（J1-J2-J3-J4-J5）の36より6短縮できました。先頭に来た J2 は機械1が2と短く（早く機械2を動かし始められる）、末尾の J1 は機械2が2と短い（終盤の機械2の遊休を最小化）——ジョンソン法の狙いがそのまま並びに出ています。ガント図を見ると、機械2（下段）は機械1（上段）が各ジョブを終えるのを追いかけて動き、序盤に少しだけ待つものの、その後はほぼ詰まって流れ、最後の J1 が時刻30で完了します。順序を変えるだけで、設備も人も増やさずに納期を6縮められる——スケジューリングが「タダで効く改善」と呼ばれるゆえんです。

⚠️ よくある誤解

「SPT は万能の最適規則」ではない：SPT が最小化するのは平均フロータイムだけ。長いジョブが後回しにされ続けて飢える（スターベーション）副作用があり、納期の観点では最悪になりえます（上の例でも SPT の最大遅れ9は EDD の4より悪い）。納期遵守なら EDD、最悪遅れの抑制なら EDD、平均の速さなら SPT、と目的で使い分けます。万能の単一規則は存在しません。
「ジョンソン法は何台の機械でも使える」ではない：ジョンソン法が最適性を保証するのは2機械フローショップ（および一定条件を満たす特殊な3機械）に限られます。3機械以上の一般フローショップには直接は使えず、別の手法（分枝限定・近似・メタヒューリスティクス）が要ります（要最新確認：適用条件は教科書で確認を）。
「ジョブショップも規則を当てれば最適が出る」ではない：ジョブごとに機械の経路が異なる一般のジョブショップはNP困難で、ジョブ数が増えると厳密最適は現実時間で解けません。現場は SPT・EDD・最小スラックなどのディスパッチ規則（優先規則）で良い解を発見的に得ます。最適保証はないが、十分実用的、という割り切りです。
「メイクスパンを縮めれば全部良くなる」ではない：メイクスパン・平均フロータイム・最大遅れは別々の目的で、ある順序がメイクスパン最小でも平均フロータイムや遅れは最良とは限りません（単一機械ではメイクスパンは順序不変ですらある）。何を最適化したいのかを先に決めること。目的を曖昧にしたまま「良い順序」は定まりません。
「処理時間が確定している前提」に注意：ここでの最適性は処理時間 $p_i$ が既知で確定という前提の上です。現実は故障・段取り・ばらつきがあり、ばらつきが大きいと計画は崩れます。ばらつきと待ちの関係は第4章待ち行列の基礎とリトルの法則が扱い、スケジューリングはその上の「平均的な順序付け」と捉えるのが安全です。