基本情報技術者 2015年 春期 午前（科目A） 問78
問題文
三つの製品A、B、Cを、2台の機械M1、M2で加工する。加工は、M1→M2の順で行わなければならない。各製品をそれぞれの機械で加工するのに要する時間は、表のとおりである。
このとき、三つの製品をどの順序で加工すれば、加工を始めてから全製品の加工が終了するまでの時間が最も短くなるか。ここで、ある製品のM1での加工が終了したとき、別製品を続けてM1で加工することができるものとする。
選択肢
ア：A → C → B
イ：B → A → C（正解）
ウ：B → C → A
エ：C → B → A
🔒 解説は解答すると表示されます
フローショップの最短順序【午前解説】
正解の理由
本問題は「2台の機械（M1→M2）のフローショップで全完了時間（makespan）を最小化する問題」であり、ジョンソンの法則（Johnson’s rule）が最適解を与えます。ジョンソンの手順に従うと、M1 と M2 の加工時間を比較して前後に配置することで最短順序が求まります。与えられた加工時間は次の通りです。
- A: M1 = , M2 =
- B: M1 = , M2 =
- C: M1 = , M2 =
ジョンソンのルール適用結果は、前方群に B（M1≤M2）、後方群に A,C（M1>M2）を入れ、後方群は M2 の降順に並べるため最終順序は イ: B → A → C となります。実際にスケジュールをシミュレーションすると全完了時間は となり、他の順序より短くなります。
解法ステップ
- 各製品の M1 と M2 の加工時間を表にする（A(7,3), B(5,6), C(4,2)）。
- 各製品について M1 ≤ M2 なら「前方群」、M1 > M2 なら「後方群」に振り分ける。
- 前方群：B（5 ≤ 6）
- 後方群：A（7 > 3）、C（4 > 2）
- 前方群は M1 の昇順、後方群は M2 の降順に並べる。
- 前方群（昇順）→ B
- 後方群（降順）→ A（M2=3）、C（M2=2）
- 最終順序 = 前方群 の順序 + 後方群 の順序 → B → A → C。
- 順序を実際にガントチャートでシミュレーションし、makespan（全完了時間）を計算して確認する（＝）。
選択肢別の誤答解説
- ア: A → C → B
- M1 時間の累積：A –, C –, B –
- M2 開始終了：A –, C –, B – → makespan = （非最短）
- イ: B → A → C（正解）
- M1: B –, A –, C –
- M2: B –, A –, C – → makespan = （最短）
- ウ: B → C → A
- M1: B –, C –, A –
- M2: B –, C –, A – → makespan =
- エ: C → B → A
- M1: C –, B –, A –
- M2: C –, B –, A – → makespan =
それぞれシミュレーションすると イ が最短であることが確認できます。
よくある誤解
- ジョンソンの法則を知らずに単純に M1 の短い順や M2 の短い順で並べると最適にならないことがある点。局所最短が全体最短とは限りません。
- 後方配置群を M2 の降順ではなく昇順で並べてしまう誤り。後ろから処理される製品は M2 が長い順に置く必要があります。
- M2 が空いている間に前作業を割り込ませる「非順序スケジュール」を考えてしまうが、2機械フローショップの最短はジョンソンで得られる順序（順序保持）で十分です。
補足コラム
ジョンソンの法則は「2台の機械のフローショップ問題（順序同一）」に対して常に最適解を与える古典的アルゴリズムです。手順は単純で計算量は O(n log n)（ソートによる）程度。3台以上ではこの単純なルールは一般に最適ではなく、拡張やヒューリスティック（例：Campbell等の手法）を使います。試験対策では、まずジョンソンの手順を確実に手で適用できるようにし、結果の makespan を素早く計算して確認する練習が有効です。
FAQ
Q1. 時間が同じ場合の扱いは？
A1. 同値のときはどちらへ入れてもジョンソンの手順は崩れません。前方群・後方群のどちらに入るかで処理が変わる場合は、問題によってどちらでも最適となることがあります。
Q2. 3台以上の機械どうする？
A2. ジョンソンは2台専用。3台以上は問題が NP困難になり、分割やヒューリスティック、近似手法を用います。
Q3. makespan の手順でよく間違う点は？
A3. M2 は M1 の終了を待たないと作業できない点や、M2 が空いている時間ができる（待ちが生じる）ことを忘れて累積のみで計算してしまうミスに注意してください。
A1. 同値のときはどちらへ入れてもジョンソンの手順は崩れません。前方群・後方群のどちらに入るかで処理が変わる場合は、問題によってどちらでも最適となることがあります。
Q2. 3台以上の機械どうする？
A2. ジョンソンは2台専用。3台以上は問題が NP困難になり、分割やヒューリスティック、近似手法を用います。
Q3. makespan の手順でよく間違う点は？
A3. M2 は M1 の終了を待たないと作業できない点や、M2 が空いている時間ができる（待ちが生じる）ことを忘れて累積のみで計算してしまうミスに注意してください。
関連キーワード: ジョンソンの法則、フローショップ、スケジューリング、ガントチャート、加工時間、順序最適化、二段工程、機械加工、所要時間計算
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！