修了試験 2020-06-14実施分 基本情報技術者試験 問77

解説

正解は2です。 2台の機械で順に加工するときに、全体の加工時間が最短になる順序を求める問題です。 各製品はM1、M2の順に加工し、M1は前の製品が終わればすぐ次の製品を加工できます。 M2は、その製品のM1加工が終わり、かつM2が空いたときに加工を始めます。 各順序について、M2での加工がすべて終わる時刻を求めて比較します。 【計算】 選択肢1（A、C、Bの順）：AはM1で0〜7、M2で7〜10です。 CはM1で7〜11、M2で11〜13です。 BはM1で11〜16、M2で16〜22です。 終了は22です。 選択肢2（B、A、Cの順）：BはM1で0〜5、M2で5〜11です。 AはM1で5〜12、M2で12〜15です。 CはM1で12〜16、M2で16〜18です。 終了は18です。 選択肢3（B、C、Aの順）：BはM1で0〜5、M2で5〜11です。 CはM1で5〜9、M2で11〜13です。 AはM1で9〜16、M2で16〜19です。 終了は19です。 選択肢4（C、B、Aの順）：CはM1で0〜4、M2で4〜6です。 BはM1で4〜9、M2で9〜15です。 AはM1で9〜16、M2で16〜19です。 終了は19です。 最も短いのは、B、A、Cの順の18です。 【選択肢別解説】 1：× A、C、Bの順では、M1の加工時間が長いAを先にするのでM2の待ちが生じます。 さらにM2の時間が長いBが最後になり、終了は22と最も遅くなります。 2：○ B、A、Cの順では、全製品の加工が18で終わり、4つの順序の中で最も短くなります。 3：× B、C、Aの順では、M2の時間が3のAが最後になり、終了は19です。 B、A、Cの順より1長くなります。 4：× C、B、Aの順でも、Aが最後になり終了は19です。 最短の18より長くなります。 【ポイント】 2台の機械の順序付けには、ジョンソン法が使えます。 すべての加工時間の中で最小のものを探し、それがM1なら先頭、M2なら最後に置く操作を繰り返します。 本問では、最小のCのM2（2）でCを最後に、次に小さいAのM2（3）でAをその前に置き、残るBを先頭にしてB、A、Cの順が得られます。