平成24年度 秋期 応用情報技術者試験 午前 問73
製造業のA社では，NC工作機械を用いて，四つの仕事a〜dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで，仕事はどの順序で行ってもよく，a〜dを一度ずつ行うものとし，FROMからTOへの段取り時間で検討する。
単位 時間
| FROM＼TO | 仕事a | 仕事b | 仕事c | 仕事d |
|---|---|---|---|---|
| 仕事a | － | 2 | 1 | 2 |
| 仕事b | 1 | － | 1 | 2 |
| 仕事c | 3 | 2 | － | 2 |
| 仕事d | 4 | 3 | 2 | － |
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：ア
4つの仕事を1回ずつ行うので，段取りは3回発生します。段取り時間の最小値は1時間なので，合計は少なくとも3時間ですが，1時間の段取り（a→c，b→a，b→c）だけでは4つの仕事をつなげられません。
そこで，1時間の段取りをできるだけ多く使う順序を考えます。
- b → a → c → d：1 + 1 + 2 = 4時間
他の順序も確認すると，例えば
- a → c → b → d：1 + 2 + 2 = 5時間
- b → c → d → a：1 + 2 + 4 = 7時間
- d → c → b → a：2 + 2 + 1 = 5時間
となり，どの順序でも4時間を下回ることはありません（仕事dへ入る段取りも仕事dから出る段取りも最小2時間なので，dを最後にして1時間の段取りを2回使う b→a→c→d が最小です）。
したがって，最小の合計段取り時間は4時間です。
答え
ア: 4
出典：平成24年度 秋期 応用情報技術者試験 午前 問73
