応用情報技術者 2010年秋期午前2 問72

問題文

製造業のA社では、NC 工作機械を用いて、四つの仕事を行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで、仕事はどの順序で行ってもよいものとし、FROM からTOへの段取り時間で検討する。

選択肢

ア：4（正解）

イ：5

ウ：6

エ：7

製造業の段取り時間最小化問題【午前2 解説】

要点まとめ

結論：仕事の順序を工夫し、合計段取り時間が最小となるのは4時間である。
根拠：各仕事間の段取り時間を考慮し、全ての順序を比較して最小値を求める問題である。
差がつくポイント：段取り時間はFROM→TOで異なるため、順序の全パターンを検討し最小合計を見つけることが重要。

正解の理由

選択肢アの「4時間」が正解です。
これは4つの仕事の順序を変え、各段取り時間を合計した中で最も小さい値だからです。
例えば、順序 a→c→b→d の場合、段取り時間は a→c(1) + c→b(2) + b→d(2) = 5時間ですが、他の順序を検討すると4時間にまで減らせます。
最適な順序は a→b→c→d で、段取り時間は a→b(2) + b→c(1) + c→d(2) = 5時間ですが、逆に b→a→c→d のようにすると b→a(1) + a→c(1) + c→d(2) = 4時間となり、これが最小です。

よくある誤解

段取り時間は対称的だと誤解しがちですが、FROM→TOで異なるため注意が必要です。
また、単純に隣接する仕事の段取り時間だけでなく、全体の合計を考える必要があります。

解法ステップ

仕事の全ての順列（4! = 24通り）を列挙する。
各順列について、隣接する仕事間の段取り時間をFROM→TOで合計する。
合計段取り時間の最小値を求める。
最小値に対応する順序を確認し、最小合計時間を選択肢から選ぶ。

選択肢別の誤答解説

イ（5時間）：よくある誤りで、単純に a→b→c→d の順序を選びがちだが、最小ではない。
ウ（6時間）：段取り時間の合計を過大評価しているケース。
エ（7時間）：段取り時間の合計を誤って最大値として選んでしまう。
ア（4時間）：正しく全順序を検討し、最小合計を導出している。

補足コラム

この問題は「巡回セールスマン問題（TSP）」の一種で、段取り時間を距離に見立てて最短経路を求める問題です。
ただし、段取り時間が非対称（FROM→TOとTO→FROMで異なる）ため、非対称TSPに分類されます。
実務ではこうした最適化問題を解くために、ヒューリスティックやメタヒューリスティック手法が用いられます。