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

正解

ウ. C→A→B

正答率 65.0%（1,290人中 838人が正解）

問題の解説

ジョンソン法（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分）が短いにもかかわらず中間に置くことで全体の処理効率が低下する。