段取り時間の最小化
出典: 令和6年度 秋期 応用情報技術者試験 午前 問72 (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 時間になる順序もありますが、4 時間で済む順序 (b → a → c → d) があります。
- ウ: 6 時間は最小ではありません。表の小さい値をうまくつなぐと 4 時間になります。
- エ: 7 時間は最小ではありません。
ポイント
- 4 つの仕事を 1 回ずつ行うので、段取りは 3 回です。1 回の段取り時間は最小でも 1 時間なので、合計は最小でも 3 時間です。
- 1 時間の段取りは a→c、b→a、b→c の 3 つだけで、この 3 つだけで 4 つの仕事をつなぐことはできません (d へ行く段取りが入らない)。
- b → a → c → d なら 1 ＋ 1 ＋ 2 = 4 時間 です。これが最小です。