この問題の解説と、これまでの解答の記録です。
機械メーカのS社では，製品Xに組み込むソフトウェア（以下，Xソフトという）の開発作業A～Hを表1のように計画した。ここで，前作業とは当該作業を開始する前に終了していなければならない作業のことであり，各作業は前作業が終了すればすぐに開始する。各作業に掛かった費用は，各作業完了時に計上する。 表1 Xソフト開発の作業
| 作業 | 日数 | 費用 | 前作業 |
|---|---|---|---|
| A | 2 | 5 | なし |
| B | 3 | 7 | A |
| C | 4 | 4 | B |
| D | 4 | 5 | A |
| E | 5 | 6 | D |
| F | 2 | 5 | A |
| G | 6 | 6 | D, F |
| H | 7 | 12 | C, E, G |
図1は，表1に基づいて作成したアローダイアグラムである。 Xソフトの開発が終了する日は, 開始から最短で何日目か。
※ この問題は、解説作成時の検算で公表解答を確認しきれませんでした。判定は IPA 公表の解答どおりです。
16 は経路 A→B→C→H の長さ 2+3+4+7=16 日である。確かに C は9日目に完了するが、H の前作業は C だけでなく E (11日目完了) と G (12日目完了) も含むため、9日目には着手できない。合流点で最も早く終わる前作業に合わせてしまった誤りで、最早結合点時刻は必ず最も遅い前作業に合わせる。
17 になる経路は表1・図1 の依存関係の下では成立しない。G の前作業を F だけと読み違えると A→F→G→H = 2+2+6+7=17 日となるが、表1 の G の前作業は D と F の両方であり、図1 でもその関係が D の終了結合点から F の終了結合点へ向かうダミー作業 (破線) で示されている。所要日数が0だからとダミー作業を無視すると生じる典型的な誤りである。
18 は経路 A→D→E→H の長さ 2+4+5+7=18 日である。E は11日目に完了するが、H の前作業には12日目完了の G が含まれるため、H の開始は12日目まで待たされる。E を通る経路を最長と取り違えており、この経路はクリティカルパスではない。
正解 正解はエ「19」。アローダイアグラムで全体の所要日数を求めるときは、各結合点の最早結合点時刻 (そこに入ってくる作業がすべて終わる最も早い時刻) を開始側から順に計算し、複数の作業が合流する結合点では前作業の完了時刻のうち最も遅いものを採る。表1 と図1 に沿って計算すると次のようになる。まず作業A (2日) は前作業なしなので開始から2日目に完了する。A の後は B・D・F の三方向に分かれる。B (3日) は 2+3=5日目に完了し、その後の C (4日) は 5+4=9日目に完了する。D (4日) は 2+4=6日目に完了し、その後の E (5日) は 6+5=11日目に完了する。F (2日) は 2+2=4日目に完了する。ここで G (6日) の前作業は D と F の両方なので、開始できるのは遅いほうである D の完了、すなわち6日目であり、G は 6+6=12日目に完了する。最後の H (7日) の前作業は C・E・G の三つなので、開始できるのは最も遅い G の完了である12日目であり、H は 12+7=19日目に完了する。これが Xソフト開発の終了日なので答えは19日目となる。裏返して言えば、最長経路 (クリティカルパス) は A→D→G→H で 2+4+6+7=19 日であり、この経路上の作業が1日でも遅れると全体の終了日がそのまま遅れる。