応用情報技術者 2019年 春期 午前2 問53

作業Eの余裕時間【午前2解説】

正解の理由

解法ステップ

1. 順算（最早時刻 = ES, EF）
   • 開始ノード: 時刻 = 1
   • A: ES_A = 1, EF_A = 1 + 5 = 6
   • B: ES_B = 1, EF_B = 1 + 10 = 11
   • N1（Aとダミー（B経路）が合流するノード）の最早時刻は incoming の最大 → max(EF_A, EF_dummy_from_B) = max(6, 11) = 11
   • C: ES_C = 11, EF_C = 11 + 20 = 31
   • D: ES_D = 11, EF_D = 11 + 30 = 41
   • E: ES_E = 11, EF_E = 11 + 10 = 21
   • F: ES_F = EF_B = 11, EF_F = 11 + 10 = 21
   • N3（EとF合流）の最早時刻 = max(EF_E, EF_F) = max(21,21) = 21
   • G: ES_G = EF_C = 31, EF_G = 31 + 20 = 51
   • N5（D,G,dummy(N3)合流）の最早時刻 = max(EF_D, EF_G, EF_dummy_from_N3) = max(41,51,21) = 51
   • H: ES_H = 51, EF_H = 51 + 10 = 61（プロジェクト終了時刻）
2. 逆算（最遅時刻 = LF, LS）
   • 終了ノード LF = EF_H = 61
   • H: LS_H = LF_H - 10 = 61 - 10 = 51 → H の LS = 51
   • N5 の最遅時刻 = LS_H = 51
   • G: LS_G = 51 - 20 = 31 → C の LF = 31
   • C: LS_C = 31 - 20 = 11
   • D: LS_D = 51 - 30 = 21
   • N3 の最遅時刻は N5 に到達するダミーを通じて N5 の最遅時刻に等しいため N3_latest = 51
   • E: LS_E = 51 - 10 = 41
   • F: LS_F = 51 - 10 = 41
   • N1 の最遅時刻 = min(LS_C, LS_D, LS_E) = min(11,21,41) = 11 → A の LS = 11 - 5 = 6
   • N2 の最遅時刻 = min(LS_F, (N1の最遅時刻 経由のダミー)) = min(41,11) = 11 → B の LS = 11 - 10 = 1
3. 総余裕 = LS - ES（各作業）
   • A: ES=1, LS=6 → 余裕 = 5
   • B: ES=1, LS=1 → 余裕 = 0
   • C: ES=11, LS=11 → 余裕 = 0
   • D: ES=11, LS=21 → 余裕 = 10
   • E: ES=11, LS=41 → 余裕 = 30
   • F: ES=11, LS=41 → 余裕 = 30
   • G: ES=31, LS=31 → 余裕 = 0
   • H: ES=51, LS=51 → 余裕 = 0
   • ダミーは所要0だがノード時刻で拘束され、該当するダミーの余裕は0等になる場合がある

選択肢別の誤答解説

• ア: 「作業Cを最も早く開始できるのは6日目である。」
  • 誤り。C の ES は N1 の最早時刻に依存します。A の EF=6 でも、B→ダミーにより N1 は EF_B=11 の影響を受けるため N1 の最早は 11 日目であり、C の開始は 11 日目です（6日目ではありません）。
• イ: 「作業Dはクリティカルパス上の作業である。」
  • 誤り。D の総余裕は 10 日であり（ES=11, LS=21）、余裕が0の作業のみがクリティカルパス上にあると判定します。本問題のクリティカル経路は B →（ダミー）→ C → G → H（これらの作業は総余裕が0）です。従って D はクリティカルではありません。
• ウ: 「作業Eの総余裕時間は30日である。」
  • 正しい。上記の順算・逆算により ES_E=11, LS_E=41 となり、総余裕は 30 日です。
• エ: 「作業Fを最も遅く開始できるのは11日目である。」
  • 誤り。F の ES は 11 日ですが、最遅開始（LS）は 41 日で、最遅で開始できる日は 41 日目となります。11日目は最早開始日です。

よくある誤解

• ダミー作業を無視すると誤る：ダミーは期間0でもノードの依存関係を作るため、合流ノードの最早時刻を決める要因になり得ます（本問ではこれがC/Eの開始時刻に影響）。
• EF/LS の定義混同：EF = ES + 所要日数（ここでの扱い）とするか EF = ES + 所要日数 - 1 とするかの違いで数値がずれるため、解法中は一貫した扱いを必ず明示すること（本解説は EF = ES + 所要日数 の表式を採用）。
• ノードの最早時刻は「incoming の最大」・最遅時刻は「outgoing の最小」である点を忘れると、誤った ES/LS を出す。

補足コラム

• クリティカルパスの同定法：各作業の総余裕が0である作業群をつないでいき、開始ノードから終了ノードまで連続する経路を見つけると、プロジェクト全体のクリティカルパスが得られます。必ずダミーや並列分岐を考慮してノード時刻（イベント時刻）を求めてください。
• 総余裕（Total Float）と自由余裕（Free Float）の違い：
  • 総余裕 = LS - ES（または LF - EF）。作業全体が遅れてもプロジェクトの終了に影響が出ない最大遅延日数。
  • 自由余裕 = 次のイベントの最早時刻 - EF。直後の作業に影響を与えずに遅らせられる日数。

FAQ