問題プレビューID: 31fa77a9

問 78

三つの製品 A, B, Cを，2 台の機械 M1, M2 で加工する。加工は，M1 $\to$ M2 の順で行わなければならない。各製品をそれぞれの機械で加工するのに要する時間は，表のとおりである。

このとき，三つの製品をどの順序で加工すれば，加工を始めてから全製品の加工が終了するまでの時間が最も短くなるか。ここで，ある製品の M1 での加工が終了したとき，別製品を続けて M1 で加工することができるものとする。

製品 \ 機械	M1	M2
A	7	3
B	5	6
C	4	2

解説

2 台の機械を直列に通過するジョブショップ・スケジューリングの最適化（総処理時間の最小化）には、**ジョンソン法（Johnson's Rule）**を用います。

全データの中から、最小の処理時間を見つける。
その時間が「前工程（M1）」なら、その製品を最初に配置する。
その時間が「後工程（M2）」なら、その製品を最後に配置する。
その製品を除いて繰り返す。

手順:

全体の最小値は、製品 C の M2 ( $= 2$ ) です。後工程なので、C を最後（3 番目）に配置します。 $\to (\dots, \dots, C)$
残りの A と B の中で最小値を探すと、製品 A の M2 ( $= 3$ ) です。後工程なので、A を最後（残りの中で最後、つまり 2 番目）に配置します。 $\to (\dots, A, C)$
残った B を最初（1 番目）に配置します。 $\to (B, A, C)$

したがって、最適順序は B $\to$ A $\to$ C となります。

正解は「イ」です。