応用情報技術者 2024年 秋期 午前2 問72
問題文
製造業のA社では、NC工作機械を用いて、四つの仕事a〜dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで、仕事はどの順序で行ってもよく、a〜dを一度ずつ行うものとし、FROMからTOへの段取り時間で算出する。
選択肢
ア：4（正解）
イ：5
ウ：6
エ：7
製造業の段取り時間最小化問題【午前2 解説】
要点まとめ
- 結論：仕事a〜dの順序を工夫し、合計段取り時間が最小となるのは4時間である。
- 根拠：全ての仕事順列を検討し、FROM→TOの段取り時間を合計して最小値を求める問題である。
- 差がつくポイント：段取り時間の表を正確に読み取り、全順列を漏れなく比較できるかが鍵となる。
正解の理由
ア: 4が正解です。
4つの仕事の順序は全部で24通り（4!）ありますが、段取り時間表を基に各順序の合計段取り時間を計算すると、最小値は4時間となります。例えば、仕事a→c→b→dの順序では、a→cが1時間、c→bが2時間、b→dが2時間で合計5時間ですが、a→b→c→dの順序ではa→bが2時間、b→cが1時間、c→dが2時間で合計5時間です。最小値はさらに別の順序で4時間となるため、選択肢の中で最も小さい4時間が正解です。
4つの仕事の順序は全部で24通り（4!）ありますが、段取り時間表を基に各順序の合計段取り時間を計算すると、最小値は4時間となります。例えば、仕事a→c→b→dの順序では、a→cが1時間、c→bが2時間、b→dが2時間で合計5時間ですが、a→b→c→dの順序ではa→bが2時間、b→cが1時間、c→dが2時間で合計5時間です。最小値はさらに別の順序で4時間となるため、選択肢の中で最も小さい4時間が正解です。
よくある誤解
段取り時間の表のFROMとTOの方向を逆に読み間違え、誤った合計時間を計算してしまうことがあります。
また、全ての順列を検討せずに一部だけで判断し、最小値を見逃すことも多いです。
また、全ての順列を検討せずに一部だけで判断し、最小値を見逃すことも多いです。
解法ステップ
- 仕事a〜dの全ての順列（4! = 24通り）をリストアップする。
- 各順列について、隣接する仕事間の段取り時間を表から読み取る。
- それらの段取り時間を合計し、最小値を記録する。
- 最小の合計段取り時間を選択肢と照合し、正解を決定する。
選択肢別の誤答解説
- イ: 5時間はよくある計算ミスの結果で、特定の順序での合計時間だが最小値ではない。
- ウ: 6時間は段取り時間を過大に見積もった場合の誤答。
- エ: 7時間は段取り時間の方向を誤認したり、重複計算した場合に出やすい。
- ア: 4時間は全順列を正確に検討した結果の最小値であり正解。
補足コラム
この問題は「巡回セールスマン問題（TSP）」の簡易版と考えられます。
段取り時間を最小化するために全順列を検討するのは小規模問題に有効ですが、仕事数が増えると計算量が爆発的に増加するため、ヒューリスティックや近似アルゴリズムが必要になります。
段取り時間を最小化するために全順列を検討するのは小規模問題に有効ですが、仕事数が増えると計算量が爆発的に増加するため、ヒューリスティックや近似アルゴリズムが必要になります。
FAQ
Q: なぜ全ての順列を調べる必要があるのですか？
A: 段取り時間は仕事の順序によって大きく変わるため、最小値を見つけるには全順列を比較する必要があります。
A: 段取り時間は仕事の順序によって大きく変わるため、最小値を見つけるには全順列を比較する必要があります。
Q: 段取り時間表のFROMとTOの意味は？
A: 「FROM→TO」の段取り時間を示しており、仕事の切り替えにかかる時間を表しています。
A: 「FROM→TO」の段取り時間を示しており、仕事の切り替えにかかる時間を表しています。
関連キーワード: 段取り時間、順列、最小化問題、巡回セールスマン問題、組合せ最適化
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！