企業活動
平成27年度 春期 基本情報技術者試験 午前 問78
三つの製品 A, B, C を，2 台の機械 M1, M2 で加工する。加工は，M1→M2 の順で行わなければならない。各製品をそれぞれの機械で加工するのに要する時間は，表のとおりである。
このとき，三つの製品をどの順序で加工すれば，加工を始めてから全製品の加工が終了するまでの時間が最も短くなるか。ここで，ある製品の M1 での加工が終了したとき，別製品を続けて M1 で加工することができるものとする。
加工時間表（行＝製品，列＝機械）:
| 製品＼機械 | M1 | M2 |
|---|---|---|
| A | 7 | 3 |
| B | 5 | 6 |
| C | 4 | 2 |
答えを選ぶ
出典：平成27年度 春期 基本情報技術者試験 午前 問78（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：イ
覚える知識
ジョンソン法による2工程加工順序の最短化
2工程の総所要時間を最短にするには、M1 時間が M2 以下の製品を M1 昇順で先、残りを M2 降順で後に並べる(ジョンソン法)。
この問題で必要なこと
M1 で先に短く終わる製品を先、M2 の短い製品を後にする。B→A→C だと M1 が 16、M2 完了が 18 分で最短になる。
ひっかけ
単純に加工時間の短い順に並べて誤る。
この知識の出題：本試験系 1 回・免除試験 7 回（公開問題での観測値）