スタートページ> Web教材一覧> オペレーションズリサーチ> PERT
PERTによりプロジェクトの最短完成時刻を求める手順は先に学習しました。ここでは,追加費用を払うことにより各作業の所要時間が短縮できるとしたとき,その追加費用を最小にしつつプロジェクトの最短完成時刻をさらに短縮することを考えます。
その方法にCPM(クリティカル・パス・メソッド)という方法がありますが,そのアルゴリズムは複雑です。こでは、CPMの考え方を理解するだけにします。
CPM(クリティカル・パス・メソッド),特急時間,費用勾配
下のアローダイヤグラムで赤線がクリティカル・パスを示しており,このプロジェクトの最短完了時刻は27日です。
ここで,人員増強や機械の利用などにより追加費用をかければ所用時間を短縮できるとします。例えば作業1-2は所要時間は6日ですが,1日あたり5円/日(これを費用勾配といいます)の費用を追加することにより,特急時間4日にまで短縮できるとします。これを下のアローダイヤグラムでは
所要時間≧ (余裕時間)¥費用勾配
の形式で表示しました。なお,費用をかけても短縮できない作業は,特急時間と費用勾配を省略しています。
全体所要日数=27日
クリティカルパス=1→2→4→5→6
開始 終了 日数 特急日数 費用勾配 (余裕)
1 2 6 4 5 0
1 3 7 4 3 3
1 4 5 4 2 5
2 4 4 1 6 0
3 4 0 0 ∞ 0
3 5 3 2 1 8
4 5 8 0 ∞ 0
5 6 9 1 4 0
この最短完了時刻27日を26日,25日,・・・というように短縮したいのですが,追加費用を最小限にして短縮するには,どの作業を短縮すればよいかというのが問題です。このような問題の解法にはCPM(クリティカル・パス・メソッド)という手法があります。
クリティカル・パスの作業のうちから費用勾配の小さい作業を短縮することになります。全作業での費用勾配が最小のものは作業3-5の1円ですが,これはクリティカル・パスの作業ではないので,この作業を短縮してもプロジェクトの短縮にはなりません。クリティカル・パスのなかでは作業5-6の4円が最小ですから,それを短縮することを考えます。特急時間は1日ですが,この作業が2日になると作業4-5の余裕がなくなりますので,とりあえず2日までに短縮することにします。
これにより,4円×7日=28円の追加費用がかかりますがプロジェクトは7日短縮されました。なお,作業4-6の余裕時間がなくなりクリティカルな作業になりました。その結果は次のようになります。
作業5-6と作業4-6でさらに1日短縮しようとすると,この2つの作業の費用勾配が3+4=7円になります。それよりもクリティカル・パスでの作業1-2の費用勾配5のほうが安いので,それを特急時間4日まで短縮します。2日短縮され,追加費用は10円です。この短縮をしてもクリティカル・パスには変化がありません。
次にクリティカル・パスで費用勾配が小さいのは作業2-4の6円です。ここで1日短縮すると作業1-3がクリティカルになりますので,作業2-4を3日で行うことにします。ここまででアローダイヤグラムは次のようになります。
イベント4の左右について考えます。イベント4よりも左側で短縮するには,作業1-3と作業2-4を同時に短縮するので,費用勾配は3+6=9円になります。それに対して右側では,作業4-6と作業5-6を同時に短縮するので,費用勾配は3+4=7円ですから,こちらのほうで作業5-6の特急時間限度1日まで短縮します。
イベント4の右側では,もはや短縮することはできませんので,作業1-3と作業2-4を短縮します。その限界は作業2-4の2日です。その結果,作業1-4もクリティカルになりました。この段階で,作業1-2,2-4,4-5,5-6のクリティカル・パスが短縮不可能になりましたので,これ以上は短縮できないことになります。
以上の短縮経過を表にすると次のようになります。
短縮作業 費用勾配 短縮時間 追加費用 その累計 完了時刻
5-6 4円/日 7日 28円 28円 20日
1-2 5 2 10 38 18
2-4 6 1 6 44 17
4-6,5-6 7 1 7 51 16
1-3,2-4 9 2 18 69 14
右のアローダイヤグラムでは,
所要時間≧特急時間(余裕時間)¥費用勾配
の形式で表示している。
追加費用を最小限にしつつ,プロジェクト全体の完成期間を短縮せよ。
全体所要日数=13日
クリティカルパス=0→2→3→7
開始 終了 日数 特急日数 費用勾配 (余裕)
1 2 6 3 4 0
1 3 5 3 3 1
1 4 3 1 1 4
1 6 7 4 1 2
2 3 0 0 ∞ 0
2 5 4 2 2 1
3 7 7 4 3 0
4 6 2 0 ∞ 4
5 7 2 1 ∞ 1
6 7 4 2 3 2
期間を短縮するには,クリティカルパスの作業を短縮するしかない。
Aの部分を短縮するには¥4,Bでは¥3の費用勾配がかかるので,費用勾配の小さいBの部分を短縮する。
短縮可能日数は,Bでは7-4=3日であるが,余裕期間の最小値はCの部分の1であり,1日短縮するとCの部分もクリティカルパスになるので,短縮できる日数は1日である。
その結果,作業3-7の所要日数が6日になり,各作業の余裕が1日小さくなり,Bの部分がクリティカルパスになる。
Dの費用勾配=¥4,Eの費用勾配=(作業2-5の費用勾配)+(作業3-7の費用勾配)=¥2+¥3=¥5なので,Dを短縮する。
Dでの短縮可能日数=6-3=3日であるが,FとGの余裕が1なので,短縮できる日数は1日である。
さらに短縮するには,
ア:HとIで短縮
イ:JとKで短縮
を同時に行わなければならない。
アでは,Hの費用勾配=¥4+¥3=¥7,Iの費用勾配=¥2+¥3=¥5・・・Iを短縮
イでは,Jの費用勾配=¥1,Kの費用勾配=¥3・・・Jを短縮
なので,IとJを短縮することになる(費用勾配=¥5+¥3=¥8)
短縮可能日数は,Iでは2日,Jでは3日,Kでは2日なので,2日短縮できる。
Mで短縮:費用勾配=¥7,短縮可能日数=2日
NとOで短縮→Nで短縮:費用勾配=¥2,短縮可能日数=1日
Pで短縮:費用勾配=¥7,短縮可能日数=1日
Qで短縮:費用勾配=¥2,短縮可能日数=2日
短縮できるのは,作業1-4と作業6-7であるが,それらを短縮しても全体の日数は短縮されない。すなわちこれが最大短縮の状況である。
短縮日数 所要日数 増加費用
0 13 0
1 12 3
2 11 7
4 9 19
5 8 28
6 7 38