平成30年度 秋期 ITパスポート試験 公開問題 問5 解説 機械使用の最適化

2台の機械を順番に通る複数の作業について、全体の終了時間を最も短くするスケジュールを決めるには、ジョンソン法と呼ばれる手順を用います。表の中のすべての数値から最小値を探し、それが1台目の機械（機械X）の値であればその作業をできるだけ前に、2台目の機械（機械Y）の値であればその作業をできるだけ後ろに配置するのがポイントです。

今回の問題にジョンソン法を適用する手順は以下の通りです。

1. 表にあるすべての数値の中で、最小のものを探します。 作業Bの機械Yにおける5分が最小値です。

2. 最小値がどちらの機械のものか判断し、順番を決めます。 最小値5分は2番目の工程である機械Yの数値なので、作業Bを全体の最後に配置します。 現在の確定順序：[（空き）, （空き）, 作業B]

3. 決定した作業Bを除いた残り（作業A、作業C）の中から、再び最小値を探します。 作業Cの機械Xにおける6分が最小値です。

4. その最小値がどちらの機械のものか判断し、順番を埋めます。 最小値6分は1番目の工程である機械Xの数値なので、作業Cを残っている枠の中で最も前に配置します。 現在の確定順序：[作業C, （空き）, 作業B]

5. 最後に残った作業Aを空いている枠に入れます。 最終的な順序：[作業C, 作業A, 作業B]

この手順によって導き出された C→A→B が、総所要時間を最小にする最適な順番となります。

flowchart TD
    Step1["未配置の作業の中から\n最小の作業時間を見つける"] --> Judge{"その時間は\nどちらの機械か？"}
    Judge -- "機械X（1台目）" --> Front["その作業を\n前から順に詰める"]
    Judge -- "機械Y（2台目）" --> Back["その作業を\n後ろから順に詰める"]
    Front --> Finish{"すべての作業の\n順序が決まったか？"}
    Back --> Finish
    Finish -- "No" --> Step1
    Finish -- "Yes" --> End["最適な作業順序の完成"]

ジョンソン法が有効なのは、この問題のようにすべての作業が同じ順序で2つの工程を通過するフローショップ・スケジューリングと呼ばれる場面です。なぜこの方法で時間が短縮できるのかというと、1台目の機械を早く動かして2台目の待ち時間を減らし、かつ2台目の機械をなるべく最後まで動かし続けることで、2台の機械が並行して稼働する時間を最大化できるからです。

ITパスポート試験では、生産管理やオペレーションズ・リサーチの分野でこのような最適化の手法が問われます。計算そのものよりも、最小値が1番目の機械なら前、2番目の機械なら後ろというルールを覚えているかどうかが正解の分かれ目になります。

• 2台の機械のスケジューリング（ジョンソン法） - 基本情報技術者試験対策
• ジョンソン法（ITパスポート用語辞典）