応用情報技術者 2016年 秋期 午前2 問52

最遅開始時刻【午前2解説】

正解の理由

解法ステップ

1. ネットワークをノード単位で前方（最早）計算する。各アクティビティの最早開始（ES）＝所属ノードの最早時刻、最早終了（EF）＝ES＋所要日数。次ノードの最早時刻はそのノードへ入る活動のEFの最大値。
   • ノード1（開始）: 時刻 $0$。
   • A (1→2, 8): ES=0, EF=8 → ノード2最早=8
   • B (1→3, 5): ES=0, EF=5 → ノード3最早=5
   • C (1→5, 12): ES=0, EF=12 → ノード5候補=12
   • D (2→4,10): ES=8, EF=18 → ノード4候補=18
   • E (3→4,9): ES=5, EF=14 → ノード4候補=14 → ノード4最早 = max(18,14) = 18
   • ダミー (4→5,0): ノード4最早=18 → ノード5候補=18 → ノード5最早 = max(12,18) = 18
   • G (4→7,12): ES=18, EF=30 → ノード7候補=30
   • F (2→7,8): ES=8, EF=16 → ノード7候補=16
   • H (5→6,5): ES=18, EF=23 → ノード6最早=23
   • I (6→7,4): ES=23, EF=27 → ノード7候補=27 → ノード7最早 = max(30,16,27) = 30
   • よってプロジェクトの最短所要日数 = 30日（クリティカルパスは1→2→4→7）。
2. 後方（最遅）計算を行う。終点ノードの最遅終了（LF）はプロジェクト所要日数に等しい（ここでは30）。各アクティビティの最遅開始（LS）＝LS（終点ノード）＝LF−所要日数。始点ノードの最遅時刻は各出口のLSの最小値。
   • ノード7 LF = 30
   • 各終端活動のLS:
     • G (4→7,12): LS_G = 30−12 = 18 → ノード4 LF ≤ 18
     • F (2→7,8): LS_F = 30−8 = 22 → ノード2 LF ≤ 22
     • I (6→7,4): LS_I = 30−4 = 26 → ノード6 LF ≤ 26
   • ノード4 LF = 18（G の LS＝18 と、ダミー（4→5）経由のノード5 LF＝21 の小さい方）
   • D (2→4,10): LS_D = 18−10 = 8 → ノード2 LF ≤ 8（ただしノード2は他の出口との最小をとる）
   • E (3→4,9): LS_E = 18−9 = 9 → ノード3 LF = 9
   • ノード2の出口LSはDが8、Fが22 → ノード2 LF = min(8,22) = 8
   • ノード6 LF = 26（Iにより）
   • H (5→6,5): LS_H = 26−5 = 21 → ノード5 LF ≤ 21
   • C (1→5,12): LS_C = ノード5 LF −12 = 21−12 = 9 → ノード1 LFの候補
   • 最終的にHの最遅開始はLS_H = 21
3. 作業Hを遅くとも開始しなければならない時刻はLS_H = 21日であるため、選択肢は エ（21）。

選択肢別の誤答解説

• ア: 12
  誤りの典型は「作業Cの最早終了（12）」と混同してHの最遅開始とすることです。12はダミー（4→5）を無視したときの作業Hの最早開始です。実際にはHはダミーを通じて作業Dの完了も待つので、最早開始は18日です。いずれにしても“遅くとも開始しなければならない時刻”ではありません。
• イ: 14
  どこかの途中ノードの最早／最遅時刻の差を誤って採用した値です。ネットワーク全体の後方計算を行わず局所的に計算すると出やすい誤答です。
• ウ: 18
  18は作業Hの最早開始（ノード5の最早時刻）です。Hは18日後から開始できますが、遅くとも開始しなければならない時刻は後方計算で求める21日です。
• エ: 21（正答）
  前方・後方両方の計算により作業Hの最遅開始が $21$ 日であることが示されます。すなわちHはプロジェクト開始から遅くとも21日後に開始しなければ最短で終了できません。

よくある誤解

• 最早開始（ES）と最遅開始（LS）を混同する
  ESは「いつから始められるか」、LSは「遅くともいつまでに始めないと遅延するか」。両者は別の値であるため混同に注意。
• ダミー矢印を無視する
  ダミーは所要日数ゼロでも依存関係を表す重要要素で、ノードの最早時刻や最遅時刻に影響するため省略してはいけません。
• クリティカルパス長＝ある作業の最遅開始とは限らない
  クリティカルパス上の作業ならLS＝ESとなるが、HはクリティカルでないためLSはプロジェクト全体の所要日数から逆算する必要がある。

補足コラム

• ネットワーク図の表現にはAOA（矢印表現）とAON（ノード表現）があります。本問題はAOA形式で、ダミー矢印（所要日数0）が使われています。ダミーは同じノード（AON）なら不要ですが、AOAでは依存関係を表現するためにしばしば必要です。
• クリティカルパス法（CPM）の手順は「前方計算で最短所要日数と各ノードの最早時刻を得る → 後方計算で各ノードの最遅時刻を求める → 活動の余裕（スラック）を算出してクリティカル活動を特定する」です。

FAQ