ITパスポート 2018年 秋期 問05

作業順序の最短化（機械X→機械Y）【ITパスポート 解説】

正解の理由

• 機械X（第1工程）の処理時間が機械Y（第2工程）より短い作業は前方に置く。
• 機械Xの処理時間が機械Yより長い作業は後方に置く。
• 前方グループは機械X時間の小さい順に、後方グループは機械Y時間の大きい順に並べる。

• 作業A：X=8分、Y=10分（X≤Y → 前）
• 作業B：X=10分、Y=5分（X>Y → 後）
• 作業C：X=6分、Y=8分（X≤Y → 前）

解法ステップ

1. 各作業について「機械Xの時間」と「機械Yの時間」を比較する。
2. Xの時間が小さい（X≤Y）作業は「前（先頭）グループ」へ、Xの時間が大きい（X>Y）作業は「後（末尾）グループ」へ振り分ける。
3. 前グループはX時間の昇順（小さいものから先）に並べる。後グループはY時間の降順（大きいものから後ろ寄せ）に並べる。
4. 前グループの順、次に後グループの順で結合したものが最短順序となる。

• 前グループ：C(6,8), A(8,10) → X時間で昇順 → C, A
• 後グループ：B(10,5) → 単独なので B
• 結果：C → A → B（ウ）

• C の Y 開始：X終了 6 → Y 6～14（8分）
• A の Y 開始：X終了 14、Yは14時点で空く → Y 14～24（10分）
• B の Y 開始：X終了 24 → Y 24～29（5分） ゆえに全体の終了時刻（メイクスパン）は $29$ 分になります。

選択肢別の誤答解説

• ア: A → B → C
  機械Xの順序は A(8) → B(10) → C(6)。この順で計算するとメイクスパンは $32$ 分になります。ジョンソンの法則に従っていないため最短とはならない。
• イ: A → C → B
  Xの順は 8 → 6 → 10。こちらもジョンソンの並べ方に反しており、メイクスパンは $31$ 分です。
• ウ: C → A → B
  ジョンソンの法則に合致する並びで、計算するとメイクスパンは $29$ 分となり最小になります。
• エ: C → B → A
  こちらは前に置くべきもの（X時間が短いA）を後ろに回してしまっているため、メイクスパンは $34$ 分と最も長くなります。

よくある誤解

1. 「単純にXの短い順に並べればよい」と考える誤り
   → Xだけで昇順にすると、Yの時間が長い作業が後半に残り、Yで待ちが発生して総時間が増えます。ジョンソンのルールではXとYの比較で前後を振り分けます。
2. 「処理時間の合計が小さい順にすれば良い」と勘違いする
   → 各作業のX+Yの合計が小さい順は常に最適ではありません。機械間の順序関係（X→Y）があるため、ジョンソンの考え方が必要です。
3. 並列可能な機械だと勘違いする
   → 問題文のように機械XとYは並行で使える（同時に別作業を処理できる）点は重要ですが、それぞれの機械が同時に複数作業を処理できない点を忘れると誤ったスケジュールを作ってしまいます。

補足コラム

• ジョンソンのアルゴリズムは「2工程（2台の機械）で順序が同じ（すべてX→Y）」という条件で最適性が保証されます。工程が3つ以上の場合や、処理の順序が作業ごとに異なると一般に難しくなり、別の手法や近似解法が必要になります。
• 覚え方のコツ：小さい時間は「前へ」、大きい時間（ただしY側が大きい）を「後ろへ」──これをXとYの大小比較で分けるだけです。
• 実務では「ガントチャート（棒グラフで工程を示す図）」を使って視覚的に確認するとミスが減ります。

FAQ