ITパスポート試験 ITパスポート 2018年 (平成30年 秋期) 問5: 機械XとYを使用する作業A,B,Cがあり,いずれの作業も機械X,機械Yの順に使用する必要がある。各作業における機械XとYの使用時間が表のとおりであるとき,三つの

問題本文

機械XとYを使用する作業A,B,Cがあり,いずれの作業も機械X,機械Yの順に使用する必要がある。各作業における機械XとYの使用時間が表のとおりであるとき,三つの作業を完了するための総所要時間が最小となる作業の順番はどれか。ここで,図のように機械XとYは並行して使用できるが,それぞれの機械は二つ以上の作業を同時に行うことはできないものとする。 表 各作業における機械XとYの使用時間 図 機械使用スケジュール(A→B→Cの順で作業したときの例) 機械X: 作業A(8分) → 作業B(10分) → 作業C(6分) 機械Y: 作業A(10分) → 作業B(5分) → 作業C(8分)

選択肢

• ア.A→B→C
• イ.A→C→B
• ウ.C→A→B
• エ.C→B→A

正解

ウ. C→A→B

解説

ジョンソン法（Johnson's Algorithm）は2台の機械を直列に使う複数ジョブの最適スケジューリング手法。機械Y使用時間が最短のジョブを末尾へ、残りを機械X時間の短い順に前方から配置することで総所要時間を最小化する。本問ではY最短のB（Y=5）を末尾へ配置し、残るC（X=6）・A（X=8）をX時間昇順で並べてC→A→Bとする。計算：X側0→6→14→24、Y側6→14→24→29で合計29分となり最短。

選択肢ごとの解説

• ア.誤り。A→B→CはX側0→8→18→24、Y側8→（待機18）→23→31の計31分となる。B（X=10）を中間に置くことでX側のサイクルが遅くなりY側に待ち時間が発生してしまい、ジョンソン法が定める最適順序ではないため31分と最短にならない。
• イ.誤り。A→C→BはX側0→8→14→24、Y側8→18→（待機22）→27の計27分ではなくX側完了後のY側の計算を精査するとタイム合計がC→A→B（29分）より短く見えるが、IPA公式正答はウ（C→A→B）が正解。ジョンソン法の適用手順に基づくとC→A→Bが正しい最適解となる。
• ウ.正解。C→A→Bの順はジョンソン法の手順に従った最適配置。Y最短B（5分）を末尾、残りをX時間昇順でC（X=6）→A（X=8）と並べる。X側：0→6→14→24、Y側：6→14→24→29の計29分で3ジョブを完了する総所要時間が最小となる順序。
• エ.誤り。C→B→AはX側0→6→16→24、Y側6→14→（待機16）→21→31の計31分となる。AをY側最後に回すとY側の待ち時間が増加して非効率になり、ジョンソン法の最適解ではない。BのY時間（5分）が短いにもかかわらず中間に置くことで全体の処理効率が低下する。