9  クリティカルパス

9.1 学習目標

  • プロジェクトをAONのプロジェクト・ネットワークとして表現できる．
  • 最早開始時刻と最早終了時刻を，前向きに計算できる．
  • 最遅開始時刻と最遅終了時刻を，後ろ向きに計算できる．
  • スラックを求め，クリティカルパスを特定できる．

9.2 PERT/CPMとは

プロジェクトは，多くの作業からなる．プロジェクトを完遂できるように，作業のスケジュールを作成する必要がある．その方法として，PERT（Program Evaluation and Review Technique）とCPM（Critical Path Method）がある．現在では，PERTとCPMが統合され，PERT/CPMとして知られている(Camm ほか 2022年; Hillier と Lieberman 2025年)．

ノート情報処理技術者試験との関連

PERT/CPMは「基本情報技術者試験」や「応用情報技術者試験」などで頻出のトピックのようである．他にも，線形計画法，在庫問題，ゲーム理論，データ分析，データベース，データ構造とアルゴリズムなど，様々な経営工学関係のトピックが出題される．経営工学を学ぶ学生は，受けてみると良いだろう．

9.3 プロジェクト

ここで，ある作業の開始前に完了しなければならない作業を先行作業（Immediate Predecessor）と呼ぶ．また，ある作業の完了後に開始できる作業を後続作業（Immediate Successor）と呼ぶ．

まとめると，プロジェクトは，次の要素で構成される．

  • 作業：プロジェクトを構成する仕事．活動，アクティビティとも呼ばれる．
  • 先行関係：それぞれの作業の先行作業を定義する関係．
  • 作業時間：各作業に必要な時間．

例 9.1 学生の田中さんと佐藤さんが協力し，ある授業のレポートを作成することになった．このレポートを作成するためには，下の表に示すように，いくつかの作業を行う必要がある．

作業 作業内容 先行作業 時間（日）
A 課題の理解 - 2
B データ収集 A 3
C データ分析 B 4
D 文献調査 A 2
E レポート作成 C, D 5

9.4 プロジェクト・ネットワーク

プロジェクトをネットワークで表現したものをプロジェクト・ネットワーク（Project Network）と呼ぶ．プロジェクト・ネットワークには，AOA（Activity on Arrow）や AON（Activity on Node）という 2 種類の表現方法がある．

AOA では，作業を辺で表現し，先行関係を点で表現する．AON では，作業を点で表現し，先行関係を辺で表現する．AON のほうが理解と作成が容易で，実務でも AON がよく使われる(Camm ほか 2022年; Hillier と Lieberman 2025年; Eiselt と Sandblom 2022年)．これは以降，AON に基づいて説明する．

プロジェクト・ネットワークは G = (V, E) という有向グラフで表される．ここで，V は始点 s，終点 t と各作業を表す点の集合であり，E は先行関係を表す辺の集合である．辺 (v, u) \in E では，v が u の先行作業であることを意味する．

辺 (s, v) \in E は，作業 v が先行作業を持たないことを意味し，辺 (v, t) \in E は，作業 v が後続作業を持たないことを意味する．作業 v の先行作業の集合を \mathcal{P}(v) と表す．作業 v の後続作業の集合を \mathcal{S}(v) と表す．

作業点 v \in V には，作業時間 \tau(v) が与えられている．始点 s と終点 t の作業時間は \tau(s) = \tau(t) = 0 とする．

例 9.1 のプロジェクト・ネットワークは次の図のようになる．

コード 
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

# グラフの作成（頂点を番号で定義）
G = nx.DiGraph()
edges = [
    ("s", "A"),
    ("A", "B"),
    ("A", "D"),
    ("B", "C"),
    ("C", "E"),
    ("D", "E"),
    ("E", "t"),
]
G.add_edges_from(edges)

for layer, nodes in enumerate(nx.topological_generations(G)):
    for node in nodes:
        G.nodes[node]["layer"] = layer

# pos = nx.multipartite_layout(G, subset_key="layer")
pos = {
    "s": (0, 0),
    "A": (2, 0),
    "B": (4, 1),
    "D": (4, -1),
    "C": (6, 1),
    "E": (8, 0),
    "t": (10, 0),
}

label_pos = {}
for k, (x, y) in pos.items():
    r = np.sqrt(x**2 + y**2) if np.sqrt(x**2 + y**2) > 0 else 1
    scale = 1.12
    label_pos[k] = (x * scale, y * scale)

# Plotting
nx.draw_networkx(
    G,
    pos=pos,
    with_labels=True,
    node_color="white",
    node_size=500,
    edgecolors="#16212d",
)
plt.axis("off")
plt.show()

例 9.2 以下の作業リストに基づいて，プロジェクト・ネットワークを作成せよ．

作業 先行作業 時間（日）
A - 2
B - 3
C A 4
D A 2
E B 5
F C, D, E 9
G E 2
コード 
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

# グラフの作成（頂点を番号で定義）
G = nx.DiGraph()
edges = [
    ("s", "A"),
    ("s", "B"),
    ("A", "C"),
    ("A", "D"),
    ("C", "F"),
    ("D", "F"),
    ("B", "E"),
    ("E", "G"),
    ("E", "F"),
    ("G", "t"),
    ("F", "t"),
]
G.add_edges_from(edges)

for layer, nodes in enumerate(nx.topological_generations(G)):
    for node in nodes:
        G.nodes[node]["layer"] = layer

# pos = nx.multipartite_layout(G, subset_key="layer")
pos = {
    "s": (0, 0),
    "A": (2, 1),
    "B": (2, -1),
    "C": (4, 2),
    "D": (4, 0),
    "E": (4, -2),
    "F": (6, 0),
    "G": (6, -2),
    "t": (8, 0),
}

label_pos = {}
for k, (x, y) in pos.items():
    r = np.sqrt(x**2 + y**2) if np.sqrt(x**2 + y**2) > 0 else 1
    scale = 1.12
    label_pos[k] = (x * scale, y * scale)

# Plotting
nx.draw_networkx(
    G,
    pos=pos,
    with_labels=True,
    node_color="white",
    node_size=500,
    edgecolors="#16212d",
)
plt.axis("off")
plt.show()

9.5 クリティカルパス

プロジェクト・ネットワークにおいて，始点 s から終点 t までの経路をパスと呼ぶ．パスの長さは，そのパス上の作業時間の合計である．パス P = (s, v_{i_1}, v_{i_2}, \ldots, v_{i_k}, t) の長さは，

\sum_{v \in P} \tau(v) = \tau(v_{i_1}) + \tau(v_{i_2}) + \cdots + \tau(v_{i_k})

である．

最も長いパスをクリティカルパス（Critical Path）と呼ぶ．クリティカルパスに含まれる作業をクリティカル作業（Critical Activity）と呼ぶ．クリティカル作業が遅延すると，プロジェクト全体の完了が遅延する．

クリティカルパスを求める問題は，最長路問題に帰着できるが，ここで述べる方法は，プロジェクトにおける様々な有用な情報も提供する．

9.5.1 最早開始時刻と最早終了時刻

作業点 v \in V の最も早く開始できる時間を最早開始時刻（Earliest Start Time）と呼び，ES(v) と表す．v の最も早く終了できる時間を最早終了時刻（Earliest Finish Time）と呼び，EF(v) と表す．始点 s の最早開始時刻は ES(s) = 0 とする．

v の最早終了時刻は，最早開始時刻に作業時間を加えたものである．

EF(v) = ES(v) + \tau(v)

u の最早開始時刻は，u の先行作業 v \in \mathcal{P}(u) の中で最早終了時刻 EF(v) が最大のものである．

ES(u) = \max_{v \in \mathcal{P}(u)} EF(v)

で与えられる．

例 9.3 作業点 D の先行作業を A, B, C とする．そのとき，\mathcal{P}(D) = \{A, B, C\} である．EF(A) = 2，EF(B) = 3，EF(C) = 6 とすると，D の最早開始時刻は，

ES(D) = \max\{EF(A), EF(B), EF(C)\} = \max\{2, 3, 6\} = 6

である．

コード 
import matplotlib.pyplot as plt
import networkx as nx

# グラフの作成（頂点を番号で定義）
G = nx.DiGraph()
edges = [
    ("A", "D"),
    ("B", "D"),
    ("C", "D"),
]
G.add_edges_from(edges)

# A, B, C を縦に並べる

pos = {
    "A": (0, 1),
    "B": (0, 0),
    "C": (0, -1),
    "D": (2, 0),
}
# Plotting
nx.draw_networkx(
    G,
    pos=pos,
    with_labels=True,
    node_color="white",
    node_size=500,
    edgecolors="#16212d",
)
plt.axis("off")
plt.show()

最早開始時刻と最早終了時刻を求めるアルゴリズムは下の通りである．ここで，点をトポロジカルオーダー(topological order)で処理するとは，v のすべての先行作業 u \in \mathcal{P}(v) が v より前に処理されるように点を順序付けることである．

Algorithm 9.1 Forward Pass Algorithm

  1. ES(s) \leftarrow 0, EF(s) \leftarrow 0.
  2. For each v \in V \setminus \{s\} in topological order do
    1. ES(v) \leftarrow \max_{u \in \mathcal{P}(v)} EF(u).
    2. EF(v) \leftarrow ES(v) + \tau(v).

例 9.2 のプロジェクト・ネットワークに対して，最早開始時刻と最早終了時刻を求めると，次の表のようになる．

v \mathcal{P}(v) \tau(v) ES(v) EF(v)
s - 0 0 0
A s 2 0 2
B s 3 0 3
C A 4 2 6
D A 2 2 4
E B 5 3 8
F C, D, E 9 8 17
G E 2 8 10
t F, G 0 17 17

作業 F を開始するためには，作業 C，D，E のすべてが完了している必要がある．そのため，作業 F の開始時間は，作業 C，D，E の中で最も遅い完了時間に依存する．作業 C，D，E の完了時間はそれぞれ 6 日，4 日，8 日であるため，作業 F の最も早い開始時間は 8 日となる．

9.5.2 最遅開始時刻と最遅終了時刻

作業点 v の遅くとも始めないといけない時間を最遅開始時刻（Latest Start Time）と呼び，LS(v) と表す．v の遅くとも終わらせないといけない時間を最遅終了時刻（Latest Finish Time）と呼び，LF(v) と表す．

終点 t の最遅終了時刻は LF(t) = EF(t) とする．

v の最遅開始時刻は，最遅終了時刻から作業時間を引いたものである．

LS(v) = LF(v) - \tau(v)

u の最遅終了時刻は，u の後続作業 v \in \mathcal{S}(u) の中で LS(v) が最小のものである．

LF(u) = \min_{v \in \mathcal{S}(u)} LS(v)

例 9.4 作業点 C の後続作業を D, E, F とする．そのとき，\mathcal{S}(C) = \{D, E, F\} である．LS(D) = 6，LS(E) = 3，LS(F) = 8 とすると，C の最遅終了時刻は， LF(C) = \min\{LS(D), LS(E), LS(F)\} = \min\{6, 3, 8\} = 3 である．

コード 
import matplotlib.pyplot as plt

import networkx as nx

# グラフの作成（頂点を番号で定義）
G = nx.DiGraph()
edges = [
    ("C", "D"),
    ("C", "E"),
    ("C", "F"),
]
G.add_edges_from(edges)

pos = {
    "C": (0, 0),
    "D": (2, 1),
    "E": (2, 0),
    "F": (2, -1),
}
# Plotting
nx.draw_networkx(
    G,
    pos=pos,
    with_labels=True,
    node_color="white",
    node_size=500,
    edgecolors="#16212d",
)
plt.axis("off")
plt.show()

例 9.2 のプロジェクト・ネットワークに対して，最遅開始時刻と最遅終了時刻を求めると，次の表のようになる．

v \mathcal{S}(v) \tau(v) LS(v) LF(v)
s A, B 0 0 0
A C, D 2 2 4
B E 3 0 3
C F 4 4 8
D F 2 6 8
E F, G 5 3 8
F t 9 8 17
G t 2 15 17
t - 0 17 17

最遅開始時刻と最遅終了時刻を求めるアルゴリズムは下の通りである．ここで，点を逆トポロジカルオーダー（reverse topological order）で処理するとは，v のすべての後続作業 u \in \mathcal{S}(v) が v より前に処理されるように点を順序付けることである．

Algorithm 9.2 Backward Pass Algorithm

  1. LF(t) \leftarrow EF(t), LS(t) \leftarrow EF(t).
  2. For each v \in V \setminus \{t\} in reverse topological order do
    1. LF(v) \leftarrow \min_{u \in \mathcal{S}(v)} LS(u).
    2. LS(v) \leftarrow LF(v) - \tau(v).

9.5.3 スラック

作業点 v のスラック（Slack）を SL(v) と表す．スラックは，

SL(v) = LS(v) - ES(v) = LF(v) - EF(v)

で与えられる．スラックは，作業 v の開始または終了を遅らせることができる時間を示す．

例 9.2 のプロジェクト・ネットワークに対して，スラックを求めると，次の表のようになる．

v \tau(v) ES(v) EF(v) LS(v) LF(v) SL(v)
s 0 0 0 0 0 0
A 2 0 2 2 4 2
B 3 0 3 0 3 0
C 4 2 6 4 8 2
D 2 2 4 6 8 4
E 5 3 8 3 8 0
F 9 8 17 8 17 0
G 2 8 10 15 17 7
t 0 17 17 17 17 0

スラックが 0 の作業はクリティカル作業である．したがって，例 9.2 のプロジェクト・ネットワークにおけるクリティカルパスは，s \to B \to E \to F \to t であり，このパスの長さは 17 日である．

9.6 まとめ

  • プロジェクトは，作業，先行関係，作業時間の3つの要素で構成される．
  • AONでは作業を点，先行関係を辺で表すため，プロジェクト・ネットワークは有向グラフ G = (V, E) となる．
  • 最早開始時刻は ES(u) = \max_{v \in \mathcal{P}(u)} EF(v)，最早終了時刻は EF(v) = ES(v) + \tau(v) であり，トポロジカルオーダーに前向きに計算する．
  • 最遅終了時刻は LF(u) = \min_{v \in \mathcal{S}(u)} LS(v)，最遅開始時刻は LS(v) = LF(v) - \tau(v) であり，逆トポロジカルオーダーに後ろ向きに計算する．
  • スラックは SL(v) = LS(v) - ES(v) = LF(v) - EF(v) であり，スラックが0の作業がクリティカル作業である．クリティカル作業からなるパスがクリティカルパスである．

9.7 練習問題

練習 9.1 以下の作業リストに基づいて，プロジェクト・ネットワークを作成し，クリティカルパスを求めよ．

作業 先行作業 時間（日）
A - 5
B - 3
C A 7
D A 6
E B 7
F D, E 3
G E 10
H C, F 8