平成27年度　経営工学部門　Ⅲ-28PR含む

• Facebook
• X(旧:Twitter)
• はてブ
• LINE
• Pocket

問題

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

条件

a. 1つの工程では同時に2つの処理を行うことができない。
b. どのジョブも時刻0で開始可能である。

①　E → A → D → B → F → C
②　A → E → B → C → F → D
③　E → D → B → C → F → A
④　A → D → B → C → F → E
⑤　A → D → C → B → F → E

解答

正解は　4　になります。

ジョンソンのアルゴリズムを徹底解説：手順を詳しく理解しよう

ジョンソンのアルゴリズムは、2工程フローショップ・スケジューリング問題において、最大メイクスパンを最小化するジョブの順序を見つけるために使用される効率的な手法です。
以下では、アルゴリズムの手順をさらに詳しく解説し、今回の問題に適用していきます。

ジョンソンのアルゴリズム：詳細な手順

ジョンソンのアルゴリズムは、以下のステップで進めます。

STEP 1: 各ジョブの処理時間を比較

• 各ジョブについて、第1工程（M1）と第2工程（M2）の処理時間を比較します。
• ルール：
  • 第1工程（M1）の処理時間が短い場合、そのジョブを前方グループに配置します。
  • 第2工程（M2）の処理時間が短い場合、そのジョブを後方グループに配置します。

STEP 2: グループ内で並べ替え

• 前方グループ：
  • 第1工程（M1）の処理時間が短い順に並べます。
• 後方グループ：
  • 第2工程（M2）の処理時間が長い順に並べます。

STEP 3: 前方グループと後方グループを結合

• 前方グループの順序 → 後方グループの順序 の形で結合します。
• この結合された順序が、最大メイクスパンを最小化する最適なジョブの順序となります。

問題への適用

与えられたジョブと処理時間データを基に、ジョンソンのアルゴリズムを適用していきます。

STEP 1: 各ジョブの処理時間を比較

まず、第1工程（M1）と第2工程（M2）の処理時間を比較し、前方グループと後方グループに分けます。

• 前方グループ（M1 < M2）：
  • A (11 < 15)
  • D (12 < 14)
• 後方グループ（M1 >= M2）：
  • B (13 >= 14)
  • C (16 >= 18)
  • E (12 >= 11)
  • F (18 >= 16)

STEP 2: グループ内で並べ替え

前方グループ

• M1の処理時間が短い順に並べます。
• 並び替え結果：A (11), D (12)

後方グループ

• M2の処理時間が長い順に並べます。
• 並び替え結果：C (18), F (16), B (14), E (11)

STEP 3: 前方グループと後方グループの結合

• 前方グループ + 後方グループ → A → D → B → C → F → E

この順序が、最大メイクスパンを最小化する最適なジョブの順序です。

各選択肢について検討

以下では、与えられた5つの選択肢について、それぞれガントチャートを基に最大メイクスパンを計算し、正否を検討します。

選択肢①: E → A → D → B → F → C

• この順序では、第1工程と第2工程で待機時間が多く発生します。
• 最大メイクスパンは他よりも長くなり、不適切です。

選択肢②: A → E → B → C → F → D

• ジョンソン法による最適な順序ではありません。
• 最大メイクスパンは改善されますが、他よりも効率的ではありません。

選択肢③: E → D → B → C → F → A

• 順序自体は近似的ですが、第1工程と第2工程間で待機時間が発生しやすい構造です。
• 最大メイクスパンは他よりも長くなります。

選択肢④: A → D → B → C → F → E（正解）

• ジョンソン法による最適な順序です。
• 最大メイクスパンが最小化されており、全体的な効率が最も高いです。

選択肢⑤: A → D → C → B → F → E

• 順序自体は近似的ですが、第2工程で待機時間が発生するため最大メイクスパンが増加します。

比較表

以下に各選択肢について最大メイクスパンと評価をまとめます：

結論

本問題における正解は選択肢④: A → D → B → C → F → Eです。この順序では：

1. 全ての条件を満たしています。
2. ジョンソンのアルゴリズムによって最大メイクスパンが最小化されています。

感想

ジョンソンのアルゴリズム、全く知りませんでした。

語句自体はココ↓で出てきますが。

関連記事

平成27年度　経営工学部門　Ⅲ-10問題Ⅲ－10次のうち、生産計画に関する説明として最も不適切なものはどれか。①MRPにおける独立需要品……

内容がわかると考え方は簡単ですね。

もう覚えたぞ！

しかしこのアルゴリズム、導くまでが大変だったろうなあ・・・。

• Facebook
• X(旧:Twitter)
• はてブ
• LINE
• Pocket