平成27年度 春期 基本情報技術者試験 午前 問78
ストラテジ／企業活動三つの製品A，B，Cを，2台の機械M1，M2で加工する。加工は，M1→M2の順で行わなければならない。各製品をそれぞれの機械で加工するのに要する時間は，表のとおりである。 このとき，三つの製品をどの順序で加工すれば，加工を始めてから全製品の加工が終了するまでの時間が最も短くなるか。ここで，ある製品のM1での加工が終了したとき，別製品を続けてM1で加工することができるものとする。 〔機械での加工時間〕製品A：M1＝7，M2＝3 製品B：M1＝5，M2＝6 製品C：M1＝4，M2＝2 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成27年度 春期 基本情報技術者試験 午前 問78
- アA→C→B
- イB→A→C
- ウB→C→A
- エC→B→A
正解：イ
解説
2台の機械による加工順序の最適化はジョンソン法で求めることができます。各製品についてM1とM2の加工時間のうち短い方を求めると，Aは3（M2），Bは5（M1），Cは2（M2）です。M1の時間が短い製品（B）は加工順の前方に，M2の時間が短い製品（A，C）は加工順の後方に，M2の時間が長い順（A＝3，C＝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となって最短になります。
選択肢ごとの解説
- ア誤り。A→C→Bの順で計算すると，完了時刻は22となり，B→A→C（18）より長くなってしまいます。
- イ正しい。ジョンソン法に基づき，M1の加工時間が短い製品（B）を先頭に，M2の加工時間が短い順に他の製品（A，C）を後方に並べたB→A→Cが，全体の完了時刻18で最短になります。
- ウ誤り。B→C→Aの順で計算すると，完了時刻は19となり，B→A→C（18）より長くなってしまいます。
- エ誤り。C→B→Aの順で計算すると，完了時刻は19となり，B→A→C（18）より長くなってしまいます。