スケジュール管理手法PERT－Time 解 説 “最早開始時間計算のアルゴリズム” 【 最早開始時間計算アルゴリズムはどこに役立つか 】 ① 多数の仕事を多くの人が協力して行うとき，遅くても いつまで仕事が終わるか事前に計算するアルゴリズム． 「スケジュール管理」の標準アルゴリズムとして有名． （実用上は,最も重点的に管理すべきクリティカルパスや作業工程が どの程度余裕があるかの日数計算等の計算も含む） ② 最短経路探索と同様に，情報処理技術者試験にもよく 出題される代表的なアルゴリズム （とゆうことは ソフトウェア開発技術者が知っておくべき基本的な アルゴリズム）． 【問題】 グループを組んで，以下のような作業項目と作業日数を もつプログラムを開発するとしたとき，このプログラムは最も早く て何日後に完成するか？ (注)“データベーススキーマ設計”と“CGIプ ログラムの調査”が終わらないと次の作業 “CGIプログラムの設計”は開始できない． CGIプログラムの設計 12日 ４ ６ データベースのスキーマ設計 プログラム機能の決定 １ 5日 5日 ９日 CGIプログラム作成＆テスト 8日 ＤＢアクセス ７日 ２ プログラム作成 ７ 総合テスト 4日 CGIプログラムの調査 3日 ３ 10日 画面設計 HTML調査と デザイン 《 ５ ６日 ホームページ作成 C/S型プログラム開発作業を例としたアローダイアグラム 》 ８ １ 基本的な考え方は，すべて最短経路探索と同じ． トークンを同じ速さで移動させる． ４ ６ 5日 ９日 8日 5日 １ 12日 ７日 ２ ７ ３ 3日 10日 ５ ６日 4日 ８ 2 トークンの移動結果を各ノードに記録して置く 14 -∞ ２2 22 ノード4に入ってくる入力アーク数 -∞ 5 11 １ １ 5日 ４ 経由時間合計 -∞ 21 12日 １つ前の経由ノード ノードに入ってくる 入力アークの数 （あらかじめ計算） ６ -∞ 21 5日 ９日 8日 ７日 ２ ７ 3日 ３ 8 -∞ 221 1 10日 ６日 ５ -∞ 1 -∞ 23 4日 ８ 3 トークンがノードに到着したとき ① すべてのトークンが到着してるかを見て，到着していなければ待つ（＝トークンを 出発させ，次の仕事を始めるためには，前の仕事がすべて終わらなければならな いことを意味している）． ノードにトークンが到達したら，“入力アーク数” 14 （=未到着のトークン数を示すデータを兼ねて いる）を一つ減らす． すでにトークンが 出発したノードでは “入力アーク数”は ０以外の数(例えば －１）にしておく． ２ １ 22 ４ 5 1 経由時間合計 -∞ 12日 ６ 2 1 １つ前の経由ノード ノードに入ってくる 入力アークの数 5日 ９日 8日 -１ １ ７日 ２ 5日 ７ 3日 10日 ３ 8 2 20 1 ５ ６日 -∞ 21 -∞ 23 4日 -∞ 21 ８ ② ノードに記録されている経由時間合計とトークンが経由してきた時間合計を比較する もしトークンが経由してきた時間合計の方が長ければ ・ノードの経由時間合計を長い方に書き換える ・1つ前の経由ノードをトークンが経由してきたノードに書き換える 経由時間合計の長い方の時間が経たな 15 14 ければ，次の仕事は開始できないので， 最も長い経由時間合計（＝その時間にな れば，次の仕事が開始できる最早の時 間） -∞ ６ 21 32 20 ４ 経由時間合計 12日 １つ前の経由ノード ノードに入ってくる 入力アークの数 をノードに記録する．同時に1つ前の経由 ノードを記録する 5日 ９日 8日 5日 １ ７日 ２ 5 1 ‐1 ７ 3日 10日 ３ ５ ６日 8 18 2 3 2‐1 20 -∞ 23 4日 -∞ 21 ８ 4 トークンがノードから出発するとき ③ 経由時間合計が一番短いノードからトークンを出発させる． なぜなら，計算の都合上，一気にトークンが次のノードに移動したのであって，一番 短い経由時間合計の時間には，他のトークンは実際にはアーク上にあり，出発でき ない． 15 出発させるノードを探すには，入力 ノード数がゼロ（＝すべてのトークン が到着）のノードだけ探せばいい． （※入力ノード数が－１のノードは， すでにトークンが出発したノードを 示しているので対象外） ９日 １ 5日 -∞ ６ 21 3 ４ 20 経由時間合計 12日 １つ前の経由ノード ノードに入ってくる 入力アーク数 5日 8日 ７日 ２ ７ 5 1 -1 3日 ３ 10日 8 ５ ６日 18 2 3 2-1 20 -∞ 23 4日 -∞ 21 ８ アルゴリズムをプログラムにするときの考え方 アークで接続している先のノード番 号と作業時間は，link表がもって いる． 例えば，ノード2から接続し ているノードと時間は・・ link[i].connectNode link[i].time 15 History[ 4 ].totalTime 3 History[ 4 ].previousNode 20 History[ 4 ].inputArcCount ４ （詳しくはデータ構造で説明） ９日 対応 int ｑ ; // トークンを送るノード番号 5日 １ ７日 ２ 5 3日 1 ‐1 q = 4; // ノード4にトークンを送る ３ 8 2 2‐1 int ｐ ; // 着目しているノード番号 p = 3; // ノード3に着目する 《 最早開始時間計算のアルゴリズム 》 経由経路表(route)の初期値として0，最長経由時間合計表(totalTime) の初期値として -∞をそれぞれ設定する ｐ に 始点ノード番号をセットする // トークンをｐに置く ｐが終点ノードに一致するまで繰返す // トークンがｐに到着するまで繰り返す ｐにリンクしているすべてのノードについて繰返す // 繰返しトークンを移動する ｑをリンク先のノードの番号とする； ノードｑまでの時間をtime_q とする; トークンの到着 Yes ①ノードqにまだトークンが未到着のアークがあるか（“入力アーク数”>0) No /* Yes // トークンの１つの移動先をｑとする ②ノードｑに到着したトークンの数と経過距離の比較 */ ノードｐまでの経由時間 ＋ time_q > ノードｑの経由時間 No /* ノードｐを経由したルートの方が，経由時間合計が短いので ノードｐ経由に変更する */ ノードｑの“経由時間合計”をノードｐの“経由時間合計”＋ time_q にする ノードｑの“1つ前の経由ノード”をpにする ノードｑの“入力アーク数”を一つ減らす //ｑの未到達のアーク数を減らす すべてのトークンが出発したことを示すために“入力アーク数”を－1にする トークンの 出発 /* ③ 次にトークンを出発させるノードの決定 */ ネットーク全体から“入力するアーク数”が０で ，かつ経由時間の最も短い ノードを選び出し，次にトークンを進めるべきノードをｐとする 【参考】最短経路探索のアルゴリズム 経由経路表(route)の初期値として0，最短経由距離表(totalDist) の初期値として ∞をそれぞれ設定する ｐ に 始点ノード番号をセットする ｐが終点ノードに一致するまで繰返す // トークンをｐに置く // トークンがｐに到着するまで繰り返す ｐにリンクしているすべてのノードについて繰返す // 繰返しトークンを移動する トークンの到着 ｑをリンク先のノードの番号とする； ノードｑまでの距離をdist_q とする Yes //トークンの１つの移動先をｑとする ノードqの出発済みを示すフラッグが降りているか？ /* ①ノードｑに到着したトークンの経過距離比較 */ ノードｐまでの経由距離 ＋ dist_q < ノードｑの経由距離 Yes /* ノードｐを経由したルートの方が，経由距離合計が短いので ノードｐ経由に変更する */ ノードｑの“経由距離”をノードｐまでの“経由距離 ”＋dist_qにする； ノードｑの“1つ前の経由ノード”をpにする； ノードｑのフラッグを下げる No No トークンが出発済みであることを示すために，ノードｐのフラッグを上げる トークンの 出発 /* ② 次にトークンを出発させるノードの決定 */ ネットーク全体からフラッグが立っていなくて，かつ経由距離の最も短い ノードを選び出し，次にトークンを進めるべきノードをｐとする 《 ネットワークを表すデータ構造 》 Node[ 1 ] 1 1 3 2 2 ノード2に接続す るリンク（＝アー ク）データの位置 (linkPosition) ノード１に接続す るリンク（＝アー ク）データの位置 (linkPosition) Link[] 1 2 5 2 2 4 2 4 9 time 5 ４ 6 7 12日 ６ 5日 8日 ７日 ２ 3日 ノード４に接続する リンク数(linkSize) 4 7 5 10 6 12 7 5 ９日 １ 2 ノード4に接続す るリンク（＝アー ク）データの位置 (linkPosition) 4 connectNode 5日 6 ノード3に接続す るリンク（＝アー ク）データの位置 (linkPosition) 3 3 3 4 ３ 10日 ７ ５ ６ 日 4日 ８ 8 アルゴリズムの設計と並んで データ構造をいかに設計するかが，計算効率のよさを決める データ構造設計の重要性
© Copyright 2024 ExpyDoc
