特許
J-GLOBAL ID:200903005459822949
時間制約管理方式
発明者:
,
出願人/特許権者:
代理人 (1件):
大菅 義之 (外1名)
公報種別:公開公報
出願番号(国際出願番号):特願平4-162809
公開番号(公開出願番号):特開平6-004286
出願日: 1992年06月22日
公開日(公表日): 1994年01月14日
要約:
【要約】【目的】 スケジューリングやプランニングなど、時間を扱う分野の制約処理に関し、そこで、最短経路探索アルゴリズムの計算量を改善するとともに、制約が変更された場合に、できるだけもとの計算結果を利用し、変更の影響を受けた部分のみを再計算することを目的とする。【構成】 与えられた制約がつくる無向グラフを2重連結成分に分割し、各2重連結成分、間接点の集合からなる成分について、個々にall-pairs-shortest-pahts algorithmを使うことにより計算量を減らすとともに、使用する記憶容量を小さくする。
請求項1:
外部から時間制約の集合を受け取るインタフェース部(1)と、入力された制約集合が作る無向グラフを2重連結成分に分割する制約ネットワーク分割部(2)と、分割結果を保存する制約ネットワーク管理部(3)と、各2重連結成分に属する制約からなる時間制約問題をall pairs shortest pathsalgorithm(Warshall Floyd 法) を用いて解きその結果を制約ネットワーク管理部に通知・保存する時間制約計算部(4)と、2重連結成分間の径路とその距離を求める連結状態管理部(5)と、外部から2個の時刻間の差に関する問い合わせがあった場合は、制約ネットワーク管理部に保存されている2重連結成分内における時刻の差と連結状態管理部に保存されている2重連結成分間の距離から時刻間の差を求めて出力する時間制約推論部(6)とを具備することを特徴とする時間制約管理方式。
IPC (2件):
G06F 9/44 330
, G06F 15/21
前のページに戻る