PERTチャートにおけるクリティカルパスを求める並列アルゴリズム(アルゴリズム理論)

概要

論文の詳細を見る
PERT(Program Evaluation and Review Technique)解析の1つに,PERTチャートにおけるクリティカルパス(critical path)を求める問題があるが,そのクリティカルパスを求める効率良い並列アルゴリズムは見当たらない.本稿では,すでに提案した効率良い並列トポロジカル整列アルゴリズムをもとに,PERTチャートをDAG(Directed Acyclic Graph)の節点に重み付けして表し,CREW-PRAM計算機モデルのもとでPERTチャートにおけるクリティカルパスを求める並列アルゴリズムを提案する.具体的には,まずPERTチャートを入出次数がたかだか1の線形リストに分割し,これを併合しながら各節点の最長所要時間を求める.次にその逆向線形リストを構成し,同様に各節点の最長所要時間を求める.これら2つの最長所要時間を用いて各節点の最早開始時刻(earliest start time),最遅開始時刻(latest start time)および余裕時間(floating time)を求める.最後に節点と経路の判定を定数時間で行い,PERTチャートにおけるすべてのクリティカルパスを求める並列アルゴリズムである.PERTチャートにおいて節点数n,辺数mとするとき,提案する並列アルゴリズムの計算量はCREW-PRAMモデルで,プロセッサ数がO(n+m),時間量がO(log^2m)である.
2006-07-15