ＰＤＭ（プレシデンス・ダイアグラム法）

学習のポイント

代表的なスケジュールモデルには、
　　作業を矢線で表現する　　　ＡＤＭ（アローダイアグラム法）
　　作業をボックスで表現する　ＰＤＭ（プレシデンス・ダイアグラム法）
があります。ここでは、アローダイアグラム法の理解の上で、プレシデンス・ダイアグラム法について学習します。

キーワード

ＰＤＭ、プレシデンス・ダイアグラム法、依存関係、リード／ラグ

ＰＤＭの概念

ＡＯＡ図法とＡＯＮ図法

アローダイアグラム（ＡＯＡ図法）では作業を矢線で表しました。右図のクリティカルパスは、①→②→④→⑤、すなわちＡ・Ｃ・Ｅになります。
　ＡＯＮ図法では、作業をノードで示し、先行・後続関係を矢線で示します。下図は、右図を表およびネットワーク図にしたものです。このほうがが直観的に理解しやすいでしょう。ＡＯＡとＡＯＮは単なる表記法、入力データの違いであり、解法は同じです。→参照：ＡＯＮでのＰＥＲＴの計算プログラム
　プレシデンス・ダイアグラム法（ＰＤＭ）は、ＡＯＮの拡張機能です。

　　作業名　先行作業　作業時間　
　　　Ａ　　　なし　　　２
　　　Ｂ　　　なし　　　１
　　　Ｃ　　　Ａ　　　　２
　　　Ｄ　　　Ａ，Ｂ　　３
　　　Ｅ　　　Ｃ　　　　２

プレシデンス・ダイアグラム法
（Precedence Diagramming Method：ＰＤＭ）

precedenceは「優先順位」の意味です。

ＳＳ＋１：ＢはＡ開始後１時間後に開始できる。
ＦＳ＋１：ＣはＡ終了後１時間後に開始できる。
ＦＦ＋１：ＤはＣ終了後１時間後に終了できる＝ＣはＤ終了１時間前に終了前に終了しなければならない。

依存関係とリード／ラグ

上図での「ＸＸ±ｒ」の「ＸＸ」を依存関係、「±ｒ」をリード／ラグといいます。
　　リードは先行作業に対して後続作業の開始を前倒しする時間（－）
　　ラグは先行作業に対して後続作業の開始を遅らせる時間（＋）

ＦＳ±ｒ：終了－開始関係（Ｐ終了のｒ後にＱを開始できる）
最も基本的でよく用いられる関係です。ＰＥＲＴでは、全てが「ＦＳ＋０」の関係になります。
ＳＳ±ｒ：開始－開始関係：開始－開始関係（Ｐ開始のｒ後にＱを開始できる）
ＦＦ±ｒ：終了－終了関係（Ｐ終了のｒ後にＱを終了できる）
「終了できる」であり、「終了しなければならない」ではありません。いいかえれば「Ｐ終了後ｒ経過するまでＱを終了できない」、「Ｑの終了よりｒ以前にＰが終了していなければならない」という関係です。
ＳＦ±ｒ：開始－終了関係（Ｐ開始のｒ後にＱを終了できる）
「上映開始後ｒ分後になったら、入場窓口を終了できる」（「終了しなければならない」ではない）というようなケースですが、上映が先行作業、窓口が後続作業になり不自然なこともあります。あまり使われません。

依存関係の例

「基本情報技術者試験、平成３１年午前、問５２」を変更
（「～する」は「しなければならない」ように解釈できるので「～できる」のほうが適切だと思いますが）

「受付の開始から３０分経過したら、試験を開始する。」　→　受付（ＳＳ＋３０）試験
「受付の終了から１０分経過したら、試験を開始する。」　→　受付（ＦＳ＋１０）試験
「受付の終了から４５分経過したら、試験を終了する。」　→　受付（ＦＦ＋４５）試験
「試験の開始から２０分経過したら、受付を終了する。」　→　試験（ＳＦ＋２０）受付

ＰＤＭでの結果の作業表記形式

ＰＤＭ→ＡＯＮ

ＰＤＭを直接解くアルゴリズムやアプリがあると思いますが、私は知りません。それで依存関係を解釈してダミー作業を加えることによりＡＯＮに変換することを試みました（間違いがあるかもしれません）。

下表の凡例

先行作業をＰ、後続作業をＱとし、作業時間をｐ、ｑとします。
依存関係を表すために、ダミー作業を追加します。赤枠のノードで示しました。
リードとラグをｒとします。
ダミー作業の名称を、(作業時間)により、次のようにしています。
　　R0(0), 　R1(r).　R2(p-r),　R3(r-p)
Ｓは、ＰあるいはＱの後続作業です。複数の作業がある場合もあります。
ＡＯＮ図法での矢線の区分
　赤線：以前の先行・後続関係を削除
　黒線：新規に先行・後続関係を追加
　細線：以前から設定されている先行・後続関係（変更しない）
「作業：先行作業」は、作業表を変更する内容です。
　　R1：Ｐ　　　ダミー作業 P1 を追加し、その先行作業をＰとする
　　　Ｑ：R1　　これまでの先行作業Ｐを R1 に変更

ＦＳ±ｒ　終了－開始関係（Ｐ終了のｒ後にＱを開始できる）

ＳＳ±ｒ　開始－開始関係（Ｐ開始のｒ後にＱを開始できる）

ＦＦ±ｒ　終了－終了関係（Ｐ終了のｒ後にＱを終了できる）

ＳＦ±ｒ　開始－終了関係（Ｐ開始のｒ後にＱを終了できる）

簡単な実例

依存関係の指定がないとき

　作業名作業時間　先行作業　
　　Ａ　　　２　　　　
　　Ｂ　　　１　　　　
　　Ｃ　　　２　　　　Ａ
　　Ｄ　　　３　　　　Ａ
　　　　　　　　　　　Ｂ
　　Ｅ　　　２　　　　Ｃ

依存関係の設定

ア：ＢはＡ開始後１時間後に開始できる。
イ：ＣはＡ終了後１時間後に開始できる。
ウ：ＤはＣ終了後１時間後に終了できる＝ＣはＤ終了１時間前に終了前に終了しなければならない

　作業名作業時間　先行作業　依存関係　リード／ラグ
　　Ａ　　　２　　　　
　　Ｂ　　　１　　　　Ａ　　　　ＳＳ　　　１
　　Ｃ　　　２　　　　Ａ　　　　ＦＳ　　　１
　　Ｄ　　　３　　　　Ａ
　　　　　　　　　　　Ｂ
　　　　　　　　　　　Ｃ　　　　ＦＦ　　　１
　　Ｅ　　　２　　　　Ｃ

ア　Ａ（SS+1) Ｂ: R0：Ｐの先行作業　→　R0を作成し、R0の先行作業をＡの先行作業（開始）とする
　Ｐ：R0　　　　　→　Ａの先行作業を R0 とする
　　　　アを開始作業とすれば、この変更作業は不要
R1：R0　　　　　　→　R1(ア) を作成し、R1の先行作業を R0 とする
　　　　　　　　　　　R0 が開始なので、R1(ア) 作成だけでよい
　Ｑ：R1　　　　　→　Ｂの先行作業をアにする
イ　Ａ（FS+1）Ｃ: R1：Ｐ　　→　R1(イ) を作成。イの先行作業をＡとする。
　Ｑ：R1　→　Ｃの先行作業のＡをイに変更する。
ウ　Ｃ（FF+1）Ｄ: Ｐ→Ｑを削除　→　「Ｃ→Ｄ」を削除
R1：Ｐ　　→　R1(ウ) を作成。その先行作業をＣとする
　Ｓ：R1、Ｑ　→　Ｅの先行作業をウとＤにする
　　　Ｅが開始できるのは、ウとＤの終了時刻

ＡＯＮでの表示

　作業名作業時間　先行作業　
　　Ａ　　　２　　　　
　　ア　　　１　　　　
　　Ｂ　　　１　　　　ア
　　イ　　　１　　　　Ａ
　　Ｃ　　　２　　　　イ
　　Ｄ　　　３　　　　Ａ、Ｂ
　　ウ　　　１　　　　Ｃ
　　Ｅ　　　２　　　　ウ、Ｄ

計算結果

上の表をＡＯＮでのＰＥＲＴの計算プログラムを用いて計算

　　　　　　　　　　　　　　　　　最早日　　　　最遅日　　　余裕
　作業名 作業時間　先行作業　　 開始　完了　　開始　完了　　日数
　　Ａ　　　２　　　　　　　　　　0　　	2　　　 0　　 2　　　0
　　ア　　　１　　　　　　　　　　0     1       1     2      1
　　Ｂ　　　１　　　　ア　　　　　1　　	2　　　 2　　 3　　　1　
　　イ　　　１　　　　Ａ　　　　　2　　	3　　　 2　　 3　　　0
　　Ｃ　　　２　　　　イ　　　　　3　　	5　　　 3　　 5　　　0
　　Ｄ　　　３　　　Ａ、Ｂ　　　　2　　	5　　　 3　　 6　　　1
　　ウ　　　１　　　　Ｃ　　　　　5　　	6　　　 5　　 6　　　0
　　Ｅ　　　２　　　ウ、Ｄ　　　　6　　 8　　　 6　　 8　　　0

全所要時間 ＝ 8
クリティカルパス ＝ （Ａ,ア）、イ、Ｃ、ウ、Ｅ

条件の確認

ア：ＢはＡ開始後１時間後に開始できる。
Ａの開始時刻は０、Ｂの開始時刻は１になっている
イ：ＣはＡ終了後１時間後に開始できる。
Ａの終了時刻は５、Ｃの開始時刻は６になっている
ウ：ＣはＤ終了１時間前に終了前に終了しなければならない
Ｄは３～６で行えばよいので、最遅終了時刻は６になる。Ｃの終了時刻は５