段取り時間の最小化
出典: 令和4年度 春期 応用情報技術者試験 午前 問73 (IPA)
製造業の 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 |
- ア 4
- イ 5
- ウ 6
- エ 7
正解と解説を見る
正解: ア
- ア: b → a → c → d の順で、段取り時間は 1 ＋ 1 ＋ 2 = 4 時間になるので、正しい答えです。
- イ: 5 時間は、a → c → b → d などの順の場合です。もっと短い順があります。
- ウ: 6 時間は、a → c → d → b などの順の場合です。
- エ: 7 時間は、さらに段取りの大きい順の場合です。
ポイント
a〜d を 1 回ずつ行う順序の中で、FROM → TO の段取り時間の合計が最小になるものを探します。
- 最初の仕事には段取り時間がかからないので、3 回分の段取りを足します。
- b → a (1) → c (1) → d (2) = 4 時間
- 他の順番では 5 時間以上になります (例: a → c → b → d = 1 ＋ 2 ＋ 2 = 5)。
合計は 4 時間です。