問題
問5
機械XとYを使用する作業 A, B, Cがあり、いずれの作業も機械X, 機械Yの順に使用する必要がある。各作業における機械XとYの使用時間が表のとおりであるとき、三つの作業を完了するための総所要時間が最小となる作業の順番はどれか。ここで、図のように機械XとYは並行して使用できるが、それぞれの機械は二つ以上の作業を同時に行うことはできないものとする。
- A→B→C
- A→C→B
- C→A→B
- C→B→A
[出典：ITパスポート試験 平成30年度秋期 問5]
正解
正解は「ウ」です。
解説
この問題は、複数の作業（A, B, C）を2つの機械（XとY）で順次処理する際の、全体の所要時間を最小にするスケジューリングを求めるものです。機械XとYは並行して稼働できますが、各機械は同時に1つの作業しかできません。全ての選択肢について総所要時間を計算し、最も短いものを選びます。計算は、機械Xの作業が終了し、かつ機械Yが前の作業を終えている場合に、機械Yの作業を開始できるというルールで行います。
ウ C→A→Bの場合:
- 機械Xの進捗:
- C: 6分で終了。
- A: 機械XはCの終了後（6分時点）に開始。8分かかるので、6+8=14分で終了。
- B: 機械XはAの終了後（14分時点）に開始。10分かかるので、14+10=24分で終了。
- 機械Yの進捗:
- C: 機械XでのC作業終了後（6分時点）に開始。8分かかるので、6+8=14分で終了。
- A: 機械XでのA作業終了（14分時点）と機械YでのC作業終了（14分時点）のうち、遅い方で開始。両方14分なので、14分に開始。10分かかるので、14+10=24分で終了。
- B: 機械XでのB作業終了（24分時点）と機械YでのA作業終了（24分時点）のうち、遅い方で開始。両方24分なので、24分に開始。5分かかるので、24+5=29分で終了。
総所要時間は29分となり、これが他の選択肢と比較して最も短い時間になります。
ア(A→B→C):
A→B→Cの順で計算すると、総所要時間は32分となります。これは、正解の29分よりも長い時間です。
イ(A→C→B):
A→C→Bの順で計算すると、総所要時間は31分となります。これは、正解の29分よりも長い時間です。
エ(C→B→A):
C→B→Aの順で計算すると、総所要時間は34分となります。これは、正解の29分よりも長い時間です。
難易度
この問題は、複数の作業工程を考慮したスケジューリング計算が必要で、やや複雑に感じるかもしれません。各選択肢について機械XとYの作業時間を一つずつ丁寧に追っていく必要があり、計算ミスを誘発しやすいです。しかし、求められる計算は足し算と最大値の比較だけなので、落ち着いて取り組めば正解にたどり着けます。中程度の難易度と言えるでしょう。
用語補足
ジョンソン法：
複数の作業を2つの連続した工程で処理する際に、全体の所要時間を最小にするためのスケジューリングアルゴリズムです。例えば、料理の準備（切る作業）と調理（焼く作業）のように、どの順番で食材を処理すれば全ての料理が最も早く完成するかを効率的に見つける方法です。
スケジューリング：
資源（人、機械、時間など）が限られている中で、複数のタスクや作業をいつ、どの順番で実行するかを計画することです。例えば、一日の家事を、掃除、洗濯、料理のどの順番で、いつ行うかを決めるようなイメージです。
総所要時間：
ある一連の作業やプロジェクトが開始されてから、全ての作業が完全に終了するまでの合計時間です。例えば、旅行の計画を立ててから、実際に旅行を終えて家に帰るまでの全期間を指します。
並行処理：
複数のタスクや作業が、同時に進められているように見える状態のことです。実際には、コンピュータのCPUが非常に高速に処理を切り替えることで、あたかも同時に実行されているかのように見せたり、複数のCPUが物理的に同時に処理を行ったりします。例えば、料理中に片手で野菜を切りながら、もう片方の手で鍋をかき混ぜるような状況です。
対策
この問題のポイントは、機械XとYが並行して使用できることと、各機械は同時に1つの作業しかできないという制約を正確に理解し、スケジューリングをシミュレーションすることです。特に、機械Yの作業開始時刻は、その作業が機械Xで終了する時刻と、機械Yが前の作業を終える時刻の「遅い方」になることを忘れないでください。全選択肢を丁寧に計算することで、計算ミスを防ぎ、最小時間を導き出せます。
