【解答】
製造業のA社では、NC工作機械を用いて、四つの仕事a～dを行っている。各仕事間の段取り時間は表のとおりである。合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。ここで、仕事はどの順序で行ってもよいものとし、FROM から TO への段取り時間 (仕事a から仕事b へは 2) で検討する。
a b c d
━┳━━━━━━━━━━
a ┃ ＊ ２ １ ２
b ┃ １ ＊ １ ２
c ┃ ３ ２ ＊ ２
d ┃ ４ ３ ２ ＊
a → c に１時間、b → a に1時間があるので、b → a → c は確実と考えられる。
そうすると、あとは d → b とするか、 c → d とするかの２択になる。
d → b は3時間、 c → d は2時間なので、b → a → c → d が最適である。
よって、 1 + 1 + 2 = 4 時間が回答となる。