ダミー作業を含むアローダイアグラムの所要日数の求め方
基本情報技術者試験 令和6年度 問13 ／ プロジェクトマネジメント › プロジェクトの時間
過去問にチャレンジ
アローダイアグラムで表されるプロジェクトは，完了までに最少で何日を要するか。
- ア
105
- イ
115
- ウ
120
- エ
125
会話形式の解説
講師今回はアローダイアグラムから、プロジェクトが完了するまでの最短日数を求める問題です。注目してほしいのは点線の矢印、つまりダミー作業です。所要日数は0日ですが、作業の順番の決まりを表しています。
受験者最短日数と聞くと、一番短い経路を選べばよい気がしてしまいます。でも、そういうことではないのですよね。
講師はい。すべての作業が終わらないとプロジェクトは完了しないので、最短の完了日数は、開始から終了までで最も長い経路の日数になります。この経路をクリティカルパスと呼びます。
受験者では、経路を全部書き出して、一番長いものを探せばよいのでしょうか。私は計算に時間がかかるので、経路を見落としそうで不安です。
講師見落としを防ぐには、結合点、つまり丸印ごとに最早結合点時刻を前から求めていく方法がおすすめです。最早結合点時刻は、その結合点から次の作業を最も早く始められる日のことです。矢印が1本だけ入るなら足し算、複数入るなら到着時刻の最大値を取ります。
受験者やってみます。Aが終わるのが30日、Bの終点は30+5で35日です。Cの終点には、Cから来る60日と、Bの終点からのダミーで来る35日が入るので、大きいほうの60日ですか。
講師そのとおりです。次はGの始点です。ここにはDからの矢印と、Cの終点からのダミーが入っています。
受験者Dからは30+20で50日、ダミーからは60日なので、60日です。ダミーがなかったら50日になるところでした。
講師そこが大事な点です。続けて、E・F・Gが合流する結合点はどうなりますか。
受験者Eからは35+40で75日、Fからは60+25で85日、Gからは60+30で90日です。最大値は90日で、最後にHの30日を足すと120日になります。
講師正解です。経路でいうと、A、C、ダミー、G、Hと進む30+30+0+30+30=120日がクリティカルパスです。ほかの選択肢の数値も確認しましょう。105日は、A、B、E、Hの経路の合計です。これより長い経路があるので、全体の完了日数にはなりません。
受験者115日は、A、C、F、Hの合計ですね。でもHは、Gを通る120日の経路が終わるまで始められないので、足りないということですか。
講師そうです。しかも115日は、ダミーを無視したときの答えと同じ値になります。Gの始点を50日とすると、合流点はmax(75,85,80)=85日で、85+30=115日になってしまいます。典型的な引っかけです。
受験者125日はどこから出てくるのでしょうか。どの経路を足しても見当たりませんでした。
講師どの経路をたどっても、合計が125日になることはありません。並行して進む先行作業は足し合わせず最大値を取るので、余分な日数が加わることもありません。参考までに、全経路は105日、90日、95日、115日、120日、110日で、最長は120日です。
受験者まとめると、合流点では最大値を取ること、ダミーは0日でも先行関係として必ず計算に入れること、の2点が大事なのですね。
講師はい。ダミーの矢印は「この作業が終わるまで次は始められない」という意味だと覚えておけば、読み落としにくくなります。試験では結合点の横に最早時刻を書き込みながら進めると、計算が速く正確になります。
まとめ
プロジェクトの最短完了日数は、開始から終了までで最も長い経路（クリティカルパス）の日数に等しくなります。この問題では、結合点ごとに最早結合点時刻を前から求め、複数の矢印が入る結合点では最大値を取ります。ダミー作業は0日ですが先行関係を表すため、Gの始点はD経由の50日ではなくダミー経由の60日になります。E・F・Gの合流点は90日で、Hの30日を足すと120日が正解です。ダミーを無視すると115日になってしまうので、典型的な引っかけとして注意が必要です。
解答・解説
正解はウです
この問題のテーマ
ダミー作業を含むアローダイアグラムから、プロジェクトが完了するまでに最短で何日かかるか、つまりクリティカルパスの所要日数を求める問題です。
解き方の考え方
開始の結合点から順に「最早結合点時刻」を計算します。矢印が1本だけ入る結合点では、前の時刻に作業日数を足します。複数の矢印が入る結合点では、到着時刻のうち最大の値を取ります。ダミー作業は0日ですが、先行関係を表すので必ず考慮します。図ではBの終点からCの終点へ、Cの終点からGの始点へダミーが引かれています。
計算は次のとおりです。Aの完了は0+30=30日です。Bの終点は30+5=35日です。Cの終点には、C経由の30+30=60日とダミー経由の35日が入るので、max(60,35)=60日になります。Gの始点には、D経由の30+20=50日とダミー経由の60日が入るので60日です。E・F・Gが合流する結合点は、max(35+40, 60+25, 60+30)=max(75,85,90)=90日です。最後にHの30日を足し、90+30=120日となります。これは正解のウと一致します。
選択肢ごとの解説
- ×ア 105105日は、A→B→E→Hの経路の合計（30+5+40+30=105）です。これより長い経路があるため、プロジェクト全体の最短完了日数にはなりません。
- ×イ 115115日は、A→C→F→Hの経路の合計（30+30+25+30=115）です。ただしHは、Gを通る経路（120日）が終わるまで始められません。そのため115日では足りません。
- ○ウ 120A→C→ダミー→G→Hの合計は30+30+0+30+30=120日で、これが最長の経路（クリティカルパス）です。結合点ごとに最早時刻を計算しても、合流点の90日にHの30日を足して120日となり、結果が一致します。
- ×エ 125どの経路をたどっても合計が125日になることはありません。並行して進む先行作業は足し合わせず最大値を取るので、余分な日数が加わることもありません。
補足
ダミーを無視すると、Gの始点はD経由の50日となり、合流点はmax(75,85,80)=85日、完了は115日と計算してしまいます。これはイと同じ値になるので、典型的な引っかけと言えます。参考までに全経路を挙げると、A→B→E→Hが105日、A→B→ダミー→F→Hが90日、A→B→ダミー→ダミー→G→Hが95日、A→C→F→Hが115日、A→C→ダミー→G→Hが120日、A→D→G→Hが110日で、最長は120日です。
POINT
- プロジェクトの最短完了日数は、開始から終了までで最も長い経路（クリティカルパス）の所要日数に等しくなります。
- 複数の矢印が入る結合点の最早時刻は、到着時刻の合計ではなく最大値を取ります。
- ダミー作業の所要日数は0日ですが、「この作業が終わるまで次は始められない」という先行関係を表します。
- 経路を全部書き出すより、結合点ごとに最早時刻を前から順に求めるほうが、見落としが少なくなります。