NC工作機械における段取り替え時間の総和最小化（巡回問題）

正解は ア （4時間）です。 4つの仕事を1回ずつ行うと、段取り替えは3回です。表で段取り時間が1時間の組（a→c、b→a、b→c）を できるだけつなげる 順序を探します。 順序 段取り時間 合計 b → a → c → d 1＋1＋2 4 a → c → b → d 1＋2＋2 5 b → c → a → d 1＋3＋2 6 d → c → b → a 2＋2＋1 5 1時間の組を3つ全てつなぐ順序は無い（b からは a か c の一方にしか進めない）ので、1時間を2回使う b → a → c に、c → d（2時間）を続けた4時間が最小です。

製造業の 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

-

出典令和6年度 秋期 応用情報技術者試験 午前 問72
ア
4
イ
5
ウ
6
エ
7