アローダイアグラムを描くだけでしたら「そういう見方もある」という程度の評価しか得られ なかったかもしれません。また、複雑なプロジェクトになれば、アローダイアグラムでさえも全 体を把握することは困難です。
P ERT の特徴は、作業そのものではなく、作業の開始時点、終了時点をあらわすノードに着
目し、そのノードの時間管理を自動化した点にあります。具体的には、
• 個々の作業が開始できるようになるのは、プロジェクト開始からどれくらい後になるか
• プロジェクトは各作業が予定通り進めば、最短でいつ終わるのか、
• ある作業をいつまでに終わらせれば、予定通りにプロジェクトを終わらせることができ るか
• ある作業が予定通り進まなかったとしたら、プロジェクトはどれくらい遅延するか などを数量的にきちんと計算できるというのがこの方法の最大のメリットです。その計算法を説 明しましょう。
説明のために記号を用意します。Tikは作業(i, k)の作業時間とします。またIn(k)はノードk を完了ノードとするような作業の開始ノードの集合、Out(k)はノードkを開始ノードとするよう な作業の完了ノードの集合とします。たとえば、下の図ではIn(3) ={1,2}, Out(3) ={4,5,6}
です。ダミー作業も普通の作業と同格に扱います。
6.5.1 最早開始時刻
ある作業の最早開始時刻Earliest Start timeとは、文字通り、その作業が開始できる最も早い 時刻です。最も早い、といえるためには、すべての作業は始められるときにすぐに始め、予定通 り作業を終える、という条件が必要で、その条件の下で、その作業のすべての先行作業（の先行 作業、...もすべて含めて）が終了する最も早い時刻ということができます。
二つ以上の作業が同じノードから枝分かれしている場合、どの作業も同じ先行作業を必要とし ているので、それらの最早開始時刻は同じになります。ということは、「作業の最早開始時刻」と いう代わりに「ノードの最早開始時刻」と言った方が紛れがないかもしれません。ノードkの最 早開始時刻をESkと書くことにして、ESkを計算する方法を考えましょう。ノードkを出発点 とする作業の最早開始時刻はすべてESkです。
ノードkを終端ノードとする作業の一つを作業(i, k)とすると、作業(i, k)はどうがんばって もESiより前には作業が開始できないので、作業(i, k)が完了するのはESiにその作業時間Tik
を足した時刻になり、ノードkの最早開始時刻はそれ以降、ということになります。したがって、
ESk≥ESi+Tik (∀i∈In(k))
が成り立ちます。ESi+Tikを作業(i, k)の最早完了時刻ということにします。この式が、ノー ドkを終端ノードとする作業の一つ一つに当てはまりますから、結局
ESk = max
i∈In(k){ESi+Tik}
が成り立ちます。In(k)はノードkを終端ノードとする作業の開始ノードの集合だったことを思 い出してください。
例6.1 たとえば下の図のようなネットワークの場合で考えてみましょう。In(3) ={1,2}です。
矢印の脇に書いてある記号は作業の名前と作業時間を表すものとします。またノード１とノード ２の最早開始時刻がそれぞれES1= 11, ES2= 10と与えられているものとします。ノード３の 最早開始時刻ES3は二つの作業(1,3)と(2,3)が両方とも終わるもっとも早い時刻ですが、作 業(1,3)は時刻11に開始できるので完了するのは時刻ES1+T13 = 16です。一方ノード２の 最早開始時刻は10ですから作業(2,3)の完了できるのは早くても時刻ES2+T23= 17です。
したがって作業(3,4)が開始できるのは作業(2,3)が終わった直後の時刻 max{ES1+T13, ES2+T23}= 17 だということが分かります。
プロジェクトの開始ノードの最早開始時刻を0とします。以下、上の式を順番に適用して行く と、すべてのノードの最早開始時刻が計算できますが、これは、もし時刻0にプロジェクトを開 始したとしたら、そのノードを出発点とする作業が最短でいつから始められるか、ということを 表していることになります。最後に最右端のノードすなわちプロジェクト完了ノードの最早開始 時刻が計算されますが、プロジェクトの完了ノードの最早開始時刻とは何でしょうか。「完了」
したのに「開始」とは？ このプロジェクトを終了したら打ち上げパーティが予定されている、
という状況を想定すれば理解しやすいかもしれません。打ち上げパーティが開始できる最も早い 時刻ですから、すべての作業が完了する最短時刻に等しく、結局、プロジェクトを完了するため に必要な（最小、最短）時間（プロジェクトの最短所要時間）を表していることが分かります。
最早開始時刻計算手順のまとめ
1. プロジェクトの開始ノードの最早開始時刻を0とする。
2. In(k)の最早開始時刻がすべて分かっているというノードkについて、
ESk= max
i∈In(k){ESi+Tik} によって最早開始時刻を計算する。
3. すべてのノードの最早開始時刻が計算できれば終わり。
PERT計算に必要なのはすべての作業の最早開始時刻ですが、前に説明したとおり、ノードi
を開始ノードとする作業(i, k)(∀k∈Out(i))の最早開始時刻はノードiの最早開始時刻ESiに 等しいということから求めることができます。
練習6.8 ノ ー ド 5 の 先 行 ノ ー ド が 2,3,4 で そ れ ぞ れ の 最 早 開 始 時 刻 が 10,14,18、作 業 (2,5),(3,5),(4,5)の作業時間がそれぞれ12,9,3、ノード5の後続ノードが6と7、としたとき、
ノード5の最早開始時刻を計算しなさい。また、作業(5,6),(5,7)の最早開始時刻を計算しな さい。
6.5.2 最遅完了時刻
最早開始時刻の計算によって得られたプロジェクトの最短所要時間を変えないという条件の 下で、ある作業はここまでに終わらせなければいけない、という時刻をその作業の最遅完了時
刻Latest Finish timeといいます。後続の作業がない作業の最遅完了時刻はプロジェクト完了
ノードの最早開始時刻、すなわち、プロジェクト完了時刻とします。
最早開始時刻を計算したときと同じように、あるノードを終端ノードとする作業が二つ以上 あった場合、それらの作業は同時に終わればよいので、最遅完了時刻はすべて同じになるはずで す。したがって、「作業の最遅完了時刻」という代わりに「ノードの最遅完了時刻」と言った方 が紛れがないかもしれません。
ノードiの最遅完了時刻をLFiと書くことにして、LFiを計算する方法を考えましょう。ノー ドiを開始ノードとする作業の一つを(i, k)とすると、作業(i, k)は、最遅完了時刻LFkから作 業時間Tikを引いた時刻より後に開始するわけにはいかないので、ノードiを終端とする作業は それ以前に終わっていなければなりません。つまり、ノードiの最遅完了時刻LFiはLFk−Tik
以下でなければいけないということになり、次の式が成り立ちます。
LFi≤LFk−Tik
LFk−Tikは作業(i, k)の最遅開始時刻と言います。ノードiを開始ノードとするすべての作業 についてこのような評価をすれば、最遅完了時刻の漸化式が以下のように得られます。
LFi= min
k∈Out(i){LFk−Tik}
Out(i)はノードiを開始ノードとする作業の終端ノードの集合だったということを思い出して
ください。
例 6.2 たとえば次の図を例にとって説明しましょう。ノード３と４の最遅完了時刻をそれぞれ LF3= 21, LF4= 19とします。作業(2,3)は時刻21までに完了していなければいけません。と いうことは遅くとも時刻LF3−T23= 13には開始していなければ間に合いません。同様に考え て、作業(2,4)は時刻19までに完了していなければいけないので時刻LF4−T24 = 14には開 始しなければいけません。ということは先行作業(1,2)は時刻
min{LF3−T23, LF4−T24}= 13
までには完了していなければプロジェクトを最短時間で終わらせることができないことが分かり ます。ということでノード２の最遅完了時刻はLF2= 13ということになります。
この手順にしたがい、プロジェクトの完了ノードの最遅完了時刻（プロジェクト完了ノードの 最早開始時刻と同じ）から出発して、作業の進行とは逆向きにたどって、各ノードの最遅完了時 刻を順に計算して行けば、プロジェクトの開始ノードの最遅完了時刻は0になっているはずで す。開始ノードなのに完了時刻とは、という疑問に対しては、完了ノードの最早開始時刻と同じ ような解釈をすればよいでしょう。プロジェクトを開始するためには「お祓い」が必要！
最遅完了時刻計算手順のまとめ
1. プロジェクトの完了ノードの最遅完了時刻は、そのノードの最早開始時刻と置く。
2. Out(i)に含まれるすべてのノードの最遅完了時刻が分かっているというノードiにつ
いて、
LFi= min
k∈Out(i){LFk−Tik} を使って最遅完了時刻を計算する。
3. すべてのノードについて最遅完了時刻を計算したとき、プロジェクトの開始ノードの最遅 完了時刻が０であることを確かめる。
PERT計算に必要なのはすべての作業の最遅完了時刻ですが、最早開始時刻の計算と同様に、
ノードiを完了ノードとする作業(k, i)(∀k∈In(i))の最遅完了時刻はノードiの最遅完了時刻 LFiに等しいので、これですべてが計算されたことになる、ということに注意しておきます。
練習6.9 ノード15の後続ノードが16,17,18でそれぞれの最遅完了時刻が25,24,28、作業 (15,16),(15,17),(15,18)の作業時間がそれぞれ8,4,10、ノード15の先行ノードが13と14、 としたとき、ノード15の最遅完了時刻を計算しなさい。また、作業(13,15),(14,15)の最遅完 了時刻を計算しなさい。
最早開始時刻と最遅完了時刻の関係
最遅完了時刻はそれまでに先行作業が終わらないとプロジェクトの進行が遅れるという時刻で すが、言い換えると、その時刻に開始しなければならない作業がある、ということです。一方最 早開始時刻はそれ以降いつでも後続の作業を開始することができるという時刻ですから、ある ノードの最遅完了時刻は最早開始時刻より小さくはないという関係があります。
ESk≤LFk