(57)【要約】【課題】同じ分析プログラムを複数の依頼者で共有して利用し、グリッド処理が完了する前であってもその時点の最適解を依頼者が取得可能とする。【解決手段】グリッドサーバシステム３は、分析クライアントシステム１からグリッド処理要求を受信すると、受付番号を割り当てるとともに、ジョブを複数生成してジョブの実行をグリッドクライアント５へ分散して指示する。グリッドクライアント５は、ジョブを実行し、前回通知した当該ジョブよりよい処理結果が得られた場合は、グリッドサーバシステム３へ通知することを所定の時間毎に繰り返す。グリッドサーバシステム３は、ジョブの処理結果を受信して、当該ジョブの生成元となったグリッド処理の受付番号に対応して処理結果記憶部に記憶されている処理結果と比較し、受信した情報で示される処理結果のほうがよりよい処理結果であれば処理結果記憶部内の現在の処理結果を、受信した処理結果により更新する。【選択図】図１
2008234293.tif 000002
【特許請求の範囲】
【請求項１】
グリッド処理依頼システムと、グリッドサーバシステムと、グリッドクライアントとからなるグリッドシステムにおいて、
前記グリッドサーバシステムは、
グリッド処理要求を一意に特定する受付番号と、当該受付番号により特定される実行中のグリッド処理の処理結果の情報とを対応付けて記憶する作業データ記憶部と、
前記グリッド処理依頼システムからグリッド処理要求を受信するインタフェース部と、
前記インタフェース部により受信したグリッド処理要求へ受付番号を割り当てるとともに、要求されたグリッド処理のジョブを複数生成して、生成した各ジョブの実行を前記グリッドクライアントへ分散して指示するジョブ起動制御部と、
前記ジョブ起動制御部によりジョブの実行を指示したグリッドクライアントから当該ジョブの処理結果の情報を受信して、当該ジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果と比較し、受信した情報で示される処理結果のほうがよりよい処理結果であれば前記作業データ記憶部内の現在の処理結果の情報を、受信した処理結果の情報により更新するグリッドアプリケーション実行部とを備え、
前記グリッドクライアントは、
前記グリッドサーバシステムからジョブの実行指示を受信し、当該ジョブを実行して処理結果を得、所定の時間毎に、前回通知を行った後に新たに得られた処理結果を通知することを繰り返す計算実行部を備える、
ことを特徴とするグリッドシステム。
【請求項２】
前記グリッドサーバシステムのグリッドアプリケーション実行部は、
前記グリッドクライアントから現在の最適な処理結果の問い合わせを受け、当該グリッドクライアントへ実行を指示したジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果の情報を返送し、
前記グリッドクライアントの計算実行部は、
前記ジョブを実行する１サイクルの時間である最適化探索サイクル、前記最適化探索サイクルの途中においてジョブを継続するか否かを判断するチェックポイント時間、ジョブのサイクルを繰り返し行う上限の時間である総計算時間の情報の入力を受け、
前記グリッドサーバシステムからジョブの実行指示を受信して最適化探索サイクルを開始し、入力値の初期値を発生させ、当該入力値を変化させながらチェックポイント時間に達するまで前記ジョブを実行し、チェックポイント時間内でジョブを実行して得た処理結果と、前記グリッドサーバシステムへ問い合わせを送信して得た現在の最適な処理結果とを比較し、チェックポイント時間内でジョブを実行して得た処理結果のほうがよければ最適化探索サイクルの終了まで前記入力値を変化させながらのジョブの実行を継続し、前記グリッドサーバシステムから受信した処理結果のほうがよければ、再び最適化サイクルを開始し、
最適化探索サイクルが終了したときに、当該最適化探索サイクル内でジョブを実行して得た処理結果の情報をグリッドサーバシステムへ通知し、再び最適化探索サイクル開始することを、前記総計算時間に達するか、ジョブの停止指示が入力されるまで繰り返す、
ことを特徴とする請求項１に記載のグリッドシステム。
【請求項３】
前記処理結果は、解とその評価値との情報を含み、
前記グリッド処理依頼システムは、
グリッド処理要求と、解の評価値の算出に用いる入力データとを前記グリッドサーバシステムへ通知し、
前記グリッドサーバシステムのジョブ起動制御部は、
前記分析クライアントから受信した入力データを、当該グリッド処理依頼システムから要求されたグリッド処理のジョブを実行する前記グリッドクライアントへ通知し、
前記グリッドクライアントの計算実行部は、
ジョブを実行して解を得ると、前記グリッドサーバシステムから受信した入力データを用いて当該解の評価値を算出し、
前記グリッドアプリケーション実行部及び前記グリッドクライアントの計算実行部は、
２つの処理結果の比較を、当該処理結果で示される評価値同士の大小によって行い、どちらの処理結果がよりよいかを判断する、
ことを特徴とする請求項１または請求項２に記載のグリッドシステム。
【請求項４】
グリッド処理依頼システムと、グリッドサーバシステムと、グリッドクライアントとからなるグリッドシステムにおけるグリッド処理方法であって、
前記グリッドサーバシステムは、
グリッド処理要求を一意に特定する受付番号と、当該受付番号により特定される実行中のグリッド処理の処理結果の情報とを対応付けて記憶する作業データ記憶部とを備えており、
前記グリッドサーバシステムにおいて、
インタフェース部が、前記グリッド処理依頼システムからグリッド処理要求を受信し、
ジョブ起動制御部が、前記インタフェース部により受信したグリッド処理要求へ受付番号を割り当てるとともに、要求されたグリッド処理のジョブを複数生成して、生成した各ジョブの実行を前記グリッドクライアントへ分散して指示し、
前記グリッドクライアントにおいて、
計算実行部が、前記グリッドサーバシステムからジョブの実行指示を受信し、当該ジョブを実行して処理結果を得、所定の時間毎に、前回通知を行った後に新たに得られた処理結果を通知することを繰り返し、
前記グリッドサーバシステムにおいて、
グリッドアプリケーション実行部が、前記ジョブ起動制御部によりジョブの実行を指示したグリッドクライアントから当該ジョブの処理結果の情報を受信して、当該ジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果と比較し、受信した情報で示される処理結果のほうがよりよい処理結果であれば前記作業データ記憶部内の現在の処理結果の情報を、受信した処理結果の情報により更新する、
ことを特徴とするグリッド処理方法。
【請求項５】
グリッド処理依頼システムと、グリッドサーバシステムと、グリッドクライアントとからなるグリッドシステムの前記グリッドサーバシステムとして用いられるコンピュータを、
グリッド処理要求を一意に特定する受付番号と、当該受付番号により特定される実行中のグリッド処理の処理結果の情報とを対応付けて記憶する作業データ記憶部、
前記グリッド処理依頼システムからグリッド処理要求を受信するインタフェース部、
前記インタフェース部により受信したグリッド処理要求へ受付番号を割り当てるとともに、要求されたグリッド処理のジョブを複数生成して、生成した各ジョブの実行を前記グリッドクライアントへ分散して指示するジョブ起動制御部、
前記ジョブ起動制御部によりジョブの実行を指示したグリッドクライアントから当該ジョブの処理結果の情報を受信して、当該ジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果と比較し、受信した情報で示される処理結果のほうがよりよい処理結果であれば前記作業データ記憶部内の現在の処理結果の情報を、受信した処理結果の情報により更新するグリッドアプリケーション実行部、
として機能させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グリッドシステム、グリッド処理方法、及び、コンピュータプログラムに関する。
【背景技術】
【０００２】
従来、グリッドシステムは、単一のユーザによる処理の依頼を、システム内のグリッドクライアント、すなわち、ネットワークを介して接続されるコンピュータに分割し、それぞれのグリッドクライアントにおいて処理を実行させることによって処理の高速化を狙うものが一般的である（例えば、非特許文献１参照）。また、サービス提供サーバが、ユーザコンピュータから要求されたサービスを実行するための複数の処理ブロックそれぞれをユーザコンピュータに実行させ、サービスを要求した資源使用者に、使用した資源に応じて課金を行い、ユーザコンピュータ資源を提供した資源提供者への支払い金額を算出するグリッドシステムがある（例えば、特許文献１参照）。
【特許文献１】特開２００４−３２６４５２号公報
【非特許文献１】”ネットワークコンピューティングのためのバークレー・オープン・インフラストラクチャ”，[online]，２００７年，[平成１９年３月１日検索]、インターネット<http://boinc.oocp.org/indexj.php>
【発明の開示】
【発明が解決しようとする課題】
【０００３】
組み合わせ最適化問題を解く探索的なアルゴリズムは、多くの初期値を発生させて長い時間をかけて実行することにより、よい解が得られることが期待される。そこで、グリッドシステムを利用して、複数のパーソナルコンピュータ（ＰＣ）に処理を分散し、多くの初期値を用いて計算を実行することで、探索の効率化を図ることが実行されてきた。
【０００４】
一方で、このような組み合わせ最適化問題を実際に解く際に、何かしらの分析を実施したのち、その分析結果を入力として探索アルゴリズムを実行させる場合がある。そこで、このような場合に、分析アルゴリズムごとにプログラムが用意され、かつ、ユーザは用意されたプログラムを自在に組み合わせて利用したり、複数のユーザの同時利用が可能であったりするような分析システムが存在すれば、ユーザの利便性は向上する。しかし、このシステムに、グリッドの仕組みを取り入れたプログラムを統合することを考えた際には以下のような問題があった。
【０００５】
ひとつは、BOINCなどのグリッドプログラムのプラットフォームでは、同じ分析プログラムを複数人で共有して利用することは想定していないという問題である。そのため、複数人で利用する分析システムの場合に、グリッドで処理している分析プログラムが、どのユーザのどのデータの処理であるかを区分けできる仕組みを追加する必要がある。
もうひとつは、通常組み合わせ最適化問題を解く探索的なアルゴリズムを利用する場合、処理時間がかかり、なおかつどの程度処理時間をかければ十分な結果が得られるかが事前にはわからないという問題である。つまり、依頼元はグリッドサーバの実行状況を常に監視していなければならず、ひとつのグリッド処理が完了するまでは他の処理を行うことができなかった。
【０００６】
本発明は、このような事情に鑑みてなされたものであり、同じ分析プログラムを複数の依頼者で共有して利用することができ、かつ、グリッド処理が完了する前であってもその時点の最適解を依頼者が取得することができるグリッドシステム、グリッド処理方法、及び、コンピュータプログラムを提供することをその目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明は、グリッド処理依頼システムと、グリッドサーバシステムと、グリッドクライアントとからなるグリッドシステムにおいて、前記グリッドサーバシステムは、グリッド処理要求を一意に特定する受付番号と、当該受付番号により特定される実行中のグリッド処理の処理結果の情報とを対応付けて記憶する作業データ記憶部と、前記グリッド処理依頼システムからグリッド処理要求を受信するインタフェース部と、前記インタフェース部により受信したグリッド処理要求へ受付番号を割り当てるとともに、要求されたグリッド処理のジョブを複数生成して、生成した各ジョブの実行を前記グリッドクライアントへ分散して指示するジョブ起動制御部と、前記ジョブ起動制御部によりジョブの実行を指示したグリッドクライアントから当該ジョブの処理結果の情報を受信して、当該ジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果と比較し、受信した情報で示される処理結果のほうがよりよい処理結果であれば前記作業データ記憶部内の現在の処理結果の情報を、受信した処理結果の情報により更新するグリッドアプリケーション実行部とを備え、前記グリッドクライアントは、前記グリッドサーバシステムからジョブの実行指示を受信し、当該ジョブを実行して処理結果を得、所定の時間毎に、前回通知を行った後に新たに得られた処理結果を通知することを繰り返す計算実行部を備える、ことを特徴とするグリッドシステムである。
【０００８】
また、本発明は、上述するグリッドシステムであって、前記グリッドサーバシステムのグリッドアプリケーション実行部は、前記グリッドクライアントから現在の最適な処理結果の問い合わせを受け、当該グリッドクライアントへ実行を指示したジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果の情報を返送し、前記グリッドクライアントの計算実行部は、前記ジョブを実行する１サイクルの時間である最適化探索サイクル、前記最適化探索サイクルの途中においてジョブを継続するか否かを判断するチェックポイント時間、ジョブのサイクルを繰り返し行う上限の時間である総計算時間の情報の入力を受け、前記グリッドサーバシステムからジョブの実行指示を受信して最適化探索サイクルを開始し、入力値の初期値を発生させ、当該入力値を変化させながらチェックポイント時間に達するまで前記ジョブを実行し、チェックポイント時間内でジョブを実行して得た処理結果と、前記グリッドサーバシステムへ問い合わせを送信して得た現在の最適な処理結果とを比較し、チェックポイント時間内でジョブを実行して得た処理結果のほうがよければ最適化探索サイクルの終了まで前記入力値を変化させながらのジョブの実行を継続し、前記グリッドサーバシステムから受信した処理結果のほうがよければ、再び最適化サイクルを開始し、最適化探索サイクルが終了したときに、当該最適化探索サイクル内でジョブを実行して得た処理結果の情報をグリッドサーバシステムへ通知し、再び最適化探索サイクル開始することを、前記総計算時間に達するか、ジョブの停止指示が入力されるまで繰り返す、ことを特徴とする。
【０００９】
また、本発明は、上述するグリッドシステムであって、前記処理結果は、解とその評価値との情報を含み、前記グリッド処理依頼システムは、グリッド処理要求と、解の評価値の算出に用いる入力データとを前記グリッドサーバシステムへ通知し、前記グリッドサーバシステムのジョブ起動制御部は、前記分析クライアントから受信した入力データを、当該グリッド処理依頼システムから要求されたグリッド処理のジョブを実行する前記グリッドクライアントへ通知し、前記グリッドクライアントの計算実行部は、ジョブを実行して解を得ると、前記グリッドサーバシステムから受信した入力データを用いて当該解の評価値を算出し、前記グリッドアプリケーション実行部及び前記グリッドクライアントの計算実行部は、２つの処理結果の比較を、当該処理結果で示される評価値同士の大小によって行い、どちらの処理結果がよりよいかを判断する、ことを特徴とする。
【００１０】
また、本発明は、グリッド処理依頼システムと、グリッドサーバシステムと、グリッドクライアントとからなるグリッドシステムにおけるグリッド処理方法であって、前記グリッドサーバシステムは、グリッド処理要求を一意に特定する受付番号と、当該受付番号により特定される実行中のグリッド処理の処理結果の情報とを対応付けて記憶する作業データ記憶部とを備えており、前記グリッドサーバシステムにおいて、インタフェース部が、前記グリッド処理依頼システムからグリッド処理要求を受信し、ジョブ起動制御部が、前記インタフェース部により受信したグリッド処理要求へ受付番号を割り当てるとともに、要求されたグリッド処理のジョブを複数生成して、生成した各ジョブの実行を前記グリッドクライアントへ分散して指示し、前記グリッドクライアントにおいて、計算実行部が、前記グリッドサーバシステムからジョブの実行指示を受信し、当該ジョブを実行して処理結果を得、所定の時間毎に、前回通知を行った後に新たに得られた処理結果を通知することを繰り返し、前記グリッドサーバシステムにおいて、グリッドアプリケーション実行部が、前記ジョブ起動制御部によりジョブの実行を指示したグリッドクライアントから当該ジョブの処理結果の情報を受信して、当該ジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果と比較し、受信した情報で示される処理結果のほうがよりよい処理結果であれば前記作業データ記憶部内の現在の処理結果の情報を、受信した処理結果の情報により更新する、ことを特徴とするグリッド処理方法である。
【００１１】
また、本発明は、グリッド処理依頼システムと、グリッドサーバシステムと、グリッドクライアントとからなるグリッドシステムの前記グリッドサーバシステムとして用いられるコンピュータを、グリッド処理要求を一意に特定する受付番号と、当該受付番号により特定される実行中のグリッド処理の処理結果の情報とを対応付けて記憶する作業データ記憶部、前記グリッド処理依頼システムからグリッド処理要求を受信するインタフェース部、前記インタフェース部により受信したグリッド処理要求へ受付番号を割り当てるとともに、要求されたグリッド処理のジョブを複数生成して、生成した各ジョブの実行を前記グリッドクライアントへ分散して指示するジョブ起動制御部、前記ジョブ起動制御部によりジョブの実行を指示したグリッドクライアントから当該ジョブの処理結果の情報を受信して、当該ジョブの生成元となったグリッド処理の受付番号に対応して前記作業データ記憶部に記憶されている処理結果と比較し、受信した情報で示される処理結果のほうがよりよい処理結果であれば前記作業データ記憶部内の現在の処理結果の情報を、受信した処理結果の情報により更新するグリッドアプリケーション実行部、として機能させることを特徴とするコンピュータプログラムである。
【発明の効果】
【００１２】
本発明によれば、グリッドサーバシステムは、依頼元からのグリッド処理の要求に対して受付番号を割り当て、この受付番号ごとに、当該グリッド処理のジョブを実行しているグリッドクライアントから所定の時間毎に通知される実行結果の中から最適解を選択して保持する。従って、同じ分析プログラムを複数の依頼者で共有して利用することができ、かつ、グリッド処理が完了する前であってもその時点の最適解を依頼者が取得することができる。また、依頼者は常にグリッド処理の実行状況を監視する必要がない。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態を図面を参照して詳細に説明する。
図１は、本実施の形態によるグリッドシステムの機能ブロック図である。
同図において、グリッドシステムは、グリッドサーバシステム３と、分析クライアントシステム１、１、…と、グリッドクライアント５、５、…とを、ＩＰ（Internet Protocol）などを用いたネットワークを介して接続してなる。
【００１４】
グリッド処理依頼システムとしての分析クライアントシステム１は、１または複数のサーバ、コンピュータ端末などで実現することができ、制御部１１、通信部１２、記憶部１３、分析処理部１４を備える。制御部１１は、各部の制御や、データの一時的な格納や、データの転送等を行う。通信部１２は、ネットワークを介したデータの送受信を行う。記憶部１３は、各種データを記憶する。分析処理部１４は、処理受付部１５と分析プログラム実行部１６を備える。処理受付部１５は、分析処理の実行、分析処理実行中に起動されたグリッド処理の処理結果やステータスの表示、グリッド処理の停止等の指示の入力を受け付け、分析プログラム実行部１６のプログラムを起動する。分析プログラム実行部１６は、処理受付部１５から起動された分析プログラムや、グリッド処理の処理結果取得、テータス表示、グリッド処理の停止などのプログラムなどを実行し、グリッドサーバシステム３へ各種コマンドを発行する。
【００１５】
グリッドサーバシステム３は、１または複数のサーバで実現することができ、制御部３１、通信部３２、ジョブ作成部３３、ジョブ記憶部３７、処理結果記憶部３８、作業データ記憶部３９を備える。制御部３１は、各部の制御や、データの一時的な格納や、データの転送等を行う。通信部３２は、ネットワークを介したデータの送受信を行う。ジョブ作成部３３は、インタフェース部３４、グリッドアプリケーション実行部３５、ジョブ起動制御部３６を備える。インタフェース部３４は、分析クライアントシステム１から発行された各種コマンドに応じて、各部への指示を発行したり、分析クライアントシステム１へ各種コマンドの実行結果、例えば、グリッド処理の処理結果やステータスを通知したりする。グリッドアプリケーション実行部３５は、グリッド処理のジョブを作成するとともに、グリッドクライアント５から受信したジョブの処理結果に基づき処理結果記憶部３８内に保持しているグリッド処理の処理結果を更新する。ジョブ起動制御部３６は、グリッドクライアント５へのジョブの送信や、ジョブの停止指示を行うとともに、グリッドクライアント５からジョブのステータスの情報を取得する。ジョブ記憶部３７は、ジョブの管理に関する情報を記憶する。処理結果記憶部３８は、グリッド処理の処理結果を記憶する。作業データ記憶部３９は、現在実行中のグリッド処理の最適解の情報を保持する。
【００１６】
グリッドクライアント５は、コンピュータ端末であり、制御部５１、通信部５２、記憶部５３、計算実行部５４を備える。制御部５１は、各部の制御や、データの一時的な格納や、データの転送等を行う。通信部５２は、ネットワークを介したデータの送受信を行う。記憶部５３は、各種データを記憶する。計算実行部５４は、クライアントプログラム実行部５５及びジョブアプリケーション実行部５６を備える。クライアントプログラム実行部５５は、グリッドサーバシステム３からジョブの起動や停止の指示を受けるとともに、ジョブの処理結果やステータスをグリッドサーバシステム３へ通知するためのグリッド処理クライアントプログラムを実行する。ジョブアプリケーション実行部５６は、クライアントプログラム実行部５５からの指示によりジョブの実行プログラムであるジョブアプリケーションプログラムを実行する。
【００１７】
図２は、グリッドサーバシステム３のジョブ記憶部３７が記憶する受付番号管理テーブルのデータ構成を示す図である。受付番号管理テーブルは、分析クライアントシステム１から要求されたグリッド処理を特定するための受付番号、当該グリッド処理を要求した分析クライアントシステム１を特定するＩＤ（要求分析クライアントＩＤ）、当該グリッド処理要求の受付時刻、当該グリッド処理の処理結果を記憶している記憶領域のアドレスの情報を含む。分析クライアントシステム１のＩＤとしては、例えば、ＩＰアドレスを用いることができる。
【００１８】
図３は、グリッドサーバシステム３のジョブ記憶部３７が記憶するジョブ管理テーブルのデータ構成を示す図である。ジョブ管理テーブルは、ジョブを特定するジョブ番号、当該ジョブがどのグリッド処理から発生したのかを特定する受付番号、当該ジョブを割り当てたグリッドクライアント５を特定するＩＤ（実行グリッドクライアントＩＤ）、当該ジョブのステータスの情報を含む。グリッドクライアント５のＩＤとしては、例えば、ＩＰアドレスを用いることができる。
【００１９】
次に、グリッドシステムの動作を説明する。
図４は、グリッドシステムにおける概要処理のフローチャートである。
同図において、グリッドサーバシステム３は、ユーザから依頼されたグリッド処理要求を分析クライアントシステム１から受け、ユーザ毎に受付番号を発行してグリッド処理のジョブを生成し、依頼元から指定された条件等に基づいたジョブの実行条件をグリッド用計算資源であるグリッドクライアント５に通知してジョブを実行させる（ステップＳ１１）。
【００２０】
グリッドクライアント５は、ある初期値から入力値を変えながらジョブを実行して当該ジョブの処理結果を得る処理を、実行条件で示される、処理結果をチェックすべき時間（チェックポイント時間）に達するまで繰り返し実行する。グリッドクライアント５は、チェックポイント時間に達すると、そのとき得られている処理結果がこれまでよりよい処理結果であれば、実行条件で示される探索時間（最適化探索サイクル）まで探索を継続し、最適化探索サイクルが終了すると、受付番号とともにその時点で当該グリッドクライアント５が保持する最もよい処理結果をグリッドサーバシステム３へ通知する。グリッドサーバシステム３は、受付番号に対応した作業データ記憶部３９の作業領域を参照し、現在グリッドサーバシステム３が保持する最適な処理結果よりもよい処理結果を得られたと判断した場合に、現在の保持している最適な処理結果を新たに受信した当該処理結果に書き換え、グリッドクライアント５に再度ジョブを実行させる（ステップＳ１２）。
【００２１】
分析クライアントシステム１は、グリッド処理の受付番号をグリッドサーバシステム３へ通知することにより、依頼元のユーザは、全てのグリッド処理が完了していなくても、その時点での最適な処理結果を取得することができる（ステップＳ１３）。グリッドクライアント５は、実行条件で示される総計算時間に達するか、停止の指示があるまでジョブを実行する。
【００２２】
次に、グリッドシステムにおける各処理の詳細な動作について説明する。
なお、以下に示す図５〜図９のシーケンスでは、グリッドサーバシステム３のジョブ起動制御部３６及び作業データ記憶部３９の機能をグリッドサーバ４１が実現し、ジョブ記憶部３７及び処理結果記憶部３８の機能をＤＢサーバ４２が実現するものとする。
【００２３】
図５は、図４に示すジョブ作成処理（ステップＳ１１）におけるシーケンスを示す図である。
分析クライアントシステム１の処理受付部１５は、ユーザから分析プログラム実行の指示を受けると（ステップＳ１１０）、分析プログラムをコールする（ステップＳ１１５）。分析プログラム実行部１６は、コールされた分析プログラムを起動して分析処理を実行する。分析プログラム実行部１６は、実行している分析処理の中に、例えば最適化問題等の所定のグリッド処理の実行が含まれている場合、その所定のグリッド処理を実行するためのグリッド処理プログラムをコールする。これにより、分析プログラム実行部１６は、グリッドサーバシステム３のＩＰアドレスをあて先として、通信部１２を介してグリッドサーバシステム３へ受付番号発行コマンドを送信し、受付番号の発行を依頼する（ステップＳ１２０）。
【００２４】
グリッドサーバシステム３のインタフェース部３４が、通信部３２を介して受付番号発行依頼を受信すると、ＤＢサーバ４２内のジョブ記憶部３７が保持するジョブ管理テーブルを参照し、このジョブ管理テーブル内に登録されておらず、受信した受付番号依頼を一意に識別可能な受付番号を発行する（ステップＳ１２５）。この受付番号は、例えば、連番で発行する。インタフェース部３４は、ＤＢサーバ４２内のジョブ記憶部３７の受付番号管理テーブルに、発行した受付番号、受付番号発行依頼元の分析クライアントシステム１のＩＤ（ＩＰアドレス）、受付番号発行依頼の受付時刻の情報からなるレコードを追加する（ステップＳ１３０）。インタフェース部３４は、さらに、グリッドサーバ４１の作業データ記憶部３９内に作業領域を確保すると、ステップＳ１３０においてジョブ記憶部３７内の受付番号管理テーブルへ追加したレコードに、確保した作業領域のメモリアドレスの情報を処理結果記憶アドレスとして追加する（ステップＳ１３５）。インタフェース部３４は、分析クライアントシステム１へ発行した受付番号の情報を返送する（ステップＳ１４０）。
【００２５】
分析クライアントシステム１の分析プログラム実行部１６は、グリッドサーバシステム３から受信した受付番号の情報を記憶部１３に記憶すると、グリッドサーバシステム３へ受付番号、実行を要求するグリッド処理、グリッド処理の入力データ及び設定情報を記述したジョブ作成依頼データと、ジョブ作成依頼コマンドを送信する（ステップＳ１４５）。
【００２６】
図１０に、ジョブ作成依頼データに含まれる内容を示す。ジョブ作成依頼データには、グリッドクライアント５で動作させるグリッド処理のジョブアプリケーション、設定情報ファイル、入力データ、受付番号の情報などが含まれる。ジョブアプリケーションの情報には、実行されるべき最適化プログラムの情報、つまり、最適化問題を解くためのモデル（制約式や解の評価関数式）のプログラム名が設定される。また、設定情報ファイルには、作成すべきジョブ数を示す作成クライアント数、最適化探索サイクル、総計算時間、チェックポイント時間の情報が含まれており、これらは、ステップＳ１１０にてユーザが実行を指示する前あるいは指示するときに、分析クライアントシステム１内に登録されたものである。最適化探索サイクルとは、１回の探索にかける時間、すなわち、初期値を発生してから探索をやめるまでの時間である。総計算時間とは、探索（ジョブ）のサイクルを繰り返し行う時間の上限である。また、チェックポイント時間とは、１サイクルの探索の途中で、グリッドサーバシステム３で集められた処理結果の中で最もよい値の処理結果と比較をし、探索の継続の判定処理を行う時間である。このとき、新たに得られた処理結果のほうがよく、継続と判定された場合は最適化探索まで探索を行い、そうでなければ初期値を発生して探索をやりなおす。入力データは、最適化プログラムにおける最適化処理の実行、及び、その処理結果の解の評価の算出に利用するデータを記述したファイルであり、入力データ、入力データを記述したファイルの数は最適化プログラムに依存して任意である。
【００２７】
図５において、グリッドサーバシステム３のインタフェース部３４は、分析クライアントシステム１から受付番号、実行を要求するグリッド処理、グリッド処理の入力データ及び設定情報を記述したジョブ作成依頼データを受信すると、グリッドサーバ４１へ当該ジョブ作成依頼データの書き込みを指示する。グリッドサーバ４１のジョブ起動制御部３６は、受付番号に対応した作業データ記憶部３９内の作業領域に受信したジョブ作成依頼データを書き込む（ステップＳ１５０）。
【００２８】
分析クライアントシステム１の分析プログラム実行部１６は、さらに、受付番号とジョブ登録コマンドをグリッドサーバシステム３へ送信し、ジョブ登録アプリケーションを起動する（ステップＳ１５５）。グリッドサーバシステム３のインタフェース部３４は、受付番号、ジョブ作成コマンド、受付番号に対応したジョブ作成依頼データにより示される入力ファイル名、設定情報ファイル名をグリッドアプリケーション実行部３５へ通知する（ステップＳ１６０）。ジョブ作成コマンドには、受付番号に対応したジョブ作成依頼データにより示される、起動すべきジョブアプリケーション名（最適化プログラム名）が含まれる。
【００２９】
グリッドアプリケーション実行部３５は、ジョブ起動制御部３６へ受付番号、ジョブ作成コマンドにより示されるジョブアプリケーション名、入力ファイル名、設定情報ファイル名を通知し、ジョブの作成及び登録を指示する（ステップＳ１６５）。ジョブ起動制御部３６は、受付番号及び設定情報ファイル名に対応した設定情報を作業データ記憶部３９内の作業領域から読み出し、設定情報で示される作成クライアント数により、今回作成するジョブの数を決定し、ＤＢサーバ４２内のジョブ管理テーブルを参照して、各ジョブにまだ未割り当てのジョブ番号を割り当てる（ステップＳ１７０）。なお、ジョブの数だけグリッドクライアント５へ最適化処理が配られることになる。ジョブ起動制御部３６は、生成したジョブ番号をグリッドアプリケーション実行部３５へ通知する（ステップＳ１７５）。
【００３０】
グリッドアプリケーション実行部３５は、受付番号と、当該受付番号について生成したジョブ番号とからなるレコードを、ＤＢサーバ４２内のジョブ記憶部３７が保持するジョブ管理テーブルに追加する（ステップＳ１８０）。グリッドサーバ４１のジョブ起動制御部３６は、それぞれのジョブ番号についてジョブを実行させるべきグリッドクライアント５を選択する。なお、グリッドクライアント５は、ジョブの実行が可能である場合には、その旨をグリッドサーバシステム３へ通知しているため、ジョブ起動制御部３６は、現在ジョブ記憶部３７内のジョブ管理テーブル内にジョブ実行中として登録されておらず、かつ、ジョブの実行が可能である旨を通知してきたグリッドクライアント５を、ジョブを実行させるべきグリッドクライアント５として選択する。なお、グリッドサーバシステム３は、使用可能リソース量の情報を記憶する構成を備えていてもよい。
【００３１】
ジョブ起動制御部３６は、選択したグリッドクライアント５それぞれへ、当該グリッドクライアント５へ割り当てるべきジョブのデータを送信する（ステップＳ１８５）。つまりジョブ起動制御部３６は、送信先のグリッドクライアント５に対応したジョブ番号と、実行するジョブアプリケーションプログラム（最適化プログラム）と、作業領域から読み出した入力ファイルと、設定情報ファイルを示す起動ジョブデータを通知する。このときの設定情報ファイルには、作成クライアント数の情報は含まれなくともよい。また、ジョブアプリケーションは、あらかじめグリッドサーバ４１内あるいは他の記憶装置から読み出した、設定情報ファイルに記述されるプログラム名のジョブアプリケーションプログラムである。グリッドクライアント５の計算実行部５４は、入力された情報に従ってジョブを実行する（ステップＳ１９０）。
【００３２】
なお、上記においては、分析クライアントシステム１からグリッドサーバシステム３へ送信する設定情報の中には、ジョブアプリケーション名を設定し、グリッドサーバシステム３において当該ジョブアプリケーション名のアプリケーションプログラムを取得してグリッドクライアント５へ送信しているが、分析クライアントシステム１からジョブアプリケーションプログラム自体を送信してもよい。
【００３３】
図６は、図４に示す計算実行処理（ステップＳ１２）におけるシーケンスを示す図である。
グリッドクライアント５のクライアントプログラム実行部５５は、グリッドサーバシステム３から送信されたジョブデータをジョブアプリケーション実行部５６へ通知し、ジョブの実行を指示する（ステップＳ２１０）。ジョブアプリケーション実行部５６は、以下の様に起動ジョブデータで通知されたジョブアプリケーション（最適化プログラム）を実行する（ステップＳ２１５）。なお、最適化プログラムの実行の詳細については、後述する。
【００３４】
まず、ジョブアプリケーション実行部５６は、ジョブアプリケーションの最適化処理を行うに当たり、初期値を決定する。これは、各グリッドクライアント５がランダムに発生する乱数に基づく。次に、ジョブアプリケーション実行部５６は、最適化探索サイクルで設定された時間まで最適化処理の探索アルゴリズムを繰り返す。探索アルゴリズムは、複数の変数の中から１つずつ値を変えていき、その変数を用いたときの評価値がよくなった場合はその変更された値を解として採用することにより、解の改善を図る。よって、探索アルゴリズムを実行するたびによりよい解が得られる。
【００３５】
ジョブアプリケーション実行部５６は、探索を実行する途中で、設定情報により示されるチェックポイント時間になると、ジョブ番号とともに、グリッドサーバの記憶部５３内に記憶された現在の最適解について問い合わせ依頼を送信して、現在、グリッドサーバシステム３に記憶されている最適解の評価値を取得し、チェックポイント時間までに自身の得た最適解の評価値と比較する。そして、チェックポイント時間までに自身が得た最適解の評価値より、グリッドサーバシステムから通知された最適解の評価値のほうがよいと判断された場合は、探索を中止して、新たに乱数により初期値を発生させて、探索処理をやり直す。一方、チェックポイント時間までに自身が得た最適解の評価値のほうがよいと判断された場合は、最適化探索サイクルまで探索を継続する。
【００３６】
ジョブアプリケーション実行部５６は、最適化探索サイクル内で得られた解が、グリッドサーバシステム３に記憶された最適解の値よりよりよい解であると判断した場合、得られた解及びその評価値を示す結果データと、ジョブ番号をグリッドサーバシステム３へ送信するようクライアントプログラム実行部５５へ指示する（ステップＳ２２０）。
グリッドクライアント５は、この処理を総計算時間に達するまで繰り返し実行する。
【００３７】
上記のように、入力値に対する解の評価値を算定し、処理結果がよいか否かについては、その算定した評価値を比較することによって行う。よって、値の大小のみの比較により簡易にどちらが最適解であるかを容易に判断することができる。
【００３８】
なお、グリッドサーバシステム３が、グリッドクライアント５から最適解の問い合わせを受けたときには、以下のように動作する。
グリッドサーバ４１内のジョブ起動制御部３６は、グリッドクライアント５から最適解の問い合わせと、ジョブ番号を受信すると、受信したジョブ番号をグリッドアプリケーション実行部３５へ通知する。グリッドアプリケーション実行部３５は、ＤＢサーバ４２のジョブ記憶部３７内に保持されているジョブ管理テーブルから、受信したジョブ番号に対応した受付番号を取得する。さらに、グリッドアプリケーション実行部３５は、ＤＢサーバ４２のジョブ記憶部３７内に保持されている受付番号管理テーブルから、受付番号に対応した処理結果記憶アドレスを読み出すと、グリッドサーバ４１へアクセスし、当該アドレスで示される作業データ記憶部３９内の作業領域に記憶されている、現在の最適解及びその評価値を読み出す。グリッドサーバ４１のジョブ起動制御部３６は読み出された最適解及び評価値の情報をグリッドクライアント５へ返送する。
【００３９】
グリッドクライアント５のクライアントプログラム実行部５５は、ジョブアプリケーション実行部５６からジョブ番号と、最適解及び当該最適解の評価値とを示す処理結果データを受信し、グリッドサーバシステム３へ通知する（ステップＳ２２５）。グリッドサーバ４１内のジョブ起動制御部３６は、受信したジョブ番号をグリッドアプリケーション実行部３５へ通知する（ステップＳ２３０）。グリッドアプリケーション実行部３５は、受信したジョブ番号をＤＢサーバ４２へ通知し、受付番号の取得を要求する（ステップＳ２３５）。ＤＢサーバ４２は、ジョブ記憶部３７を参照し、受信したジョブ番号に対応した受付番号をジョブ管理テーブルから読み出してグリッドアプリケーション実行部３５へ通知し、さらに、読み出した受付番号に対応した処理結果記憶アドレスを受付番号管理テーブルから読み出してグリッドアプリケーション実行部３５へ通知する（ステップＳ２４０）。グリッドアプリケーション実行部３５は、グリッドサーバ４１へアクセスし、受信した処理結果記憶アドレスで特定される作業領域から現在の最適解の評価値を読み出す。そして、作業領域から読み出した評価値とグリッドクライアント５から通知された評価値とを比較し、グリッドクライアント５から通知された処理結果データで示される評価値のほうがよければ、作業領域内の最適解及びその評価値を、グリッドクライアント５から通知された処理結果データで示される解とその評価値に更新する。
【００４０】
図７は、図４に示す処理結果取得処理（ステップＳ１３）におけるシーケンスを示す図である。
組み合わせ最適化問題など、処理時間をかけることでよりよい結果が得られる問題では、総計算時間が終了する前に途中経過を取得することが行われる。これは、分析クライアントシステム１で求めた最適化式や、初期設定条件が適切なものであるか判断するためである。
【００４１】
分析クライアントシステム１の処理受付部１５は、ユーザから結果表示の指示の入力を受けると（ステップＳ３１０）、結果取得プログラムをコールし、受付番号の情報を分析プログラム実行部１６へ通知する（ステップＳ３１５）。分析プログラム実行部１６は、コールされた結果取得プログラムを起動し、グリッドサーバシステム３へ結果要求コマンドと、受付番号の情報とを送信する（ステップＳ３２０）。
【００４２】
グリッドサーバシステム３のインタフェース部３４は、結果要求コマンドと受付番号の情報を受信すると、ＤＢサーバ４２内のジョブ記憶部３７が保持する受付番号管理テーブルから受付番号に対応した処理結果記憶アドレスを読み出す。ＤＢサーバ４２は、グリッドサーバ４１へアクセスし、読み出した処理結果記憶アドレスで特定される作業領域から、最適解を結果データとして読み出す（ステップＳ３２５）。インタフェース部３４は、受信した受付番号と、グリッドサーバ４１から読み出した結果データを分析クライアントシステム１へ返送する（ステップＳ３３０）。
【００４３】
分析クライアントシステム１の分析プログラム実行部１６は、グリッドサーバシステム３から受付番号及び結果データを受信すると、結果データを処理受付部１５へ通知する。処理受付部１５は、結果データをディスプレイに表示したり、プリンタに印刷するなどして、現在の最適解を出力する（ステップＳ３３５）。
【００４４】
図８は、ステータス管理処理のシーケンスを示す図である。
各グリッドクライアント５において、クライアントプログラム実行部５５は、定期的にジョブアプリケーション実行部５６からジョブの実行状況の情報を取得して記憶部５３に書き込んでいる。ジョブの実行状況には、実行中、計算終了、計算エラー、停止中などがあり、計算エラーの場合にはそのエラー項目の情報が含まれうる（ステップＳ４１０）。
【００４５】
一方、グリッドサーバシステム３において、グリッドサーバ４１のジョブ起動制御部３６は、ステータスを監視するために、グリッドクライアント５へジョブを実行させた後、所定の時間ごとにグリッドクライアント５に対して、ステータス取得要求と、ジョブ番号を送信する（ステップＳ４１５）。グリッドクライアント５のクライアントプログラム実行部５５は、受信したジョブ番号、当該ジョブ番号に対応して記憶部５３から読み出したジョブの実行状況の情報と、当該ジョブの実行時間の情報とをグリッドサーバシステム３へ返送する（ステップＳ４２０）。グリッドサーバ４１のジョブ起動制御部３６は、ＤＢサーバ４２へアクセスし、ジョブ記憶部３７が保持するジョブ管理テーブルにおいて、ジョブ番号と、グリッドクライアント５のＩＤとで特定されるレコードを特定し、特定されたレコードへ実行状況と実行時間の情報を書き込む（ステップＳ４２５）。
【００４６】
一方、分析クライアントシステム１の処理受付部１５は、ユーザからステータス表示の指示受けると（ステップＳ４５０）、ステータス表示プログラムをコールし、分析プログラム実行部１６へ受付番号の情報を通知する（ステップＳ４５５）。分析プログラム実行部１６は、コールされたステータス表示プログラムを起動し、グリッドサーバシステム３へステータス要求コマンドと、受付番号の情報とを送信する（ステップＳ４６０）。
【００４７】
グリッドサーバシステム３のインタフェース部３４は、ステータス要求コマンドと受付番号の情報を受信すると、ＤＢサーバ４２内のジョブ記憶部３７が保持するジョブ管理テーブルから、受付番号に対応したジョブ番号を取得し（ステップＳ４６５）、さらに、取得したジョブ番号に対応したステータス情報を、ジョブ管理テーブルから読み出す（ステップＳ４７０）。ステータス情報には、実行グリッドクライアント５の数（ジョブ数）、各ジョブの実行状況の情報などが含まれる。インタフェース部３４は、読み出したステータス情報を分析クライアントシステム１へ返送する（ステップＳ４７５）。分析クライアントシステム１の処理受付部１５は、受信したステータス情報をディスプレイに表示したり、プリンタに印刷したりする（ステップＳ４８０）。
【００４８】
図９は、ジョブ停止処理のシーケンスを示す図である。
分析クライアントシステム１の処理受付部１５は、ユーザからジョブの停止指示の入力を受けると（ステップＳ５１０）、ジョブ停止プログラムをコールし、受付番号を分析プログラム実行部１６へ通知する（ステップＳ５１５）。分析プログラム実行部１６は、コールされたジョブ停止プログラムを起動し、グリッドサーバシステム３へジョブ停止コマンドと、受付番号の情報とを送信する（ステップＳ５２０）。
【００４９】
グリッドサーバシステム３のインタフェース部３４は、ジョブ停止コマンドを受信すると（ステップＳ５２５）、ＤＢサーバ４２内のジョブ記憶部３７が保持する受付番号管理テーブルから、受付番号に対応したジョブ番号と、当該ジョブ番号のジョブを実行しているグリッドクライアント５のＩＤを読み出す（ステップＳ５３０）。グリッドサーバ４１のジョブ起動制御部３６は、読み出されたＩＤにより示されるグリッドクライアント５に、当該グリッドクライアント５に対応したジョブ番号と、停止命令とを送信する（ステップＳ５３５）。また、グリッドサーバ４１のジョブ起動制御部３６は、受付番号と、作業データ記憶部３９の作業領域内に当該受付番号に対応して保持している解とその評価値をＤＢサーバ４２の処理結果記憶部３８へ書き込む。グリッドクライアント５のクライアントプログラム実行部５５は、ジョブアプリケーション実行部５６へ、受信したジョブに対応したジョブアプリケーションの停止を指示し、ジョブアプリケーション実行部５６は指示されたジョブアプリケーションの実行を停止する（ステップＳ５４０）。
【００５０】
図１１は、グリッドクライアント５におけるジョブ実行フローを示す図である。
なお、ここでは、評価値が小さいほどよい解である場合を想定する。
まず、ジョブアプリケーション実行部５６は、現在の処理時間ｔが、設定情報ファイルに示される総計算時間timeoutを越えているか否かを判断する（ステップＳ６１０）。ジョブアプリケーション実行部５６は、現在の処理時間ｔが、総計算時間timeoutを越えていないと判断した場合（ステップＳ６１０：ＮＯ）、乱数にて変数の初期値を発生させるとともに、探索処理時間search_tを０クリアする（ステップＳ６１５）。ジョブアプリケーション実行部５６は、探索処理時間search_tが、設定情報ファイルに示される最適化探索サイクルcycleに達しているか否かを判断し（ステップＳ６２０）、達していないと判断した場合は（ステップＳ６２０：ＮＯ）、変数を初期値から１ずつ変化させながら探索処理（ジョブアプリケーション）を実行して、変数から得られる評価値evalを更新するとともに、探索処理時間search_tを更新する（ステップＳ６２５）。
【００５１】
そして、ジョブアプリケーション実行部５６は、初めて探索処理時間search_tが、チェックポイント時間checkpointを満たしたかを判断する（ステップＳ６３０）。初めて探索処理時間search_tが、チェックポイント時間checkpointを満たしたと判断した場合は（ステップＳ６３０：ＹＥＳ）、現在の評価値evalと、最適結果のチェックポイント時間での評価値opt_cとを比較する（ステップＳ６３５）。現在の評価値evalが、最適結果のチェックポイント時間での評価値opt_cよりも悪いと判断した場合（ステップＳ６３５：ＮＯ）、ジョブアプリケーションの実行を開始してからの処理時間ｔを更新してステップＳ６１０に戻り、新たな初期値を発生させて探索処理を行う。
【００５２】
一方、現在の評価値evalより、最適結果のチェックポイント時間での評価値opt_cがよい場合（ステップＳ６３５：ＹＥＳ）、ジョブアプリケーション実行部５６は、再びステップＳ６２５からの処理を行って初期値を１ずつ変化させながら探索処理を継続する。そして、ステップＳ６３０において、２回目以降に探索処理時間search_tが、チェックポイント時間checkpointを満たした場合（ステップＳ６３０：ＮＯ）、ステップＳ６２０に戻り、探索処理時間search_tが、設定情報ファイルに示される最適化探索サイクルcycleに達したか否かを判断する。
【００５３】
ジョブアプリケーション実行部５６は、探索処理時間search_tが、設定情報ファイルに示される最適化探索サイクルcycleに達したと判断した場合（ステップＳ６２０：ＹＥＳ）、現在の評価値evalと最適結果のチェックポイント時間での評価値opt_cとを比較し（ステップＳ６４５）、現在の評価値evalが、最適結果のチェックポイント時間での評価値opt_cよりよい場合は（ステップＳ６４５：ＮＯ）、現在の評価値evalをグリッドサーバシステム３へ送信する。これにより、グリッドサーバシステム３から、現在の最適結果optと、最適結果のチェックポイント時間での評価値opt_cが返送される（ステップＳ６５０）。そして、ジョブアプリケーション実行部５６は、処理時間tを更新し（ステップＳ６４０）、再びステップＳ６１０からの処理を実行する。
一方、現在の評価値evalが最適結果のチェックポイント時間での評価値opt_cと同じか悪い場合には（ステップＳ６４５：ＮＯ）、グリッドサーバシステム３へ処理結果の送信は行わずに、処理時間tを更新し（ステップＳ６５０）、再びステップＳ６１０からの処理を実行する。
【００５４】
上記処理を繰り返し、ステップＳ６１０において、現在の処理時間ｔが、総計算時間timeoutを越えたと判断した場合（ステップＳ６１０：ＹＥＳ）、処理を終了する。
【００５５】
続いて、具体的な最適化探索処理を例にして、評価値をどのように算出するかの例を説明する。
図１２は、最適化問題の例を示す図である。ここでは、最適化処理として、お客様の希望に沿うように座席の割り当てを行う処理を想定する。この最適化問題では、お客様を各座席に割り当てた組み合わせそれぞれについて、お客様の希望に沿わない席の割り当てが発生しているかを調べ、お客様の希望に沿わない席の割り当てが発生している場合にはペナルティ値を加算していく。そして、ペナルティ値の総和を評価値とし、なるべくペナルティが小さくなるように配置を行う。
【００５６】
図１３は設定情報ファイルの具体例を示す図である。
同図において、設定情報は、クライアント数（cilent）が１０、総計算時間（timeout）が３６００秒、最適化探索サイクル（cycle）が６０秒、チェックポイント時間（checkpoint）が１０秒であることを示すデータが設定されている。
【００５７】
図１４及び図１５は、入力データの具体例を示す図である。
図１４の入力データは、お客様の希望が満たされなかったときのペナルティ値を示す。同図において、顧客１に前方の席が割り当てられた場合のペナルティ値は１００であり、顧客２に通路側の席が割り当てられた場合のペナルティ値は８０、左列の席が割り当てられた場合のペナルティ値は１０であり、顧客３に前方の席が割り当てられた場合のペナルティ値は１０、通路側の席が割り当てられた場合のペナルティ値は４０、中央列の席が割り当てられた場合のペナルティ値は１００、…であることを示している。これは、各顧客が希望する席の情報から導かれるものである。
【００５８】
図１５の入力データは、座席の特性を示す。同図においては、座席番号に対応して「１」が設定されている特性が、その座席番号で特定される座席の有する特性を示す。つまり、座席Ａ１は、前方、左列の席、座席Ａ２は前方、通路側、左列の席、座席Ａ３は、前方、通路側、中央列の席、…であることを示している。
【００５９】
次に、分析クライアントシステム１から指定される最適化プログラムに含まれる評価値の計算式等について説明する。
同図において、変数は以下のように指定される。つまり、顧客i、座席j、座席特性pとしたとき、座席変数place(i,j)={0,1}であり、顧客iが座席jに座る場合「1」、そうでない場合「0」をとる。顧客情報customer(i,p)は、顧客iが座席特性pの席に座れない場合のペナルティ値である。また、座席情報seat(j,p)={0,1}であり、座席jが座席特性pを有する場合「1」、そうでない場合「0」をとる。
【００６０】
また、制約には以下がある。式１によれば、一席には一人しか座れないことを示し、式２によれば、一人に割り当てる席は一席以下でなければならないことを示している。
【００６１】
【数１】
2008234293.tif 000003
【００６２】
また、評価値の計算式は以下の式３のように示される。これは、ペナルティをなるべく小さくするように座席変数place(i,j)を選ぶことを示している。
【００６３】
【数２】
2008234293.tif 000004
【００６４】
上述した変数、制約式、評価値の算出式が、最適化プログラムに含まれる。
【００６５】
図１６は、グリッドクライアント５のジョブアプリケーション実行部５６が実行する最適化処理を説明する図である。同図において、行がお客様を示し、列が座席を示す。そして、お客様に対応した行において、「1」のフラグがたっている座席が、当該お客様に割り当てられた座席を示す。そして、制約条件に従い、フラグは、縦横それぞれの和が必ず１以下になるようにする。
【００６６】
上記において、ジョブアプリケーション実行部５６は、制約条件下でランダムにフラグを立てることにより、初期値を設定する。なお、ランダムにフラグを立てるため、複数のグリッドクライアント５が同じ初期値を発生させる確率は低い。ジョブアプリケーション実行部５６は、初期値について、指示されたペナルティ値の算出式と条件、つまり、最適化プログラムと入力データに基づいて、各お客様のペナルティ値を算出して合計し、評価値とする。ジョブアプリケーション実行部５６は、ペナルティ値の合計値が少なくなるように座席を交換して再び評価値を算出することを繰り返す。
上記により、評価値のみを考慮することにより、そのときの解がその時点の最適解であるか否かを簡易に判断することが可能となる。
【００６７】
なお、上記実施形態においては、グリッドサーバシステム３の受付番号管理テーブルに分析クライアントシステム１のＩＤを記憶しているが、グリッドサーバシステム３が分析クライアントシステム１から受付番号を受信したときのみジョブの処理結果やステータスを通知する場合には、ＩＤを保持しておかなくともよい。
【００６８】
なお、上述の分析クライアントシステム１、グリッドサーバシステム３、及び、グリッドクライアント５は、内部にコンピュータシステムを有している。そして、分析クライアントシステム１の制御部１１及び分析処理部１４、グリッドサーバシステム３の制御部３１及びジョブ作成部３３、グリッドクライアント５の制御部５１及び計算実行部５４の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＣＰＵ及び各種メモリやＯＳ、周辺機器等のハードウェアを含むものである。
【００６９】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【図面の簡単な説明】
【００７０】
【図１】本発明の一実施の形態によるグリッドシステムの機能ブロック図である。
【図２】同実施の形態による受付番号管理テーブルのデータ構成を示す図である。
【図３】同実施の形態によるジョブ管理テーブルのデータ構成を示す図である。
【図４】同実施の形態によるグリッドシステムにおける概要処理のフローチャートである。
【図５】同実施の形態によるグリッドシステムにおけるジョブ作成処理のシーケンスを示す図である。
【図６】同実施の形態によるグリッドシステムにおける計算実行処理のシーケンスを示す図である。
【図７】同実施の形態によるグリッドシステムにおける処理結果取得処理のシーケンスを示す図である。
【図８】同実施の形態によるグリッドシステムにおけるステータス管理処理のシーケンスを示す図である。
【図９】同実施の形態によるグリッドシステムにおけるジョブ停止処理のシーケンスを示す図である。
【図１０】同実施の形態によるジョブ作成依頼データに含まれる内容を示す。
【図１１】同実施の形態によるグリッドクライアントにおけるジョブ実行フローを示す図である。
【図１２】同実施の形態による最適化問題の例を示す図である。
【図１３】同実施の形態による最適化問題の例を示す図である。
【図１４】同実施の形態による入力データの具体例を示す図である。
【図１５】同実施の形態による入力データの具体例を示す図である。
【図１６】同実施の形態による最適化処理の例を説明する図である。
【符号の説明】
【００７１】
１…分析クライアントシステム（グリッド処理依頼システム）
３…グリッドサーバシステム
５…グリッドクライアント
１１、３１、５１…制御部
１２、３２、５２…通信部
１３、５３…記憶部
１４…分析処理部
１５…処理受付部
１６…分析プログラム実行部
３３…ジョブ作成部
３４…インタフェース部
３５…グリッドアプリケーション実行部
３６…ジョブ起動制御部
３７…ジョブ記憶部
３８…処理結果記憶部
３９…作業データ記憶部
５４…計算実行部
５５…クライアントプログラム実行部
５６…ジョブアプリケーション実行部
【図１】
2008234293.tif 000005
【図２】
2008234293.tif 000006
【図３】
2008234293.tif 000007
【図４】
2008234293.tif 000008
【図５】
2008234293.tif 000009
【図６】
2008234293.tif 000010
【図７】
2008234293.tif 000011
【図８】
2008234293.tif 000012
【図９】
2008234293.tif 000013
【図１０】
2008234293.tif 000014
【図１１】
2008234293.tif 000015
【図１２】
2008234293.tif 000016
【図１３】
2008234293.tif 000017
【図１４】
2008234293.tif 000018
【図１５】
2008234293.tif 000019
【図１６】
2008234293.tif 000020