JPH01201770A - ミッション・スケジューリング装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概要〕 本発明は、宇宙ステーションで実施されるミッションの
スケジューリング装置に関し。

発見的な手法を用いて１組合わせ的爆発を克服しつつ実
用的な時間とメモリーの範囲内で準最適なスケジュール
解を発見することを目的とし。

ミッションのスケジューリングを決定するためのミッシ
ョン・スケジューリング装置において。

ミッション間でのスケジューリング順序を決定するため
のスケジューリング順序決定手段と、スケジューリング
対象ミッションのリソース消費量とそのミッションへの
供給可能なリソース供給量とを参照比較することでスケ
ジューリング可能時間帯を算出するスケジューリング可
能時間帯算出手段と、スケジューリング可能時間帯中に
優先順序を伴ったスケジューリング時刻を設定するスケ
ジューリング時刻設定手段と、スケジューリング可能時
間帯が求まらないときにスケジューリング対象ミッショ
ンのバックトラックを行うバックトランク実行手段とス
ケジュール解の最適性の評価値を算出する評価値算出手
段とを備え、上記スケジューリング順序決定手段は集中
化スケジューリングのときにはミッションのリソース消
費量と消費時間長の大きい順に、そして分散化スケジュ
ーリングのときにはリソース消費量と消費量最大値の大
きい順に従ってスケジューリング順序を決定するととも
に、上記スケジューリング可能時間帯算出手段及びスケ
ジューリング時刻設定手段は、集中化スケジューリング
のときには離散的に定められる時刻系列の時刻順に、そ
して分散化スケジューリングのときにはそれらの時刻の
内でリソース供給残量の大きい順に従ってスケジューリ
ング時刻を決定すると共に、このスケジューリング手法
で得られたスケジュール解の最適性評価値を評価値算出
手段で算出するように構成するものである。

〔産業上の利用分野〕

本発明は、米国の宇宙ステーションに建設され、る日本
実験モジュール（以下ＪＥＭという）で実施される材料
実験、ライフサイエンス、科学観測等の種々の実験（以
下ミッションという）のスゲジューリングを行うための
ミッション・スケジューリング装置に関するものである
。

〔従来の技術〕

”　　１９９０年代半ばに、米国の宇宙ステーションに
ＪＥＭが建設され、宇宙空間の無重力、高真空、高エネ
ルギー粒子等の環境を有効に利用して９種々のミッショ
ンの実施が行われる予定である。このようなミッション
の実施のための運用計画は、５年位のタイムスパンにわ
たる国際間の調整で長期計画を作成の後３年間計画一８
半期（４５日）計画−週間計画−デイリイ計画の順に１
段階的に具体化して作成される構成がとられている。

このように構成される運用計画の内、比較的長い期間の
計画であるところの年間計画から週間計画までの計画作
成は地上運用管制が行い、デイリイ計画の７日分にあた
る週間計画（ベーススケジュール）がオンボードのＪＥ
Ｍ統合管制にアップリンクされることになる。そして、
オンボードのクルーは、アンプリンクされたこのベース
スケジュールに基づきミッションを実施するとともに。

宇宙ステーションやＪＥＭの進捗状況によりベーススケ
ジュールの見直しが生じた噛合には、自らがデイリイ計
画を作成してベーススケジュールを変更することになる
。

このように、ＪＥＭでは、オンボードのクルーに対して
、必要に応じてミッション運用のデイリイ計画を作成し
てい（という日常業務が課せられるものである。このデ
イリイ計画の作成にあたって、クルーは、ミッションの
実施のために必要となる電力消費量や流体消費量といっ
たリソース消費量が、ＪＥＭのリソース供給量の範囲内
に収まるように考慮しながら複数あるミッションの実験
開始時刻を決定していかなければならない。第１１図に
、ミッションの実施にあたっての制限条件の一例を一覧
表にして示す。この第１１図にも示すように、１つのミ
ッションの実施に加わるリソースの制限条件は相当数あ
り、しかも１日に実施が予定されているミッション数も
１０個程度とかなりな数になることから、ミッションの
実施のためのスケジューリングの作成の負荷は、たとえ
１日分であってもクルーにとって相当大きなものになる
ことが予想されている０例えば、ＦＭＰＴ（第１次材料
実験）の場合、１日分の類似の実験スケジュール作成に
１手作業で約１週間かかる。

これから、クルーとの対話によってミッションのスケジ
ューリングを自動的に作成できるようにするミッション
・スケジューリング装置の開発の要求がでてきているの
である。しかるに、ＪＥＭのような宇宙ステーションで
行われる実験への参加は我国でも今までに例がなく１本
発明のミッション・スケジューリング装置に対応する従
来技術はないというのが現状である。

これから、全く新たな観点に立って、ミッション・スケ
ジューリング装置を構成させていく必要があるのである
。

〔発明が解決しようとする問題点３ 以上に説明したように９本発明では、第１２図に示すよ
うな、地上運用管制と宇宙ステーションＪＥＭとの間で
連携して運用されることになるミッション運用のスケジ
ューリングシステム（第１２図では“ＭＩＳＥＳ”と略
しである）の提供を目的としているのである。このミッ
ション運用のスケジューリングシステムは、オンボード
のクルーのスケジューリング作業の軽減を目的として実
装されるものである。このような複数のミッションを所
定の制限条件下で組合わせていくという問題は、計算機
を使って盲目的に試行錯誤的に解いていこうとすると、
第１３図に探索木を示すように、［ミッション数の組合
わせの数１分の探索木。

及び、１つのミッションのスケジューリングに関し、［
スケジューリング可能時間帯の中の無限価の解の存在可
能性」があり、これらに関する探索木は、いわゆる「組
合わせ的場発」をもたらすことになる。このような組合
わせ的爆発が起るようなスケジューリングシステムでは
、適切なスケジューリング解が実用的な時間内において
事実上求まることがない。

これから２本発明は２発見的な手法即ち９人間の持つヒ
ユーリスティクスな知識を利用して、解として見込みが
少ない技を予め早期に切り捨てることにより９組合わせ
的爆発を克服しつつ実用的な時間とメモリーの範囲内で
準最適なミッションのスケジュール解を発見することを
目的とするものである。

〔問題点を解決するための手段〕

第１図は本発明の原理説明図である。

図中、ｌはスケジューリング順序決定手段であり、スケ
ジューリング対象となるミッション間でのスケジューリ
ング順序を決定する。この決定は。

集中化スケジューリングのときにはミッションのリソー
ス消費量と消費時間長の大きい順に、そして分散化スケ
ジューリングのときにはリソース消費量と消費量最大値
の大きい順に従ってスケジューリングの試行がなされる
よう構成される。２はスケジェーリング可能時間帯算出
手段であり、スケジューリング順序決定手段ｌによって
ミッション試行順序が定まるスケジューリング対象ミッ
ションのリソース消費量とそのミッションへの供給可能
なリソース供給量とをそれぞれの格納手段６゜７から参
照し、比較することで、スケジューリング期間における
スケジューリング可能時間帯を算出するとともに、スケ
ジューリング可能時間帯中に最適性の評価基準により定
まる探索の優先順位を伴ったスケジューリング時刻を算
出する。この探索優先順位は、解の最良さの順でもあり
、集中化スケジューリングのときには離散的に定められ
る時刻系列の時刻順に、そして分散化スケジューリング
のときにはそれらの時刻の内でリソース供給残量の大き
い順に従って探索がなされて解を発見するよう構成され
る。３は、スケジューリング時刻設定手段であり、スケ
ジューリング可能時間帯算出手段２により求まるスケジ
ューリング可能時間帯中のスケジューリング候補時刻の
複数個の要素のうち、優先順位の最も高いものを除去し
。

一方、それをスケジューリング時刻として設定する。ま
だスケジューリングがされていないミッションがあれば
、それらにつき、スケジューリング可能時間帯算出手段
２から同様の処理を繰り返す。

４はバックトラック実行手段であり、スケジューリング
可能時間帯算出手段２によりスケジューリング可能時間
帯が求まらない、即ちそのミッションのスケジューリン
グが不能になったときに、スケジューリング対象ミッシ
ョンのバックトラックを実行する。５は、評価値算出手
段であり、上記手段１から４までの手段（スケジューリ
ング手法）により得られたスケジュール解の「ミッショ
ンの集中化、又は分散化」に関する最適性の評価値を算
出する。

〔作用〕

本発明では、第１図（Ｂ）に示す如（，１つのミッショ
ンを取り出し、この取り出されたミッションに対してリ
ソース供給が可能であるところのスケジューリング可能
時間帯を算出し、このようにして算出されたスケジュー
リング可能時間帯中でスケジューリング時刻を設定して
、続いて次にスケジューリングするミッションのための
リソース供給量となるリソース残量パターンを生成して
い（ことになる。そして、リソース供給が足りなくなっ
てスケジューリングが不可能となった場合にはバックト
ラックを実行する。

この処理過程において２本発明では、スケジューリング
順序決定手段ｌがミッションのスケジューリング試行順
序を一意的に定めていくとともに。

スケジューリング時刻設定手段３がスケジューリング時
刻を離散的な値の中から優先的に定めていく。このミッ
ションの試行優先順位とスケジューリング時刻の探索優
先順位は、バッキング問題に対して人間がもつところの
ヒユーリスティクスな経験的知識に基いて定められる。

これらの知識は。

ミッション・スケジューリングにおいてスケジューリン
グが成功しやすいと判断される探索枝のみを発生し、見
込みの小さい技を切り捨てるとともに９発生した技の探
索に関しては、各ミッションのスケジューリング段階で
、集中化／分散化の意味で９局所的に最良と判断される
ものから優先的にスケジューリング試行する効果がある
。従って。

準最適なミッションのスケジューリングが計算時間とメ
モリーに関し、効率よく実現できることになる。

〔実施例〕

以下、実施例に従って本発明の詳細な説明する。

本発明を実現するためのシステム構成図を第２図に示す
０図中、２０はＥＳＨＥＬＬ、　　２４はＵＤＦ、　２
５はＵＴＩＬＩＳＰ　、　２６はＴＳＳ、２７はＦＯＲ
ＴＲＡＮ、　２８はＧＳＰ、２９はスケジュールファイ
ルである。エキスパートシステム構築ツールとしてのＥ
ＳＨＥＬＬ　２０は、　　ＵＴＩＬＩＳＰ２５の環境下
で動作して、推論エンジン２１と、知識ベースとなるフ
レームファイル２２及びＫＳファイル２３を構築する。

ｔｌＤＦ２４は、　　ＵＴＩＬＩＳＰ２５の関数が使え
るような形にするために設けられており、リソース供給
残量等の計算をする。ＦＯＲＴＲＡＮ　２７とＧＳＰ２
８はマンマシンインターフェースの向上のために設けら
れており。

スケジュールファイル２９には求められたミッション・
スケジュールが格納されることになる。

フレームファイル２２には、ＪＥＭの各リソース源のリ
ソース供給量情報を表わすところのリソースフレーム２
２ａと、ＪＥＭで実施されることになる各ミッションの
リソース消費量情報を表わすところのミッションフレー
ム２２ｂが、意味ネフトワークの一表現であるところの
フレーム構造をもって格納されることになる。第３図に
このリソースフレーム２２ａの一例を、また第４図にこ
のミッションフレーム２２ｂの一例を示す、第３図に示
すように、電力、クルーといったＪＥＭのリソース源の
リソース供給量は時間とともに変化することになるが１
本発明ではこれを階段状の関数で近似して表現し、この
ようにパターン化されたリソース供給量がリソースフレ
ーム２２ａで時刻と値のベアの組合わせで表わされるこ
とになる。

そしてこのリソースフレーム２２ａには、リソース供給
量能力を表わすところの面積が併わせで記述されるよう
構成される。同様に、第４図に示すように、ミッション
がその実施にあたって必要とするリソースの消費量もま
た時間に対しての階段状の関数で近似して表現し、この
ようにパターン化されたミッションのリソース消費量が
ミッションフレーム２２ｂで時刻と値のペアの組合わせ
で表わされることになる。そしてこのミッションフレー
ム２２ｂには、ミッションのリソース消費特性を表わす
ところの面積（全リソース消費量）。

高さ（最大リソース消費値）、長さ（消費時間）が併わ
せで記述されるよう構成される。

次に、推論エンジン２１の作業領域として使われること
になる黒板について説明する。黒板とは意味ネットワー
クの一表現であって、属性とその属性のもつ値とを対応
付けるノードを基本単位として、このノード間をリンク
をもって意味付けるものである。本発明の黒板では、第
５図に示すように、′管理”、“計画１．“リソース”
、“解”という４種類のノードが用意されることになる
。この管理ノードは、リソースの種類とスケジューリン
グ期間とミッションの種類とスケジューリング手法を管
理し、計画ノードは、ミッションのスケジューリングの
ための特性データを管理し、リソースノードはリソース
供給パターンを管理するものである。そして、計画ノー
ド間は、前計画と次計画という関係で互いにリンクされ
、計画ノードとリソースノード間は、リソースの供給消
費という関係で互いにリンクされることになる。

次に、第６図に示す知識源遷移図に従って１本発明のミ
ッション・スケジューリング装置がどのようにしてミッ
ションのスケジューリングを実現することになるのかに
ついて説明する。ここで。

第６図に示す“初期設定ＫＳ”、“可能時間帯計算ＫＳ
”、“割付時刻決定ＫＳ”、“新パターン生成ＫＳ”、
“スケジューリング成功ＫＳ”、６スケジユ一リング失
敗ＫＳ”及び“バックトランクＫＳ”という知識源は、
第２図で示したＫＳファイル２３に格納されることにな
る。これらの知識源は推論の手順を定めるもので基本的
には。

１Ｆ　　条件　ＴＨＥＮ　　結論／行為という型式のプ
ロダクションルールによって記述されるものであり、推
論エンジン２１がフレームファイル２２の格納情報を使
ってこれらの知識源に基づいて推論を実行していくこと
で、ミッションのスケジューリングが実現されることに
なる。

（イ）初期設定ＫＳ 最初に実行されることになる初期設定ＫＳは。

作業領域の確保とミッションの順序付と初期値の設定を
行うための知識源である。この初期設定ＫＳの実行にお
いては、まずミッションのスケジューリングの際の制限
条件となるリソースの種類、スケジューリング期間及び
スケジューリングミッション名及びスケジューリング手
法が黒板の管理ノードに設定されることになる。

次に、リソースフレーム２２ａとミッションフレーム２
２ｂの格納データを使い、ミッションのスケジューリン
グの順序が決定されることになる。この順序付は、下式
に従ってリソース消費率の最も大きいリソース（以下Ｄ
Ｒと略す） リソースＡｉの供給パターンの面積 が求まると、スケジューリング手法が集中化スケジュー
リング（ミッションをスケジューリング期間の前半部に
集中させるスケジューリング）のときには、各ミッショ
ン毎に下式のＳｉを算出し。

Ｓｉ＝α・ｋｉ　＋β・　１ｉ ｋｉ：ＤＲの消費面積の小さい順の通し番号ｊ！ｉ：Ｄ
Ｒの消費時間の短い順の通し番号α、β：消費面積と消
費時間の重み係数このＳｉの大きい順にスケジューリン
グの順序を定めるとともに９分散化スケジューリング（
ミッションをスケジューリング期間の全般に分散させる
スケジューリング）のときには、各ミッション毎に下式
のＳｉを算出し。

Ｓｉ＝α・ｋｉ＋ｒ−ｈｉ ｋｉ：ＤＲの消費面積の小さい順の通し番号ｈｉ：ＤＲ
の最大消費値の小さい順の通し番号 α、Ｔ：消費面積と最大消費値の重み係数このＳｔの大
きい順にスケジューリングの順序を定めることで求めら
れることになる。

このような評価式に従ってスケジューリングの順序を定
めたのは、大きいものからパフキングしていった方が解
が求まり易いという人間のもつしニーリスティクスな知
識を利用するとともに、集中化スケジューリングのとき
には、前半部のリソース残量が早く少なくなるので横長
のパターンをもつミッションが順序的に後になるとスケ
ジューリングが困難になり易いからであり１分散化スケ
ジューリングのときには、リソース残量が平均的に消費
されていくので高さの高いパターンをもつミッションが
順序的に後になるとスケジューリングが困難になり易い
からである。

このようにしてスケジューリングの順序付が定まると、
第５図にも示すように、この順序通りに黒板の管理ノー
ドの“ミッション名”を再登録（第５図の例ではＡｓ　
＝Ａ＋　−Ｂｚ　）　し直すとともに、計画ノードを生
成してこの順序通りのミッション名を登録して、対応す
るリソースノードにリンクポインタを張る処理を行う。

そして、スケジューリングの開始のために、第５図のグ
ローバル変数領域に計画１ノードに登録されている最も
スケジューリング順序の早いミッション名を登録（第５
図の例ではＡ３）するとともに、計画１ノードがリンク
するリソースノードの“新パターン゛に各々のリソース
源のリソース供給量を表すところのリソースフレーム２
２ａの供給パターンを設定することになる。

（Ｅｌ）可能時間帯計算ＫＳ 初期設定ＫＳに続いて実行されることになる可能時間帯
計算ＫＳは、先ずグローバル変数領域の指している計画
ノードのミッションに対してリソース供給可能であると
ころの時間帯を求める。可能時間帯の一例を第７図に示
す。この可能時間帯を求める方法は第８図に示すように
。

ミッションのリソース消費パターンをそのパターンに最
大的に包含される四角形（以下最大被包含四角形という
）で分解するとともに、リソースのリソース供給パター
ンも同様に最大被包含四角形で分解し、この分解により
求まるこれらの各々の四角形の大小を比較することで実
現されることになる。このような処理により、グローバ
ル変数領域の指している計画ノードがリンクしているリ
ソース毎に可能時間帯が求まるので、その共通部分をと
ることでミッションのスケジューリング可能時間、帯が
求まることになる。このようにして求められるスケジュ
ーリング可能時間帯は、計画ノードの“スケジュール可
能時間帯”にと設定される。

更にこの可能時間帯計算ＫＳでは、求められたスケジュ
ーリング可能時間帯の中からスケジューリング時刻の候
補選定を行う。このスケジューリング候補時刻の選定は
、集中化スケジューリングのときには、第９図（Ａ）に
示すように、スケジューリング可能時間帯中にある妥当
な時間幅Ｔの間隔毎に選択されるとともに９時刻列の時
刻順に従って優先度が定められる。従って第９図（Ａ）
の例でみるならば、まず時刻ｔ、にミッションをスケジ
ューリングするとともに、後述するバックトラックがあ
った場合にはｔｔ、ｔ３．・・・の順で再試行されるこ
とになる。

また分散化スケジューリングのときには、第９図（Ｂ）
に示すように、スケジューリング可能時間帯がある妥当
な時間幅Ｔより長い場合にはリソース残量パターンを検
索して最も残量値の大きい２点の時刻が、そしてスケジ
ューリング可能時間帯がＴより短い場合にはその両端の
時刻がスケジューリング時刻の候補とされ、優先度はリ
ソース残量の大きい順に定められる。従って第９図（Ｂ
）の例でみるならば、まず時刻ｔｔにミッションをスケ
ジューリングするとともに、バックトラックがあった場
合には＋ｔｊ＋ｔ４＋ｔ３の順で再試行されることにな
る。

このような選択基準に従ってスケジューリング候補時刻
を選択したのは、ある時刻でスケジューリングが失敗し
たならばその近傍もまた失敗する可能性が高いのである
程度離れた時刻で再試行すべきであるという人間のもつ
ヒエ−リスティクスな知識を利用するとともに、集中化
スケジューリングのときにはスケジューリング期間の前
半部にできるだけ多（のミッションを集中的に実施する
ことを最適化の目的としているからであり１分散化スケ
ジューリングのときには、リソース残量を平均的に消費
することをスケジューリング最適化の目的とするからで
ある。

このようにして求められたスケジューリング時刻の候補
は、優先度順に従うてソートされて計画ノードの“候補
時刻゛にと設定される。

（八）割付時刻決定ＫＳ 可能時間帯計算ＫＳに続いて実行されることになる割付
時刻決定ＫＳは、計画ノードに設定されたスケジューリ
ング時刻の候補時刻中で最も優先順序の高い時刻を計画
ノードの“割付時刻”に設定するとともに、“候補時刻
”よりその時刻を削除するための知識源である。この知
識源を実行することで試行するスケジューリング時刻が
設定されることになる。

（ニ）新パターン生成ＫＳ 新パターン生成ＫＳは、スケジューリング時刻が設定さ
れたときに、下式に従ってリソース供給残量を計算し。

リソース供給残量＝（リソース供給量）−（リソース消
費量） この計算により求まるリソース供給残量をグローバル変
数領域の指す計画ノードの次の計画ノードがリンクする
リソースノードの“新パターン”に設定する。本発明で
は、すべてのリソース源についてリソース供給量とリソ
ース消費量を共に時間に対して階段的に変化する関数の
形式で表しであるので、第９−１図に示すように。

これらの差分値として求まるリソース供給残量も同様に
時間に対して階段的に変化する関数の形式で表されるこ
とになる。そして１本新パターン生成ＫＳは、グローバ
ル変数領域が示す計画ノードを次の計画ノードに更新し
リンクさせて１次のミッションのスケジューリングを行
うために可能時間帯計算ＫＳを発行するための知識源と
なっている。従って、“新パターン゛に設定されるリソ
ース供給残量が９次のミッションへのリソース供給量と
してセントされて２次の優先順序のミッションのスケジ
ューリングの試行が実行されることになる。他方、この
知識源は、もしもすべてのミッションのスケジューリン
グが終了していれば、スケジューリング成功ＫＳを発行
する。

（ネ）バックトラックＫＳ バックトランクＫＳは、可能時間帯計算ＫＳの実行でス
ケジューリング可能時間帯が求まらないときに、グロー
バル変数領域の指す計画ノードのミッションの“候補時
刻”が存在する場合にはそのミッションのスケジュール
解の候補で、試行されていないものが残っているから。

それらを試行してみるために１割付時刻決定ＫＳを発行
する。又、“候補時刻”が存在しない場合、そのミッシ
ョンの解の候補をすべて試行しても、そのミッションの
スケジューリングができなかったことを意味し、従って
、１つ手前のミッションのスケジューリングをやり直す
（再試行）する必要があるので、グローバル変数領域を
、それが指す計画ノードの前計画リンクが指す計画ノー
ドに新たに設定し直して、再びバックトランクＫＳに入
るための知識源である、他方、この際、１つ手前のミッ
ションすら。

無（なった場合、ヒユーリスティックに発生した探索木
の技を、すべて探索し終えたことになるので、スケジュ
ーリング失敗ＫＳを発行する。

この様に、この知識源を実行することで、途中でスケジ
ューリングがうまくいかなくなったミッションのスケジ
ューリングが縦型探索の原理に基き再度試行されること
になる。

（へ）スケジューリング成功ＫＳ すべてのミッションのスケジューリングが成功裏に終了
した時、この知識源が実行され、そのスケジュール解、
即ちすべてのミッションの実験開始時刻をクルーに知ら
せるとともに、第１０図で示した評価値計算式に従って
、解の集中度合、若しくは分散度合の評価値を算出して
クルーに知らせる。更に、要求に応じて、別解の探索に
はいる場合、バックトランクＫＳを発行する。

（ト）スケジューリング失敗ＫＳ この知識源が起動されるのは、１つも解が見つからず、
スケジューリングが失敗に終わった場合か、別解をすべ
て探索し尽くして、終了する場合であり、その旨をクル
ーに知らせて終了する。

このように９本発明では、推論エンジン２１は、初期設
定ＫＳによって定められる優先順序に従ってスケジュー
リングの対象となるミッションの順序を定め、そして可
能時間帯計算ＫＳによって定められるスケジューリング
時刻順にその対象ミッションのスケジューリングを実行
していくことになる。

以上の説明において、集中化スケジューリングはスケジ
ューリング期間の前半部に集中させる例をもって示した
が、スケジューリング期間の後半部に集中させることも
可能である。このときは第９図（Ａ）で時刻の遅い方に
高い優先度を与えることになる。

また、第５図で用いた黒板は、フレーム構造で実験する
ことが可能であり、一方リソースフレームとミッション
フレームは、フレーム構造の意味ネットワークをもって
説明したが、これに限られることなく、これらはオブジ
ェクト指向型の他の意味ネットワークによって表現する
ことも可能である。　更に本発明はＪＥＭに限られるこ
となく。

リソース供給能力の限られている地上における実験設備
での実験スケジューリングに対しても同様′　な効果を
発揮することができるのである。

【発明の効果〕

以上説明したように２本発明によれば、スケジューリン
グの制約条件をリソースの供給と消費という観点に立っ
て二次元階段関数（パターン）で表現することでミッシ
ョンのスケジューリング問題を供給パターンに消費パタ
ーンをバッキングするパフキング問題として把えるとと
もに、バッキング問題に対して人間がもつところのヒユ
ーリスティクスな知識をスケジューリング方式に利用し
て探索回数を大きく減らし、準最適なスケジューリング
解を実用的な時間内に求めることができるようにしたこ
とから、ＪＥＭのオンボードのクルーの負担を大きく減
少できると予想されるのである。

【図面の簡単な説明】

第１図は本発明の原理説明図。 第２図は本発明のシステム構成図。 第３図はリソースフレームの説明図。 第４図はミツシランフレームの説明図。 第５図は本発明の黒板の構成図。 第６図は本発明の知識源遷移図。 第７図は可能時間帯計算の説明図。 第８図は最大被包含四角形への分解の説明図。 第９図はスケジューリング時刻の選択とリソース供給量
とについての説明図。 第１Ｏ図はスケジューリングの評価値の説明図。 第１１図はスケジューリングの制約条件の説明図。 第１２図はスケジューリングシステムの運用概念図。 第１３図は組合わせ的爆発の説明図である。 図中、１はスケジューリング順序決定手段、２はスケジ
ヱーリング可能時間帯算出手段、３はスケジューリング
時刻設定手段、４はバックトラック実行手段である。

Claims (1)

【特許請求の範囲】
1. リソース源からのリソース供給能力とミッションによる
   リソース消費とを含む制約条件の下でミッションのスケ
   ジューリングを決定するためのミッション・スケジュー
   リング装置において、スケジューリング対象となるミッ
   ション間でのスケジューリング順序を決定するためのス
   ケジューリング順序決定手段（１）と、このスケジュー
   リング順序決定手段（１）によって定まるスケジューリ
   ング対象ミッションのリソース消費量とそのスケジュー
   リング対象ミッションへの供給可能なリソース供給量を
   含む制約条件を比較することで、スケジューリング期間
   におけるスケジューリング可能時間帯を算出し、更にそ
   の時間帯の中から最良な解を算出するスケジューリング
   可能時間帯算出手段（２）と、このスケジューリング可
   能時間帯算出手段（２）により求まる優先順序を伴った
   複数個のスケジューリング候補時刻の中からその時点で
   優先順序の最も高い時刻を、そのミッションのスケジュ
   ール解として選択設定するスケジューリング時刻設定手
   段（３）と、上記スケジューリング可能時間帯算出手段
   （２）によりスケジューリング可能時間帯が求まらない
   ときに、前回スケジュール試行したミッションのスケジ
   ューリングについて再試するためにスケジューリング対
   象ミッションのバックトラックを行うバックトラック実
   行手段（４）とスケジューリング時刻設定手段（３）に
   よる処理をすべてのミッションに成功裏に実行した結果
   として得られるスケジュール解の最適性の評価値を算出
   する評価値算出手段（５）とを備え、上記スケジューリ
   ング順序決定手段（１）は、集中化スケジューリングの
   ときにはミッションのリソース消費量と消費時間長の大
   きい順に、そして分散化スケジューリングのときにはリ
   ソース消費量と消費量最大値の大きい順に従ってスケジ
   ューリング順序を決定するとともに、上記スケジューリ
   ング可能時間帯算出手段（２）及びスケジューリング時
   刻設定手段（３）は、集中化スケジューリングのときに
   は離散的に定められる時刻系列の時刻順に、そして分散
   化スケジューリングのときにはそれらの時刻の内でリソ
   ース供給残量の大きい順に従ってスケジューリング時刻
   を決定するとともに、すべてのミッションに対して最適
   性の評価値を評価値算出手段（５）により計算するよう
   に構成されていることを、特徴とするミッション・スケ
   ジューリング装置。