12  クリティカルパス

12.1 学習目標

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

12.2 PERT/CPM とは

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

12.3 プロジェクト

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

  • 作業：プロジェクトを構成する仕事．活動，アクティビティとも呼ばれる．
  • 先行関係：各作業を開始する前に，どの作業が完了していなければならないかを表す関係．
  • 作業時間：各作業に必要な時間．

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

例 12.1 学生の田中さんと佐藤さんが，授業のレポートを共同で作成する．必要な作業とその先行関係，作業時間を 表 12.1 に示す．

表 12.1: レポート作成の作業リスト
作業 作業内容 先行作業 時間（日）
A 課題の確認と計画 - 2
B データ収集 A 3
C データ分析 B 4
D 文献調査 A 2
E レポートの執筆 C, D 5

作業 A が終わると，その後続作業である B と D を並行して進められる．E を始めるには，先行作業である C と D の両方が完了している必要がある．

12.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 に基づいて説明する．

例 12.1 を AON で表したものが 図 12.1 である．各作業を点で表し，先行作業から後続作業へ向かう矢印で結ぶ．また，プロジェクト全体の開始と完了を表すために，始点 s と終点 t を加えている．

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


def draw_network(G, pos, scale=0.45):
    """プロジェクト・ネットワークを描画する．

    座標 1 あたり scale インチとし，どの図も同じ縮尺にする．
    作業名は立体，始点 s と終点 t は斜体で表示する．
    """
    xs, ys = zip(*pos.values())
    width = scale * (max(xs) - min(xs) + 1)
    height = scale * (max(ys) - min(ys) + 1)
    fig, ax = plt.subplots(figsize=(width, height))
    labels = {v: f"${v}$" if v in ("s", "t") else rf"$\mathrm{{{v}}}$" for v in G}
    nx.draw_networkx(
        G,
        pos,
        labels=labels,
        node_color="white",
        edgecolors="black",
        linewidths=1.0,
        node_size=450,
        font_size=11,
        width=1.0,
        arrowstyle="-|>",
        arrowsize=12,
        ax=ax,
    )
    ax.set(
        xlim=(min(xs) - 0.5, max(xs) + 0.5),
        ylim=(min(ys) - 0.5, max(ys) + 0.5),
        aspect="equal",
    )
    ax.axis("off")
    fig.subplots_adjust(left=0, right=1, bottom=0, top=1)
    plt.show()


# プロジェクト・ネットワークの作成
G = nx.DiGraph()
edges = [
    ("s", "A"),
    ("A", "B"),
    ("A", "D"),
    ("B", "C"),
    ("C", "E"),
    ("D", "E"),
    ("E", "t"),
]
G.add_edges_from(edges)

# 点の座標を固定（D は B, C と並行するので，その中央の下に置く）
pos = {
    "s": (0, 0),
    "A": (2, 0),
    "B": (4, 1),
    "C": (6, 1),
    "D": (5, -1),
    "E": (8, 0),
    "t": (10, 0),
}
draw_network(G, pos)
図 12.1: レポート作成のプロジェクト・ネットワーク

プロジェクト・ネットワークは G = (V, E) という有向グラフで表される．ここで，V は始点 s，終点 t と各作業を表す点の集合であり，E は先行関係を表す辺の集合である．辺 (v, u) \in E は，v が u の先行作業であることを意味する．先行関係が循環していると，循環に含まれる作業はどれも開始できない．そのため，プロジェクト・ネットワークは閉路を持たない有向グラフ，すなわち チャプター 6 で定義した有向非巡回グラフである．

辺 (s, v) \in E は，作業 v が先行作業を持たないことを意味し，辺 (v, t) \in E は，作業 v が後続作業を持たないことを意味する．

点 v の先行作業の集合 \mathcal{P}(v) と後続作業の集合 \mathcal{S}(v) は，チャプター 6 と同様に

\mathcal{P}(v) = \{u \in V \mid (u, v) \in E\}, \quad \mathcal{S}(v) = \{u \in V \mid (v, u) \in E\}

で定義する．始点 s と終点 t も点として扱うため，先行作業を持たない作業 v では \mathcal{P}(v) = \{s\}，後続作業を持たない作業 v では \mathcal{S}(v) = \{t\} となる．

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

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

表 12.2: 作業 A〜G の作業リスト
作業 先行作業 時間（日）
A - 2
B - 3
C A 4
D A 2
E B 5
F C, D, E 9
G E 2

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

コード 
# プロジェクト・ネットワークの作成
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)

# 点の座標を固定
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),
}
draw_network(G, pos)
図 12.2: 作業 A〜G からなるプロジェクト・ネットワーク

12.5 クリティカルパス

以下では，チャプター 6 で定義したパスのうち，始点 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})

である．

始点 s から終点 t までのパスのうち，長さが最大のものをクリティカルパス（Critical Path）と呼ぶ．クリティカルパスは一つとは限らない．

パス上の作業は，先行関係により一つずつ順に行わなければならない．そのため，プロジェクト全体の所要時間は，どのパスの長さよりも短くすることはできない．一方，後述するように，各作業をできるだけ早く開始すれば，クリティカルパスの長さでプロジェクトを完了できる．したがって，クリティカルパスの長さは，プロジェクト全体の最短所要時間に等しい．

クリティカルパスに含まれる作業をクリティカル作業（Critical Activity）と呼ぶ．ほかの作業時間が変わらなければ，クリティカル作業の遅れは，プロジェクト全体の完了の遅れにつながる．

例 12.1 では，始点 s から終点 t までのパスは次の二つである．

  • (s, \mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{E}, t)：長さは 2 + 3 + 4 + 5 = 14 日．
  • (s, \mathrm{A}, \mathrm{D}, \mathrm{E}, t)：長さは 2 + 2 + 5 = 9 日．

したがって，クリティカルパスは (s, \mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{E}, t) であり，プロジェクト全体の最短所要時間は 14 日となる．

クリティカルパスを求める問題は，プロジェクト・ネットワーク上の最長路問題として捉えられる．一般のグラフでは最長路問題を効率よく解くことは難しいが，閉路を持たないプロジェクト・ネットワークでは効率よく解くことができる．以下では，クリティカルパスを特定するとともに，各作業の開始・終了時刻や，作業を遅らせられる時間の余裕を求める方法を説明する．

12.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)

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

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

で与えられる．

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

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

である．

コード 
G = nx.DiGraph()
edges = [
    ("A", "D"),
    ("B", "D"),
    ("C", "D"),
]
G.add_edges_from(edges)

# A, B, C を縦に並べる
pos = {
    "A": (0, 1.2),
    "B": (0, 0),
    "C": (0, -1.2),
    "D": (1.5, 0),
}
draw_network(G, pos)
図 12.3: 作業 D とその先行作業 A，B，C

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

\begin{algorithm} \caption{Forward Pass Algorithm} \begin{algorithmic} \State $ES(s) \gets 0$, $EF(s) \gets 0$ \For{each $v \in V \setminus \{s\}$ in topological order} \State $ES(v) \gets \max_{u \in \mathcal{P}(v)} EF(u)$ \State $EF(v) \gets ES(v) + \tau(v)$ \EndFor \end{algorithmic} \end{algorithm}

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

表 12.3: 作業 A〜G の最早開始時刻と最早終了時刻
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 日となる．

12.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)

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

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

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

コード 
G = nx.DiGraph()
edges = [
    ("C", "D"),
    ("C", "E"),
    ("C", "F"),
]
G.add_edges_from(edges)

# D, E, F を縦に並べる
pos = {
    "C": (0, 0),
    "D": (1.5, 1.2),
    "E": (1.5, 0),
    "F": (1.5, -1.2),
}
draw_network(G, pos)
図 12.4: 作業 C とその後続作業 D，E，F

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

\begin{algorithm} \caption{Backward Pass Algorithm} \begin{algorithmic} \State $LF(t) \gets EF(t)$, $LS(t) \gets EF(t)$ \For{each $v \in V \setminus \{t\}$ in reverse topological order} \State $LF(v) \gets \min_{u \in \mathcal{S}(v)} LS(u)$ \State $LS(v) \gets LF(v) - \tau(v)$ \EndFor \end{algorithmic} \end{algorithm}

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

表 12.4: 作業 A〜G の最遅開始時刻と最遅終了時刻
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

12.5.3 スラック

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

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

で与えられる．スラックは，プロジェクト全体の完了を遅らせることなく，作業 v の開始または終了を遅らせることができる最大の時間を示す．

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

表 12.5: 作業 A〜G のスラック
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 の作業はクリティカル作業である．表 12.5 では，始点 s と終点 t を除くと，スラックが 0 の作業は B，E，F であり，これらを通るパス (s, \mathrm{B}, \mathrm{E}, \mathrm{F}, t) の長さ 3 + 5 + 9 = 17 日は EF(t) に一致する．したがって，例 12.2 のプロジェクト・ネットワークにおけるクリティカルパスは (s, \mathrm{B}, \mathrm{E}, \mathrm{F}, t) であり，その長さは 17 日である．

ただし，スラックが 0 の作業だけからなるパスが，クリティカルパスであるとは限らない．そのため，パスの長さが EF(t) に一致することを確かめる必要がある．

12.6 まとめ

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

12.7 練習問題

練習 12.1 表 12.6 の作業リストに基づいて，以下の問いに答えよ．

表 12.6: 作業 A〜H の作業リスト
作業 先行作業 時間（日）
A - 5
B - 3
C A 7
D A 6
E B 7
F D, E 3
G E 10
H C, F 8
  1. プロジェクト・ネットワークを AON で書け．
  2. 各作業の最早開始時刻，最早終了時刻，最遅開始時刻，最遅終了時刻，スラックを求めよ．
  3. このプロジェクトのクリティカルパスを求めよ．