平成30年度 秋期 ITパスポート 問5（ストラテジ）
出典：平成30年度 秋期 ITパスポート試験 公開問題 問5（独立行政法人情報処理推進機構（IPA））
機械XとYを使用する作業A，B，Cがあり，いずれの作業も機械X，機械Yの順に使用する必要がある。各作業における機械XとYの使用時間が表のとおりであるとき，三つの作業を完了するための総所要時間が最小となる作業の順番はどれか。ここで，図のように機械XとYは並行して使用できるが，それぞれの機械は二つ以上の作業を同時に行うことはできないものとする。
- アA→B→C
- イA→C→B
- ウC→A→B
- エC→B→A
正解と解説を見る
正解：ウ
【作業の順番と総所要時間】
どの作業も、機械X、機械Yの順に使います。機械Xと機械Yは並行して使えますが、それぞれの機械は同時に1つの作業しかできません。そのため、ある作業の機械Yでの作業は、その作業の機械Xでの作業が終わり、かつ、機械Yが空いてから始めます。
【表の値】
・作業A：機械X 8分、機械Y 10分
・作業B：機械X 10分、機械Y 5分
・作業C：機械X 6分、機械Y 8分
【各順番の総所要時間】
ア：A→B→C（図の例）
・機械X：A 0〜8分、B 8〜18分、C 18〜24分
・機械Y：A 8〜18分、B 18〜23分、C 24〜32分
総所要時間は32分です。
イ：A→C→B
・機械X：A 0〜8分、C 8〜14分、B 14〜24分
・機械Y：A 8〜18分、C 18〜26分、B 26〜31分
総所要時間は31分です。
ウ：C→A→B
・機械X：C 0〜6分、A 6〜14分、B 14〜24分
・機械Y：C 6〜14分、A 14〜24分、B 24〜29分
総所要時間は29分です。
エ：C→B→A
・機械X：C 0〜6分、B 6〜16分、A 16〜24分
・機械Y：C 6〜14分、B 16〜21分、A 24〜34分
総所要時間は34分です。
総所要時間が最小になるのは、C→A→Bの29分です。機械Xの時間が短い作業を先にして機械Yを早く動かし始め、機械Yの時間が短い作業を最後にすると、総所要時間が短くなります。
よって、正解は選択肢ウです。