機械フローショップの一歩目！Johnson法について解説してみた！

皆様こんにちは！ばるとーくです！
今回はJohnson法について解説していこうと思います！

先に断りを入れておくと，今回紹介するJohnson法は，「スケジューリング問題」に関するものであって，「グラフ理論」に関するものではございませんのでご注意ください！

スケジューリング問題におけるJohnson法は，2機械と（一部）3機械フローショップで使える高速なアルゴリズムですので，ぜひ覚えていってもらえると嬉しいですっ！

フローショップとは

まずそもそも，「フローショップ」って何なのでしょうか？

その答えとして，ASPROVA株式会社のページを見るとこのような説明があります¹

設備の編成形式の1つで、ライン配置とも呼ばれ、すべての仕事（ジョブ）の加工経路が同じ場合、この流れに合わせて編成した工程もしくはショップをいう。
これは、ジョブの流れが決まっており、繰返し生産が行われ、かつ生産量も比較的多い場合に有効である。ジョブとしての流れの管理はしやすくなるが、製品の多様化への対応は難しくなる。
また、各機械設備での作業時間が異なることがある。この場合各作業のピッチタイムをとり、ラインバランシングを行い、流れ作業化を実現することが必要となる。

つまり，車の生産などで使われる「組み立てライン」のような工場形態の時に使われる設備編成というわけです．
そして，「ジョブとしての流れの管理はしやすくなるが、製品の多様化への対応は難しくなる。」とある通り，フローショップの最適化というのは非常に難しいものです．

というのも，基本的に，フローショップなどのスケジューリング問題の計算量はNP困難と言われ，最適解を求める計算は膨大になりがちです．
多項式時間で解けるようなスケジューリング問題は，かなり特殊な条件下だったり，単純な場合に限られることが分かります．²

Johnson法とは

Johnson法とは，先の章で述べたうちの「かなり特殊な条件下だったり，単純な場合」に相当する，と言ってもいいでしょう．
これは，「2機械，または条件付きの3機械から構成される作業について，全体の作業時間が最適になるようなスケジュールを作成することができる」という手法です．^{3 4}
ここでいう「機械」というのは「工程」であって，いわば「その製品を作るためにいくつの工程を経る必要があるのか」ということです．
それでは，実際の計算方法を見ていきましょうか．

2機械フローショップ

例えば，以下のような2機械の仕事を考えます．

製品は7つです．これらの生産には最短で何日かかるでしょうか？
Johnson法を使って解いてみましょう．
(解いてみたい人は一度ここでストップ！)

Johnson法による作業順序決定は，以下の流れで進みます．
ただし，ここでは上の例題に合わせ，機械 $A$ を先に，機械 $B$ を後に行う工程とします．

1. 現時点で選ばれていない製品のうち，機械 $A$，あるいは機械 $B$ のうちどちらかの作業時間が最も少ない製品を選ぶ．
2. (機械 $A$ の作業時間) $\le$ (機械 $B$ の作業時間)，つまり，先に行う工程の作業時間が，あとに行う工程の作業時間以下なら，その製品を最初に処理する．
3. 2.のようにならないなら，その製品は最後に処理する．
4. 同数が出たときは，以下のように対処する．
   1. 機械 $A$ の値が複数同時に最小値をとる場合は，その中から機械 $B$ の工程時間がより短い製品を先に選ぶ．
   2. 機械 $B$ の値が複数同時に最小値をとる場合は，その中から機械 $A$ の工程時間がより長い製品を先に選ぶ．
   3. ある製品の機械 $A$ の値と別の製品の機械 $B$ の値が同時に最小値をとる場合は，どちらを先に選んでも最終的な処理順は同じ結果になる（前者は先頭側，後者は末尾側に配置されるため）．
5. 選ばれていない製品がなくなるまで，この工程を繰り返す．

ここで，「処理」とは，機械へ投入することを意味しています．
つまり，「最初に処理する」とは，先に機械へ投入すること，「最後に処理する」とは，機械への投入を後回しにすることを表します．

それでは，これに則り，この問題を解いてみましょう．
なお，これ以降，機械 $A$, 機械 $B$ を単に $A, B$ と呼ぶことにします（そろそろ煩わしいだけ...ですっ）

まず，製品2の $A$ が作業時間1で最短です．これを最初に選びます．
$A < B$ より，最初に処理します．
分かりやすく配列 $Q$ を定義しておくと，現在は $Q = {2}$ となっています．

次に短いのは製品4の $A$ ですね．
$A < B$ より，最初に処理します．
$Q = {2, 4}$ となりました，先頭から連結するイメージです．

次に短いのは製品3の $B$，製品1の $A$ が3で並んでいます．
製品1は $A < B$ より，最初に処理し，製品3は $A > B$ より，最後に処理します．
$Q = {2, 4, 1, 3}$ となります．製品3のように $A > B$ の時は，末端から連結するイメージです．

次に短いのは製品6の $B$ です．
$A > B$より，最後に処理します．
$Q = {2, 4, 1, 6, 3}$ となります．末尾からつなぐので，結果的に製品3より先に処理されることになる点に注意です．

次に短いのは製品7の $A, B$ ですね．どちらも7です．
$A = B$ の場合も，最初に処理します．
$Q = {2, 4, 1, 7, 6, 3}$ となりました，いよいよ次でラストです．

最後に残ったのは製品5です．
$A < B$ より，最初に処理します．
$Q = {2, 4, 1, 7, 5, 6, 3}$ となりました．

こうして，結果的に，$2 \to 4 \to 1 \to 7 \to 5 \to 6 \to 3$ という順で処理するといいことが分かりました．
これをガントチャートに表してみましょう．すると，以下のようになります．

これより，43日ですべての作業を終えることができると求まりました．

3機械フローショップ

3機械フローショップでも，以下の条件付きでJohnson法を適用することができます．

条件：3つの機械をそれぞれ $A, B, C$，製品数を $n$ とする．
この時，$\min_i A_i \ge \max_i B_i$ または $\min_i C_i \ge \max_i B_i$ を満たす．
ただし，$1 \le i \le n$ であり，$\min, \max$ はそれぞれ全 $i$ にわたる「最小値」「最大値」を示す．

では，こちらも以下のような例題を考えてみましょう．

以下に示される5つの製品を生産するには3工程必要である．

これらすべての生産には最短で何日必要でしょうか？
（こちらも「自力で解きたい！」って人はここでストップです！）ｓ

まず，Johnson法の適用条件を満たしているかの確認を行います．
ここで，$A$ と $B$ について，$\min_i A_i = 5, \max_i B_i = 5$ より，$\min_i A_i \ge \max_i B_i$ が成立し，適用条件を満たしていることが分かります．
というわけで，今回もJohnson法を用いて解いていきましょう．

3機械のJohnson法もやることはほとんど変わりませんが，少しだけ手順が変わります．

1. $(A_i + B_i)$ を仮想機械 $X_i$, $(B_i + C_i)$ を仮想機械 $Y_i$ として考える． <-ここが新しいところ！
2. 現時点で選ばれていない製品のうち，機械 $X$，あるいは機械 $Y$ のうちどちらかの作業時間が最も少ない製品を選ぶ．
3. (機械 $X$ の作業時間) $\le$ (機械 $Y$ の作業時間)，つまり，先に行う工程の作業時間が，あとに行う工程の作業時間以下なら，その製品を最初に処理する．
4. 3.のようにならないなら，その製品は最後に処理する．
5. 同数が出たときは，以下のように対処する．
   1. 機械 $X$ の値が複数同時に最小値をとる場合は，その中から機械 $Y$ の工程時間がより短い製品を先に選ぶ．
   2. 機械 $Y$ の値が複数同時に最小値をとる場合は，その中から機械 $X$ の工程時間がより長い製品を先に選ぶ．
   3. ある製品の機械 $X$ の値と別の製品の機械 $Y$ の値が同時に最小値をとる場合は，どちらを先に選んでも最終的な処理順は同じ結果になる．
6. 選ばれていない製品がなくなるまで，工程2. ~ 6.を繰り返す．

ではまず，仮想機械 $X, Y$ について考えていきます．
すると，以下の表のようになると思います．

それでは，ここからは2機械の時と同様に処理していきます．

まず，製品4のYが作業時間5と最短です．
$X > Y$ より，最後に処理します．
こちらもわかりやすく待期列 $R$ を定義しておくと，$R = {4}$ です．
1つしかないのでわかりにくいですが，最後尾なので間違えないようにしましょう．

次に短いのは製品1の $Y$ と製品5の $X, Y$ です．どちらも作業時間6と並んでいます．
製品1は $X > Y$ より最後に処理し，製品5は $X = Y$ より最初に処理します．
$R = {5, 1, 4}$ となりました．何度も言いますが間違えないように！

次に短いのは製品2の $Y$ です．
$X > Y$ より，最後に処理します．
$R = {5, 1, 2, 4}$ となりました．早くも次がラストです．

最後に残ったのは製品3です．
$X < Y$ より，最初に処理します．
$R = {5, 1, 3, 2, 4}$ となりました．

結果として，$5 \to 1 \to 3 \to 2 \to 4$ という順で処理を行うのが最適とわかりました．
ガントチャートを書くとこのようになります．

よって，39日ですべての作業を終えることができると求まりました．

証明

それでは，これよりJohnson法がフローショップ問題の最適解を求めることができることの議論・証明をしていきます．
証明は大きく分けて3つです

1. 2機械フローショップ問題の場合
2. 3機械フローショップ問題の場合(条件を満たさないとき)
3. 3機械フローショップ問題の場合(条件を満たすとき)

2機械フローショップ問題の場合

設定

2つの機械 $M_1, M_2$ と $n$ 個のジョブ ${1, 2, \ldots, n}$ からなるフローショップを考える．各ジョブ $i$ は $M_1$ で処理時間 $A_i$，続いて $M_2$ で処理時間 $B_i$ を要する ($A_i, B_i > 0$)．

本節では，一般性を保つため，$M_1$ 上と $M_2$ 上でそれぞれ独立にジョブ順を選べる設定 (すなわち $M_1$ での処理順と $M_2$ での処理順が一致していなくてもよい設定) で議論を進める．この設定のもとでのスケジュール全体を $S$ と書き，メイクスパンを $F(S)$，これを最小化するスケジュールを $S^\ast$ とする．

なお，元の問題設定（「工程間で投入する順を入れ替えることはできない」）のように $M_1, M_2$ の順序を強制的に一致させた場合の最適値は，上の一般設定の最適値と一致する．これは次の補題によって保証される．したがって以下で示す結果は，そのまま同順序制約下の問題にも適用できる．

補題1: 置換スケジュールの最適性

主張: 最適解の中には，$M_1$ と $M_2$ で同じジョブ順を用いる置換スケジュールが存在する．

証明: $M_1$ 上での順序を固定したとき，$M_2$ 上での順序を $M_1$ と同じにしても総所要時間は悪化しない．実際，$M_2$ 上で $M_1$ と異なる順序を用いているとすると，隣接する不整合ペアを交換していくことで $M_1$ と同じ順序に変形できる．各交換で $M_2$ の完了時刻は増加しないため，置換スケジュールに帰着してよい．

以下では置換スケジュールのみを考える．順序を $S = (S_1, S_2, \ldots, S_n)$ と書く．ここで $S_i$ は「$i$ 番目に処理されるジョブの番号」を表す（例えば $S_1 = 3$ なら，最初に処理するのは元の番号で言うところのジョブ 3 である）．

記法と定式化

以降の議論では順序 $S$ を1つ固定して考える．表記の簡単化のため，「順序 $S$ において $i$ 番目に処理されるジョブ ($S_i$) の $M_1$ での処理時間」を $a_i := A_{S_i}$，$M_2$ での処理時間を $b_i := B_{S_i}$ と書く．すなわち，添字 $i$ は元のジョブ番号ではなく，順序 $S$ における位置を表すことに注意する．

順序 $S$ の下で，$X_i$ を「$i$ 番目に処理されるジョブが $M_2$ に到着する直前の $M_2$ の遊休時間」と定義する．$M_1$ には遊休時間を入れず，ジョブを連続して処理するとしてよい (これは総所要時間を悪化させない)．

このとき $M_2$ の総所要時間は次のように書ける: $F(S) = \sum_{i=1}^{n} X_i + \sum_{i=1}^{n} b_i$．

第2項 $\sum b_i$ は結局全ジョブの $B$ の総和に等しく順序に依存しないため，$F(S)$ の最小化は $\sum X_i$ の最小化と等価である．

$X_i$ の漸化的な定義は $X_1 = a_1$ および $i \geq 2$ に対して $X_i = \max\left(a_1 + \cdots + a_i - b_1 - \cdots - b_{i-1} - \sum_{k=1}^{i-1} X_k,\ 0\right)$ で与えられる．

これを整理すると，次の閉じた形が得られる: $\sum_{i=1}^{n} X_i = \max_{1 \leq u \leq n} K_u$，ただし $K_u = \sum_{i=1}^{u} a_i - \sum_{i=1}^{u-1} b_i$．

したがって目的関数は $F(S) = \max_{1 \leq u \leq n} K_u + \sum_{i=1}^{n} b_i$ となり，$\max_u K_u$ を最小化する順序を求めればよい．
⁵

隣接交換の効果

順序 $S$ における $j$ 番目と $j+1$ 番目のジョブを交換した順序を $S'$ とする．$S'$ における $K$ 値を $K^\prime_u$ と書く．

$K_u$ の定義から，$u \neq j, j+1$ については $K^\prime_u$ と $K_u$ は等しい ($u$ 番目までの $a, b$ の総和が交換によって変わらないため)．したがって $F(S) \leq F(S') \iff \max(K_j, K_{j+1}) \leq \max(K^\prime_j, K^\prime_{j+1})$．

以下，交換前の $j, j+1$ 番目のジョブ（すなわち $S_j, S_{j+1}$）をそれぞれ $p, q$ とし，交換後は $q, p$ となる．元のジョブ番号による処理時間として $A_p, B_p, A_q, B_q$ を用いる（$a_j = A_p$，$a_{j+1} = A_q$，$b_j = B_p$，$b_{j+1} = B_q$）．

順序 $S, S'$ のいずれにおいても $1$ から $j-1$ 番目までのジョブは変わらないため，共通項 $\alpha := \sum_{i=1}^{j-1} a_i - \sum_{i=1}^{j-1} b_i$ は $S$ と $S'$ で等しい．これを用いて

• $K_j = \alpha + A_p$，$K_{j+1} = \alpha + A_p + A_q - B_p$
• $K^\prime_j = \alpha + A_q$，$K^\prime_{j+1} = \alpha + A_q + A_p - B_q$

$\max(K_j, K_{j+1}) < \max(K^\prime_j, K^\prime_{j+1})$ となる条件を求める．両辺から $\alpha + A_p + A_q$ を引くと $\max(-A_q, -B_p) < \max(-A_p, -B_q)$，すなわち $-\min(A_q, B_p) < -\min(A_p, B_q)$．

したがって $\min(A_p, B_q) < \min(A_q, B_p)$ ならば $p$ を $q$ より先に置くほうがよい．これが Johnson法 である．なお等号 $\min(A_p, B_q) = \min(A_q, B_p)$ の場合はどちらの順で並べても $F$ は変わらない．

補題2: 最小値ジョブの端寄せ

主張: $2n$ 個の値 $\{A_i, B_i\}_{i=1}^{n}$ の全体最小値をもつジョブを $k$ とする．

• 最小値が $A_k$ なら，$k$ を先頭に置く最適順序が存在する．
• 最小値が $B_k$ なら，$k$ を末尾に置く最適順序が存在する．

証明: $A_k$ が全体最小値の場合を示す（$B_k$ の場合は対称）．任意の順序 $S_0$ を取り，$S_0$ において $k$ が位置 $j \ge 2$ にあるとする．$k$ の直前のジョブを $\ell$ とすると，$A_k$ が全体最小値であることから

$A_k \le A_\ell,\quad A_k \le B_\ell,\quad A_k \le B_k$

が成り立つ．したがって $\min(A_k, B_\ell) = A_k$ かつ $\min(A_\ell, B_k) \ge A_k$，すなわち

$\min(A_k, B_\ell) \le \min(A_\ell, B_k)$

となる．隣接交換の効果より，$\ell$ と $k$ を入れ替えた順序（$k$ を1つ前に送った順序）は $F$ を悪化させない．この隣接スワップを繰り返して $k$ を先頭まで送ることで，$F(S_0)$ 以下のメイクスパンをもつ「$k$ が先頭にある順序」が得られる．$S_0$ として最適順序をとれば，$k$ を先頭に置く最適順序の存在が示される．$\blacksquare$

定理: Johnson法による順序の最適性

定理: 以下の再帰的手続きで構成される順序 $S^\ast$ は $F(S)$ を最小化する．

Johnson法の再帰的構成:

1. $2n$ 個の値の中から全体最小値をもつジョブ $\ { \ k}$ を選ぶ．
2. 最小値が $A_k$ なら $k$ を（残っている位置の）先頭に，$B_k$ なら 末尾に固定する．
3. $k$ を除いた $n-1$ ジョブに対し，1. から同じ操作を再帰的に適用する．

証明: ジョブ数 $n$ に関する帰納法．⁶

Base ($n = 1$): 順序は一意で自明に最適．

Step ($n \ge 2$): $n-1$ ジョブについて定理が成り立つと仮定する．$2n$ 個の値の全体最小値をもつジョブを $k$ とする．補題2 より，$k$ を端（$A_k$ 最小なら先頭，$B_k$ 最小なら末尾）に置いた最適順序が存在するので，$k$ を端に固定した順序集合の中で最小化を考えれば十分．以下 $A_k$ が全体最小値で $k$ を先頭に置く場合を示す（$B_k$ 最小・末尾の場合は対称）．

$T$ を残り $n-1$ ジョブの任意の順序とし，順序 $T$ における $v$ 番目のジョブの M1 処理時間を $a^\prime_v$，M2 処理時間を $b^\prime_v$ と書く（記法と定式化と同じ流儀）．$F^\prime(T)$ を $T$ の $(n-1)$-ジョブ単体でのメイクスパン，$F(k, T)$ を $(k, T)$ の $n$-ジョブメイクスパンとする．
このとき，次の恒等式が成り立つ:

$F(k, T) = A_k + \max( F^\prime(T),\ \sum_{j=1}^{n} B_j )$

証明: 記法と定式化で得た閉じた形 $F(S) = \max_u K_u + \sum_i b_i$ に $a_1 = A_k$，$b_1 = B_k$ を代入する．$T$ 上の $K$ 値を $K^\prime_v := \sum_{i=1}^{v} a^\prime_i - \sum_{i=1}^{v-1} b^\prime_i$ とおくと，$u \ge 2$ に対して

$K_u = A_k - B_k + K^\prime_{u-1}$

かつ $K_1 = A_k$．したがって

$\max_u K_u = \max( A_k,\ A_k - B_k + \max_v K^\prime_v ) = A_k - B_k + \max( B_k,\ \max_v K^\prime_v )$

$C := \sum_{j \ne k} B_j$ とおくと $\sum_i b_i = B_k + C$．よって

$F(k, T) = A_k + \max( B_k,\ \max_v K^\prime_v ) + C = A_k + \max( B_k + C,\ \max_v K^\prime_v + C )$

ここで $(n-1)$-ジョブ問題での閉じた形より $F^\prime(T) = \max_v K^\prime_v + C$，また $B_k + C = \sum_{j=1}^{n} B_j$．したがって

$F(k, T) = A_k + \max( F^\prime(T),\ \sum_{j=1}^{n} B_j )$

以上より恒等式が示された．$\blacksquare$

この恒等式の右辺は $F^\prime(T)$ について単調非減少（$\max$ の第1引数について単調非減少）である．したがって $F^\prime$ を最小化する $T$ は $F(k, \cdot)$ も（$k$ 先頭固定下で）最小化する．

帰納法の仮定より，Johnson法の再帰手続きを残り $n-1$ ジョブに適用して得られる順序 $T^\ast$ は $F^\prime$ の最小化を達成するので，$S^\ast := (k, T^\ast)$ は「$k$ 先頭固定」下で $F$ を最小化する．冒頭に述べたように $k$ 先頭固定の中に全体最適が存在するので，$S^\ast$ は $n$-ジョブ問題全体の最適順序である．$\blacksquare$

(おまけ)実装のための Working Rule

上の証明中の再帰手続きをアルゴリズムとして書き下すと，次の Working Rule になる:

• $(A_i, B_i)$ の $2n$ 個の値の中から最小値を選ぶ．
• 最小値が $A_i$ ならジョブ $i$ を「前から順に」配置．
• 最小値が $B_i$ ならジョブ $i$ を「後ろから順に」配置．
• そのジョブに関する両方の値を除外し，残った $2n-2$ 個の値に対して同じ操作を繰り返す．

値をあらかじめソートしておけば $O(n \log n)$ で最適順序が構成できる．

3機械フローショップ問題の場合

3機械フローショップ問題では，Johnson法は無条件では最適解を与えない．最適性が保証されるのは以下の条件を満たすときである．

条件: 3つの機械をそれぞれ $A, B, C$，製品数を $n$ とする．このとき

$\min_{1 \le i \le n} A_i \ge \max_{1 \le i \le n} B_i \quad \text{または} \quad \min_{1 \le i \le n} C_i \ge \max_{1 \le i \le n} B_i$

を満たす．

以下では，(i) この条件を満たさないときにJohnson法が最適解を与えない例が存在すること，(ii) 条件を満たすときにJohnson法が必ず最適解を与えることを示す．
なお本節では前者を示すが，これは「条件を満たさないなら必ず非最適」を意味するのではなく，あくまで「最適性が保証されない」ことを意味する．

条件を満たさないときに最適性が保証されないこと

反例として，以下の3製品を考える．

条件の確認: $\min A = 1$，$\max B = 10$ より $\min A \ge \max B$ は不成立．$\min C = 1$，$\max B = 10$ より $\min C \ge \max B$ も不成立．
したがって条件を満たさない．

仮想機械 $P_1 = A + B$，$P_2 = B + C$ を考えると:

Johnson法を適用すると，$P_1 \le P_2$ の集合 $= {1, 2}$ を $P_1$ 昇順で $2 \to 1$，$P_1 > P_2$ の集合 $= {3}$ を後ろに配置し，順序 $2 \to 1 \to 3$ を得る．このときの3機械メイクスパンは $27$ となる．

一方，全探索により真の最適順序を確認すると $2 \to 3 \to 1$ でメイクスパン $25$ が達成される．よってJohnson法は最適解を与えていない．したがって，条件を満たさない場合にJohnson法の最適性は一般には保証されないことが示された．

条件を満たすときにJohnson法が最適解を与えること

以降，条件 $\min_i A_i \ge \max_i B_i$ を満たす場合について証明する ($\min_i C_i \ge \max_i B_i$ の場合は対称的な議論で示せる)．

方針: 条件下で，任意の順序 $S$ について 3機械メイクスパン $F^{(3)}(S)$ と仮想2機械メイクスパン $F^{(2v)}(S)$ が定数差の関係にあることを示し，最適順序集合が一致することを結論する．

記法と定式化

以降，2機械の場合と同様に順序 $S$ を1つ固定し，$S$ において $i$ 番目に処理されるジョブ ($S_i$) の $M_1, M_2, M_3$ での処理時間をそれぞれ $a_i := A_{S_i}$，$b_i := B_{S_i}$，$c_i := C_{S_i}$ と書く．すなわち $a_i, b_i, c_i$ は「$i$ 番目に処理されるジョブ」の処理時間である．

順序 $S$ の下で，$Y_i$ を「$i$ 番目に処理されるジョブが $M_3$ に到着する直前の $M_3$ の遊休時間」と定義する．

2機械のときと同様に，$M_3$ の総所要時間は次のように書ける:

$F^{(3)}(S) = \sum_{i=1}^{n} Y_i + \sum_{i=1}^{n} c_i$

第2項は結局全ジョブの $C$ の総和に等しく順序に依存しないので，$F^{(3)}(S)$ の最小化は $\sum Y_i$ の最小化と等価である．

2機械の議論を (M1, M2) と (M2, M3) に2段階で合成すると，一般に次が成り立つ:

$\sum_{i=1}^{n} Y_i = \max_{1 \le u \le v \le n} (H_v + K_u)$

ただし $H_v = \sum_{i=1}^{v} b_i - \sum_{i=1}^{v-1} c_i$，$K_u = \sum_{i=1}^{u} a_i - \sum_{i=1}^{u-1} b_i$ である．

これは M2 と M3 に 2機械の議論を単純に適用した形ではなく，(M1, M2) の結果を (M2, M3) に入力として渡す合成になっている点に注意．導出は以下の通り．

Step 1 (M2 側の完了時刻): 2機械の議論を (M1, M2) に部分和として適用すると，M2 上での $v$ 番目のジョブの完了時刻は

$C_2(v) = \max_{1 \le w \le v} K_w + \sum_{i=1}^{v} b_i$

と書ける ($F(S) = \max_u K_u + \sum b_i$ の導出をそのまま $v$ までの部分に適用したもの)．

Step 2 (M3 側への適用): ジョブ $v$ が M3 に到着する時刻を $\tau_v := C_2(v)$ とみなすと，「到着時刻付きの1機械 M3」への 2機械型の議論より，M3 の総遊休時間は

$\sum_{i=1}^{n} Y_i = \max_{1 \le v \le n} \left(\tau_v - \sum_{i=1}^{v-1} c_i\right)$

となる ($\tau_v$ を M1 側の累積 $\sum a_i$ に対応させれば $K$ 値の導出と同型)．

Step 3 (合成): Step 1 の $\tau_v$ を Step 2 に代入し，$w$ に関する max を外に出すと

$\sum Y_i = \max_{1 \le v \le n} \max_{1 \le w \le v} \left(K_w + \sum_{i=1}^{v} b_i - \sum_{i=1}^{v-1} c_i\right) = \max_{1 \le w \le v \le n} (K_w + H_v)$

を得る．これで冒頭の双 max 形式が示された．

条件による簡約

条件 $\min_i A_i \ge \max_i B_i$（元のジョブ番号による最小・最大なので $\min_i a_i \ge \max_i b_i$ と同値）の下で，$\sum Y_i$ の表現を簡約する．まず次の補題を示す．

補題3: 条件 $\min_i A_i \ge \max_i B_i$ の下で，$K_u = \sum_{i=1}^{u} a_i - \sum_{i=1}^{u-1} b_i$ は $u$ について単調非減少である．

証明: $u \ge 2$ に対して

$K_u - K_{u-1} = \left(\sum_{i=1}^{u} a_i - \sum_{i=1}^{u-1} b_i\right) - \left(\sum_{i=1}^{u-1} a_i - \sum_{i=1}^{u-2} b_i\right) = a_u - b_{u-1}$

ここで $a_u$ はある1つのジョブの $A$ 値，$b_{u-1}$ もある1つのジョブの $B$ 値であるから，条件より $a_u \ge \min_i A_i \ge \max_i B_i \ge b_{u-1}$．したがって $K_u - K_{u-1} \ge 0$．$\blacksquare$

系: 任意の $v$ について $\max_{1 \le u \le v} K_u = K_v$．

証明: 補題3より $K_1 \le K_2 \le \cdots \le K_v$ であるから，最大値は $u = v$ で達成される．$\blacksquare$

系を用いて $\sum Y_i$ の表現を書き換える:

$\sum_{i=1}^{n} Y_i = \max_{1 \le u \le v \le n} (H_v + K_u) = \max_{1 \le v \le n} \left(H_v + \max_{1 \le u \le v} K_u\right) = \max_{1 \le v \le n} (H_v + K_v)$

ここで $L_v := H_v + K_v$ と置くと

$L_v = \sum_{i=1}^{v} b_i - \sum_{i=1}^{v-1} c_i + \sum_{i=1}^{v} a_i - \sum_{i=1}^{v-1} b_i = \sum_{i=1}^{v}(a_i + b_i) - \sum_{i=1}^{v-1}(b_i + c_i)$

これは 各ジョブ $i$ について $P_1(i) := A_i + B_i$，$P_2(i) := B_i + C_i$ を処理時間とする仮想2機械フローショップにおける（順序 $S$ の下での）$K$ 値そのもの である．

帰着の完成 (最適順序集合の一致)

以上の議論をまとめると，条件下では任意の順序 $S$ について

$F^{(3)}(S) = \max_{1 \le v \le n} L_v + \sum_{i=1}^{n} c_i$

が成り立つ．一方，$P_1, P_2$ を処理時間とする仮想2機械フローショップのメイクスパンは，2機械の場合の議論より

$F^{(2v)}(S) = \max_{1 \le v \le n} L_v + \sum_{i=1}^{n} P_2(S_i) = \max_{1 \le v \le n} L_v + \sum_{i=1}^{n} (b_i + c_i)$

と書ける．両者の差をとると

$F^{(2v)}(S) - F^{(3)}(S) = \sum_{i=1}^{n} b_i$

これは全ジョブの $B$ の総和に等しく，$S$ に依存しない定数である．したがって

$\arg\min_S F^{(3)}(S) = \arg\min_S F^{(2v)}(S)$

すなわち，元3機械問題の最適順序集合と仮想2機械問題の最適順序集合は一致する．

2機械フローショップ問題ではJohnson法が最適解を与えることが既に示されているので，仮想2機械問題にJohnson法を適用して得た順序 $S^\ast$ は，元の3機械問題においてもメイクスパンを最小化する．
具体的にはJohnson法は次の形で書ける（$p, q$ はジョブ番号）:

$\min(A_p + B_p,\ B_q + C_q) < \min(A_q + B_q,\ B_p + C_p) \implies p \text{ を } q \text{ より先に置く}$

補足: 条件が本質的である理由

条件を用いなければ，$\sum Y_i$ の表現は $\max_{u \le v}(H_v + K_u)$ の形のままとどまり，補題3の単調性が成り立たないため $\max_{u \le v} K_u = K_v$ の簡約ができない．
この場合，隣接交換 $j \leftrightarrow j+1$ で影響を受ける項が添字 $j, j+1$ に閉じず，それ以前の順序に依存するため，局所的な決定則としてのJohnson法が導けない (P-402 §2末尾でJohnson自身が指摘している通り⁵)．条件 $\min A \ge \max B$ は，補題3を介して $\sum Y_i$ を $\max_v L_v$ という2機械問題の形に閉じ込める役割を果たしている．

以上より，2機械フローショップ問題ではJohnson法が必ず最適解を与えること，3機械フローショップでは無条件にはJohnson法の最適性が保証されないこと，並びに，$\min A \ge \max B$ (または $\min C \ge \max B$) の条件下では2機械問題への帰着を通じてJohnson法が最適解を与えることが示された．

余談～なぜJohnson法やフローショップ問題は競プロ典型になりえないのか

ここからは私の余談です．
実は私一度，yukicoderでフローショップ問題を題材にした問題を作ったことがあるんです...
※何ならその補足のためにこの記事を書いてるまである

で，私ふと思いました．「なんでこの類の問題ってあまり見ないんだろう？」と．
もしかしたら私の競プロ人生がまだ浅すぎて出会ってないだけの可能性も十分考えられますが，あんまり話題に聞かないなと思い...

というわけで今から，私がこの記事を書くためにいろいろ調べたり，大学の授業でかじったりした知識をもとにして，自身を論駁していこうと思います...というのがこの章の趣旨です///

まずそもそも，「拡張性が小さい」と思いましたね．
これを題材に使おうとすると，どうしてもストーリー性がワンパターンになるなーと感じます．
だって，「工場のライン生産」以外にこの題材が当てはまりそうなシチュエーションが思いつかないんですもん．
※思いついた方，ぜひこの下のコメ欄，Ｘなどなどでコメントください．または問題を作って送り付けてきてください．

次に，「Johnson法の条件が厳しすぎる」点が挙げられます．
2機械はともかく，3機械になると条件が厳しすぎて制約で手法がバレます．
これはあまり快しとしない人もいるのではないかな～と考えています．
例えば「$N$ が小さいからビット全探索でしょ」みたいな経験あると思います．こういう体験が追加されるのは...どうなんでしょうか？とも思ってしまいますね．
ただ，（論駁に論駁を重ねてしまいますが）2機械ならいい練習問題になるんではないでしょうか．こちらは制限がほぼないですからねっ
私の見立てでは(Novistep基準)4Qくらいの難易度になるんじゃないかなと...

また，「スケジューリング問題が基本的にNP困難」である点が致命的な気がします．
最初の章でも述べた通り，スケジューリング問題は基本的にNP困難です．
とすると，計算量での厳密な証明ができないので，上界をしっかり定めないと問題として破綻しうる，という面倒くささ付きです．
※主も実際その問題に立ちはだかりました．tester様には感謝してもしきれません...

これだけの論駁で，十分競プロ向きではないことが証明できてしまいましたね...
とはいえ，最適化問題を考える上では必ず出てくる問題であるため，認知自体はしておくことをお勧めします．

さいごに

ここまで，Johnson法について解説してきました！
ここまでぎゅっとした記事を書くのもなんだか久しぶりで，ちょっと楽しかったです．
現在は（コンテストの都合により）壊れた部屋のみでの公開ですが，コンテスト後にqiitaにも投稿いたしますので，併せて見ていってくださるととてもうれしいです！

というわけで，今回はここまでにしたいと思います！
この記事が皆様のためになることを願っております！
ご意見・ご感想あれば，コメ欄やXなどのSNSまでよろしくお願いいたします！
※上記「リンク集」からばるとーくのアカウントがあるサイト一覧が載っておりますので，ぜひ見てみてください！
また，お時間ございましたら，他の記事も見ていってください！

それではまた！