平成30年度　経営工学部門　Ⅲ-23

問題

Ⅲ－２３　２工程のフローショップで処理される６個の仕事（A～F）に関するデータが下表に与えられている。以下のa～cの条件の下で、ジョンソンのアルゴリズムを用いたメイクスパンが最小となる仕事の順序付けとして、最も適切なものはどれか。

【条件】
a．１つの工程では同時に２つの仕事の処理を行うことはできない。
b．どの仕事も時刻０で開始可能である。
c．１つの仕事は第１工程の処理終了後に第２工程で処理される。

表　仕事の処理時間

仕事	第１工程	第２工程
A	17	12
B	10	16
C	13	15
D	18	14
E	14	11
F	16	18

①　Ｂ → Ｃ → Ｅ → Ｆ → Ａ → Ｄ
②　Ｅ → Ａ → Ｄ → Ｃ → Ｂ → Ｆ
③　Ｂ → Ｃ → Ｆ → Ｄ → Ａ → Ｅ
④　Ｂ → Ｅ → Ａ → Ｃ → Ｄ → Ｆ
⑤　Ｄ → Ａ → Ｆ → Ｅ → Ｃ → Ｂ

解答

正解は　3　になります。

全体解説：ジョンソンのアルゴリズムによる順序決定

この問題は「2工程フローショップスケジューリング」に関するものです。
複数の仕事（A～F）が、第1工程・第2工程を順番に処理され、それぞれの工程で同時に2つ以上の仕事はできません（単一機械）。
目標は「全作業が完了するまでの最短時間（メイクスパン）を実現する仕事の順序」を決定することです。

ジョンソンのアルゴリズムは、2工程で加工する仕事の順序最適化を効率的に求める手法です。適用方法は次の通りです。

ジョンソンのアルゴリズムの要点

1. 各仕事について「第1工程」と「第2工程」の所要時間を見る。
2. 全仕事から、最も小さい処理時間を探す。
   • それが「第1工程」にある場合は左端へ順次配置。
   • 「第2工程」にある場合は右端へ順次配置。
3. 配置が終わるまで繰り返す。
4. 配置順を確認し、左→右に並べればメイクスパン最小となる。

ジョンソンのアルゴリズムで順序を求める

• 最小値は「Bの第1工程10」（左端にB）
• 残り：A(17/12), C(13/15), D(18/14), E(14/11), F(16/18)
• 次は「Eの第2工程11」（右端にE）
• 残り：A(17/12), C(13/15), D(18/14), F(16/18)
• 次は「Aの第2工程12」（右端のEの左へA）
• 残り：C(13/15), D(18/14), F(16/18)
• 次は「Cの第1工程13」（Bの右、まだ空いている左ブロックにC）
• 残り：D(18/14), F(16/18)
• 次は「Dの第2工程14」（右端のEとAのさらに左へD）
• 残り：F(16/18)
• 最後はF（空いている箇所に）

並べると：左から「B→C→F→D→A→E（右）」

正しい順序および選択肢の検討

選択肢③が

• 「B→C→F→D→A→E」
  と一致。

各選択肢の詳細解説

①　Ｂ→Ｃ→Ｅ→Ｆ→Ａ→Ｄ

• E→Fの順でEが前だが、Eは第2工程最小なので最後に来るべき→誤り

②　Ｅ→Ａ→Ｄ→Ｃ→Ｂ→Ｆ

• 最小の第1工程Bは最初でない。右端にFが来るがFは第2工程最大→誤り

③　Ｂ→Ｃ→Ｆ→Ｄ→Ａ→Ｅ

• ジョンソンのアルゴリズム通り。適切な順序

④　Ｂ→Ｅ→Ａ→Ｃ→Ｄ→Ｆ

• Eが序盤で使われているが第2工程最小なので右端にすべき。誤り

⑤　Ｄ→Ａ→Ｆ→Ｅ→Ｃ→Ｂ

• 最小第1工程Bが最後、明らかに不適切

図表：ジョンソンのアルゴリズム順序決定フロー

配置手順	選択した仕事（工程/値）	配置位置	現在の順序
1	B（第1/10）	左端	B
2	E（第2/11）	右端	B, E
3	A（第2/12）	Eの左	B, A, E
4	C（第1/13）	Bの右	B, C, A, E
5	D（第2/14）	Aの左	B, C, D, A, E
6	F	残り	B, C, F, D, A, E

まとめ・問題解決のポイント

• ジョンソンのアルゴリズムは「2工程フローショップ」でメイクスパン最小解を速く出せる。
• 最短順序の鍵は“最小の処理時間”が「第1工程か第2工程か」で配置を決めること。
• クリティカルパス同様、プロジェクト全体時間最小化に必須の考え方。

感想

ジョンソンのアルゴリズム、過去記事でも登場しています。

今回の解説作成で、より理解が深まりました。

前回はふ～ん、そんなもんか。で終わっていた可能性あり（笑）

やっぱり書き出すのが大事ですね、表問題は！！