応用情報技術者 2012年 春期 午前2 問51

クリティカルパス短縮の最適選択【午前2解説】

正解の理由

• A→B→E→G: $4+6+5+5=20$
• A→C→G: $4+8+5=17$
• A→D→F→G: $4+4+4+5=17$

解法ステップ

1. 図から全ての開始→終了経路を列挙する。
2. 各経路の標準日数を足して所要日数を計算する。
3. 最長経路（クリティカルパス）を特定する。
4. 遅れを回復するためにはクリティカルパス上の作業を短縮する必要があることを確認する（非クリティカル作業はスラックがある）。
5. クリティカルパス上で1日短縮したときの増加費用（費用増加率）を比較し、最小のものを選ぶ。

選択肢別の誤答解説

• ア: B
  • Bはクリティカルパス上の作業だが、費用増加率は6と高い。1日短縮する増加費用がE（2.5）に比べて大きいため最小化にならない。
• イ: C
  • Cを1日短縮しても、C経路の所要は$17$→$16$となり、依然としてクリティカルパスの$20$を下回る。プロジェクト全体の終了日には影響せず、意味がない。
• ウ: D
  • Dも同様にD経路（A→D→F→G）の所要は$17$でスラックが$3$あるため、1日短縮してもプロジェクトの終了日は変わらない。
• エ: E（正解）
  • Eはクリティカルパス上にあり、費用増加率が$2.5$で候補の中で最小。したがって1日短縮する増加費用を最小化できる。

よくある誤解

• クリティカルパス上にあると思い込み、経路の合算をせずに誤認する。特に分岐がある図では全経路の合算を必ず行うこと。
• 非クリティカル作業を短縮すればよいと考える。スラックが残る作業を短縮しても完成日は短縮されない。
• 単に作業の右隣や同じ段にある作業を短縮候補とする誤り（図の位置だけで判断しない）。

補足コラム

• この問題は「クラッシング（crashing）」の基本です。遅れを取り戻すためにクリティカルパス上の活動を短縮するが、短縮には単位当たりの追加費用がかかる。複数日短縮する場合は、日ごとの限界費用（1日目の増加費用と2日目の増加費用が同じとは限らない）や各作業の最短可能日数制約も考慮します。本問は単純化されており、1日短縮でよいケースです。
• もし複数のクリティカルパスが存在すると、どのパスにも影響する作業を短縮するか、または複数パスに渡って短縮を組み合わせる必要があります。最小費用を決めるには全ての該当作業の増加率を比較します。

FAQ