製造業のA社では，NC工作機械を用いて，四つの仕事a〜dを行っている。
各仕事間の段取り時間は表のとおりである。
合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。
ここで，仕事はどの順序で行ってもよく，a〜dを一度ずつ行うものとし，FROMからTOへの段取り時間で検討する。
（表：単位 時間、行＝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
解説
正解は1です。
四つの仕事a〜dを1回ずつ行うので、仕事と仕事の間の段取りは3回です。
表の行がFROM（直前の仕事）、列がTO（次の仕事）で、例えばaからbへの段取り時間は2時間です。
3回の段取り時間の合計が最小になる順序を探します。
【計算】
表で段取り時間が1時間なのは、aからc、bからa、bからcの三つだけです。
bからa（1時間）、aからc（1時間）と続ければ、1時間の段取りを2回連続で使えます。
最後にcからd（2時間）を行うと、合計は1＋1＋2＝4時間です。
一方、dに入る段取りもdから出る段取りも全て2時間以上なので、どの順序でも合計は少なくとも2＋1＋1＝4時間です。
したがって、b、a、c、dの順で行ったときの4時間が最小です。
【選択肢別解説】
1：○ b、a、c、dの順に行うと、段取り時間は1＋1＋2＝4時間です。
dに関わる段取りは必ず2時間以上かかるので、これより小さくはなりません。
2：× 5時間になる順序は、例えばa、b、c、d（2＋1＋2）です。
4時間で済む順序があるので、最小ではありません。
3：× 6時間になる順序は、例えばa、b、d、c（2＋2＋2）です。
4時間で済む順序があるので、最小ではありません。
4：× 7時間になる順序は、例えばd、a、b、c（4＋2＋1）です。
4時間で済む順序があるので、最小ではありません。
【ポイント】
全ての順序（4つなら24通り）を書き出すのは時間がかかるので、短い段取り時間をつなげられる順序から試すのが効率的です。
必ずかかる段取り時間の下限を考えると、見つけた答えが最小かどうかを確かめられます。