(57)【特許請求の範囲】
【請求項１】
スケジュールを構成するｎ個（ｎは１以上の整数）のタスク｛ｖ１，ｖ２，・・，ｖｎ｝から成るタスクグラフを解析するタスクグラフ解析装置であって、
上記ｎ個のタスクを識別するタスク識別情報、上記ｎ個のタスクの上記スケジュール上での処理順序を表す順序情報、および上記ｎ個のタスクの負荷の大きさを表す負荷情報を含むタスク情報を入力するタスク情報入力部と、
上記タスク情報入力部により上記タスク情報が入力された上記ｎ個のタスクの先頭に開始タスクｖ０として０番目のタスク情報を仮設定するとともに、上記ｎ個のタスクの末尾に終了タスクｖｎ＋１としてｎ＋１番目のタスク情報を仮設定するタスク仮設定部と、
上記タスク情報入力部により入力された上記ｎ個のタスクの上記タスク情報と上記タスク仮設定部により仮設定された上記開始タスクおよび上記終了タスクの上記タスク情報とに基づいて、タスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）からタスクｖｊ（ｊ＝０，１，・・，ｎ，ｎ＋１）までのクリティカルパスをそれぞれ算出し、それぞれのクリティカルパス毎にパス上に含まれるタスクを求めるクリティカルパス算出部と、
上記タスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）のそれぞれについて、当該タスクｖｉから始まるそれぞれのクリティカルパス上に含まれるタスクの総数を上記タスクｖｉの評価値として算出する評価値算出部とを備えたことを特徴とするタスクグラフ解析装置。
【請求項２】
上記タスク情報に含まれる上記タスク識別情報および上記順序情報に基づいて、上記各タスクの先行後続関係をタスクグラフとして表示装置に表示するマップ表示部を更に備え、
上記マップ表示部は、上記評価値算出部により算出された評価値の大きさに応じて、上記タスクｖｉから出力される上記先行後続関係を表す線の表示態様を異ならせるようにしたことを特徴とする請求項１に記載のタスクグラフ解析装置。
【請求項３】
スケジュールを構成するｎ個（ｎは１以上の整数）のタスク｛ｖ１，ｖ２，・・，ｖｎ｝から成るタスクグラフを解析するためのコンピュータ読み取り可能なプログラムであって、
上記ｎ個のタスクを識別するタスク識別情報、上記ｎ個のタスクの上記スケジュール上での処理順序を表す順序情報、および上記ｎ個のタスクの負荷の大きさを表す負荷情報を含むタスク情報を入力するタスク情報入力手段、
上記タスク情報入力手段により上記タスク情報が入力された上記ｎ個のタスクの先頭に開始タスクｖ０として０番目のタスク情報を仮設定するとともに、上記ｎ個のタスクの末尾に終了タスクｖｎ＋１としてｎ＋１番目のタスク情報を仮設定するタスク仮設定手段、
上記タスク情報入力手段により入力された上記ｎ個のタスクの上記タスク情報と上記タスク仮設定手段により仮設定された上記開始タスクおよび上記終了タスクの上記タスク情報とに基づいて、タスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）からタスクｖｊ（ｊ＝０，１，・・，ｎ，ｎ＋１）までのクリティカルパスをそれぞれ算出し、それぞれのクリティカルパス毎にパス上に含まれるタスクを求めるクリティカルパス算出手段、および
上記タスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）のそれぞれについて、当該タスクｖｉから始まるそれぞれのクリティカルパス上に含まれるタスクの総数を上記タスクｖｉの評価値として算出する評価値算出手段、
としてコンピュータを機能させるためのコンピュータ読み取り可能なタスクグラフ解析プログラム。
【請求項４】
上記タスク情報に含まれる上記タスク識別情報および上記順序情報に基づいて、各タスクの先行後続関係をタスクグラフとして表示装置に表示するマップ表示手段であって、上記評価値算出部により算出された評価値の大きさに応じて、上記タスクｖｉから出力される上記先行後続関係を表す線の表示態様を異ならせるように表示するマップ表示手段としてコンピュータを更に機能させるための請求項３に記載のコンピュータ読み取り可能なタスクグラフ解析プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はタスクグラフ解析装置およびタスクグラフ解析プログラムに関し、特に、スケジュールを構成する複数のタスクから成るタスクグラフをクリティカルパスを用いて解析する技術に関するものである。
【背景技術】
【０００２】
従来、複数のタスクから成るクリティカルパスを解析する手段として、タスクグラフ（ＰＥＲＴ図、アローダイヤグラム、クリニカルパス、ケアマップ等とも呼ばれる）が用いられている。このタスクグラフ上、時間的にまったく余裕がない最長のタスクの連なりはクリティカルパスと呼ばれ、クリティカルパス上のタスクを重点的に管理することがスケジューリングの定石とされている。クリティカルパス上の各タスクに対する評価は、各タスクの所要処理時間について行うもの（例えば、特許文献１〜４を参照）と、クリティカルパス上に出現するタスクの確率的統計計算について行うもの（例えば、非特許文献１を参照）とに大別される。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平６−１９９９８号公報
【特許文献２】特公平６−４２２５３号公報
【特許文献３】特開２００８−１７１１５３号公報
【特許文献４】特開２００８−２８７５０９号公報
【非特許文献】
【０００４】
【非特許文献１】情報処理学会研究報告「統計的静的遅延解析における偽パス除去手法について」20010111;2001(2):81-8
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、大規模タスク系では一般に、クリティカルパス上のタスクは全タスクの２０％以内であると言われている。このため、全体の２割程度の重要とされるタスクは少なくともしっかりと着目しなければならない。また、スケジュールの時間短縮を図りたい場合、クリティカルパス上のタスクに注目し、当該タスクの時間短縮を行う必要がある。
【０００６】
一方、大規模タスク系の８割を占めることになる、クリティカルパスに含まれないタスクには、並行パスが数多く存在する。また、これら並行パスの確率変動、あるいは計時経過による純増等に伴う干渉は、第２クリティカルパス、第３クリティカルパスのような準クリティカルパスを生み出す。このため、クリティカルパスに含まれないタスクの適切な取り扱いがスケジューリングにおいて重要性を増している。
【０００７】
しかしながら、上記従来の技術では、最もクリティカルなタスクに対してのみ評価が行われるため、それ以外にどの程度クリティカルなタスクがどれくらい存在するのかを即座に把握できないという問題があった。また、確率的統計によりタスクの評価値を算出する場合、タスク系全体を多数回実行する必要があり、計算に多くの時間がかかってしまうという問題もあった。
【０００８】
すなわち、クリティカルパスのみに基づいてタスクを評価する方法では、系全体に関しての情報が欠落するため、準クリティカルパスについて評価を正しく行うことができない。これを防ぐためには、タスク系全体の多数回実行を要する。このことから、例えば、大規模なプロジェクトでタスクの全数が非常に多い場合、全数調査が余力により不可能な場合、あるいは、ミッションクリティカルなシステムなどでそもそも情報を取得する回数に制限がある場合など、タスクの情報取得に関して制約が存在するような場合は、充分な評価を行うことができない。
【０００９】
本発明は、このような問題を解決するために成されたものであり、タスク系全体を多数回実行することなく、クリティカルパスのみならず準クリティカルパスについても各タスクの評価を行うことができるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
上記した課題を解決するために、本発明では、スケジュール対象とするｎ個のタスク｛ｖ１，ｖ２，・・，ｖｎ｝と、当該ｎ個のタスクの先頭および末尾に仮設定した開始タスクｖ０および終了タスクｖｎ＋１とを含むタスク系に属するタスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）からタスクｖｊ（ｊ＝０，１，・・，ｎ，ｎ＋１）までのクリティカルパスをそれぞれ算出し、タスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）のそれぞれについて、当該タスクｖｉから始まるそれぞれのクリティカルパス上に含まれるタスクの総数をタスクｖｉの評価値として算出するようにしている。
【発明の効果】
【００１１】
上記のように構成した本発明によれば、開始タスクｖ０から終了タスクｖｎ＋１までの系全体のクリティカルパスのみならず、タスクｖｉからタスクｖｊまでの部分的なクリティカルパスも算出され、タスクｖｉを始点とする全てのクリティカルパス上に含まれるタスクの数がカウントされることによってタスクｖｉの評価値が算出されることとなる。このため、系全体のクリティカルパスのみを対象としてそのパス上に含まれるタスクの評価だけを行っていた従来技術と異なり、系全体のクリティカルパス上のタスクに加え、系全体のクリティカルパス上にないタスクについても評価値を得ることが可能となる。しかも、確率的統計のような複雑な演算によるのではなく、単に上述のようなタスク数のカウント演算によって評価値が算出されるので、タスク系全体を多数回実行させることなく評価値を得ることができる。これにより、本発明によれば、タスク系全体を多数回実行することなく、クリティカルパスのみならず準クリティカルパスについても各タスクの評価を行うことができるようになる。
【図面の簡単な説明】
【００１２】
【図１】本実施形態によるタスクグラフ解析装置の機能構成例を示すブロック図である。
【図２】本実施形態によるタスク情報の一例を示す図である。
【図３】ｎ＝１の場合における各タスクの先行後続関係を示す図である。
【図４】ｎ＝１の場合に表示されるタスクグラフの例を示す図である。
【図５】ｎ＝２の場合における各タスクの先行後続関係を示す図である。
【図６】ｎ＝２の場合に表示されるタスクグラフの例を示す図である。
【図７】ｎ＝３の場合に表示されるタスクグラフの例を示す図である。
【図８】ｎ＝４の場合に表示されるタスクグラフの例を示す図である。
【図９】多数のタスクを有する系のタスクグラフの例を示す図である。
【図１０】ｎ＝２で複数のクリティカルパスが存在する場合に表示されるタスクグラフの例を示す図である。
【図１１】タスク配置に関する一例を示す図である。
【発明を実施するための形態】
【００１３】
以下、本発明の一実施形態を図面に基づいて説明する。図１は、本実施形態によるタスクグラフ解析装置の機能構成例を示すブロック図である。図１に示すように、本実施形態のタスクグラフ解析装置１０は、ｎ個（ｎは１以上の整数）のタスクから成るスケジュールを解析するものであって、その機能構成として、タスク情報入力部１、タスク仮設定部２、クリティカルパス算出部３、評価値算出部４およびマップ表示部５を備えて構成されている。なお、以下では説明の便宜上、ｎ個のタスクをｖ１，ｖ２，・・，ｖｎで表すものとする。
【００１４】
なお、タスクグラフ解析装置１０が備える各機能構成１〜５は、ハードウェア構成、ＤＳＰ、ＭＰＵ、ソフトウェアの何れによっても実現することが可能である。例えばソフトウェアによって実現する場合、本実施形態のタスクグラフ解析装置１０は、実際にはコンピュータのＣＰＵあるいはＭＰＵ、ＲＡＭ、ＲＯＭなどを備えて構成され、ＲＡＭやＲＯＭに記憶されたプログラムが動作することによって実現できる。
【００１５】
したがって、コンピュータが上記各機能を果たすように動作させるプログラムを例えばＣＤ−ＲＯＭのような記録媒体に記録し、コンピュータに読み込ませることによって実現できるものである。当該プログラムを記録する記録媒体としては、ＣＤ−ＲＯＭ以外に、フレキシブルディスク、ハードディスク、磁気テープ、光ディスク、光磁気ディスク、ＤＶＤ、不揮発性メモリカード、半導体メモリ等を用いることができる。また、当該プログラムをインターネット等のネットワークを介してコンピュータにダウンロードすることによっても実現できる。
【００１６】
タスクグラフ解析装置１０には、キーボードやマウス等から成る入力装置２０が接続されるとともに、液晶ディスプレイ等の表示装置３０が接続されている。タスクグラフ解析装置１０のタスク情報入力部１は、ｎ個のタスクに関するタスク情報を入力装置２０から入力する。ここで入力するタスク情報は、ｎ個のタスクを識別するタスク識別情報と、ｎ個のタスクのスケジュール上での処理順序を表す順序情報と、ｎ個のタスクの所要処理時間を表す時間情報（本発明の負荷情報に相当する）とを含んでいる。
【００１７】
図２は、本実施形態によるタスク情報の一例を示す図である。タスク識別情報は、タスク毎に固有のＩＤであってもよいし、タスク名であってもよい。その他、各タスクをユニークに識別できる情報であれば、これ以外の情報であってもよい。図２では、タスク名ｖ１，ｖ２，・・，ｖｎをタスク識別情報として用いる例を示している。
【００１８】
順序情報は、タスクの先行後続関係を表す情報である。例えば、個々のタスク毎に、先行して１つ前に処理されるタスクのタスク識別情報および後続して１つ後に処理されるタスクのタスク識別情報の組を順序情報とする。図２の例では、タスクｖ１に先行する１つ前の他タスクは存在せず（すなわち、タスクｖ１が最先に処理される）、後続する１つ後の他タスクがタスクｖ２であることを示している。また、タスクｖ２に先行する１つ前の他タスクがタスクｖ１で、後続する１つ後の他タスクがタスクｖ３であることを示している。
【００１９】
なお、先行して１つ前に処理されるタスクが２つ以上ある場合は、先行タスクの項目には当該２つ以上のタスクのタスク識別情報が格納される。同様に、後続して１つ後に処理されるタスクが２つ以上ある場合は、後続タスクの項目には当該２つ以上のタスクのタスク識別情報が格納される。ここでは順序情報として先行タスクおよび後続タスクの組を用いる例について説明したが、何れか一方のみとしても良い。
【００２０】
時間情報は、個々のタスクを処理するのに要する時間を表す情報である。図２の例では、タスクｖ１の所要処理時間がｔ１、タスクｖ２の所要処理時間がｔ２であることを示している。なお、ここでは時間情報をタスクの所要処理時間としているが、処理の開始時刻および終了時刻のセットを時間情報としてもよい。また、ここでは時間情報を用いているが、これに限定されない。タスクの負荷の大きさを表す情報であれば、時間以外の情報を用いることが可能である。例えば、時間以外の情報として、タスクの処理に要する費用、タスク内の情報伝達経路の物理的距離、タスクの影響を受ける周囲の影響度、タスクに関する間接的な観測値や指標値などの情報を用いてもよい。
【００２１】
より具体的には、以下に述べるような様々な分野を対象としたタスクグラフによるスケジューリングにおいて、それぞれ括弧内に示すような属性をタスクの負荷情報として用いることが可能である。プロジェクトマネージメント（時間、費用）、プロセッサ開発（時間、配線距離）、コンピュータシステム（時間、費用）、医療（時間、費用、人体への影響度、体重や投薬量などの間接的観測値）、教育（偏差値等教育効果指標）、行政（時間、費用、災害復旧優先度）、化学（時間、費用）、通信（時間、機材負荷指標）、物流（時間、費用、荷物重量）、製造（時間、費用、部品使用点数、部品在庫点数）。
【００２２】
タスク仮設定部２は、タスク情報入力部１によりタスク情報が入力されたｎ個のタスクｖ１〜ｖｎの先頭に開始タスクｖ０として０番目のタスク情報を仮設定するとともに、ｎ個のタスクの末尾に終了タスクｖｎ＋１としてｎ＋１番目のタスク情報を仮設定する。ここで仮設定するタスク情報の中身は、タスク情報入力部１が入力する図２のようなタスク情報と同様である。なお、開始タスクｖ０および終了タスクｖｎ＋１の所要処理時間ｔ０，ｔｎ＋１はそれぞれ所定の値とする。
【００２３】
クリティカルパス算出部３は、タスク情報入力部１により入力されたｎ個のタスクｖ１〜ｖｎのタスク情報と、タスク仮設定部２により仮設定された開始タスクｖ０および終了タスクｖｎ＋１のタスク情報とに基づいて、タスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）からタスクｖｊ（ｊ＝０，１，・・，ｎ，ｎ＋１）までのクリティカルパスをそれぞれ算出し、それぞれのクリティカルパス毎にパス上に含まれるタスクの集合を求める。
【００２４】
クリティカルパスの算出方法自体は公知の技術を適用することが可能である。本実施形態では、クリティカルパス算出部３は以下のような手順によってクリティカルパスを算出するものとする。まず、タスク情報に含まれる時間情報に基づいて、開始タスクｖ０の最早開始時刻と最早終了時刻を計算する。次に、順序情報により示されるタスクとタスクとの先行後続関係に従い、開始タスクｖ０に続く後続タスクの最早開始時刻と最早終了時刻を順番に計算していく。そして、終了タスクｖｎ＋１まで到達したら、その終了タスクｖｎ＋１から先行タスクに向かって逆順に最遅終了時刻と最遅開始時刻を計算していく。ここで、最早開始時刻と最遅開始時刻との差をスラックと定義し、タスクｖｉまたはタスクｖｊから遡ってスラックがない経路、すなわち余裕時間のない経路を都度辿ることでクリティカルパスを求める。
【００２５】
ここで、クリティカルパスを求めるクリティカルパス算出部３の演算内容について詳しく説明する。まず、タスク情報入力部１が入力したタスクとタスク仮設定部２が仮設定した開始タスクｖ０および終了タスクｖｎ＋１を含む系全体をＬall＝｛ｖ０，ｖ１，ｖ２，・・，ｖｎ，ｖｎ＋１｝とする。Ｌallは系全体のタスクを表す集合、ｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）は個々のタスク、ｎは総タスク数である。このとき、開始タスクｖ０から終了タスクｖｎ＋１までの系全体のクリティカルパスがただ１つ存在する。これとは別に、任意のｉを選択してタスクｖｉを終了タスクと仮定すると、開始タスクｖ０から任意タスクｖｉまでのクリティカルパスがただ１つ存在する。以下では、開始タスクｖ０から任意タスクｖｉまでの系全体のクリティカルパスを「全体クリティカルパス」と呼び、それ以外の部分的なクリティカルパスを「部分クリティカルパス」と呼ぶ。また、単に「クリティカルパス」というときは、全体クリティカルパスおよび部分クリティカルパスの両方を含むものとする。
【００２６】
ここでは、開始タスクｖ０から任意タスクｖｉまでの部分クリティカルパス上に含まれる各タスクの集合として、Ｌcpi＝｛ｖ０，・・，ｖｉ｝⊂Ｌallをとることができる。集合Ｌcpiはｉ＝０やｉ＝ｎ＋１のときに関しても拡張でき、それぞれ、Ｌcp0＝｛ｖ０｝⊂Ｌall、Ｌcpn+1＝｛ｖ０，・・，ｖｉ，・・，ｖｎ＋１｝⊂Ｌallとなる。
【００２７】
さらに、任意のｊ（ｊ＝０，１，・・，ｎ，ｎ＋１）を選択してタスクｖｊを終了タスクと仮定した部分クリティカルパス上にタスクｖｉが含まれるような集合Ｌcpjをとったとき、当該部分クリティカルパス上に含まれるタスクの集合Ｌpi,jを次のように定義する。
Ｌcpi⊆Ｌcpj  ⇒  Ｌpi,j＝（ＬcpiｘｏｒＬcpj）∪｛ｖｉ｝
Ｌcpi¬⊆Ｌcpj  ⇒  Ｌpi,j＝φ（空集合）
なお、ここでは集合を表す記号「⊆」に対して“否定”の意味を表す論理演算子「¬」を組みとして用いているが、本明細書では便宜上、「¬」を論理演算子としてではなく、集合記号の意味を否定する記号として用いるものとする。例えば「Ｌcpi¬⊆Ｌcpj」の場合は、「Ｌcpjの部分集合がＬcpiとならない」ことを意味するものとする。
【００２８】
すなわち、集合Ｌpi,jは、開始タスクｖ０から任意タスクｖｊまでの部分クリティカルパス上に含まれる各タスクのうち、開始タスクｖ０から任意タスクｖｉの１つ前の先行関係にあるタスクまでの部分クリティカルパス上に含まれる各タスクを取り去ったタスクの集合である。言い換えれば、集合Ｌpi,jは、任意タスクｖｉから任意タスクｖｊまでの部分クリティカルパス上に含まれる各タスクの集合を表している。
【００２９】
例えば、ｎ＝１の場合、系全体のタスクの集合はＬall＝｛ｖ０，ｖ１，ｖ２｝、開始タスクはｖ０、終了タスクはｖ２である。このとき、これら３つのタスクの先行後続関係は、図３のようにｖ０→ｖ１→ｖ２となる（ｎ＝１の場合、これ以外の接続関係はあり得ない）。クリティカルパス算出部３は、開始タスクｖ０から終了タスクｖ２までの全体クリティカルパス上に含まれる各タスクの集合Ｌp0,2に加え、任意タスクｖｉから任意タスクｖｊまでの部分クリティカルパス上に含まれる各タスクの集合Ｌp0,0，Ｌp0,1，Ｌp1,0，Ｌp1,1，Ｌp1,2，Ｌp2,0，Ｌp2,1，Ｌp2,2を求める。
【００３０】
ここで、クリティカルパス算出部３により求められるそれぞれの集合Ｌpi,j（ｉ＝０，１，２、ｊ＝０，１，２）は以下の通りである。
Ｌp0,0＝（Ｌcp0ｘｏｒＬcp0）∪｛ｖ０｝＝｛ｖ０｝
Ｌp0,1＝（Ｌcp0ｘｏｒＬcp1）∪｛ｖ０｝＝｛ｖ０，ｖ１｝
Ｌp0,2＝（Ｌcp0ｘｏｒＬcp2）∪｛ｖ０｝＝｛ｖ０，ｖ１，ｖ２｝
Ｌp1,0＝φ
Ｌp1,1＝（Ｌcp1ｘｏｒＬcp1）∪｛ｖ１｝＝｛ｖ１｝
Ｌp1,2＝（Ｌcp1ｘｏｒＬcp2）∪｛ｖ１｝＝｛ｖ１，ｖ２｝
Ｌp2,0＝φ
Ｌp2,1＝φ
Ｌp2,2＝（Ｌcp2ｘｏｒＬcp2）∪｛ｖ２｝＝｛ｖ２｝
【００３１】
評価値算出部４は、タスクｖｉ（ｉ＝０，１，・・，ｎ，ｎ＋１）のそれぞれについて、当該タスクｖｉから始まるそれぞれのクリティカルパス上に含まれるタスクの総数（同一のタスクは１つとカウント）をタスクｖｉの評価値として算出する。本実施形態では、系全体のタスクの集合Ｌallに対応した各タスクの評価値を重畳パススコアＳと呼び、当該重畳パススコアＳを次の（式１）のように定義する。ここで、ｓｉは任意のタスクｖｉに対する集合Ｌall内の重畳パススコアである。
【００３２】
【数１】
0005458350.tif 000002
【００３３】
例えば、ｎ＝１の場合、評価値算出部４は重畳パススコアＳ＝｛ｓ０，ｓ１，ｓ２｝を以下のように算出する。
ｓ０＝｜Ｌp0,0∪Ｌp0,1∪Ｌp0,2｜
＝｜｛ｖ０｝∪｛ｖ０，ｖ１｝∪｛ｖ０，ｖ１，ｖ２｝｜
＝｜｛ｖ０，ｖ１，ｖ２｝｜＝３
ｓ１＝｜Ｌp1,0∪Ｌp1,1∪Ｌp1,2｜
＝｜φ∪｛ｖ１｝∪｛ｖ１，ｖ２｝｜
＝｜｛ｖ１，ｖ２｝｜＝２
ｓ２＝｜Ｌp2,0∪Ｌp2,1∪Ｌp2,2｜
＝｜φ∪φ∪｛ｖ２｝｜
＝｜｛ｖ２｝｜＝１
【００３４】
ここで、タスクｖｉに対する重畳パススコアｓｉは、当該タスクｖｉに対して処理時間の短縮や延長など何か変更があった場合に、対応する重畳パススコアｓｉの数に相当するタスクが影響を受けることを意味している。このため、本実施形態の評価値算出部４が算出する重畳パススコアｓｉは、各クリティカルパスにおけるタスクｖｉの重要性を表す指標として位置付けることができる。
【００３５】
マップ表示部５は、タスク情報入力部１により入力されたｎ個のタスクｖ１〜ｖｎのタスク情報と、タスク仮設定部２により仮設定された開始タスクｖ０および終了タスクｖｎ＋１のタスク情報とに含まれるタスク識別情報および順序情報に基づいて、各タスクｖ０〜ｖｎ＋１の先行後続関係をタスクグラフ（本実施形態ではこれを「重畳パススコアマップ」という）として表示装置３０に表示する。このときマップ表示部５は、評価値算出部４により算出された重畳パススコアＳ（各タスクｖｉの重畳パススコアｓｉ）の大きさに応じて、タスクｖｉから出力される先行後続関係を表す線の表示態様（例えば、太さや色相、濃度）を異ならせるようにする。
【００３６】
図４は、ｎ＝１の場合にマップ表示部５により表示される重畳パススコアマップの例を示す図である。ｎ＝１の場合、３つのタスクｖ０，ｖ１，ｖ２の先行後続関係は、図４のようにｖ０→ｖ１→ｖ２となる。マップ表示部５は、各タスクｖ０，ｖ１，ｖ２を円で描画し、それぞれの円内にタスク名ｖ０，ｖ１，ｖ２を表示するとともに、重畳パススコアｓ０，ｓ１，ｓ２を数字で表示している。また、マップ表示部５は、タスクとタスクとを接続している先行後続関係の線の太さを、後続関係にあるタスクの重畳パススコアｓ１，ｓ２に依存して変えて表示している。具体的には、重畳パススコアｓ１，ｓ２が大きいほど線を太く表示するようにしている。
【００３７】
次に、ｎ＝２の場合について説明する。ｎ＝２のときは、図５のようにタスクの先行後続関係として２通りの配置方法が考えられる。図５（ａ）に示すパターン１では、ｎ＝１の場合と同様に各タスクｖ０，ｖ１，ｖ２，ｖ３を直線的に接続している。一方、図５（ｂ）に示すパターン２では、開始タスクｖ０から分岐した２つの経路をとり、それぞれタスクｖ１とタスクｖ２に接続している。なお、図５において、枠に囲まれたタスクは全体クリティカルパスを構成するタスクを示す。また、破線の矢印は、破線で繋がったタスク間に先行後続関係があるものの、スラックがあり、後続タスクから部分クリティカルパスを探索した場合に経路に含まれない状態を示している。
【００３８】
ｎ＝２のパターン１の場合は、ｎ＝１の場合と全く同様に重畳パススコアＳ＝｛ｓ０，ｓ１，ｓ２，ｓ３｝を算出することができる。一方、ｎ＝２のパターン２の場合は、開始タスクｖ０から分岐したタスクｖ１，ｖ２に対応する重畳パススコアｓ１，ｓ２、またこれらに関係する開始タスクｖ０の重畳パススコアｓ０に特徴的な様相が現れる。以下に、パターン２におけるタスクｖ０，ｖ１，ｖ２，ｖ３に対応する重畳パススコアｓ０，ｓ１，ｓ２，ｓ３の算出プロセスを示す。
【００３９】
ｎ＝２のパターン２の場合、クリティカルパス算出部３は、開始タスクｖ０から終了タスクｖ３までの全体クリティカルパス、および任意タスクｖｉから任意タスクｖｊ（ｉ＝０，１，２，３、ｊ＝０，１，２，３）までの部分クリティカルパス上に含まれる各タスクの集合Ｌp0,0，Ｌp0,1，Ｌp0,2，Ｌp0,3，Ｌp1,0，Ｌp1,1，Ｌp1,2，Ｌp1,3，Ｌp2,0，Ｌp2,1，Ｌp2,2，Ｌp2,3，Ｌp3,0，Ｌp3,1，Ｌp3,2，Ｌp3,3を以下のように求める。
【００４０】
Ｌp0,0＝（Ｌcp0ｘｏｒＬcp0）∪｛ｖ０｝＝｛ｖ０｝
Ｌp0,1＝（Ｌcp0ｘｏｒＬcp1）∪｛ｖ０｝＝｛ｖ０，ｖ１｝
Ｌp0,2＝（Ｌcp0ｘｏｒＬcp2）∪｛ｖ０｝＝｛ｖ０，ｖ２｝
Ｌp0,3＝（Ｌcp0ｘｏｒＬcp3）∪｛ｖ０｝＝｛ｖ０，ｖ１，ｖ３｝
Ｌp1,0＝φ
Ｌp1,1＝（Ｌcp1ｘｏｒＬcp1）∪｛ｖ１｝＝｛ｖ１｝
Ｌp1,2＝φ
Ｌp1,3＝（Ｌcp1ｘｏｒＬcp3）∪｛ｖ１｝＝｛ｖ１，ｖ３｝
Ｌp2,0＝φ
Ｌp2,1＝φ
Ｌp2,2＝（Ｌcp2ｘｏｒＬcp2）∪｛ｖ２｝＝｛ｖ２｝
Ｌp2,3＝φ
Ｌp3,0＝φ
Ｌp3,1＝φ
Ｌp3,2＝φ
Ｌp3,3＝（Ｌcp3ｘｏｒＬcp3）∪｛ｖ３｝＝｛ｖ３｝
【００４１】
また、評価値算出部４は、重畳パススコアＳ＝｛ｓ０，ｓ１，ｓ２，ｓ３｝を以下のように算出する。
ｓ０＝｜Ｌp0,0∪Ｌp0,1∪Ｌp0,2∪Ｌp0,3｜
＝｜｛ｖ０｝∪｛ｖ０，ｖ１｝∪｛ｖ０，ｖ２｝∪｛ｖ０，ｖ１，ｖ３｝｜
＝｜｛ｖ０，ｖ１，ｖ２，ｖ３｝｜＝４
ｓ１＝｜Ｌp1,0∪Ｌp1,1∪Ｌp1,2∪Ｌp1,3｜
＝｜φ∪｛ｖ１｝∪φ∪｛ｖ１，ｖ３｝｜
＝｜｛ｖ１，ｖ３｝｜＝２
ｓ２＝｜Ｌp2,0∪Ｌp2,1∪Ｌp2,2∪Ｌp2,3｜
＝｜φ∪φ∪｛ｖ２｝∪φ｜
＝｜｛ｖ２｝｜＝１
ｓ２＝｜Ｌp3,0∪Ｌp3,1∪Ｌp3,2∪Ｌp3,3｜
＝｜φ∪φ∪φ∪｛ｖ３｝｜
＝｜｛ｖ３｝｜＝１
【００４２】
マップ表示部５は、各タスクｖ０〜ｖ３の先行後続関係を重畳パススコアマップとして表示装置３０に表示する。図６は、ｎ＝２のパターン２の場合にマップ表示部５により表示される重畳パススコアマップの例を示す図である。この場合、４つのタスクｖ０，ｖ１，ｖ２，ｖ３の先行後続関係は図５（ｂ）と同様である。マップ表示部５は、各タスクｖ０，ｖ１，ｖ２，ｖ３を円で描画し、それぞれの円内にタスク名ｖ０，ｖ１，ｖ２，ｖ３を表示するとともに、重畳パススコアｓ０，ｓ１，ｓ２，ｓ３を数字で表示する。また、マップ表示部５は、タスク間の先行後続関係の線の太さを、後続関係にあるタスクの重畳パススコアｓ１，ｓ２，ｓ３に依存して変えて表示する。
【００４３】
ｎ≧３の場合についても同様にして重畳パススコアＳを算出し、重畳パススコアマップを表示することができる。図７は、ｎ＝３の場合に求められる各種パターンの重畳パススコアマップの例を示す図である。図７（ａ）に示すパターン１はｎ＝１の場合と同様であるが、図７（ｂ）〜（ｄ）に示すパターン２〜４では、分岐したタスクｖ３が全体クリティカルパス上のどのタスクに接続されるかによって周辺環境が変化し、それが重畳パススコアＳに表れていることが分かる。
【００４４】
また、図７（ｅ）に示すパターン５では、重畳パススコアＳの特徴として、開始タスクｖ０から分岐した２つのタスクｖ１，ｖ２が全体クリティカルパス上に位置するかどうかにかかわらず同じ評価値をとっている（ｓ１＝２，ｓ２＝２）。また、図７（ｆ）のパターン６では、全体クリティカルパス以外のタスクｖ２，ｖ３が同じ評価値をとっている（ｓ２＝１，ｓ３＝１）。これらのことから、あるタスクｖｉの重畳パススコアｓｉは後続の部分クリティカルパス上のタスク数に依存する重要性指標であり、全体クリティカルパスに影響を受けつつも周辺環境を表現していることが分かる。
【００４５】
図８は、ｎ＝４の場合に求められる各種パターンの重畳パススコアマップの例を示す図である。図８（ａ）のパターン１は、複数のタスクｖ３，ｖ４が入れ子状に配置された状態を示している。図８（ｂ）のパターン２は、分岐後に複数のタスクｖ３，ｖ４が直列に配置された状態を示している。また、図８（ｃ）（ｄ）のパターン３とパターン４は、タスクｖ４に対して複数のタスクｖ１，ｖ３の先行関係が存在し、部分クリティカルパスが当該先行関係にあるタスクｖ１，ｖ３のどちらに関係するかにより、タスクｖ１，ｖ３の重畳パススコアｓ１，ｓ３が変化する様子を示している。さらに、図８（ｅ）のパターン５は、タスクの配置が更に複雑となった場合の例を示している。
【００４６】
この図８からも分かるとおり、複数のタスクから成るスケジュールの系全体を表現する場合、各タスクの配置には多様性が存在する。そのため、系に含まれるタスク数が多くなればなるほど、重畳パススコアｓｉの値のみの提示では系を理解するのに混乱を生ずる可能性がある。そこで、本実施形態のようにマップ表示部５を設け、重畳パススコアｓｉの性質に従った形で視覚的に重畳パススコアマップを表示するのが好ましい。
【００４７】
一般に、１つの系に属する個々のタスクは、分岐を基準に配置されることも多い。図９は、多数のタスクを有する系の重畳パススコアマップの例を示す図である。この図９に示す系では、７つのタスクｖ０〜ｖ６が二分岐をとるような先行後続関係を有している。このようなタスク配置構成における重畳パススコアｓ０〜ｓ１５は図９ の通りであり、終了タスクｖ１５から開始タスクｖ０に向けて重畳パススコアｓｉが級数的に増加していく傾向があることが分かる。
【００４８】
そこで、全ての重畳パススコアｓｉが１以上の値であるという性質を利用し、各重畳パススコアｓｉの対数値（＝logｓｉ）をとり、さらにその対数値を系内における重畳パススコアｓｉの最大値の対数値で割ることで、終了タスクｖ１５から開始タスクｖ０に向けて値が一次直線的に増加していくような重畳パススコアｓｉ’を設定することができる。この重畳パススコアｓｉ’は、０≦ｓｉ’≦１となるような値である。これを重畳パススコアマップにおいて先行後続関係を示す線の太さや色相、濃度に反映することで、重畳パススコアｓｉ’の大きさに応じて線の太さや色相、濃度が視覚的にほぼ均一に変化するように見せることができる。
ｓｉ’＝logｓｉ／log{max(Ｓ)}
【００４９】
線の太さを例にとると、後続関係のある任意のタスクｖｉに対し、後続のタスクを例えばｖｊとする。このとき、先行後続関係を示す線の太さをｂｉ、当該線の太さｂｉを調節する段階をｋ＋１段階とすると、次の式が定義できる。
ｂｉ＝１＋ｋ・ｓｉ’
ここで、重畳パススコアＳの定義により、部分クリティカルパス上のタスクｖｉとタスクｖｊに対してはｓｉ＞ｓｊという関係が成立する。そこで、ｓｉ＞ｓｊのときは先行後続関係を示す線の太さをｂｉとする一方、ｓｉ≦ｓｊのときはクリティカルパスとして辿られないことを意味するため、１番細い太さの破線にて重畳パススコアマップに表現する。
【００５０】
この重畳パススコアマップは、系全体を表現するときだけでなく、系の一部を表現したい場合にも使用できる。系の一部を表現するときは、表示対象となるタスクに対応した重畳パススコアＳ”を以下のように算出すると便利である。
ｓｉ”＝logｓｉ／log{max(Ｓ’)}
【００５１】
なお、これまでの説明の仮定として、開始タスクｖ０から任意のタスクｖｉまでの部分クリティカルパスはただ１つのみ存在するとしていたが、同条件の部分クリティカルパスが複数存在する場合にも重畳パススコアＳを算出できることは明らかである。例として、図５（ｂ）に示したｎ＝２のパターン２における重畳パススコアｓ０，ｓ２を用いて検証してみる。
【００５２】
ｎ＝２の場合における系全体のタスクの集合Ｌallにおいて、タスクｖ３から部分クリティカルパスを辿るとき、タスクｖ１だけでなく、タスクｖ２も部分クリティカルパスとして探索されたとする。つまり、図１０に示すように、タスクｖ２とタスクｖ３との先行後続関係を示す接続線が破線ではなく、実線だった（タスクｖ２とタスクｖ３との間にスラックがなかった）とする。 
【００５３】
この場合、タスクｖ１の重畳パススコアｓ１とタスクｖ３の重畳パススコアｓ３については図５（ｂ）の場合と比べて算出環境に変更がないが、タスクｖ０の重畳パススコアｓ０とタスクｖ２の重畳パススコアｓ２については算出環境に変化が生じ、各重畳パススコアｓ０，ｓ２は以下のよう算出される。
ｓ０＝｜Ｌp0,0∪Ｌp0,1∪Ｌp0,2∪Ｌp0,3｜
＝｜｛ｖ０｝∪｛ｖ０，ｖ１｝∪｛ｖ０，ｖ２｝∪｛ｖ０，ｖ１，ｖ２，ｖ３｝｜
＝｜｛ｖ０，ｖ１，ｖ２，ｖ３｝｜＝４
ｓ２＝｜Ｌp2,0∪Ｌp2,1∪Ｌp2,2∪Ｌp2,3｜
＝｜φ∪φ∪｛ｖ２｝∪｛ｖ２，ｖ３｝｜
＝｜｛ｖ２，ｖ３｝｜＝２
【００５４】
以上のような算出の結果から分かるように、図１０のように同一のタスクから接続される複数の部分クリティカルパスが存在する場合でも、タスクｖ０については後続のタスクｖ１，ｖ２が図６の場合と変わらないため、重畳パススコアｓ０は正味の値に変化がない。一方、タスクｖ２に関しては、図６と比較して図１０の場合は後続タスクとして１つのタスクｖ３が部分クリティカルパス上に加わるため、重畳パススコアｓ２はその値が１つ増加している。このように、後続のタスクからの部分クリティカルパスが複数存在する場合でも、重畳パススコアＳを矛盾なく算出することができる。
【００５５】
以上詳しく説明したように、本実施形態のタスクグラフ解析装置１０では、ｎ個のタスクｖ１〜ｖｎと、それらの先頭および末尾に仮設定した開始タスクｖ０および終了タスクｖｎ＋１とを含むタスク系に属するタスクｖｉからタスクｖｊまでのクリティカルパスをそれぞれ算出し、タスクｖｉから始まるそれぞれのクリティカルパス上に含まれるタスクの総数をタスクｖｉの重畳パススコアＳとして算出するようにしている。
【００５６】
このように構成した本実施形態のタスクグラフ解析装置１０によれば、系全体の全体クリティカルパス上に存在するタスクに加え、当該全体クリティカルパス上にはない部分クリティカルパス上のタスクについても重畳パススコアＳを得ることが可能となる。しかも、確率的統計のような複雑な演算によるのではなく、単にタスク数のカウント演算によって重畳パススコアＳが算出されるので、タスク系全体を多数回実行することなく重畳パススコアＳを得ることができる。これにより、タスク系全体を多数回実行することなく、全体クリティカルパスのみならず準クリティカルパスについても各タスクの評価を行うことができる。
【００５７】
また、本実施形態では、算出した重畳パススコアＳを重畳パススコアマップという形に加工したタスクグラフに表わすことにより、タスクの影響の範囲や度合いを視覚的に認識しやすくすることができる。
【００５８】
なお、上記実施形態では、集合Ｌallの全体に渡って重畳パススコアＳを算出するために、集合Ｌpi,jとして採り得る全てのタスクを求める必要があり、クリティカルパス算出部３は全てのｉ（ｉ＝０，１，・・，ｎ＋１）に対応した部分クリティカルパスを解明しておかなければならない。これに対して、重畳パススコアＳの算出を以下のようにアルゴリズム化するようにしても良い。
【００５９】
まず、タスクｖ０，ｖｉ，ｖｘ，ｖｙ，ｖｚ，ｖｎ＋１を考え、これらのタスクの部分クリティカルパスには次の関係が成り立つものとする。
Ｌcpi⊂Ｌcpx  ，Ｌcpi⊂Ｌcpy
Ｌcpz¬⊂Ｌcpi，Ｌcpz¬⊂Ｌcpx，Ｌcpz¬⊂Ｌcpy
Ｌcpi¬⊂Ｌcpz，Ｌcpx¬⊂Ｌcpz，Ｌcpy¬⊂Ｌcpz
このときのタスク配置に関する一例を図１１に示す。
【００６０】
以上の関係が成り立つとき、タスクｖｉから始まる部分クリティカルパス上におけるタスクの集合Ｌpi,0，Ｌpi,i，Ｌpi,x，Ｌpi,y，Ｌpi,z，Ｌpi,n+1は、それぞれ次のように記述することができる。
Ｌpi,0＝φ
Ｌpi,i＝（ＬcpiｘｏｒＬcpi）∪｛ｖｉ｝＝｛ｖｉ｝
Ｌpi,x＝（ＬcpiｘｏｒＬcpx）∪｛ｖｉ｝＝｛ｖｉ，・・，ｖｘ｝
Ｌpi,y＝（ＬcpiｘｏｒＬcpy）∪｛ｖｉ｝＝｛ｖｉ，・・，ｖｙ｝
Ｌpi,z＝φ
Ｌpi,n+1＝（ＬcpiｘｏｒＬcpn+1）∪｛ｖｉ｝＝｛ｖｉ，・・，ｖｘ，・・，ｖｎ＋１｝
【００６１】
さらに、これら集合Ｌpi,0，Ｌpi,i，Ｌpi,x，Ｌpi,y，Ｌpi,z，Ｌpi,n+1どうしの集合和を考えると、次の計算ができる。
Ｌpi,0∪Ｌpi,i∪Ｌpi,x∪Ｌpi,y∪Ｌpi,z∪Ｌpi,n+1
＝φ∪｛ｖｉ｝∪｛ｖｉ，・・，ｖｘ｝∪｛ｖｉ，・・，ｖｙ｝∪φ∪｛ｖｉ，・・，ｖｘ，・・，ｖｎ＋１｝
＝｛ｖｉ，・・，ｖｘ，・・，ｖｙ，・・，ｖｎ＋１｝
すなわち、タスクｖｉの重畳パススコアｓｉを算出する式は、次の（式２）のように変形できる。
【００６２】
【数２】
0005458350.tif 000003
【００６３】
さらに、タスクｖｉからの部分クリティカルパスがただ１つ存在すると仮定した場合、任意の０≦ｊ≦ｎ＋１について、０≦ｘ≦ｎ＋１、０≦ｙ≦ｎ＋１、ｘ≠ｙとなる全てのｘとｙを考えたとき、｛ｖｘ｜ｖｘ∈Ｌcpx｝∩｛ｖｙ｜ｖｙ∈Ｌcpy｝＝φの条件を加味して（式２）を変形することができる。この条件は有限加法性が成り立つことを意味しているため、（式２）は次の（式３）のように変形することができる。
【００６４】
【数３】
0005458350.tif 000004
【００６５】
こうして得られた（式３）に使用される｛ｖｊ｜ｖｊ∈Ｌcpj，Ｌcpj⊃Ｌcpi｝はそもそも集合Ｌpi,jの中にタスクｖｊが存在することで得られるものである。集合Ｌpi,jの中にタスクｖｊがあるということは、集合Ｌpi,jの中にタスクｖｉもあるということであり、ｖｉ∈Ｌcpjとなることでもある。単純にタスクｖｊの０≦ｊ≦ｎ＋１での存在数の合計というのであれば、タスクｖｉの基数をカウントしても同じことになる。よって、（式３）は更に（式４）のように変形できる。ここで、特性関数χは（式５）のように定義する。
【００６６】
【数４】
0005458350.tif 000005
【００６７】
ただし、（式４）への変形は、開始タスクｖ０からタスクｖｉまでの部分クリティカルパスがただ１つ存在するという仮定のもとになされる変形である。部分クリティカルパスが複数存在する場合には（式４）への最後の変形が否定される。そのため、算出される重畳パススコアｓｉは、周辺タスクとの比較を行うための評価値としては使用できるものの、任意のタスクｖｉの重畳パススコアｓｉが後続の部分クリティカルパス上のネット数と同数であるという特徴は失われる。そこで、クリティカルパス算出部３が複数の部分クリティカルパスを検出した場合に、その旨を警告として表示装置３０に表示するようにしても良い。
【００６８】
上述した（式４）への変形をもとに、次のようなアルゴリズムにより、全体集合Ｌallに対応した重畳パススコアＳを求めることができる。
(1) まず、０≦ｉ≦ｎ＋１となる重畳パススコアＳの要素ｓｉを全て０に初期化する。また、部分クリティカルパスを保存しておく集合Ｌcpをφに初期化する。
(2) 次に、ｉ＝０とし、開始タスクｖ０に対応する重畳パススコアｓ０に１を代入する。
【００６９】
(3) ｉを１インクリメントし、タスクｖｉから遡って部分クリティカルパスを探索し、得られたパス上のタスク集合ＬcpiをＬcpに保存する。ただし、部分クリティカルパスの探索中、タスクｖｋに対応するＬcpkが集合Ｌcp中に存在した場合、それ以上探索は行わず、探索済みのタスクと共にＬcpkの要素であるタスクもＬcpiの要素として加える。
(4) 重畳パススコアＳの要素中、タスク集合Ｌcpiに対応する全ての要素ｓｉについて１インクリメントする。
(5) 上記(3)〜(4)の手順を繰り返し、ｉ＝ｎ＋１に達したところでそのときの重畳パススコアＳの値を全体集合Ｌallに対応した重畳パススコアとする。
【００７０】
このように、重畳パススコアＳの算出を重畳パススコアマップのクリティカルパス探索に適した形にアルゴリズム化することにより、重畳パススコアＳを容易に得ることができる。
【００７１】
その他、上記実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００７２】
１  タスク情報入力部
２  タスク仮設定部
３  クリティカルパス算出部
４  評価値算出部
５  マップ表示部
【図１】
0005458350.tif 000006
【図２】
0005458350.tif 000007
【図３】
0005458350.tif 000008
【図４】
0005458350.tif 000009
【図５】
0005458350.tif 000010
【図６】
0005458350.tif 000011
【図７】
0005458350.tif 000012
【図８】
0005458350.tif 000013
【図９】
0005458350.tif 000014
【図１０】
0005458350.tif 000015
【図１１】
0005458350.tif 000016