問題プレビューID: ab42e971基本情報技術者試験 午前免除試験 2019年1月27日

問 76
基本情報技術者試験 午前免除試験 2019年1月27日

三つの製品 A,B,C を,2 台の機械 M1,M2 で加工する。加工は,M1 → M2 の順で行わなければならない。各製品をそれぞれの機械で加工するのに要する時間は,表のとおりである。

このとき,三つの製品をどの順序で加工すれば,加工を始めてから全製品の加工が終了するまでの時間が最も短くなるか。ここで,ある製品の M1 での加工が終了したとき,別製品を続けて M1 で加工することができるものとする。

製品 \ 機械M1M2
A73
B56
C42
解説

正解は「イ」です。

2 台の機械を M1 → M2 の順に通過するジョブの総処理時間を最小にするには,ジョンソン法を用います。手順は次のとおりです。

  1. 全製品の中で加工時間が最小のものを選ぶ。
  2. その時間が前工程(M1)なら最初に,後工程(M2)なら最後に配置する。
  3. その製品を除いて繰り返す。

全体の最小値は製品 C の M2(2 分)で後工程なので,C を最後に配置します。次に,残りの A,B のうち最小値は製品 A の M2(3 分)で後工程なので,A を残りの最後に配置します。残った B を最初に配置します。したがって,最適な順序は B → A → C となり,総所要時間は 18 分です。

  • ア・ウ・エ: これらの順序では M2 の待ち時間が生じ,総所要時間が 18 分より長くなります。

関連問題

本文が同じ・似ている問題を表示しています