問題の理解
下のアローダイヤグラムで赤線がクリティカル・パスを示しており，このプロジェクトの最短完了時刻は２７日です。
ここで，人員増強や機械の利用などにより追加費用をかければ所用時間を短縮できるとします。例えば作業１－２は所要時間は６日ですが，１日あたり５円／日（これを費用勾配といいます）の費用を追加することにより，特急時間４日にまで短縮できるとします。これを下のアローダイヤグラムでは
所要時間≧（余裕時間）￥費用勾配
の形式で表示しました。なお，費用をかけても短縮できない作業は，特急時間と費用勾配を省略しています。
全体所要日数＝２７日
クリティカルパス＝１→２→４→５→６
開始 終了 日数 特急日数 費用勾配 (余裕)
１ ２ ６ ４ ５ ０
１ ３ ７ ４ ３ ３
１ ４ ５ ４ ２ ５
２ ４ ４ １ ６ ０
３ ４ ０ ０ ∞ ０
３ ５ ３ ２ １ ８
４ ５ ８ ０ ∞ ０
５ ６ ９ １ ４ ０
この最短完了時刻２７日を２６日，２５日，・・・というように短縮したいのですが，追加費用を最小限にして短縮するには，どの作業を短縮すればよいかというのが問題です。このような問題の解法にはＣＰＭ（クリティカル・パス・メソッド）という手法があります。
短縮の手順
短縮１
クリティカル・パスの作業のうちから費用勾配の小さい作業を短縮することになります。全作業での費用勾配が最小のものは作業３－５の１円ですが，これはクリティカル・パスの作業ではないので，この作業を短縮してもプロジェクトの短縮にはなりません。クリティカル・パスのなかでは作業５－６の４円が最小ですから，それを短縮することを考えます。特急時間は１日ですが，この作業が２日になると作業４－５の余裕がなくなりますので，とりあえず２日までに短縮することにします。
これにより，４円×７日＝２８円の追加費用がかかりますがプロジェクトは７日短縮されました。なお，作業４－６の余裕時間がなくなりクリティカルな作業になりました。その結果は次のようになります。
短縮２
作業５－６と作業４－６でさらに１日短縮しようとすると，この２つの作業の費用勾配が３＋４＝７円になります。それよりもクリティカル・パスでの作業１－２の費用勾配５のほうが安いので，それを特急時間４日まで短縮します。２日短縮され，追加費用は１０円です。この短縮をしてもクリティカル・パスには変化がありません。
次にクリティカル・パスで費用勾配が小さいのは作業２－４の６円です。ここで１日短縮すると作業１－３がクリティカルになりますので，作業２－４を３日で行うことにします。ここまででアローダイヤグラムは次のようになります。
短縮３
イベント４の左右について考えます。イベント４よりも左側で短縮するには，作業１－３と作業２－４を同時に短縮するので，費用勾配は３＋６＝９円になります。それに対して右側では，作業４－６と作業５－６を同時に短縮するので，費用勾配は３＋４＝７円ですから，こちらのほうで作業５－６の特急時間限度１日まで短縮します。
短縮４
イベント４の右側では，もはや短縮することはできませんので，作業１－３と作業２－４を短縮します。その限界は作業２－４の２日です。その結果，作業１－４もクリティカルになりました。この段階で，作業１－２，２－４，４－５，５－６のクリティカル・パスが短縮不可能になりましたので，これ以上は短縮できないことになります。
以上の短縮経過を表にすると次のようになります。
短縮作業 費用勾配 短縮時間 追加費用 その累計 完了時刻
５－６ ４円/日 ７日 ２８円 ２８円 ２０日
１－２ ５ ２ １０ ３８ １８
２－４ ６ １ ６ ４４ １７
４－６，５－６ ７ １ ７ ５１ １６
１－３，２－４ ９ ２ １８ ６９ １４
