最小費用日程計画
最小費用日程計画とは
- ある一定期間でプロジェクトを完成するために，最も費用のかからない日程を求める
例題２-１
右のようなプロジェクトがある. プロジェクト完了時刻の経済的な短縮方法を提案せよ.
CPMとは
- CPM: Critical Path Method
- 作業時間と費用にトレードオフの関係がある時に，プロジェクト完了時刻を経済的に短縮することを目的とした手法．
プロジェクト完了時刻短縮時に考慮すべき作業群
カット
プロジェクト開始イベントと終了イベントを二分する線上の作業群
カットと作業の向き
正の向き：カットの開始イベント側から終了イベント側へ
カットの短縮費用
＝（カットに含まれるクリティカルパス上の） 正の向きの作業の短縮費用の合計
ー 既に短縮されたことのある逆向きの作業の短縮費用の合計
- Minimum Cut（最小カット）: 短縮費用最小のCut
練習
（３）現在の状況で，すべてのカットに関する短縮費用を求めよう
（５）最小カット上かつクリティカルカット上の作業に 投資することにより短縮できる最大日数は？
例題2-1（続き）ＣＰＭで解いてみよう
⇒Minimum Cut はCut1 作業Ａを短縮
例題２-１（続き）作業Ａ短縮後
⇒Minimum Cut はCut３ 作業Ｄを短縮
例題２-１（続き）作業Ｄ短縮後
⇒Minimum Cut はCut３ 作業ＣとＤを同時に短縮
例題２-１（続き）作業Ｃ・Ｄ短縮後
⇒Minimum Cut はCut２ 作業ＢとＣを同時に短縮
例題２-１（続き）作業Ｂ・Ｃ短縮後
⇒この後はどこを短縮しても 効果はない．（なぜ?）
例題２-１（続き） まとめると
ＣＰＭの概略
- 短縮可能な限り以下を繰り返す．
- 各種時刻情報を算出する （クリティカル・パスの情報は特に重要）
- Minimum Cut を見つける
- Minimum Cut の作業に費用を投入し可能な限り作業日程の短縮を行う
演習2-1
以下のようなプロジェクトがある.経済的な短縮方法とその時の費用との関係を求めよ.
演習2-2
以下のようなプロジェクトがある.経済的な短縮方法とその時の費用との関係を求めよ.
例題2-2 逆向き作業を含んだカット
一度短縮を決めた作業を，延ばした場合がよい時もある．
- 以下のプロジェクトの，プロジェクト完了時刻と短縮費用の関係を見てみよう.
例題2-2（続き） カットを探す
⇒Minimum Cut はCut３ 作業Ｃを短縮
例題2-2（続き） Minimum Cutは？
例題2-2（続き） 逆向きのクリティカルな作業がカットに含まれる場合
作業Ａ,Ｅを1日短縮 ＋作業Ｃを1日再延長した場合
逆向きの作業が過去に短縮された時は考慮する必要がある
例題2-2（続き）作業Ａ・Ｅ短縮＋作業Ｃ再延長後
例題2-2（続き） 作業Ｄ・Ｅ短縮後
例題2-2（続き） 作業Ｂ・Ｃ・Ｄ短縮後
例題２-２（続き） まとめ
まとめ
- ＣＰＭにより，最小費用日程計画を求めることができる．
図を見ながら最小カットを捜していく方法では， プロジェクトが複雑になった場合限界がある
「ネットワーク計画」の手法を用いて最小カットを見つけると
演習2-3
以下のようなプロジェクトがある.経済的な短縮方法とその時の費用との関係を求めよ.