製造業のA社では，NC工作機械を用いて，四つの仕事a〜dを行っている。
各仕事間の段取り時間は表のとおりである。
合計の段取り時間が最小になるように仕事を行った場合の合計段取り時間は何時間か。
ここで，仕事はどの順序で行ってもよく，a〜dを一度ずつ行うものとし，FROMからTOへの段取り時間で算出する。
〔段取り時間表（単位 時間）〕TO：仕事a／仕事b／仕事c／仕事d
FROM＝仕事a：－／2／1／2
FROM＝仕事b：1／－／1／2
FROM＝仕事c：3／2／－／2
FROM＝仕事d：4／3／2／－
正答1
解説
正解は1です。
段取り時間表から、四つの仕事を一度ずつ行うときの合計段取り時間の最小値を求める問題です。
仕事の順序で段取り時間が変わるので、短い段取りがつながる順序を探します。
段取り時間が1時間なのは、aからc、bからa、bからcの三つだけです。
【計算】
仕事は四つなので、段取りは3回発生します。
dへの段取り（a、b、cから）はどれも2時間です。
dからの段取り（a、b、cへ）も2時間以上です。
dはどこかで必ず行うので、少なくとも1回は2時間以上の段取りが入ります。
したがって、合計は1＋1＋2＝4時間より短くなりません。
b、a、c、dの順にすると、bからaが1、aからcが1、cからdが2です。
合計＝1＋1＋2＝4時間となり、これが最小です。
【選択肢別解説】
1：○ b、a、c、dの順で合計4時間となり、これが最小です。
2：× 5時間になる順序はありますが、最小ではありません。
例えばa、c、b、dは1＋2＋2＝5時間です。
3：× 6時間は最小値より大きい値です。
b、a、c、dの順にすればさらに短くできます。
4：× 7時間は最小値より大きい値です。
例えばd、a、c、bは4＋1＋2＝7時間で、dからの段取りが長く合計が大きくなります。
【ポイント】
段取りの回数は仕事の数より1少ないことに注意しましょう。
表の中で小さい値を探し、それをつなげる順序から考えると効率的です。