(57)【要約】【課題】短い受付時間により多くのタスクを受け入れることができるようにし、高い受け入れ率と短い受付時間との間で良いトレードオフが得られるようにする。【解決手段】期限付きタスクの受付制御・スケジューリング方法を開示する。この方法は、到着した新しいタスクを待ち行列に格納する工程と、新しいタスクおよび以前に受け付けたタスクのプレスケジューリングを行うする工程と、複数のプレスケジュールを生成する工程と、実現可能性が最も高いプレスケジュールを実行スケジュールとして用いる工程と、実行スケジュールに含まれるタスクをディスパッチする工程と、を含む。【選択図】図７
2012517041.tif 000002
【特許請求の範囲】
【請求項１】
期限付きタスクの受付制御・スケジューリング方法であって、
到着した新しいタスクを待ち行列に格納する工程と、
前記新しいタスクおよび以前に受け付けたタスクのプレスケジューリングを行う工程と、
複数のプレスケジュールを生成する工程と、
実現可能性が最も高いプレスケジュールを実行スケジュールとして用いる工程と、
前記実行スケジュールに含まれるタスクをディスパッチする工程と、を含むことを特徴とする受付制御・スケジューリング方法。
【請求項２】
前記プレスケジューリングを行う工程は、
集団のバックアップをとる工程と、
前記新しいタスクを用いて集団に含まれる染色体を伸張する工程と、
遺伝的アルゴリズムを用いて最適解を探索する工程と、
前記新しいタスクを受け付けることができる場合には、前記新しいタスクを受け付けるとともに、実現可能性の最も高いスケジュールを用いることで、前記実行スケジュールを置き換える工程と、
前記新しいタスクを受け付けることができない場合には、前記新しいタスクを拒否するとともに、バックアップした集団へと集団をロールバックする工程と、を含むことを特徴とする、請求項１に記載の受付制御・スケジューリング方法。
【請求項３】
前記染色体の伸張は新しい遺伝子を付加することであり、該新しい遺伝子はノードにランダムに割り当てられた前記新しいタスクであることを特徴とする、請求項２に記載の受付制御・スケジューリング方法。
【請求項４】
前記遺伝的アルゴリズムは、
各個体を評価し、適合度および非適合度を計算する工程と、
選択を行う工程と、
交叉を行う工程と、
スライド突然変異を行う工程と、
コーディネーションを行う工程と、
置換を行う工程と、
集団サイズを更新する工程と、
停止条件を判定する工程と、を含むことを特徴とする、請求項２または３に記載の受付制御・スケジューリング方法。
【請求項５】
前記適合度は、すべてのタスクの総時間コストであり、前記非適合度は期限に間に合わないタスクの総強制時間（ｔｏｔａｌ  ｏｂｌｉｇｅｄ  ｔｉｍｅ）であることを特徴とする、請求項４に記載の受付制御・スケジューリング方法。
【請求項６】
前記時間コストはタスクがノードを排他的に占有する時間であり、前記強制時間は期限に間に合わないタスクの期限から、受付が行われている現在時刻を差し引いた時間であることを特徴とする、請求項５に記載の受付制御・スケジューリング方法。
【請求項７】
前記選択は、集団から２つの個体をランダムに選択するとともに、より良いものを親として利用するバイナリトーナメントであることを特徴とする、請求項４ないし６のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項８】
前記選択は、他の遺伝的アルゴリズムにおいてよく用いられているいくつかの代替手段を含むことを特徴とする、請求項４ないし６のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項９】
前記交叉は、ランダムに交叉点ｐを選択した後、２つの親が前者のｐ個の遺伝子と後者の（ｎ−ｐ）個の遺伝子とを互いに交換する、１点交叉であることを特徴とする、請求項４ないし８のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項１０】
前記スライド突然変異は、強制タスクを負荷の重いノードから負荷の軽いノードへ移動することであることを特徴とする、請求項４ないし９のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項１１】
前記コーディネーションは、各ノードにおけるタスクをリードタイムの昇順にソートすることであることを特徴とする、請求項４ないし１０のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項１２】
前記リードタイムは、タスクの期限と現在時刻との差の絶対値であることを特徴とする、請求項１１に記載の受付制御・スケジューリング方法。
【請求項１３】
前記置換を行う工程は、
前記交叉後に生成された新しい個体の非適合度が古い個体の非適合度よりも小さい場合には、古い個体を新しい個体によって置き換える工程と、
古い個体のすべての非適合度がゼロである場合には、適合度が最小の古い個体を置き換える工程と、
新しい個体が集団内の古い個体のいずれかと同一の染色体構造を有する場合には、新しい個体が集団に加わることを防ぐ工程と、
置換による集団サイズの更新を引き起こす工程と、を含むことを特徴とする、請求項４ないし１２のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項１４】
前記集団サイズの更新は、集団サイズが染色体の長さの１／３よりも大きい場合には、集団が縮小し、それ以外の場合には、置換によって個体が置き換えられることがなく、新しい個体を集団に直接追加して集団が拡大するようにして、集団サイズを拡大または縮小することを特徴とする、請求項４ないし１３のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項１５】
前記停止条件は進化限界および最大時間制限の２つのパラメータを含み、ＧＡのイタレーションはこれらのパラメータの少なくともいずれかが所定の値に達した場合に停止することを特徴とする、請求項４ないし１４のいずれか１項に記載の受付制御・スケジューリング方法。
【請求項１６】
前記進化限界は新しい個体を生成しても最適解が改良されないイタレーションの最大数であり、最大時間制限はＧＡのイタレーションの最大数であることを特徴とする、請求項１５に記載の受付制御・スケジューリング方法。
【請求項１７】
到着した新しいタスクを待ち行列に格納するタスクバッファと、
前記到着した新しいタスクおよび以前に受け付けたタスクのプレスケジューリングを行い、複数のプレスケジュールを生成するとともに、実現可能性が最も高いプレスケジュールを実行スケジュールとして用いるプレスケジューリングモジュールと、
前記複数のプレスケジュールを保持する第１のストレージと、
前記実行スケジュールを保持する第２のストレージと、
前記実行スケジュールに含まれるタスクをディスパッチするタスク割当部と、を備えることを特徴とする受付制御・スケジューリングシステム。
【請求項１８】
ユーザによってサブミットされたタスクは、待ち行列で待機するとともに、ＦＣＦＳ（Ｆｉｒｓｔ  Ｃｏｍｅ  Ｆｉｒｓｔ  Ｓｅｒｖｅ）の方式でサービスの提供を受け、
前記プレスケジューリングモジュールは、待機中のタスクを１つずつスケジューリングし、
前記プレスケジューリングモジュールが新しいタスクにサービスを提供する際には、新しいタスクと以前受け付けられたタスクはまとめてスケジューリングされ、以前受け付けられたタスクは再スケジューリングされ、
前記プレスケジューリングモジュールは、プレスジュールと呼ばれる実現可能なスケジュールを複数出力し、
前記プレスケジューリングモジュールは、システム要求にしたがって、最も実現可能性の高いプレスケジュールを選択し、
選択されたプレスケジュールは新しい実行スケジュールとして使用されるとともに、実行スケジュールに含まれるタスクは、対応するノードに待機中のタスクが存在しない場合に限ってディスパッチされ、
タスクがディスパッチされると、実行スケジュールからタスクの記録が削除され、
新しいタスクが受け付けられたり、古いタスクがディスパッチされたりすると、実行スケジュールは動的に変化することを特徴とする、請求項１７に記載の受付制御・スケジューリングシステム。
【請求項１９】
前記システム要求は、負荷が最も均等になるようにすることであることを特徴とする、請求項１８に記載の受付制御・スケジューリングシステム。
【請求項２０】
期限付きタスクの受付制御・スケジューリングプログラムであって、
到着した新しいタスクを待ち行列に格納する処理と、
前記新しいタスクおよび以前に受け付けたタスクに対するプレスケジューリングを行う処理と、
複数のプレスケジュールを生成する処理と、
実現可能性が最も高いプレスケジュールを実行スケジュールとして用いる処理と、
前記実行スケジュールに含まれるタスクをディスパッチする処理と、を含むことを特徴とする受付制御・スケジューリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータシステムおよび通信システムにおけるリソース管理ソフトウェアの設計に関し、特に、与えられたリソースの集合における期限付きタスク実行のため受付・スケジューリングソフトウェアの開発に関する。
【背景技術】
【０００２】
期限付きタスクのスケジューリングは、実時間タスクスケジューリングとして広く知られている。コンピュータシステムおよび通信システムにおいてよく考察される、基礎的なマルチプロセッサスケジューリング問題には、次の２つの事例が含まれる。
第１の事例は、すべてのタスクをそれぞれの期限までに完了しなければならないような実時間環境における、シーケンシャルタスクのオンラインスケジューリングである。
第２の事例は、平均応答時間を最小化するための、シーケンシャルタスクのオンラインスケジューリングである。
【０００３】
本発明は、第１のクラスに属する。非特許文献１において、リソースの個数が２以上の場合には、ハード実時間スケジューリング問題（ｈａｒｄ−ｒｅａｌ−ｔｉｍｅ  ｓｃｈｅｄｕｌｉｎｇ  ｐｒｏｂｌｅｍ）のあらゆる可能な入力をスケジュールするための最適なアルゴリズムは存在しないことが、理論的解析によって示されている。単一プロセッサの実時間スケジューリングにおいては、ＥＤＦ（Ｅａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔ）が最適であることが、非特許文献２において証明されている。しかしながら、ＥＤＦスケジューリングは、マルチプロセッサシステムにおいて最適でなくなる（非特許文献３）。
【０００４】
受付制御は、ＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）が鍵となるような、至る所で見い出される。受付制御の基本的機能は、システムが新たなリソース要求を受け付けるのに十分なリソースを保有しているかどうかを判定し、当該要求を受け付けるか拒否するかを判定することである。ＡＴＭネットワークにおいては、受付制御は、コネクション受付制御（ｃｏｎｎｅｃｔｉｏｎ  ａｄｍｉｓｓｉｏｎ  ｃｏｎｔｒｏｌ）として知られている。無線ネットワーク、例えば、ＩＥＥＥ  ８０２．１１においては、受付制御は、呼受付制御（ｃａｌｌ  ａｄｍｉｓｓｉｏｎ  ｃｏｎｔｒｏｌ）として知られている。コンピュータシステム、例えば、クラスタや実時間マルチプロセッサにおいては、タスク受付制御やジョブ受付制御は、特にサービス指向アーキテクチャ（ＳＯＡ：Ｓｅｒｖｉｃｅ  Ｏｒｉｅｎｔｅｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）においてＱｏＳを保証するのに役立つ。関連する文献として、例えば、非特許文献４ないし６が挙げられる。
【０００５】
リソース割当において遺伝的アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）を用いることは、決定論的アルゴリズムを用いるよりも有利であることが、非特許文献７、８に示されている。しかしながら、受付制御においては、長い実行時間を要することがＧＡの欠点となる（非特許文献４、８）。したがって、非特許文献９のように、現実の問題を解くのにＧＡを用いた場合に、ＧＡの高速化が図られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】国際公開第２００８／０５８８８７号
【特許文献２】米国特許出願公開第２００６／０２５３４６４号明細書
【非特許文献】
【０００７】
【非特許文献１】Ｃｙｎｔｈｉａ  Ｐｈｉｌｌｉｐｓ，Ｃｌｉｆｆ  Ｓｔｅｉｎ，Ｅｒｉｃ  Ｔｏｒｎｇ  ａｎｄ  Ｊｏｅｌ  Ｗｅｉｎ，“Ｏｐｔｉｍａｌ  Ｔｉｍｅ−Ｃｒｉｔｉｃａｌ  Ｓｃｈｅｄｕｌｉｎｇ  Ｖｉａ  Ｒｅｓｏｕｒｃｅ  Ａｕｇｍｅｎｔａｔｉｏｎ，”ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ，１９９７．
【非特許文献２】Ｃ．Ｌ．Ｌｉｕ  ａｎｄ  Ｊａｍｅｓ  Ｗ．Ｌａｙｌａｎｄ，“Ｓｃｈｅｄｕｌｉｎｇ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｍｕｌｔｉｐｒｏｇｒａｍｍｉｎｇ  ｉｎ  ａ  Ｈａｒｄ−Ｒｅａｌ−Ｔｉｍｅ  Ｅｎｖｉｒｏｎｍｅｎｔ，”Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  ＡＣＭ，１９７３．
【非特許文献３】Ｊ．Ｗ．Ｓ．Ｌｉｕ，“Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ，”Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，２０００．
【非特許文献４】Ｍａｎｉｎａｋ  Ｃｈａｔｔｅｒｊｅｅ，Ｈａｉｔａｏ  Ｌｉｎ  ａｎｄ  Ｓａｊａｌ  Ｋ．Ｄａｓ，“Ｒａｔｅ  Ａｌｌｏｃａｔｉｏｎ  ａｎｄ  Ａｄｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  ｆｏｒ  Ｄｉｆｆｅｒｅｎｔｉａｔｅｄ  Ｓｅｒｖｉｃｅｓ  ｉｎ  ＣＤＭＡ  Ｄａｔａ  Ｎｅｔｗｏｒｋｓ，”ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｍｏｂｉｌｅ  Ｃｏｍｐｕｔｉｎｇ，２００７．
【非特許文献５】Ｄ．Ｅ．Ｉｒｗｉｎ，Ｌ．Ｅ．Ｇｒｉｔ  ａｎｄ  Ｊ．Ｓ．Ｃｈａｓｅ，“Ｂａｌａｎｃｉｎｇ  Ｒｉｓｋ  ａｎｄ  Ｒｅｗａｒｄ  ｉｎ  ａ  Ｍａｒｋｅｔ−ｂａｓｅｄ  Ｔａｓｋ  Ｓｅｒｖｉｃｅ，”１３ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ，２００４．
【非特許文献６】Ｆ．Ｉ．Ｐｏｐｏｖｉｃｉ  ａｎｄ  Ｊ．Ｗｉｌｋｅｓ，“Ｐｒｏｆｉｔａｂｌｅ  Ｓｅｒｖｉｃｅｓ  ｉｎ  ａｎ  Ｕｎｃｅｒｔａｉｎ  Ｗｏｒｌｄ，”１８ｔｈ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ，２００５．
【非特許文献７】Ａ．Ｙ．Ｚｏｍａｙａ  ａｎｄ  Ｙ．Ｈ．Ｔｅｈ，“Ｏｂｓｅｒｖａｔｉｏｎｓ  ｏｎ  Ｕｓｉｎｇ  Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｄｙｎａｍｉｃ  Ｌｏａｄ−ｂａｌａｎｃｉｎｇ，”ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，２００１．
【非特許文献８】Ｔ．Ｄ．Ｂｒａｕｎ，Ｈ．Ｊ．Ｓｉｅｇｅｌ，Ｎ．Ｂｅｃｋ，ｅｔ．ａｌ．，“Ａ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｅｌｅｖｅｎ  Ｓｔａｔｉｃ  Ｈｅｕｒｉｓｔｉｃｓ  ｆｏｒ  Ｍａｐｐｉｎｇ  ａ  Ｃｌａｓｓ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｔａｓｋｓ  ｏｎｔｏ  Ｈｅｔｅｒｏｇｅｎｅｏｕｓ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ，”Ｊｏｕｒｎａｌ  ｏｆ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｍｐｕｔｉｎｇ，２００１．
【非特許文献９】Ｓ．Ｓｏｎｇ，Ｋ．Ｈｗａｎｇ  ａｎｄ  Ｙ．Ｋ．Ｋｗｏｋ，“Ｒｉｓｋ−Ｒｅｓｉｌｉｅｎｔ  Ｈｅｕｒｉｓｔｉｃｓ  ａｎｄ  Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｓｅｃｕｒｉｔｙ−Ａｓｓｕｒｅｄ  Ｇｒｉｄ  Ｊｏｂ  Ｓｃｈｅｄｕｌｉｎｇ，”ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，２００６．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の特許文献等の各開示を、本書に引用をもって繰り込むものとする。以下の分析は、本発明者によってなされたものである。
【０００９】
はじめに、詳細なプログラミングモデルと表記法を以下のように導入する。
【００１０】
（１）複数のリソースが複数のタスクにサービスを提供する。リソースは、プロセッサ、コンピュータ、通信システムにおけるチャネル等であってもよい。本書において一貫性を保つために、リソースをノードｎｉと表記する。また、ノードの総数をＮとする。タスクはコンピュータプログラミングにおけるプロセスおよびタスクであってもよいし、通信システムおける発呼および接続要求であってもよい。様々なアプリケーションやシステムにおいて、タスクには多くの事例が含まれるため、本発明においては、タスクを、一定期間リソース（すなわち、ノード）を排他的に占有するリソース要求と定義する。
【００１１】
（２）タスクＴｉが、期限ｄｉを伴って、時刻ｔｉに到来する。一般的にすべく、あるノードにおけるタスクのサービス時間は、通常、別のノードにおけるサービス時間とは異なっているものとする。したがって、全システムにおけるタスクＴｉのサービス時間は、ベクトル｛ｓｉ，１，ｓｉ，２，…，ｓｉ，Ｎ｝となる。タスクのすべてのｓｉ，ｊが同一である場合には、プログラミングモデルは均一系を表している。一方、これらが異なっている場合には、プログラミングモデルは不均一系を表している。
【００１２】
（３）本発明における受付・スケジューリングシステム、すなわち、スケジューラは、単に、ＡＳＳと呼ぶものとする。ＡＳＳのアーキテクチャを図１に示す。
【００１３】
（４）タスクが到来すると、ＡＳＳはこの新しいタスクを受け付けるべきか拒否すべきかを決定せねばならない。これが、タスク受付である。タスクの終了時間がその期限よりも早い場合には、タスクは期限に間に合うものとされ、その反対の場合には、タスクは期限に間に合わないことになる。どのノードにタスクが割り当てられるとしても、タスクは期限に間に合う場合に限って受け付けられ、それ以外の場合には、タスクは許否される。一方、すでに受け付けられたタスクは、新しいタスクを受け付けたことで、期限に間に合わなくなるようなことはない。したがって、ＡＳＳが新しいタスクを受け付けると決定した場合には、同時に、実現可能スケジュールを同時に生成しなければならない。これが、タスクスケジューリングである。
【００１４】
（５）ｍは、以前に受け付けられたタスクと新たに到来したタスクとを含む、タスクの個数を表す。これらのタスクは、新たなタスクを受け付けるとともに、実現可能スケジュールを生成する際に、ＡＳＳによって扱われる。
【００１５】
本発明の目的の１つは、短い受付時間の間により多くのタスクを受け入れることができる受付制御・スケジューリング方法およびこれに対応するシステムを提供することにある。簡単に言えば、高い受け入れ率と短い受付時間との間で良いトレードオフを提供することが目的となる。
【課題を解決するための手段】
【００１６】
本発明の一（第１の）視点によると、
期限付きタスクの受付制御・スケジューリング方法であって、
到着した新しいタスクを待ち行列に格納する工程と、
前記新しいタスクおよび以前に受け付けたタスクのプレスケジューリングを行う工程と、
複数のプレスケジュールを生成する工程と、
実現可能性が最も高いプレスケジュールを実行スケジュールとして用いる工程と、
前記実行スケジュールに含まれるタスクをディスパッチする工程と、を含む受付制御・スケジューリング方法が提供される。
【００１７】
本発明の他の（第２の）視点によると、
到着した新しいタスクを待ち行列に格納するタスクバッファと、
前記到着した新しいタスクおよび以前に受け付けたタスクのプレスケジューリングを行い、複数のプレスケジュールを生成するとともに、実現可能性が最も高いプレスケジュールを実行スケジュールとして用いるプレスケジューリングモジュールと、
前記複数のプレスケジュールを保持する第１のストレージと、
前記実行スケジュールを保持する第２のストレージと、
前記実行スケジュールに含まれるタスクをディスパッチするタスク割当部と、を備える受付制御・スケジューリングシステムが提供される。
【００１８】
さらなる（第３の）視点によると、上記アスペクトに係る方法（ないしシステム）を実行するようにさせる受付制御・スケジューリングプログラムが提供される。
【００１９】
特に、受付制御・スケジューリングプログラムは、到着した新しいタスクを待ち行列に格納する処理と、前記新しいタスクおよび以前に受け付けたタスクに対するプレスケジューリングを行う処理と、複数のプレスケジュールを生成する処理と、実現可能性が最も高いプレスケジュールを実行スケジュールとして用いる処理と、前記実行スケジュールに含まれるタスクをディスパッチする処理と、を含む。
【発明の効果】
【００２０】
本発明によると、短い受付時間により多くのタスクを受け入れることができる。すなわち、高い受け入れ率と短い受付時間との間で良いトレードオフが得られる。
【図面の簡単な説明】
【００２１】
【図１】本発明に係る受付・スケジューリングシステム（ＡＳＳ：Ａｄｍｉｓｓｉｏｎ  ａｎｄ  Ｓｃｈｅｄｕｌｉｎｇ  Ｓｙｓｔｅｍ）のアーキテクチャを示す図である。
【図２】本発明に係る遺伝的アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍ）のフローチャートを示す図である。
【図３】本発明に係るＧＡにおける染色体を示す図である。
【図４】本発明に係るＧＡにおけるスライド変異（ｓｌｉｄｅ  ｍｕｔａｔｉｏｎ）のメカニズムを示す図である。
【図５】伸び縮みする染色体の理解を助けるための事例を示す図である。
【図６】染色体長および集団サイズが動的に変動するプロセスを示す図である。
【図７】本発明に係る受付制御・スケジューリングシステムの構成を示すブロック図である。
【発明を実施するための形態】
【００２２】
本発明の第４の視点によると、
前記プレスケジューリングを行う工程は、
集団のバックアップをとる工程と、
前記新しいタスクを用いて集団に含まれる染色体を伸張する工程と、
遺伝的アルゴリズムを用いて最適解を探索する工程と、
前記新しいタスクを受け付けることができる場合には、前記新しいタスクを受け付けるとともに、実現可能性の最も高いスケジュールを用いることで、前記実行スケジュールを置き換える工程と、
前記新しいタスクを受け付けることができない場合には、前記新しいタスクを拒否するとともに、バックアップした集団へと集団をロールバックする工程と、を含む、受付制御・スケジューリング方法が提供される。
【００２３】
本発明の第５の視点によると、前記染色体の伸張は新しい遺伝子を付加することであり、該新しい遺伝子はノードにランダムに割り当てられた前記新しいタスクである、受付制御・スケジューリング方法が提供される。
【００２４】
本発明の第６の視点によると、前記遺伝的アルゴリズムは、
各個体を評価し、適合度および非適合度を計算する工程と、
選択を行う工程と、
交叉を行う工程と、
スライド突然変異を行う工程と、
コーディネーションを行う工程と、
置換を行う工程と、
集団サイズを更新する工程と、
停止条件を判定する工程と、を含む、受付制御・スケジューリング方法が提供される。
【００２５】
本発明の第７の視点によると、前記適合度は、すべてのタスクの総時間コストであり、前記非適合度は期限に間に合わないタスクの総強制時間（Ｔｏｔａｌ  Ｏｂｌｉｇｅｄ  Ｔｉｍｅ）である、受付制御・スケジューリング方法が提供される。
【００２６】
本発明の第８の視点によると、前記時間コストはタスクがノードを排他的に占有する時間であり、前記強制時間は期限に間に合わないタスクの期限から、受付が行われている現在時刻を差し引いた時間である、受付制御・スケジューリング方法が提供される。
【００２７】
本発明の第９の視点によると、前記選択は、集団から２つの個体をランダムに選択するとともに、より良いものを親として利用するバイナリトーナメントである、受付制御・スケジューリング方法が提供される。
【００２８】
本発明の第１０の視点によると、前記選択は、他の遺伝的アルゴリズムにおいてよく用いられているいくつかの代替手段を含む、受付制御・スケジューリング方法が提供される。
【００２９】
本発明の第１１の視点によると、前記交叉は、ランダムに交叉点ｐを選択した後、２つの親が前者のｐ個の遺伝子と後者の（ｎ−ｐ）個の遺伝子とを互いに交換する、１点交叉である、受付制御・スケジューリング方法が提供される。
【００３０】
本発明の第１２の視点によると、前記スライド突然変異は、強制タスクを負荷の重いノードから負荷の軽いノードへ移動することである、受付制御・スケジューリング方法が提供される。
【００３１】
本発明の第１３の視点によると、前記コーディネーションは、各ノードにおけるタスクをリードタイムの昇順にソートすることである、受付制御・スケジューリング方法が提供される。
【００３２】
本発明の第１４の視点によると、前記リードタイムは、タスクの期限と現在時刻との差の絶対値である、受付制御・スケジューリング方法が提供される。
【００３３】
本発明の第１５の視点によると、前記置換を行う工程は、
前記交叉後に生成された新しい個体の非適合度が古い個体の非適合度よりも小さい場合には、古い個体を新しい個体によって置き換える工程と、
古い個体のすべての非適合度がゼロである場合には、適合度が最小の古い個体を置き換える工程と、
新しい個体が集団内の古い個体のいずれかと同一の染色体構造を有する場合には、新しい個体が集団に加わることを防ぐ工程と、
置換による集団サイズの更新を引き起こす工程と、を含む、受付制御・スケジューリング方法が提供される。
【００３４】
本発明の第１６の視点によると、前記集団サイズの更新は、集団サイズが染色体の長さの１／３よりも大きい場合には、集団が縮小し、それ以外の場合には、置換によって個体が置き換えられることがなく、新しい個体を集団に直接追加して集団が拡大するようにして、集団サイズを拡大または縮小する、受付制御・スケジューリング方法が提供される。
【００３５】
本発明の第１７の視点によると、前記停止条件は進化限界および最大時間制限の２つのパラメータを含み、ＧＡのイタレーションはこれらのパラメータの少なくともいずれかが所定の値に達した場合に停止する、受付制御・スケジューリング方法が提供される。
【００３６】
本発明の第１８の視点によると、前記進化限界は新しい個体を生成しても最適解が改良されないイタレーションの最大数であり、最大時間制限はＧＡのイタレーションの最大数である、受付制御・スケジューリング方法が提供される。
【００３７】
本発明の第１９の視点によると、ユーザによってサブミットされたタスクは、待ち行列で待機するとともに、ＦＣＦＳ（Ｆｉｒｓｔ  Ｃｏｍｅ  Ｆｉｒｓｔ  Ｓｅｒｖｅ）の方式でサービスの提供を受け、
前記プレスケジューリングモジュールは、待機中のタスクを１つずつスケジューリングし、
前記プレスケジューリングモジュールが新しいタスクにサービスを提供する際には、新しいタスクと以前受け付けられたタスクはまとめてスケジューリングされ、以前受け付けられたタスクは再スケジューリングされ、
前記プレスケジューリングモジュールは、プレスジュールと呼ばれる実現可能なスケジュールを複数出力し、
前記プレスケジューリングモジュールは、システム要求にしたがって、最も実現可能性の高いプレスケジュールを選択し、
選択されたプレスケジュールは新しい実行スケジュールとして使用されるとともに、実行スケジュールに含まれるタスクは、対応するノードに待機中のタスクが存在しない場合に限ってディスパッチされ、
タスクがディスパッチされると、実行スケジュールからタスクの記録が削除され、
新しいタスクが受け付けられたり、古いタスクがディスパッチされたりすると、実行スケジュールは動的に変化する、受付制御・スケジューリングシステムが提供される。
【００３８】
本発明の第２０の視点によると、前記システム要求は、負荷が最も均等になるようにすることである、受付制御・スケジューリングシステムが提供される。
【００３９】
ＡＳＳのアーキテクチャは、図１に示されている。ユーザによって処理を依頼されたすべてのタスクは待ち行列で待機し、ＦＣＦＳ（Ｆｉｒｓｔ  Ｃｏｍｅ  Ｆｉｒｓｔ  Ｓｅｒｖｅ）の方式に従ってサービスの提供を受ける。プレスケジューリングは、待機中のタスクを１つずつスケジューリングする。プレスケジューリングが新しいタスクにサービスを提供する場合には、この新しいタスクと以前受け付けられたすべてのタスクとが一緒にスケジューリングされる。すなわち、以前のタスクは再度スケジューリングされることになる。プレスケジューリングは、以前受け付けられたタスクと新しいタスクの期限を保障する複数の実現可能スケジュールを出力することがあり得る。この実現可能スケジュールを、プレスケジュールと呼ぶ。例えば、すべてのタスクを最小の時間コストで処理するといったシステム要求に従って、実現可能性が最も高いプレスケジュールを選択する。選択されたプレスケジュールは、新しい実行スケジュール（ｅｘｅｃｕｔｉｖｅ  ｓｃｈｅｄｕｌｅ）として使用される。実行スケジュールに含まれるタスクは、対応するノードに待機中のタスクが存在しない場合に限ってディスパッチされる。タスクがディスパッチされると、タスクの記録は実行スケジュールから消去される。新しいタスクが受け付けられ、古いタスクがディスパッチされると、実行スケジュールは動的に変更される。長時間に亘って新しいタスクが到来しない場合には、実行スケジュールは空になり得る。この受付・スケジューリングプロセスに要する時間は、待ち行列におけるタスクの待ち時間を削減するためには、非常に短い時間でなければならない。したがって、プレスケジューリングは、短い時間の間に、候補として多くの可能なプレスケジュールを出力する必要がある。
【００４０】
明らかに、プレスケジューリングが本発明の中核となる。高いタスク受付率も、短い受付時間も、プレスケジューリングに依存している。さらに、ＳＯＡにおいて重要な、ＡＳＳの他の利点は、ユーザがタスク実行を選択できるようにすることである。この利点もまた、プレスケジューリングに依存している。ここでは、プレスケジューリングを実現するのに、遺伝的アルゴリズムを使用する。このＧＡにおいては、集団は多くの解を含むとともに、以前生成された集団はＧＡを加速するために再利用される。
【００４１】
遺伝的アルゴリズムは、生物学にヒントを得た探査方法であり、大域的解空間（「集団（ｐｏｐｕｌａｔｉｏｎ）」という。）を部分的に探査するとともに、歴史的な情報を用いることで、以前の探査結果（「世代（ｇｅｎｅｒａｔｉｏｎ）」という。）の中から最良の解を利用し、さらに、ランダム突然変異により、解空間における新たな領域を探索する。解は、集団中の個体（ｉｎｄｉｖｉｄｕａｌ）ともいう。以下では、これらの用語（すなわち、解および個体）は、置換可能とする。ＧＡのフローチャートを図２に示す。ＧＡの詳細な設定およびメカニズムを、いかに列記する。
【００４２】
＜コード化（ｅｎｃｏｄｉｎｇ）および集団サイズ（ｐｏｐｕｌａｔｉｏｎ  ｓｉｚｅ）＞
コード化されたものは、個体の染色体を表す。染色体はプレスケジュールに変換される。染色体に含まれる数字は遺伝子に相当する。遺伝子は、その数字が示すノードに割り当てられるべきタスクを表す。染色体の一例を図３に示す。サブ遺伝子は、ノードにおけるタスクの順序である。例えば、「３（２）」は、４番目のタスクが３番目のノード上にあり、その実行順序が２番目であることを表す。選択、突然変異、および交叉といった操作は、遺伝子に対して行われる。サブ遺伝子は、コーディネーション（ｃｏｏｒｄｉｎａｔｉｏｎ）によって調整される。
【００４３】
新しいタスクは、集団に含まれるすべての染色体の末尾に付加される。一方、古いタスクがノードにディスパッチされた場合には、このタスクに相当する遺伝子は、すべての染色体から削除される。遺伝的アルゴリズムにおける収束時間および結果の質は、集団サイズに敏感に応答する。集団が大きくなるにしたがって、結果の質が向上するとともに、収束時間が長くなる。収束時間を短縮するために、タスクの数、すなわち、染色体長に応じて集団サイズを変更する。集団の最小サイズは、つねにノードの数と同一であり、最大サイズは染色体長の１／３以下である。したがって、集団サイズは次式（１）となる。
【００４４】
2012517041.tif 000003
【００４５】
＜適合度（ｆｉｔｎｅｓｓ  ｖａｌｕｅ）および不適合度（ｕｎｆｉｔｎｅｓｓ  ｖａｌｕｅ）＞
個体の質を評価するために、適合度（ｆｉｔｎｅｓｓ  ｖａｌｕｅ）および不適合度（ｕｎｆｉｔｎｅｓｓ  ｖａｌｕｅ）が用いられる。ｍ個のタスクすべての総時間コストを評価するために、適合度ｆが用いられる。適合度関数（ｆｉｔｎｅｓｓ  ｆｕｎｃｔｉｏｎ）は、次式（２）によって定義される。
【００４６】
2012517041.tif 000004
【００４７】
ここで、記号
2012517041.tif 000005
は、タスクＴｉがノードｎｊに存在していることを表す。不適合度μは、ｍ個のすべてのタスクの全遅延時間を測る。不適合度関数（ｕｎｆｉｔｎｅｓｓ  ｆｕｎｃｔｉｏｎ）は、次式（３）によって定義される。
【００４８】
2012517041.tif 000006
【００４９】
したがって、適合度は負の値をとることはなく、不適合度は正の値をとることはない。
【００５０】
＜選択（ｓｅｌｅｃｔｉｏｎ）と交叉（ｃｒｏｓｓｏｖｅｒ）＞
選択は、２つのバイナリトーナメント（ｂｉｎａｒｙ  ｔｏｕｒｎａｍｅｎｔ）から成る。１つのトーナメントでは、集団の中から２つの個体がランダムに抽出される。より実現可能性の高い個体が、親（ｐａｒｅｎｔ）として選択される。２つのトーナメントにより、２つの親が選択される。
【００５１】
選択された２つの親は、交叉において新しい個体を生成する。ここで、単純な１点交叉（ｏｎｅ  ｐｏｉｎｔ  ｃｒｏｓｓｏｖｅｒ）を用いるようにしてもよい。交叉点（ｃｒｏｓｓｏｖｅｒ  ｐｏｉｎｔ）ｐは、ランダムに選択される。２つの親は、前者のｐ個の遺伝子と、後者の（ｎ−ｐ）個の遺伝子とを互いに交換する。交叉の後に、新しい個体が生成される。交叉は、他の遺伝的アルゴリズムにおいてよく用いられている、いくつかの代替手段を含む。
【００５２】
＜突然変異（ｍｕｔａｔｉｏｎ）＞
標準的なＧＡにおける突然変異操作は、一定の確率で生じるオプション操作である。基本的に、突然変異操作は染色体内の２つの遺伝子を交換し、これにより、解空間における未踏の領域をＧＡに探査させる。本発明においては、スライド突然変異（ｓｌｉｄｅ  ｍｕｔａｔｉｏｎ）と呼ぶ、特別な突然変異を開発した。スライド突然変異においては、期限に間に合わないタスクである、強制タスク（ｏｂｌｉｇｅｄ  ｔａｓｋ）を最も負荷の軽いノードに移動する。ただし、移動したタスクと移動先のノードのタスクのすべてが期限に間に合う場合に限り、タスクを移動するものとする。この振る舞いは、負荷の重いノードにおけるタスクが負荷の軽いノードへとスライドするかのように見える。ＧＡの各ループにおいて、スライド突然変異は１度だけ起こり得る。また、期限に間に合わないタスクが存在しない場合には、スライド突然変異は省略される。スライド突然変異のメカニズムを図４に示す。
【００５３】
＜コーディネーション（ｃｏｏｒｄｉｎａｔｉｏｎ）＞
タスクのリードタイム（ｌｅａｄ  ｔｉｍｅ）は、通常、タスクの期限と現在時刻の差の絶対値として定義される。コーディネーションにおいては、各ノードにおけるタスクを、リードタイムの昇順にソートする。次に、新しい順序に従ってサブ遺伝子を再割り当てする。理論上は、単一ノードにおけるＥＤＦ（Ｅａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔ）ポリシが最適である。コーディネーションは、事実上のＥＤＦポリシに従ってタスクをソートする。コーディネーション後において期限に間に合わないタスクが存在する場合には、これを改良し得る最適アルゴリズムは存在しない。そこで、ＧＡは異なるノードにおける様々なタスクの組み合わせを生成し、コーディネーションは各ノードにおけるタスクの実行順序を最終的に調整する。
【００５４】
＜置換（ｒｅｐｌａｃｅｍｅｎｔ）と停止条件（ｓｔｏｐ  ｃｏｎｄｉｔｉｏｎ）＞
置換は、適合度および非適合度に基づいて行われる。新しい個体は、古い個体よりも非適合度が小さい場合には、古い個体を置き換える。古い個体のすべての非適合度がゼロである場合には、適合度が最小の古い個体が置き換えられる。新しい個体が集団内の古い個体のいずれかと同一の染色体構造を有する場合には、新しい個体は集団に加わることを許されない。
【００５５】
置換は、集団の拡大および縮小を引き起こす。新しい個体を受け付ける前に、すべての古い個体が実現可能であり（すべての非適合度がゼロであり）、かつ、集団サイズが式（１）によって与えられる数よりも小さい場合には、新しい個体は古い個体を置換することなく、集団に直接加わる。新しい個体を受け付けた後、集団サイズが式（１）によって与えられる数よりも大きくなった場合には、最も適合しない個体、または、適合度が最大の個体が削除される。
【００５６】
ＧＡは停止条件を満たすまで、集団を進化させる。停止条件は、新しい個体を生成しても所定の世代数にわたって最適解が改良されないこと（「進化限界」という。）、または、イタレーションの回数が（予め定義されたパラメータである）ＧＡの最大世代に到達したこと（「最大時間制限」という。）とする。進化限界によると、最大時間制限よりもＧＡを早期に停止させることができる。通常、イタレーションの回数は、ＧＡの実行時間とほぼ線形の関係になる。したがって、最大時間制限を設定することで、受付時間を制御することができる。
【００５７】
＜染色体の伸び（ｅｘｐａｎｄｉｎｇ）・縮み（ｓｈｒｉｎｋｉｎｇ）＞
染色体の伸び縮みの理解を助けるために、図５に事例を示す。この事例においては、６個のノードと次々に到着するタスクが存在する。図５の第１の染色体は、スケジューリング・受付プロセスのスナップショットにおける任意の一染色体であるものとする。タスク５が終了した後、新しいタスクが到着していない場合には、染色体の長さは短くなる。次に、新しいタスクであるタスク１０が到着し、古いタスクの中に終了したものがない場合には、染色体の長さが長くなる。タスク１０が受け付けられない場合には、染色体は前の状態にロールバックする。
【００５８】
＜動的な（ｄｙｎａｍｉｃ）集団と染色体＞
上述のとおり、新しいタスクが到着し、古いタスクが去ると、染色体長および集団サイズは動的に変化し得る。図６は、このプロセスを明確に示している。新しいタスクの到着により、染色体の長さが伸びる。古いタスクが去ることにより、染色体の長さが縮む。置換により、集団サイズは拡大ないし縮小する。新しいタスクが受け付けられた場合には、この染色体を含む集団は次回のタスク受付の際にも使用されることになる。一方、新しいタスクが受け付けられなかった場合には、染色体は新しいタスクが到来する前の状態へロールバックする。
【００５９】
＜受付制御・スケジューリングシステム＞
図７は、本発明に係る受付制御・スケジューリングシステムの構成を示すブロック図である。受付制御・スケジューリングシステム１０は、タスクバッファ１１、プレスケジューリングモジュール１２、第１のストレージ１３、第２のストレージ１４、および、タスク割当部１５を有する。
【００６０】
タスクバッファ１１は、到来した新たなタスクを待ち行列に格納する。プレスケジューリングモジュール１２は、新しいタスクおよび以前に受け付けたタスクのプレスケジュールを行い、複数のプレスケジュールを生成し、最も実現可能性の高いプレスケジュールを実行スケジュールとして使用する。第１のストレージ１３は、プレスケジュールを保持する。第２のストレージ１４は、実行スケジュールを保持する。タスク割当部１５は、実行スケジュールに含まれるタスクをディスパッチする。
【００６１】
プログラムに関して言えば、上述の方法を実行し、または、上述のシステムを稼動させるようにプログラムされたプログラムによって、上述の方法またはシステムを実施するようにしてもよい。プログラムは、任意の記録媒体ないしコンピュータに記録されていてもよいし、システムを構成する単一または複数のコンピュータによって実行されるようにしてもよい。
【００６２】
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。
【００６３】
また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【００６４】
１０    受付制御・スケジューリングシステム
１１    タスクバッファ
１２    プレスケジューリングモジュール
１３    第１のストレージ
１４    第２のストレージ
１５    タスク割当部
【図１】
2012517041.tif 000007
【図２】
2012517041.tif 000008
【図３】
2012517041.tif 000009
【図４】
2012517041.tif 000010
【図５】
2012517041.tif 000011
【図６】
2012517041.tif 000012
【図７】
2012517041.tif 000013
【国際調査報告】
2012517041.tif 000014
2012517041.tif 000015