応用情報技術者 2023年 秋期 午前2 問53

作業分割とクリティカルパス【午前2解説】

正解の理由

解法ステップ

1. 元のネットワーク（図1）で各経路の所要日数を求め、クリティカルパス（最長経路）を求める。
   • 上段（A→B→D→G）: $5+8+7+7=27$ 日
   • 下段左（A→C→F→H→I）: $5+7+5+4+2=23$ 日
   • 下段経由（A→B→E→H→I）: $5+8+9+4+2=28$ 日
     よって初期所要日数は $28$ 日（クリティカルパスは A→B→E→H→I）。
2. 図2での分割後（点線を X→Y と解釈）に各ノード到達時刻を前方計算する。
   • Start→A: 5 日
   • A→B: 5+8 = 13 日（円ノード2）
   • 円ノード2→E1→X: 13+3 = 16 日（X到達）
   • X→E3→下段中央: 16+2 = 18 日 → H→I を経て終了: $18+4+2=24$ 日（この経路は24日で終了）
   • 円ノード2→D→円ノード3: 13+7 = 20 日
   • 円ノード3→E2→Y: 20+4 = 24 日（Y到達）
   • 上段の A→B→D→G: 13+7+7 = 27 日（上段は27日で終了）
3. すべての経路の最長をとると、分割後の所要日数は $\max (24,27,23)=27$ 日。
   したがって短縮量は $28-27=1$ 日。結論として選択肢 ア（1日）が正しい。

選択肢別の誤答解説

• ア（1）
  正しい。上記のとおり、点線を X→Y と解釈するとE分割によりEの主部分が並列化され、全体で1日短縮される。
• イ（2）
  誤り。2日短縮とする計算は、E分割後にE部分や他経路の時刻を誤って計算（例えばE1やE3の起点時刻を遅く見積もる、あるいはDやGの所要日を誤る）した結果で生じる。正しい前方計算をすれば24日／27日の比較になるため2日短縮にはならない。
• ウ（3）
  誤り。3日短縮は、Eの分割によって下段経路がさらに短縮されると過大に評価した場合に出やすい値。E1+E3の合計は5日で元のEは9日なので、単純に9→5で4日短縮と誤認する人がいるが、ネットワーク全体の最長経路（クリティカルパス）に着目しないと誤る。
• エ（4）
  誤り。4日短縮は、E全体9日→5日（E1+E3）として下段経路がそのまま4日短縮になると見なした場合に出る。しかしE2の配置や依存関係次第ではその4日が反映されない（または逆に増える）ため、検算が必要。正解は1日。

よくある誤解

• ダミー（点線）矢印の向きを読み間違える
  ダミーの向きは「どちらが先行か」を示す。向きを逆に解釈すると依存関係が変わり、短縮ではなく延長になることがある。
• 分割後の作業時間の単純合算のみで判断する
  作業を分割して合計時間が同じでも、分割によって並列化（重なり）が発生すれば所要日数は変わる。必ず経路ごとの最長時間（クリティカルパス）で比較する。
• ダミーは「時間を消費しない」と考えるが影響がないと誤認する
  ダミーは所要日数0だが、依存関係を作るためプロジェクトの所要日数に影響を与える（開始可能時刻を制約する）。

補足コラム

• 分割後も各作業の合計所要日は等しいか（保存則の確認）
• ダミー矢印の向きが論理的に妥当か（意図通り並列化するか）
• クリティカルパスを再計算して最長経路が短くなっているか確認する

FAQ