スタートページWeb教材一覧オペレーションズリサーチPERT

CPM

学習のポイント

PERTによりプロジェクトの最短完成時刻を求める手順はに学習しました。ここでは,追加費用を払うことにより各作業の所要時間が短縮できるとしたとき,その追加費用を最小にしつつプロジェクトの最短完成時刻をさらに短縮することを考えます。その方法にCPM(クリティカル・パス・メソッド)という方法がありますが,その考え方を理解します。

キーワード

CPM(クリティカル・パス・メソッド),特急時間,費用勾配


問題の理解

下のアローダイヤグラムで赤線がクリティカル・パスを示しており,このプロジェクトの最短完了時刻は27日です。

ここで,人員増強や機械の利用などにより追加費用をかければ所用時間を短縮できるとします。例えば作業1-2は所要時間は6日ですが,1日あたり5円/日(これを費用勾配といいます)の費用を追加することにより,特急時間4日にまで短縮できるとします。これを下のアローダイヤグラムでは
   所要時間≧特急時間(余裕時間)¥費用勾配
の形式で表示しました。なお,費用をかけても短縮できない作業は,特急時間と費用勾配を省略しています。

この最短完了時刻27日を26日,25日,・・・というように短縮したいのですが,追加費用を最小限にして短縮するには,どの作業を短縮すればよいかというのが問題です。このような問題の解法にはCPM(クリティカル・パス・メソッド)という手法があります。ここではCPMによる一般的な手順の説明は省略し,上のアローダイヤグラムでの短縮に限定して,その考え方を理解することを目的にします。

短縮の手順

短縮1

クリティカル・パスの作業のうちから費用勾配の小さい作業を短縮することになります。全作業での費用勾配が最小のものは作業3-5の1円ですが,これはクリティカル・パスの作業ではないので,この作業を短縮してもプロジェクトの短縮にはなりません。クリティカル・パスのなかでは作業5-6の4円が最小ですから,それを短縮することを考えます。特急時間は1日ですが,この作業が2日になると作業4-5の余裕がなくなりますので,とりあえず2日までに短縮することにします。

これにより,4円×7日=28円の追加費用がかかりますがプロジェクトは7日短縮されました。なお,作業4-6の余裕時間がなくなりクリティカルな作業になりました。その結果は次のようになります。

短縮2

作業5-6と作業4-6でさらに1日短縮しようとすると,この2つの作業の費用勾配が3+4=7円になります。それよりもクリティカル・パスでの作業1-2の費用勾配5のほうが安いので,それを特急時間4日まで短縮します。2日短縮され,追加費用は10円です。この短縮をしてもクリティカル・パスには変化がありません。
 次にクリティカル・パスで費用勾配が小さいのは作業2-4の6円です。ここで1日短縮すると作業1-3がクリティカルになりますので,作業2-4を3日で行うことにします。ここまででアローダイヤグラムは次のようになります。

短縮3

イベント4の左右について考えます。イベント4よりも左側で短縮するには,作業1-3と作業2-4を同時に短縮するので,費用勾配は3+6=9円になります。それに対して右側では,作業4-6と作業5-6を同時に短縮するので,費用勾配は3+4=7円ですから,こちらのほうで作業5-6の特急時間限度1日まで短縮します。

短縮4

イベント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


理解度チェック

第1問

  1. 下のアローダイヤグラムでは,
          所要時間≧特急時間(余裕時間)¥費用勾配
    の形式で表示している。
     追加費用を最小限にしつつ,プロジェクト全体の完成期間を短縮せよ。

    短縮1

    期間を短縮するには,クリティカルパスの作業を短縮するしかない。
     Aの部分を短縮するには¥4,Bでは¥3の費用勾配がかかるので,費用勾配の小さいBの部分を短縮する。
     短縮可能日数は,Bでは7-4=3日であるが,余裕期間の最小値はCの部分の1であり,1日短縮するとCの部分もクリティカルパスになるので,短縮できる日数は1日である。
     その結果,作業3-7の所要日数が6日になり,各作業の余裕が1日小さくなり,Bの部分がクリティカルパスになる。

    短縮2

    Dの費用勾配=¥4,Eの費用勾配=(作業2-5の費用勾配)+(作業3-7の費用勾配)=¥2+¥3=¥5なので,Dを短縮する。
     Dでの短縮可能日数=6-3=3日であるが,FとGの余裕が1なので,短縮できる日数は1日である。

    短縮3

    さらに短縮するには,
      ア: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日短縮できる。

    短縮4

    Mで短縮:費用勾配=¥7,短縮可能日数=2日
     NとOで短縮→Nで短縮:費用勾配=¥2,短縮可能日数=1日

    短縮5

    Pで短縮:費用勾配=¥7,短縮可能日数=1日
     Qで短縮:費用勾配=¥2,短縮可能日数=2日

    短縮できるのは,作業1-4と作業6-7であるが,それらを短縮しても全体の日数は短縮されない。すなわちこれが最大短縮の状況である。