三つの製品A，B，Cを，2台の機械M1，M2で加工する。
加工は，M1→M2の順で行わなければならない。
各製品をそれぞれの機械で加工するのに要する時間は，表のとおりである。
このとき，三つの製品をどの順序で加工すれば，加工を始めてから全製品の加工が終了するまでの時間が最も短くなるか。
ここで，ある製品のM1での加工が終了したとき，別製品を続けてM1で加工することができるものとする。
製品＼機械｜M1｜M2／A｜7｜3／B｜5｜6／C｜4｜2
正答2
解説
正解は2です。
2台の機械M1、M2を同じ順で使う加工の順序を決める問題です。
各順序について、M1とM2の作業の流れを追って全体の終了時刻を求めます。
表は、行が製品A、B、C、列が機械M1、M2の加工時間です。
【計算】
B、A、Cの順では、M1はBを0〜5、Aを5〜12、Cを12〜16で加工します。
M2はBを5〜11、Aを12〜15、Cを16〜18で加工し、全体は18で終わります。
A、C、Bの順では、M1は0〜7、7〜11、11〜16で加工します。
M2はAを7〜10、Cを11〜13、Bを16〜22で加工し、全体は22で終わります。
B、C、Aの順では、M2の最後のAが16〜19となり、全体は19で終わります。
C、B、Aの順では、M2の最後のAが16〜19となり、全体は19で終わります。
【選択肢別解説】
1：× 加工時間の長いBを最後に回すため、M2の待ちが生じ、全体で22かかります。
2：○ B、A、Cの順では、全体で18となり、最も短くなります。
3：× Aを最後に回すと、M1でのAの加工が16まで終わらず、全体で19かかります。
4：× この順でもAが最後になるため、全体で19かかります。
【ポイント】
2台の機械の順序付けには、ジョンソン法という解法があります。
最小の加工時間がM1側にある製品は前から、M2側にある製品は後ろから並べます。
この問題では、Cの2（M2）が最小なのでCを最後、次にAの3（M2）なのでAをその前、残るBを先頭とし、B、A、Cの順になります。