スケジュール管理手法PERT－Time 　　　　　解　説 　　　“最早開始時間計算のアルゴリズム”

Presentation on theme: "　　スケジュール管理手法PERT－Time 　　　　　解　説 　　　“最早開始時間計算のアルゴリズム”"— Presentation transcript:

1 　　スケジュール管理手法PERT－Time 　　　　　解　説 　　　“最早開始時間計算のアルゴリズム”

2 【 最早開始時間計算アルゴリズムはどこに役立つか 】 ① 多数の仕事を多くの人が協力して行うとき，遅くても
　【 最早開始時間計算アルゴリズムはどこに役立つか 】 ① 多数の仕事を多くの人が協力して行うとき，遅くても 　いつまで仕事が終わるか事前に計算するアルゴリズム． 　「スケジュール管理」の標準アルゴリズムとして有名． 　（実用上は,最も重点的に管理すべきクリティカルパスや作業工程が 　　　　　　　　　　　どの程度余裕があるかの日数計算等の計算も含む） ②　最短経路探索と同様に，情報処理技術者試験にもよく 　　出題される代表的なアルゴリズム　（とゆうことは 　　ソフトウェア開発技術者が知っておくべき基本的な 　　アルゴリズム）．

3 【問題】 グループを組んで，以下のような作業項目と作業日数を もつプログラムを開発するとしたとき，このプログラムは最も早く
【問題】　グループを組んで，以下のような作業項目と作業日数を もつプログラムを開発するとしたとき，このプログラムは最も早く て何日後に完成するか？ (注)“データベーススキーマ設計”と“CGIプログラムの調査”が終わらないと次の作業“CGIプログラムの設計”は開始できない． CGIプログラムの設計 12日 ４ ６ データベースのスキーマ設計 CGIプログラム作成＆テスト 5日 ９日 プログラム機能の決定 8日 ＤＢアクセス プログラム作成 総合テスト ７日 １ 5日 ２ 4日 ７ ８ CGIプログラムの調査 3日 ６日 10日 ３ ５ 画面設計 ホームページ作成 HTML調査とデザイン 《　C/S型プログラム開発作業を例としたアローダイアグラム　》

4 基本的な考え方は，すべて最短経路探索と同じ．
１ 基本的な考え方は，すべて最短経路探索と同じ． 　　　　　トークンを同じ速さで移動させる． 12日 ４ ６ 5日 ９日 8日 5日 ７日 １ ２ 4日 ７ ８ ６日 10日 ３ ５ 3日

5 トークンの移動結果を各ノードに記録して置く
2 トークンの移動結果を各ノードに記録して置く 14 ２ 2 -∞ 　- 2 -∞ - 2 1 経由時間合計 １つ前の経由ノード ノードに入ってくる 入力アークの数 （あらかじめ計算） ノード4に入ってくる入力アーク数 12日 ４ ６ 5 1 １ -∞ 　- 1 -∞ - 2 1 5日 ９日 8日 ７日 １ 5日 ２ 4日 ７ ８ -∞ - 2 3 ６日 10日 ３ ５ 3日 -∞ 　- 1 8 2 1 -∞ 　- 1

6 トークンがノードに到着したとき 3 ① すべてのトークンが到着してるかを見て，到着していなければ待つ（＝トークンを
①　すべてのトークンが到着してるかを見て，到着していなければ待つ（＝トークンを 　　出発させ，次の仕事を始めるためには，前の仕事がすべて終わらなければならな 　　いことを意味している）． 14 ２ 2 １ ノードにトークンが到達したら，“入力アーク数” （=未到着のトークン数を示すデータを兼ねている）を一つ減らす． -∞ - 2 1 経由時間合計 １つ前の経由ノード すでにトークンが出発したノードでは“入力アーク数”は０以外の数(例えば－１）にしておく． 12日 ４ ６ ノードに入ってくる 入力アークの数 5 1 -１ -∞ - 2 1 5日 ９日 8日 ７日 １ ２ 4日 ７ ８ 5日 3日 -∞ - 2 3 ６日 10日 ３ ５ 8 2 　1 -∞ - 2 　0 　1

7 ② ノードに記録されている経由時間合計とトークンが経由してきた時間合計を比較する もしトークンが経由してきた時間合計の方が長ければ
②　ノードに記録されている経由時間合計とトークンが経由してきた時間合計を比較する 　　　　　もしトークンが経由してきた時間合計の方が長ければ 　　　　　　　　　・ノードの経由時間合計を長い方に書き換える 　　　　　　　　　・1つ前の経由ノードをトークンが経由してきたノードに書き換える 15 3 経由時間合計の長い方の時間が経たな ければ，次の仕事は開始できないので， 最も長い経由時間合計（＝その時間にな れば，次の仕事が開始できる最早の時間） をノードに記録する．同時に1つ前の経由 ノードを記録する 14 2 -∞ - 2 1 経由時間合計 １つ前の経由ノード ノードに入ってくる 入力アークの数 12日 ４ ６ -∞ - 2 1 5日 ９日 8日 5日 ７日 １ ２ 4日 ７ ８ 5 1 ‐1 3日 -∞ - 2 3 ６日 10日 ３ ５ 18 3 2 8 2 ‐1

8 トークンがノードから出発するとき 4 ③ 経由時間合計が一番短いノードからトークンを出発させる．
③　経由時間合計が一番短いノードからトークンを出発させる． なぜなら，計算の都合上，一気にトークンが次のノードに移動したのであって，一番 短い経由時間合計の時間には，他のトークンは実際にはアーク上にあり，出発でき ない． 15 3 2 -∞ - 2 1 経由時間合計 　出発させるノードを探すには，入力 ノード数がゼロ（＝すべてのトークン が到着）のノードだけ探せばいい． （※入力ノード数が－１のノードは， すでにトークンが出発したノードを 示しているので対象外） １つ前の経由ノード ノードに入ってくる 入力アーク数 12日 ６ ４ -∞ - 2 1 5日 ９日 8日 ７日 １ 5日 ２ 4日 ７ ８ 5 1 -1 -∞ - 2 3 3日 ６日 10日 ３ 8 2 -1 ５ 18 3 2

9 アルゴリズムをプログラムにするときの考え方
アークで接続している先のノード番号と作業時間は，link表がもっている．　例えば，ノード2から接続しているノードと時間は・・link[i].connectNode link[i].time （詳しくはデータ構造で説明） History[ 4　].totalTime History[　4　].previousNode History[　4　].inputArcCount 15 3 2 ４ 対応 ９日 int ｑ ; // トークンを送るノード番号 q　= 4; // ノード4にトークンを送る 5日 ７日 １ ２ 5 1 ‐1 3日 int ｐ ; // 着目しているノード番号 p = 3; // 　ノード3に着目する ３ 8 2 ‐1

10 《 最早開始時間計算のアルゴリズム 》 トークンの到着 トークンの 出発
《　最早開始時間計算のアルゴリズム　》 　経由経路表(route)の初期値として0，最長経由時間合計表(totalTime) の初期値として 　-∞をそれぞれ設定する 　ｐ に 始点ノード番号をセットする　　　　　　　　// トークンをｐに置く 　ｐが終点ノードに一致するまで繰返す　　　　　　　// トークンがｐに到着するまで繰り返す ｐにリンクしているすべてのノードについて繰返す // 繰返しトークンを移動する 　　　ｑをリンク先のノードの番号とする；　　 // トークンの１つの移動先をｑとする 　　 ノードｑまでの時間をtime_q とする; 　　 　　①ノードqにまだトークンが未到着のアークがあるか（“入力アーク数”>0) 　　　　　/* ②ノードｑに到着したトークンの数と経過距離の比較 */ 　　　　　　　　　　　　ノードｐまでの経由時間 ＋ time_q　>　ノードｑの経由時間 　 　　 /* ノードｐを経由したルートの方が，経由時間合計が短いので 　　　　　　　　　　　　 ノードｐ経由に変更する */ 　　ノードｑの“経由時間合計”をノードｐの“経由時間合計”＋ time_q にする 　　ノードｑの“1つ前の経由ノード”をpにする 　　　ノードｑの“入力アーク数”を一つ減らす　//ｑの未到達のアーク数を減らす すべてのトークンが出発したことを示すために“入力アーク数”を－1にする　 トークンの到着 Yes No トークンの 出発 /* ③ 次にトークンを出発させるノードの決定　*/ 　　ネットーク全体から“入力するアーク数”が０で ，かつ経由時間の最も短い 　　ノードを選び出し，次にトークンを進めるべきノードをｐとする

11 【参考】最短経路探索のアルゴリズム トークンの到着 トークンの 出発
　経由経路表(route)の初期値として0，最短経由距離表(totalDist) の初期値として 　∞をそれぞれ設定する 　ｐ に 始点ノード番号をセットする　　　　　　　　　// トークンをｐに置く 　ｐが終点ノードに一致するまで繰返す　　　　　　　// トークンがｐに到着するまで繰り返す ｐにリンクしているすべてのノードについて繰返す // 繰返しトークンを移動する 　 ｑをリンク先のノードの番号とする；　　//トークンの１つの移動先をｑとする 　　 ノードｑまでの距離をdist_q とする　 　 　　ノードqの出発済みを示すフラッグが降りているか？ 　　　　　　/* ①ノードｑに到着したトークンの経過距離比較 */ 　 ノードｐまでの経由距離 ＋ dist_q　<　ノードｑの経由距離 /* ノードｐを経由したルートの方が，経由距離合計が短いので 　　　　　 ノードｐ経由に変更する */ 　　ノードｑの“経由距離”をノードｐまでの“経由距離 ”＋dist_qにする； 　　ノードｑの“1つ前の経由ノード”をpにする； 　　ノードｑのフラッグを下げる トークンが出発済みであることを示すために，ノードｐのフラッグを上げる Yes No トークンの到着 トークンの 出発 /* ② 次にトークンを出発させるノードの決定　*/ 　　ネットーク全体からフラッグが立っていなくて，かつ経由距離の最も短い 　　ノードを選び出し，次にトークンを進めるべきノードをｐとする

12 《 ネットワークを表すデータ構造 》 Node[] 1 1 2 2 4 2 6 2 Link[]
《　ネットワークを表すデータ構造　》 Node[] ノード１に接続するリンク（＝アーク）データの位置(linkPosition) ノード2に接続するリンク（＝アーク）データの位置(linkPosition) ノード3に接続するリンク（＝アーク）データの位置(linkPosition) ノード4に接続するリンク（＝アーク）データの位置(linkPosition) ノード４に接続するリンク数(linkSize) Link[] connectNode 12日 time ４ ６ ９日 5日 8日 5日 ７日 4日 １ ２ ７ ８ 3日 10日 ６日 ３ ５

13 アルゴリズムの設計と並んで データ構造をいかに設計するかが，計算効率のよさを決める データ構造設計の重要性