《プロジェクト管理》
【ぷろじぇくとかんり (project management) 】
大規模な建設や研究開発をプロジェクト(project)とよび, これらプロジェクトを計画・設計・日程立案・組織化し, その実行過程を統制することをプロジェクト管理という. しかし実際には, プロジェクト管理の意味するところは, その言葉を使う人によって異なる. ORの分野では伝統的に, PERT/CPMなど問題を解く技術的な側面に主な関心がもたれてきたが, ほかの分野では, プロジェクト組織といった, 人間が関係する側面により関心が払われてきた.
PERT/CPMは, プロジェクト・スケジューリング(project scheduling)と総称される. PERT}は作業(job, activity)の所要時間に関して確率的取扱いを含むのに対し, CPMは決定論的アプローチである. それでも, これら2つの方法はよく似た手法であり, PERT/CPM法とよばれる [1, 2].
(1)PERT: PERTは, それまで使われてきたガントチャート(バーチャートともいう)に替わって, 大規模な工事の計画・管理の手法として, 1958年に米海軍のポラリス・ミサイル開発プロジェクトのために生み出された.
PERTでは, プロジェクトを構成する作業の先行関係を表現するのに, 矢線(arrow)と結合点(node, event)とからなる有向のネットワーク図を用い, これに基づいて日程を計画・管理する手法である. また, このネットワーク図をアローダイヤグラムや矢線図(arrow diagram)とよび, そのかき方に次の3つのルールがある.
(i)1つの作業は2つの結合点を結ぶ1つの矢線で図示し, 矢線の両端の結合点番号の対 $ (i,j) $ によって作業を表す(図1 (a)参照).
(ii)「作業Cは作業AとBがすむと取りかかることができる」という先行関係は, 図 \ref{C-B-03+tamu2}(b)のように表現する. 作業の先行関係を正確に表現するためにダミー作業が使われる(図1 (c)参照).
(iii)付番を一意的とするため, 平行作業には図1 (d)のようにダミー作業を導入する.
\begin{figure}[h]
\begin{center}
\vspace{-4mm}
\includegraphics[scale=0.6]{0179-C-B-03-kiso-zu1.eps}
% \epsfile{file=C-B-03-kiso-zu1.eps,width=8cm}
\vspace{-2mm}
\caption{作業と先行関係の表現法} \label{C-B-03+tamu2}
\vspace{-2mm}
\end{center}
\end{figure}
アローダイヤグラムの例を図2に示す.
%%%
\begin{figure}
\begin{center}
%\vspace{-4mm}
%\includegraphics[scale=0.6]{0179-C-B-03-kiso-zu2.eps}
\includegraphics[scale=0.6]{0179-diagram.eps}
% \epsfile{file=C-B-03-kiso-zu2.eps,width=8cm}
\vspace{-2mm}
\caption{アローダイヤグラムと結合点時刻の例} \label{C-B-03+tamu3}
\vspace{-2mm}
\end{center}
\end{figure}
作業 $ (i,j) $ の作業時間 $ D_{ij} $ が与えられたとき, 結合点 $ j $ に最も早く到達しうる時刻を最早結合点時刻(earliest node time) $ t_j^E $ とよび,
\left \{
\begin{array}{ll}
t_1^E=0 & \\
t_j^E= {\max}_{(i,j) \in P} (t_i^E + D_{ij}) & \ j=2,3,\ldots ,n
\end{array}
\right.
---
---
で計算する. ただし, $ P $ はプロジェクト全体の作業集合, $ n $ は終点を意味する. この計算は前進計算という. 上式により求めた $ t_n^E $ はプロジェクト全体の工期(総所要日数ともいう)を与える. つぎに, この工期から逆算して, 結合点 $ j $ に遅くとも到達していなければならない限界の時刻である最遅結合点時刻(latest node time) $ t_j^L $ を次式から求める.
\left \{ \begin{array}{ll} t_n^L=t_n^E & \\ t_j^L=\min_{(j,k) \in P} (t_k^L - D_{jk}) & j=1,2,\ldots ,n-1 \end{array} \right.
---
---
この計算を後進計算という. これらの結合点時刻から, 各作業の開始時刻と終了時刻の限界が次式より求められる.
\left \{
\begin{array}{ll}
\mbox{最早開始時刻} & ES_{ij} = t_i^E \\
\mbox{最遅開始時刻} & LS_{ij} = t_j^L - D_{ij} \\
\mbox{最早終了時刻} & EF_{ij} = t_i^E + D_{ij} \\
\mbox{最遅終了時刻} & LF_{ij} = t_j^L
\end{array}
\right.
---
array の日本語
---
最早時刻と最遅時刻とに差異がある場合には, その作業に日程上の余裕があることを意味し, この余裕をフロート(float)とよぶ. 作業 $ (i,j) $ の全余裕時間(total float) $ TF_{ij} $ と自由余裕(freefloat) $ FF_{ij} $ は, 次式から求められる.
\begin{array}{l}
TF_{ij} = t_j^L - t_i^E - D_{ij} = LF_{ij} - EF_{ij} \\
FF_{ij} = t_j^E - t_i^E - D_{ij}
\end{array}
---
---
アローダイヤグラムの矢線を順方向にたどって, 始点から終点に至る作業の列をパス(path)とよぶ. とくに $ TF_{ij}=0 $ の作業の列で形成されるパスはクリティカルパス(criticalpath)とよばれ, その長さはすべてのパスのうち最長となっている.
PERT手法を基礎として種々な拡張が試みられている [3], [4]. 例えば, (i)作業に確率的選択の要素を入れたGERT(graphical evaluation and review technique)やVERT(ventureevaluation and review technique), (ii)PERTの時間的要素とともに費用に関するデータを考慮して, 日程と費用の両面から計画・管理を行うPERT/COST, (iii) 資源制約を考慮して, その山積み・山崩しをアローダイヤグラムを基礎に実施しようとする資源制約付きプロジェクト・スケジューリング, (iv)単一プロジェクトから複数のプロジェクトの管理へ展開するRAMPS(resource allocationand multi-project scheduling), などがある.
また, PERT計算で必要な各作業の所要時間は3点見積法で見積もられることが多い.
(2)CPM: CPMでは, アローダイヤグラムを構成する各作業 $ (i,j) $ の所要時間が投入費用によって可変であるとし, 両者の間に図3のような線形関係を仮定して日程計算を行う. 各作業を標準時間 $ D_{ij} $ で行うときの費用を $ M_{ij} $ , 特急時間で処理するときの費用を $ m_{ij} $ とするとき, 所要時間 $ y_{ij} $ ( $ d_{ij} \le y_{ij} \le D_{ij} $ )に対する費用 $ z_{ij} $ は
z_{ij} = -c_{ij}y_{ij} + k_{ij}
---
---
で与えられる. ただし,
c_{ij} = (m_{ij} - M_{ij})/(D_{ij} - d_{ij})
---
---
は, 作業を単位時間短縮するのに要する増加費用で, 費用増加率とよばれる. $ k_{ij} $ は定数項である.
CPMは, 以下のように定式化される. アローダイヤグラムの結合点 $ i $ ( $ i=1,2,\ldots ,n $ )の結合点時刻を $ t_i $ , 達成したいプロジェクト全体の工期を $ \lambda $ ( $ =t_n $ )とすると,
制約条件:
\left \{ \begin{array}{ll} y_{ij} + t_i - t_j \le 0 & (i,j) \in P \\ t_1 = 0 \\ t_n = \lambda \\ d_{ij} \le y_{ij} \le D_{ij} \end{array} \right.
---
---
のもとで, プロジェクトの総費用
z(\lambda)=\sum_{(i,j)\in P} (-c_{ij} y_{ij} + k_{ij})
---
---
を最小化するような日程計画\{ $ t_i, y_{ij} $ \}を求める問題となる. ここで, $ P $ はプロジェクトの作業集合を意味する.
CPMの解法にはいくつかの方法がある. 1つの方法は, CPM問題を工期 $ \lambda $ をパラメタとするパラメトリック線形計画法(parametric LP)と見なして解く解法で, プライマル・デュアル法(primal-dual algorithm)に基づく解法が提案されている. より広く使われている解法にラベリング法(labeling algorithm)がある. この方法は, 各作業の費用増加率 $ c_{ij} $ を矢線の容量制約とし, 始点から終点に最大フローを流す問題としてCPM問題を解く方法である. 多くの解法が提案されており, その計算量の比較も行われている [5].
\begin{figure}[h]
\begin{center}
\vspace{-4mm}
\includegraphics[scale=0.6]{0179-C-B-03-kiso-zu3.eps}
\vspace{-2mm}
\caption{費用関数} \label{C-B-03+tamu4}
\vspace{-2mm}
\end{center}
\end{figure}
プロジェクト・スケジューリングの最近の研究が [6, 7]にまとめられている.
参考文献
[1] 関根智明,『PERT・CPM』,日科技連出版社, 1973.
[2] 刀根薫,『PERT入門』,東洋経済新報社, 1977.
[3] S. E. Elmaghraby, Activity Networks, John Wiley & Sons, 1977. 加瀬滋男『アクティビティネットワーク』,日刊工業新聞社, 1979.
[4] S. I. Gass and C. M. Harris, eds., Encyclopedia of Operations Research and Management Science, Kluwer Academic, 1996. 森村英典, 刀根薫, 伊理正夫監訳,『経営科学OR用語大辞典』,朝倉書店, 1999.
[5] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Network Flows," in Optimization, G. L. Nemhauser, A. H. G. Rinnooy Kan and M. J. Todd, eds., North-Holland, 1989.
[6] L. V. Tavares, Advanced Models for Project Management, Kluwer Academic, 1999.
[7] J. Weglarz, ed., it Project Scheduling: Recent Models, Algorithms and Applications, Kluwer Academic Publishers, 1999.