この問題の解説と、これまでの解答の記録です。
機械 X と Y を使用する作業 A, B, C があり, いずれの作業も機械 X, 機械 Y の順に使用する必要がある。各作業における機械 X と Y の使用時間が表のとおりであるとき, 三つの作業を完了するための総所要時間が最小となる作業の順番はどれか。ここで, 図のように機械 X と Y は並行して使用できるが, それぞれの機械は二つ以上の作業を同時に行うことはできないものとする。 表 各作業における機械 X と Y の使用時間
| 機械 X の使用時間 | 機械 Y の使用時間 | |
|---|---|---|
| 作業A | 8分 | 10分 |
| 作業B | 10分 | 5分 |
| 作業C | 6分 | 8分 |
機械X｜作業A (8分)｜作業B (10分)｜作業C (6分) 機械Y｜ 作業A (10分)｜作業B (5分)｜作業C (8分) 図 機械使用スケジュール (A→B→C の順で作業したときの例)
A→B→C の順では、機械X: A 0〜8分、B 8〜18分、C 18〜24分。機械Y: A 8〜18分、B 18〜23分、C 24〜32分。総所要時間は 32分で、ウの 29分より長く最小ではありません。
A→C→B の順では、機械X: A 0〜8分、C 8〜14分、B 14〜24分。機械Y: A 8〜18分、C 18〜26分、B 26〜31分。総所要時間は 31分で、ウの 29分より長く最小ではありません。
正解 各作業は機械 X → 機械 Y の順で使い、機械 Y はその作業自身の X が終わり、かつ直前の作業の Y が空いてから開始できます。総所要時間を短くするには機械 Y の待ち時間(遊休)を減らすのが要点で、これはジョンソン法で求められます。各作業の X・Y 使用時間のうち最小の値に注目し、最小が前工程 X 側なら前へ、後工程 Y 側なら後ろへ並べます。作業C(最小6=X)と作業A(最小8=X)は前へ、作業B(最小5=Y)は後ろへ、前の群は X の短い順に C→A と並ぶので順序は 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分。最後の作業A(Y=10分)が末尾に来て機械Yの終了が遅れ、総所要時間は 34分と四つの中で最も長くなります。