(57)【要約】  本発明は、優先順位および相互排他の制約を受ける複数の同時ジョブシーケンスをスケジューリングするための方法およびシステムに関する。特に、本発明は、リソース（機器）群を使用する必要がある非プリエンプティブなジョブを含むとともに解放時間および実行時間に制約を有する臨床サンプルに対して生物学的分析を行うシステムのためのスケジューラに関する。スケジューリング問題は、実際の工業システムで発生する。原則として、この問題は、タイムペトリネットまたは時限オートマトンなどの同時実行モデルに対する実時間モデル検査の事例として定式化することができる。しかし、この手法は、所期のランタイム埋め込みプラットフォームでは有効ではない。本発明の好適な実施形態によるスケジューリング方法は、ＤＢＭデータ構造のコアおよびフロイド−ワーシャルアルゴリズムを本格的なモデル検査ツールのエンジンから抽出するアルゴリズム解法を意図的に活用し、これを事例の特殊な要件に適合させる。これにより、最適下限解のためのヒューリスティックを実行可能にする探索の複雑性を大幅に低減し、漸進的なアルゴリズム改善によって、所期の性能要件を達成することができる。
2015510107.tif 000002
【特許請求の範囲】
【請求項１】
決定性実行時間がｅ１…ｅｎの、複数の非プリエンプティブルなジョブＪ１…Ｊｎを実行するよう構成されたシステムにおいて、優先順位制約および排他制約に対応しつつ、各ジョブＪ１…Ｊｎのための解放時間ｒ１…ｒｎを、ジョブ集合全体の完了時間を最小化するよう決定するためのｍ個の独立した機器Ｍ１…Ｍｍのうちの１つに各ジョブを静的に割り当てるスケジューリング方法であって、
前記優先順位制約では、
-前記複数のジョブのうち、ＪｘとＪｙのペアの所定の集合について、Ｊｙの完了とＪｘの開始の間の遅延が、以下のとおり、最小遅延ｄ−ｘｙと最大遅延ｄ＋ｘｙの範囲内であり、
【数１】
2015510107.tif 000012
前記排他制約では、
-前記複数のジョブのうち、ＪｉとＪｋのペアの所定の集合について、以下の２つの排他制約のうちの１つが満たされ、
【数２】
2015510107.tif 000013
したがって、ＪｋおよびＪｉの実行期間は重ならず、
前記方法が、
-Ａ）前記優先順位制約を満たす解放時間を収集するＤＢＭ（Ｄｉｆｆｅｒｅｎｃｅ  Ｂｏｕｎｄ  Ｍａｔｒｉｘ）ゾーンを含む、未処理（ｆｒｏｎｔｉｅｒ）集合を構築する工程と、
-Ｂ）前記ＤＢＭゾーンの１つを選択し、これを前記未処理集合から除去する工程と、
-Ｃ）前記所定のペアの集合のうち、ＪｉとＪｋの１つのペアの、少なくとも１つの排他制約を満たさない、前記選択されたＤＢＭゾーンに対応させ、競合（ｒｉ≧ｒｋ＋ｅｋまたはｒｉ＋ｅｉ≦ｒｋ）を解消する前記２つの定量のそれぞれにつき、前記選択されたＤＢＭゾーンの１つの制限ゾーンを構築する工程と、
-Ｄ）前記制限ＤＢＭゾーンが非空であるか確認し、前記非空制限ＤＢＭゾーンを前記未処理集合に加える工程と、
-Ｅ）選択されたＤＢＭゾーンが前記排他制約のすべてを満たすまで、工程Ｂ〜Ｄを繰り返す工程とを備える方法。
【請求項２】
繰り返し工程が、前記未処理集合内のすべてのＤＢＭゾーンが、前記排他制約のすべてを満たすまで行われる、請求項１に記載の方法。
【請求項３】
繰り返し工程が、所定の最大探索時間に達したときに中止される、請求項２に記載の方法。
【請求項４】
すべての排他制約を満たす、すべてのＤＢＭゾーン内の最適なスケジュールを選択する工程をさらに備える、請求項１〜３のいずれか一に記載の方法。
【請求項５】
工程Ｂが、ヒューリスティック評価に依存して行われる、請求項１〜４のいずれか一に記載のスケジューリング方法。
【請求項６】
前記ヒューリスティックが、すべての排他制約を満たす前記選択されたＤＢＭゾーンの特性を評価する、最長間隔（安全な）ヒューリスティックを含む、請求項５に記載のスケジューリング方法。
【請求項７】
前記ヒューリスティックが、完了時間全体を最小化する前記選択されたＤＢＭゾーンの特性を評価する、最短間隔（欲張りな）ヒューリスティックを含む、請求項５または６に記載のスケジューリング方法。
【請求項８】
工程Ｃの実行において、制限の影響を受けないＤＢＭ係数の再計算を回避することにより、Ｏ（ｎ３）〜Ｏ（ｎ２）（ｎはジョブ数）から複雑性を低減する、ワーシャル−フロイドアルゴリズムの最適化版を用いて、制限ゾーンの正規形を導出する、請求項１〜７のいずれか一に記載のスケジューリング方法。
【請求項９】
前記アルゴリズムの時間複雑性および採用されたデータ構造の空間占有率を制限するために、コード最適化を実施する、請求項１〜８のいずれか一に記載のスケジューリング方法。
【請求項１０】
前記システムが複数のリソースを含み、各ジョブが実行のための前記複数のリソースの少なくとも１つを利用可能であることを必要とし、各所定のペアのジョブ間の排他制約が、前記ペアのジョブの両方により同一リソースを利用可能である必要を表す、請求項１〜９のいずれか一に記載のスケジューリング方法。
【請求項１１】
前記リソースが、前記スケジューリングされたジョブのいずれかにより、そのタスクの評価のために使用される、任意の論理的、電子的、または機械的ユニットを含む、請求項１０に記載の方法。
【請求項１２】
プログラムがコンピュータ上で実行される際に、請求項１〜１１のいずれか一に記載のスケジューリング方法を実行するためのプログラムコード手段を含む、コンピュータプログラム。
【請求項１３】
請求項１２に記載のコンピュータプログラムを格納するコンピュータ可読手段を含む、コンピュータプログラム製品。
【請求項１４】
解放時間がｒ１…ｒｎで、決定性実行時間がｅ１…ｅｎの、複数の非プリエンプティブルなジョブＪ１…Ｊｎの実行をスケジューリングするためのシステムであって、各ジョブはｍ個の独立した機器Ｍ１…Ｍｍのうちの１つに静的に割り当てられ、前記システムが、請求項１〜１１のいずれか一に記載されたスケジューリング方法の工程を実行するよう構成された１つまたは複数の素子を含むシステム。
【請求項１５】
請求項１４に記載のシステムを備える、生物学的分析を行うための電気機械システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、相互排他および相互遅延の制約を受ける時限ジョブの複数の並行シーケンスのための方法およびシステムに関する。本発明は特に、１つの電気機械装置群を共用しつつ、異なるサンプルに対し異なる解析プロトコルを適用する多重並行生物学的分析を行うシステムのためのスケジューラに関する。
【背景技術】
【０００２】
有界スラック時間が許容され、相互遅延および相互排他の制約のある、複数の並行・時限ジョブシーケンスのスケジューリングの問題は、非常に多様な状況に該当するが、本願では、生物学的分析用の電気機械システム、例えば、ｂｉｏＭeｒｉｅｕｘにより開発されたＶＩＤＡＳシステムなどのためのランタイムスケジューラの具体例を参照しつつ、一般性を失うことなく、この問題に対処する。
【０００３】
本例のシステムは、多重並行分析群、サンプルの生物学的反応の各順次の工程、および共通の電気機械装置により行われる転送動作を実行することができ、各反応工程の持続時間は、分析の生物学プロトコルにより決定されるが、各反応工程の完了の後、有界待ち時間が加えられる可能性がある。
【０００４】
これにより、並行分析数を最大にするとともにその全体の完了時間を最小にしつつ、最大許容遅延に適合し、共通のリソースを使用する際の競合を避けるように各行程後の待ち時間を決定するというスケジューリングの課題が生じる。
【０００５】
より詳しくは、各種の生物学的分析は、前処理段階および分析プロトコルに含まれる。分析の開始の際、サンプルは、バーコードにより一意に識別される試験チューブに容れられ、他のチューブは、希釈・培養流体を含み、また他のチューブは空である。前処理段階の間、自動分注器により、繰り返し、別個のチューブのサンプルを廃棄し、各分注動作は、決定性時間の間、継続する。連続する動作間で、待ち時間が許容されるが、待ち時間は、培養／反応期間およびサンプル劣化特性により決まる最小値と最大値の間の範囲に制限される。前処理段階の完了の後、分析プロトコルは、サンプルを試薬と混合させる工程の固定シーケンスに従い、多重測定値は、動作が決定性持続時間を費やす読み取りヘッドにより取得される（図１参照）。
【０００６】
電気機械素子の効率的な使用のために、ことによると異なる種類の多重分析を同時に行う。そのため、システムは、それぞれが各分析用の複数のセクションを構成する。各セクションは、順番に、異なる前処理を受ける可能性のある個別のサンプルを含むスロットに分配され、異なる対象のサンプルに対し動作することができる。しかし、読み取りヘッドが、セクション全体に同時に処理するよう設計されているため、同じセクション内のすべてのスロットは、同じ分析プロトコルを実行するよう制限されている（図２参照）。
【０００７】
分注器および読み取りヘッドは、個別のスロットおよびセクションにより共用され、２つの異なる分析に同時に用いることが不可能である。これにより、各前処理の初期遅延および同一分析の各イベント間の待機時間の許容値を決定する必要があるというスケジューリングの課題が生じる。このような値は、分注器および読み取りヘッドが同時期に動作しないようにしたり、許容範囲を超える待ち時間を防止したり、分析群の全体の期間を最小限にとどめたりする必要を回避しなければならない。
【０００８】
（問題の定式化）
問題は、解放時間がｒ１…ｒｎであり、決定性実行時間がｅ１…ｅｎの、ｎ個の、独立の非プリエンプティブルなジョブＪ１…Ｊｎの集合として、ジョブショップスケジューリングの一般的な表記の形に落とし込むことができ、各ジョブは、以下の優先順位および相互排他の制約を受ける、ｍ個の独立した機器Ｍ１…Ｍｍのうちの１つに静的に割り当てられる。
-任意の２つのジョブＪｉおよびＪｋは、優先順位制約により、Ｊｋの完了とＪｉの開始の間の遅延が、最小ｄ−ｉｋおよび最大ｄ＋ｉｋの範囲内であることが求められうる。
【数１】
2015510107.tif 000003
-任意の２つのジョブＪｉおよびＪｋは、相互排他制約により、ＪｋおよびＪｉの実行期間が重ならないことが求められる可能性があり、これは、ＪｉがＪｋの完了の後に開始するか、またはその逆となることを保証する、以下の２つの定量のいずれかにより達成されうる。
【数２】
2015510107.tif 000004
【０００９】
スケジューリングの課題は、定められた優先順位および相互排他のすべての制約を受ける解放時間ｒ１…ｒｎを、複数のジョブシーケンス全体の完了時間を最小化するよう決定することである。図３ａは、ジョブＪ１，Ｊ２，Ｊ３，Ｊ４が機器Ｍ１およびＭ２に割り振られ、ジョブＪ２はＪ４に対し相互排他的であり、Ｊ１およびＪ３の完了時間に対する開始時間を制限する優先順位制約を有するというインスタンスの問題を示す。優先順位制約はまた、Ｊ３の完了に対するＪ４の開始時間の遅延を制限する。図３ｂは、この問題に対する解法を示す。
【００１０】
上に定義されたスケジューリングの問題は、相互排他および優先順位の制約を有する非決定性解放時間の相互関係を特徴とするため、タイムペトリネット（ＴＰＮ）または時間オートマトン（ＴＡ）などの非決定性形式によって、ジョブのようなスケジューリング概念、制約およびリソースを、場所／位置、遷移、事前条件および事後条件に直接変換することにより、都合よく定式化することができる。これにより、リージョン（Ｄ．  Ｄｉｌｌ．  Ｔｉｍｉｎｇ  Ａｓｓｕｍｐｔｉｏｎｓ  ａｎｄ  Ｖｅｒｉｆｉｃａｔｉｏｎ  ｏｆ  Ｆｉｎｉｔｅ−Ｓｔａｔｅ  Ｃｏｎｃｕｒｒｅｎｔ  Ｓｙｓｔｅｍｓ．  Ｉｎ  Ｐｒｏｃ．  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｓｙｓｔｅｍｓ，  １９８９参照）に基づく状態空間の記号解析を通じて、並行制約と非決定性タイマーの組み合わせを管理するモデリングおよび検証ツールの適用に道が開かれる。この観点において、スケジューリング問題は、「リソース利用時の競合のない状態のみを経て、最大時間Ｔ以内で完了状態に達するすべての挙動」を選択する実時間モデル検査式（例えば  Ａ．  Ｆｅｈｎｋｅｒ．  Ｓｃｈｅｄｕｌｉｎｇ  ａ  ｓｔｅｅｌ  ｐｌａｎｔ  ｗｉｔｈ  ｔｉｍｅｄ  ａｕｔｏｍａｔａ．  Ｉｎ  Ｒｅａｌ−Ｔｉｍｅ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，  １９９９．  ＲＴＣＳＡ  ’９９．  Ｓｉｘｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ，  ｐａｇｅｓ  ２８０-２８６，  １９９９参照）を満たす記号的状態空間内の証拠の識別として定式化することができる。Ｔの最適値は、多様なツールによりサポートされ、とりわけＵｐｐａａｌ環境（例えば、Ｋ．  Ｌａｒｓｅｎ．  Ｒｅｓｏｕｒｃｅ−ｅｆｆｉｃｉｅｎｔ  ｓｃｈｅｄｕｌｉｎｇ  ｆｏｒ  ｒｅａｌ  ｔｉｍｅ  ｓｙｓｔｅｍｓ．  Ｉｎ  Ｒａｊｅｅｖ  Ａｌｕｒ  ａｎｄ  Ｉｎｓｕｐ  Ｌｅｅ，  ｅｄｉｔｏｒｓ，  Ｅｍｂｅｄｄｅｄ  Ｓｏｆｔｗａｒｅ，  ｖｏｌｕｍｅ  ２８５５  ｏｆ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｐａｇｅｓ  １６-１９．  Ｓｐｒｉｎｇｅｒ  Ｂｅｒｌｉｎ−Ｈｅｉｄｅｌｂｅｒｇ，  ２００３．または、Ｉ．  ＡｌＡｔｔｉｌｉ，  Ｆ．  Ｈｏｕｂｅｎ，  Ｇ．  Ｉｇｎａ，  Ｓ．  Ｍｉｃｈｅｌｓ，  Ｆ．  Ｚｈｕ，  ａｎｄ  Ｆ．Ｗ．  Ｖａａｎｄｒａｇｅｒ．  Ａｄａｐｔｉｖｅ  ｓｃｈｅｄｕｌｉｎｇ  ｏｆ  ｄａｔａ  ｐａｔｈｓ  ｕｓｉｎｇ  ｕｐｐａａｌ  ｔｉｇａ．  Ｉｎ  ＱＦＭ，  ｐａｇｅｓ  １-１１，  ２００９参照）でサポートされる多項式の繰り返しによって得ることができる。Ｏｒｉｓツール（Ｇ．  Ｂｕｃｃｉ  ａｎｄ  Ｌ．  Ｃａｒｎｅｖａｌｉ  ａｎｄ  Ｌ．  Ｒｉｄｉ  ａｎｄ  Ｅ．  Ｖｉｃａｒｉｏ．  Ｏｒｉｓ：  ａ  Ｔｏｏｌ  ｆｏｒ  Ｍｏｄｅｌｉｎｇ，  Ｖｅｒｉｆｉｃａｔｉｏｎ  ａｎｄ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ．  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｓｏｆｔｗａｒｅ  Ｔｏｏｌｓ  ｆｏｒ  Ｔｅｃｈｎｏｌｏｇｙ  Ｔｒａｎｓｆｅｒ，  １２（５）：３９１  -  ４０３，  ２０１０）では、所期のシーケンス処���制約（Ｅ．  Ｖｉｃａｒｉｏ．  Ｓｔａｔｉｃ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｄｙｎａｍｉｃ  Ｓｔｅｅｒｉｎｇ  ｏｆ  Ｔｉｍｅ  Ｄｅｐｅｎｄｅｎｔ  Ｓｙｓｔｅｍｓ  Ｕｓｉｎｇ  Ｔｉｍｅ  Ｐｅｔｒｉ  Ｎｅｔｓ．  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  ＳＷ  Ｅｎｇ．，  ２７（１）：７２８-７４８，  Ａｕｇｕｓｔ  ２００１）に適合する遷移の各シーケンスで費やされた最小・最大時間を評価することにより、直接的な方法で、最適値Ｔを導出する。
【００１１】
あいにく、このタイプの記号的状態空間解析技術を直接適用すると、状態空間爆発（ジョブ数とともに、状態数が指数関数的に増加する）および次元の呪い（シーケンス数とともに、各状態を符号化するデータ構造の数が２次式的に増加する）の問題に直面する。その結果、工業用途ではあまりないことではあるが、従来のＰＣに対して計算を行う場合であっても、オンラインのスケジューラにとっては遙かに受け入れ難い、メモリと時間の複雑性がもたらされる。
【００１２】
実用的な複雑性の程度を理解するだけのために、ＯｒｉｓツールによるＤＢＭゾーンに基づいた状態空間解析を、２つのセクション、セクション毎に３つのスロット、および決定性遅延からなる、非常に単純な場合のＴＰＮ表現に対し試験的に行った。ＴＰＮ列挙手続きにより、デュアルコアの２ＧＨｚデスクトップコンピュータで約２０分を要する、初期状態から終端ノードまで４２１６通りの予想経路が存在する、２５５１２８ＤＢＭ状態クラスの巨大な状態空間が生成される可能性がある。
【００１３】
モデル単純化の際の複雑性を低減するために最先端技術を適用したとしても、また、（リージョンよりは遙かに小さい）ＤＢＭゾーンにわたって状態空間を分割したとしても、この状態空間クラスの解析技術の処理時間およびメモリ需要は、上述した用途のような工業用途における目的の用法に適合しない。そのため、オンラインで、ほぼリアルタイムの手法でスケジューリング問題を解決するとともに、それが、限られた処理およびメモリリソースで動作する埋め込み素子内で実行可能であることが求められる。通常、この種の生物学的検査機器（ただし、より一般的には工業用電気機械機器）内で利用可能なハードウェアリソースは、非常に限られており、このような複雑な数学的アルゴリズムの実行の多大な需要には対応しない。
【００１４】
そのため、分析の一般性を、特定の問題の効率と引き替えにして、より高速で実行させ、メモリの需要および処理電力を低減させるようにする解法が、強く求められている。
【発明の概要】
【発明が解決しようとする課題】
【００１５】
（本開示の目的）
本発明は、先行技術に関する問題の少なくとも一部を克服することを目的とする。
【００１６】
本発明のさらなる目的は、相互排他および相互遅延の制約を受け、有界待ち時間による遅延が許容される時限工程の複数の並行シーケンスのための、許容可能で効率的なスケジュールを計算するために求められるメモリおよび処理時間が限られた方法を提供する。
【００１７】
これは、現実の工業用電気機械システムに生じるスケジューリング課題として説明され、相互排他および相互遅延の制約を満たしつつ、並行生物学的分析群をできるだけ短期間で完了するように、共通の電気機械素子群により行われる動作のための実現可能なタイミングを見つけることを包含する。ここに記載する具体例では、スケジューリングアルゴリズムは、２００ＭＨｚのＣＰＵおよび１０ＭＢ未満のメモリを備える電気機械システムとともに提供されるハードウェアの回路基板上で実行されることが求められる。さらに、システムを取り扱うオペレータに対する十分な応答性を保証するために、アルゴリズムは、最適下限でありながらも効率的な解法を見つけることが可能であるが、これは、ほぼ数秒程度の短時間で最終的に終了することが求められる。
【００１８】
本発明の別の目的は、複数の並行生物学的分析を実行する電気機械システムを提供することであり、このシステムにおいて、各交互の期間の反応および伝達動作は、共通の装置によって、生物学的分析プロトコルにより決まるタイミング・相互遅延の制約下および共通の装置の排他的な使用法により決まる相互排他制約下で行われる。
【課題を解決するための手段】
【００１９】
（概要）
本開示は、添付の請求項に提示されるスケジューリング方法を提供する。
【００２０】
本発明の第１の実施形態によると、本開示は、決定性実行時間がｅ１…ｅｎの、複数の非プリエンプティブルなジョブＪ１…Ｊｎを実行するよう構成されたシステムにおいて、優先順位制約および排他制約に対応しつつ、各ジョブＪ１…Ｊｎのための解放時間ｒ１…ｒｎを、ジョブ集合全体の完了時間を最小化するよう決定するためのｍ個の独立した機器Ｍ１…Ｍｍのうちの１つに各ジョブを静的に割り当てるスケジューリング方法であって、優先順位制約では、
-複数のジョブのうち、ＪｘとＪｙのペアの所定の集合について、Ｊｙの完了とＪｘの開始の間の遅延が、以下のとおり、最小遅延ｄ−ｘｙと最大遅延ｄ＋ｘｙの範囲内であり、
【数３】
2015510107.tif 000005
排他制約では、
-複数のジョブのうち、ＪｉとＪｋのペアの所定の集合について、以下の２つの排他制約のうちの１つが満たされ、
【数４】
2015510107.tif 000006
したがって、ＪｋおよびＪｉの実行期間は重ならず、
方法が、Ａ）優先順位制約を満たす解放時間を収集するＤＢＭ（Ｄｉｆｆｅｒｅｎｃｅ  Ｂｏｕｎｄ  Ｍａｔｒｉｘ）ゾーンを含む、未処理（ｆｒｏｎｔｉｅｒ）集合を構築する工程と、Ｂ）ＤＢＭゾーンの１つを選択し、これを未処理集合から除去する工程と、Ｃ）所定のペアの集合のうち、ＪｉとＪｋの１つのペアの、少なくとも１つの排他制約を満たさない、選択されたＤＢＭゾーンに対応させ、競合（ｒｉ≧ｒｋ＋ｅｋまたはｒｉ＋ｅｉ≦ｒｋ）を解消する２つの定量のそれぞれにつき、選択されたＤＢＭゾーンの１つの制限ゾーンを構築する工程と、Ｄ）制限ＤＢＭゾーンが非空であるか確認し、非空制限ＤＢＭゾーンを未処理集合に加える工程と、Ｅ）選択されたＤＢＭゾーンが排他制約のすべてを満たすまで、工程Ｂ〜Ｄを繰り返す工程とを備える方法を提供する。
【００２１】
本発明の方法は、ＤＢＭ（Ｄｉｆｆｅｒｅｎｃｅ  Ｂｏｕｎｄ  Ｍａｔｒｉｘ）ゾーンによってできるだけ等価の解集合を取得するとともに、許容解の同定を、グラフ理論的構造における探索として整理することにより、相互排他および遅延の制約を有する時限ジョブの並行シーケンスのスケジューリングを可能にする。このため、一連のアルゴリズム最適化およびヒューリスティック手法により、可能性のあるタイミング設定セットの厳密な（すなわち量子化されず、近似でもない）表現を保ちつつ、解の探索を高速化させることができる。
【００２２】
別の実施形態によれば、繰り返し工程は、未処理集合内のすべてのＤＢＭゾーンが、排他制約のすべてを満たすまで行われる。あるいは、繰り返し工程は、所定の最大探索時間に達したときに中止される。別の実施形態では、すべての排他制約を満たす、すべてのＤＢＭゾーン内で最適な解（スケジュール）を選択する。
【００２３】
別の実施形態によれば、工程Ｂの選択は、いわゆる最長間隔ヒューリスティック（安全）またはいわゆる最短間隔ヒューリスティック（欲張り）を含む、ヒューリスティック評価に基づいている。
【００２４】
別の実施形態によれば、上記方法を行うためのコンピュータプログラムが提供される。
【００２５】
本発明のさらなる実施形態によれば、上記方法を実施するシステムが提供される。このようなシステムは、例えば、生物学的分析を行うための電気機械装置に使用することができる。
【００２６】
本発明は、多くの利益をもたらす。本発明の好適な実施形態の利点の１つは、複雑なスケジューリング作業を、限られた時間およびハードウェアリソースで行うことができるということである。原則として、問題は、実時間モデル検査の事例として定式化することができ、確立された状態空間解析手法により解くことができる。しかし、このような列挙手法は、所定の埋め込みプラットフォームにより課せられるハードウェアの制限により、特定の設定においては有効ではない。本発明の方法により、ＤＢＭ理論の直接的で意図的な改変により、また許容解の探索を行うヒューリスティックの採用を可能にすることにより、アルゴリズムの複雑性は大幅に低減される。本発明の好適な実施形態では、その後のアルゴリズム改善により、計算時間をさらに短くするために、所期の性能要件を達成させることができる。
【００２７】
本発明の実施形態による本発明のさらなる方法およびシステムのさらなる利点は、すでにスケジューリングされた分析の実行を脅かすことなく未使用のリソースを回収することが可能なことである。
【００２８】
例えば、以下の添付図面を参照する。
【図面の簡単な説明】
【００２９】
【図１】生物学的試験を行うための電気機械装置で単一分析を実行中のシステム素子の物理的アーキテクチャの略図である。
【図２】本発明の実施形態による生物学的試験を行うための電気機械装置のスロットおよびセクションの複数の分析を構成する、システム全体の物理的構造の略図である。
【図３】図３ａは、定められた優先順位および相互排除のすべての制約を受ける解放時間ｒ１…ｒｎを、ジョブ集合全体の完了時間を最小化するよう決定するスケジューリングの課題のインスタンスの略図である。図３ｂは、解放時間の値を決定する実行可能解である。
【図４】図４ａは、変数ｔｉとｔｊの対の解集合を符号化する２次元ＤＢＭを示す。図４ｂは、無効制約の存在を強調する２次元ＤＢＭを示す。図４ｃは、３つの変数ｔｉ、ｔｊ、およびｔｋを含むＤＢＭのグラフ理論的表現を示す。
【図５】本発明の好適な実施形態によるスケジューリング方法の排他制約に関するその後の選択で構成されるバイナリツリーの例を示す。
【図６】本発明の好適な実施形態による２つの異なるヒューリスティックによる特性試験実験の結果を示す。
【発明を実施するための形態】
【００３０】
本明細書では、後処理の目的で、スケジューリング解法が依存する主概念、すなわちＤＢＭ（Ｄｉｆｆｅｒｅｎｃｅ  Ｂｏｕｎｄ  Ｍａｔｒｉｃｅｓ）およびフロイド−ワーシャルアルゴリズムを採用する。
【００３１】
ＤＢＭは、Ｎ個の変数τ＝＜τ１…τＮ＞のベクトルの解集合を同定する以下の不等式系を符号化する。
【数５】
2015510107.tif 000007
ＤＢＭの任意の２次元投影は、図４ａに表される型の多面体を生じる。１つまたは複数の制約が有効でない場合、ＤＢＭは完全に形成されず（図４ｂ参照）、この場合、これらの制約の無限数の値により、同じ解集合がもたらされる。任意のさらなる制限が、解集合を変化させうるような極限値は、その存在が証明され、以下の三角不等式が成り立つとき、またそのときに限って一意的である。
【数６】
2015510107.tif 000008
【００３２】
この条件により、上記の三角不等式を満たす表現として定義される正規形の概念が同定される。
【００３３】
ＤＢＭの制約の集合は、グラフのノードは変数を表し、エッジにＤＢＭ係数の値が記された（すなわち、変数ｉおよびｊに対応するノードを繋ぐエッジに係数ｂｉｊが記された）、グラフ理論的定式（図４ｃ参照）に落とし込むことができると好都合である。この観点において、ＤＢＭの正規形が、ｂｉｊ係数がノードｉ〜ｊからの最短路として計算される最短路問題となる。
【００３４】
ＤＢＭが非空であるという仮定が、負の閉路（すなわち、係数の合計が負の値になるグラフ内のサイクル）の存在を排除するということが、容易に証明される。そのため、この問題は、合計複雑度Ｏ（Ｎ・Ｎ２）で、周知のダイクストラアルゴリズムをＮ回繰り返し適用することにより解くことができる。フロイド−ワーシャルアルゴリズムは、変わらずＯ（Ｎ３）で実行されるが、その内側のサイクルのダイクストラよりも大幅に単純な演算を行う直接解法をもたらし、ＤＢＭドメインに対応するもののように、密な隣接行列を扱う場合に好適である（Ｅ．  Ｖｉｃａｒｉｏ．  Ｓｔａｔｉｃ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｄｙｎａｍｉｃ  Ｓｔｅｅｒｉｎｇ  ｏｆ  Ｔｉｍｅ  Ｄｅｐｅｎｄｅｎｔ  Ｓｙｓｔｅｍｓ  Ｕｓｉｎｇ  Ｔｉｍｅ  Ｐｅｔｒｉ  Ｎｅｔｓ．  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  ＳＷ  Ｅｎｇ．，  ２７（１）：７２８-７４８，  ２００１参照）。
【００３５】
アルゴリズム１で、フロイド−ワーシャル疑似コードを説明する。その核となる不変条件は、「ｋよりも大きな指数をもつ頂点のみが中間ノードとして訪問される制限の下、ｉ〜ｊからの最短路」を符号化する変数ｂｉｊｋである。この報告によれば、ｂｉｊＮに、コード内の第１のループに意味を与える、係数ｂｉｊの初期値が与えられることが明らかである。また、ｂｉｊ０が、コード内において、第２のｆｏｒループにわたりＮから１までｋを減らすことにより達成される、問題の最終解を含むことが明らかである。したがって、アルゴリズムの実際の核は、ネストされたｉ、ｊの２重ループがｂｉｊｋ−１をｂｉｊｋから導出できる方法に制約される。
【００３６】
（アルゴリズム１）フロイド−ワーシャルアルゴリズム
【００３７】
【表１】
2015510107.tif 000009
【００３８】
ＤＢＭデータ構造およびフロイド−ワーシャルアルゴリズムは、スケジューリング課題を解く機能性をもたらしうる汎用の検証・モデル検査ツールの基礎をなす。本発明の好適な実施形態では、一般モデルの状態空間解析の複雑性を制限するために、スケジュールシーケンスの特定の規則的構造を活用することによって、相互排他制約を受ける演算間の異なる順序性から生じうるタイミングの識別に、ＤＢＭ（Ｄｉｆｆｅｒｅｎｃｅ  Ｂｏｕｎｄ  Ｍａｔｒｉｘ）ゾーンのアルゴリズムコアを適応させた。これにより、ＤＢＭゾーンを正規形に維持するために用いられるフロイド−ワーシャルアルゴリズムの様々な最適化適応が生じた。
【００３９】
その後、逐次トラバーサルを可能にするグラフ理論的構造内の異なる相互排他制約集合の異なる定量に対応するＤＢＭを整理した。広義において、このアルゴリズムは、漸次、排他制約を追加するとともに時間パラメータと課題により課された制約との適合性を検証することにより解候補を反復的に構築する。この環境において、得られた結果の（効率的な）操作および比較を可能にするために、フロイド−ワーシャルアルゴリズムを繰り返し実行してＤＢＭをその正規形に保ちつつ、ＤＢＭ構造を用いてジョブ間の優先順位および排他を決定する制約集合をコードする。
【００４０】
このアルゴリズムは、最初に、問題の優先順位制約のすべてを表すＤＢＭゾーンＤｐｒｅｃを構築する。次に、２種類の異なる定量の各排他制約を加え、空となった制限ゾーンを廃棄することにより、ゾーンＤｐｒｅｃを繰り返し制限する。すべての排他制約のためのある定量に制限された任意の非空ゾーンは、スケジューリング問題のための解集合を含む。この解は、排他制約の単一定量に一義的に対応し、そのＤＢＭゾーンは、これらの定量と整合性のあるタイミングのすべてのみを含む。最適なタイミングは、単純かつ直接的な方法でＤＢＭゾーンの正規形から導出することができる。
【００４１】
この観点では、本発明のスケジューリングアルゴリズムは、構造の各ノードがＤＢＭゾーンと関連する、グラフ理論的構造のトラバーサルとみなされうる。具体的には、ルートは、すべての優先順位を満たすが、排他を満たさないゾーンＤｐｒｅｃであり、中間ノードは、排他制約の部分集合でＤｐｒｅｃを制限し、葉ノードは、ある定量のすべての排他制約でＤｐｒｅｃを制限し、グラフ理論的構造の各エッジは、１つまたは複数の排他制約のある定量の選択を表す。一般性を失うことなく、アルゴリズム２は、本発明の好適な実施形態による実施態様のアルゴリズム疑似コードを報告する。この特定の場合、各エッジは、単一の相互排他制約を加え、グラフ理論的構造がバイナリツリーとなるようにする。
【００４２】
（アルゴリズム２）スケジューリングアルゴリズム
【００４３】
【表２】
2015510107.tif 000010
【００４４】
この実施態様は、以下のとおり、いくつかのデータ構造および不変条件に依存する。
-指数ｃは、制限に加えられた排他制約の数を表し、バイナリツリーの深さの意味も有し、さらに、Ｃはすべての排他制約の数であるため、Ｃの深さのノードは葉ノードである。
-Ｄｓｏｌは、計算の任意の時点における最適同定解を表す。それは、あるダミー評価、例えば、平凡なで非効率的なスケジュールまたは他よりも悪いとみなすことができる何らかの象徴値により初期化される。
-アルゴリズムは、それぞれがＤＢＭゾーンＤおよび深さ指数ｃにより同定される、ツリーのノードを含む待ち行列に依存する。
-排他制約は、指数ｃが排他制約を一意に同定するようにソートされるものとする。
【００４５】
このアルゴリズムはまた、以下の様々な関数に依存する。
-Ｎｏｒｍａｌｉｚｅ（Ｄ）は、フロイド−ワーシャルアルゴリズムを適用してパラメータとしてのＤＢＭ  Ｄを正規化する。
-Ｅｎｑｕｅｕｅ（＜Ｄ，ｃ＞）およびＤｅｑｕｅｕｅ（）は、待ち行列に対し、それぞれ追加および抽出作業を行い、ＱｕｅｕｅＩｓＮｏｔＥｍｐｔｙ（）は、待ち行列が少なくとも１つの要素を含むかどうか確認する。
-ＡｄｄＲｉｇｈｔＣｏｎｓｔｒａｉｎｔ（Ｄ，ｃ）は、右側の定量で順序ｃの制約を加えることによりＤを制限し（すなわち、制約がジョブＪｉとジョブＪｊの間である場合、加えられた制約はｒｉ−ｒｊ≧ｅｊ）、同様に、ＡｄｄＬｅｆｔＣｏｎｓｔｒａｉｎｔ（Ｄ，ｃ）は、左側の定量で順序ｃの制約を加えることによりＤを制限する（すなわち、制約がジョブＪｉとジョブＪｊの間である場合、加えられた制約はｒｊ−ｒｉ≧ｅｉ）。
-ＧｅｔＢｅｓｔＳｏｌｕｔｉｏｎ（Ｄ’，Ｄ’’）は、２つのＤＢＭゾーンを受け取り、最良のタイミング、例えば、すべてのジョブシーケンスの完了時間全体を最小化するタイミングを含む方を選択する。
【００４６】
上述の例は、各ペアのジョブの各相互排他制約のための定量のペア間の選択に基づくため、グラフ理論的構造はバイナリツリーとなる。当業者は、他の実施態様が可能であることを理解するであろう。例えば、アルゴリズムが、競合するジョブ間の最小スラック遅延を許容する定量集合の中から選択することができる（すなわち、ｒｉ−ｒｊ≧ｅｊ＋ｄｉｊの類の制約、ここで、ｄｉｊは、正の数量）場合、その結果生じる構造はｋ項ツリーとなる可能性があり、ｋは、各相互排他制約に関連した、起こりうるスラック遅延の数である。
【００４７】
アルゴリズムを整理することにより、以下に概説した性能に大きな影響を及ぼす、様々な、実行可能な最適化に余地がもたらされる。
【００４８】
（排他制約定量間のヒューリスティック選択）
Ｅｎｑｕｅｕｅ（＜Ｄ，ｃ＞）およびＤｅｑｕｅｕｅ（）の演算の実際の実施によっては、探索ツリー（すなわち、幅優先、深さ優先など）の訪問のために様々なポリシーを実行することができる。アルゴリズムの目的は、スケジューリング問題の解に関連するリーフを可能な限り早く発見することであるため、最も単純で自然な選択である、深さ優先訪問を採用した。そのため、列挙待ち行列Ｑは、後入先出（ＬＩＦＯ）待ち行列として実装される。
【００４９】
アルゴリズム動作は、ＤｒおよびＤｌが待ち行列に追加された順序（すなわち、アルゴリズム２の１４行目と２１行目の順番）によっても左右され、例えば、Ｄｌが常に最初に追加される場合、先行順訪問が行われ、反対に、Ｄｒを常に最初に追加することにより後行順訪問となる。本発明の場合、良好なヒューリスティックは、探索アルゴリズムに多大なオーバーヘッドを加えることなく、常に、許容解を導く可能性が最も高い選択を行う必要がある。本明細書では、緊密性と実行可能性の対立する意義によってアルゴリズム動作に影響する２つの単純なヒューリスティックを説明する。
-実行可能性は、実行不可能な制約に遭遇することなく、完了まで続く可能性が最も高い、疎らな構成をまず探索する特性を表す。直感的に、これは、得られる構成内の制約付きジョブＪｉおよびＪｊに、より大きな自由度を許し、すなわち、解放時間の間の間隔｜ｒｉ−ｒｊ｜が最大間隔（「安全」または「最長間隔」ヒューリスティックと呼ぶ）の範囲内であることが可能である排他制約を選択することにより達成することができる。
-緊密性特性は、より実行不可能な解に遭遇するリスクを負っても密集したスケジュールを得るという、正反対の目標を目指す。結果として、得られたヒューリスティック（「欲張りな」または「最短間隔」ヒューリスティックと呼んだ）は、ｒｉとｒｊの間の間隔を最も狭める制約を選択する。
【００５０】
（時間間隔解析による問題の単純化）
排他制約に与えられた順序は、スケジュールの完了につながらない定量の早期廃棄を調整するアルゴリズムの動作に影響を与える。さらに、いくつかの改善は、競合するジョブペアの数Ｃを低減することを目的とし、この種の最適化は、アルゴリズムの理論的複雑さに影響を与えないが、多くの実際の事例において、計算時間を大幅に減少させることができる。排他制約をアルゴリズムの各工程に追加する必要がある選択は、Ｄｐｒｅｃの制約によりすでに解決されている場合がある。例えば、同じリソースを必要とする２つのイベントがシーケンス中に発生するよう明確に制約されている場合、排他制約は不必要であり、無視することができる。特定の用途では、これにより、ジョブが当然線形のシーケンスに沿って構成されたシステム動作を表す場合の大幅な時間短縮を決定づける。明確に制約されていなくとも、遅延構成により確実にオーバーラップされないイベントペアを想定して、より僅かではあるが、非常に有効な短縮を達成することができる。このような条件の最も単純な例は、ＪｉおよびＪｋの両方がＪｊの完了後に開始するよう制約され、かつｄｉｊ＋＋ｅｉ＜ｄｋｊ−となるような３つのジョブＪｉ、ＪｊおよびＪｋで構成される。これらの３つの条件を満たすことにより、実際、ＪｉおよびＪｋが、その間に明確な制約が存在しない場合でもオーバーラップしないことが保証される。インタラクションは、より複雑となりえ、識別により労力を必要としうる。さらに、探索手続中に反復して制約が追加されるため、初期のＤｐｒｅｃゾーンで検証されない場合でも、同様の条件がＤｒおよびＤｌゾーンの構築中に動的に生じてしまう可能性がある（アルゴリズム２の８行目および１５行目）。しかし、待ち行列（アルゴリズム２の７行目）から抽出されたゾーンＤの正規形を直接観察することにより、このような条件を簡単に検出することができる。さらに、これを早期の競合検出を可能にする探索アルゴリズムの最適化に変換し、ゾーンＤｒおよびＤｌの不要な構築および正規化を防止する。
【００５１】
（ウオームリスタートフロイド−ワーシャルアルゴリズムによる複雑さの低減）
第２の最適化によって、手続の漸近的時間複雑性を低減させ、そのコアエンジンであるフロイド−ワーシャルアルゴリズムの構造に作用するようにする。
【００５２】
ＤＢＭの正規形（アルゴリズム１）の発見に用いられるフロイド−ワーシャルアルゴリズムの標準的な定式化は、ゾーンの次元数（本発明の事例では、ジョブの数）に関して、時間Ｏ（Ｎ３）で行われる。ただし、アルゴリズム２の９行目および１６行目で実行される正規化は、特定のアルゴリズムを改善することが可能である特徴を示す。実際、工程７で待ち行列から抽出された、正規形のゾーンＤに単一の制約を加えてゾーンＤｒおよびＤｌを得ることができる。これは、ＤｒおよびＤｌの係数の一部のみが正規化の影響を受けることを意味する。したがって、フロイド−ワーシャルアルゴリズムは、時間Ｏ（Ｎ２）で実行されるように書き換えることができる（アルゴリズム３参照）。
【００５３】
（アルゴリズム３）最適化されたフロイド−ワーシャル
【００５４】
【表３】
2015510107.tif 000011
【００５５】
（イベント縮約による問題の単純化）
問題が、即時遅延を有するジョブ、すなわち次々と即座に実行されるよう制約されるジョブを含む場合、第３の最適化を導入してＤＢＭマトリックスＮのサイズを縮小する。２つのＪｉとＪｊの間で優先順位制約がｄｉｊ＝ｄｉｊ＋＝ｄｉｊ−＝０となるように設定された場合であって、その場合のみ起こりうることである。
【００５６】
この場合、ジョブＪｉおよびＪｊをマージして解放時間ｒｉｊ＝ｒｊ、実行時間ｅｉｊ＝ｅｉ＋ｅｊの単一のジョブＪｉｊとすることができる。その結果、１行分および１列分縮小されたＤＢＭマトリックスが得られる。
【００５７】
（低レベルコード最適化）
アルゴリズム２の探索アルゴリズムのコアは、ちょうど数十行のコードになる。製品バージョンをターゲットプラットフォームに正常に導入させるために、軽量ＡＮＳＩ−Ｃライブラリを実装し、入出力管理、実行時間制御および異なるヒューリスティック間のオンライン切り替えのような補助機能を合計約２６００行のコードに割り当てた。ハードウェアの制限が厳しいため、アルゴリズムの改善に加えて、いくつかのコード最適化を採用して空間および時間の消費をさらに低減するようにした。その中で最も重要なものは、中間解を実際に符号化することに関する。アルゴリズム２の疑似コードでは、中間解Ｄが生成されると、待ち行列を用いてこれをスプールする。これは、探索アルゴリズムでは標準的な手法であるが、本発明の事例では、使用可能なメモリを簡単に飽和させてしまう。別の解法として、実装アルゴリズムは、それまで選択された排他制約のコンパクト表現を符号化するためのスタックを用いて、初期ゾーンＤｐｒｅｃおよび実際の中間ゾーンＤのみを完全に記憶する。ロールバックが必要とされるたびに、アルゴリズムは、発見された情報によるＤｐｒｅｃから新たな解をスタック内に再構築する。この場合、複数の係数が修正されるため、完全正規化（すなわち、アルゴリズム１の正規化）が必要とされるが、この小規模なオーバーヘッドの大部分は空間占有率の大幅な低減により正当化される。
【００５８】
図５は、本発明の好適な実施形態による解法の略図である。探索は、排他制約に対して一連の連続する二分決定を行うツリー走査として定式化される。探索アルゴリズムは、許容解を生じるゾーンを発見するとともに、このような解の中から最適解に対応する解を選択することを目的とする。本方法の重要な特徴は、すべてのありうる場合を探索することなく解を見つけ出せるように、所定の評価基準にしたがって「リーズナブル」な経路のヒューリスティック選択をすることができることである。本例では、「欲張りな」（すなわち最短間隔ヒューリスティック）および「安全な」（すなわち最短間隔ヒューリスティック）の、２つのありうるヒューリスティックを考えた。×印は、ツリー内の、実行可能解が見つからないノードを示すため、このようなノードから出発するすべてのノードおよび葉は、さらに計算せずに廃棄することができる。
【００５９】
上述の問題の単純化は、複雑さを減じることにより計算の高速化をもたらす結果となった。特に、時間間隔解析により、独立した制約の数が最小になり、ウォームリスタートにより、コアとなるＯ（Ｎ３）〜Ｏ（Ｎ２）の工程の複雑性が低減されるとともに、イベント集約により、変数の数が減少する。
【００６０】
図６表ＡおよびＢは、動作試験を示し、「欲張りな」ヒューリスティックおよび「安全な」ヒューリスティックをそれぞれ適用する２つの異なる実施態様を用いた本方法を比較している。
【００６１】
実験結果は、デスクトップコンピュータ（デュアルコア、２ＧＨｚのプロセッサ）で測定した。これは、本アルゴリズムが実行されるところの電気機械機器上の実環境よりもおよそ１０倍速いと考えられる（すなわち、ターゲットプラットフォーム上での実行は、デスクトップコンピュータ上での同様の実行の約１０倍を超える時間がかかりうる）。
【００６２】
本発明の探索アルゴリズムを、実在の生物学的分析手法から取られた現実的な例である、以下の３つの分析プロトコル（ＡＰ１−ＡＰ３）からなるテストスイートに対し実行した。
（ＡＰ１）２つのセクション、スロット毎に１〜３回の分注器動作、セクション毎に４回の読み取りヘッド動作、非決定性遅延
（ＡＰ２）２つのセクション、スロット毎に１〜３回の分注器動作、セクション毎に４回の読み取りヘッド動作、非決定性遅延
（ＡＰ３）２つのセクション、スロット毎に１回の分注器動作、セクション毎に４回の読み取りヘッド動作、非決定性遅延
【００６３】
実験は、最短間隔ヒューリスティックおよび最長間隔ヒューリスティックの両方を採用して実行される探索アルゴリズムに、提示した改善を漸次加えることにより行った。結果は、それぞれ図６の表ＡおよびＢに示す。特に注目すべき点は、モデル検査手法に必要とされる２０分の計算と比較してどうかということである。予想されるとおり、アルゴリズムを連続的に改善することにより、より良い結果が得られた。特に、探索ツリーの深さが深いほど、時間間隔解析で行われる刈り込みおよびフロイド−ワーシャルアルゴリズムの高速化に大きな関連性が見られた。最長間隔ヒューリスティックと最短間隔ヒューリスティックの比較から、もう１つの興味深い結果が得られた。現実的な試験事例では、完全探索の実施および最適解への収束の両方について、後者の方で、前者よりもより良い動作が見られた（選択された事例では、最短間隔ヒューリスティックは、常に最初の解として最適解を発見する）。
【００６４】
調査された各生物学的プロトコル（ＡＰ１−ＡＰ３）および各最適化レベル（Ｂａｓｉｃ，ＴＩＡ，ＴＩＡ＋ＷＲ，ＴＩＡ＋ＷＲ＋ＥＡ）については、性能はｆｉｒｓｔ／ｂｅｓｔ／ｔｏｔａｌの３つで特徴付けられ、ｆｉｒｓｔは最初の解が発見される時間、ｂｅｓｔは最適解が発見される時間、ｔｏｔａｌは合計実行時間である。ＴＩＡは時間間隔解析（Ｔｉｍｅ  Ｉｎｔｅｒｖａｌ  Ａｎａｌｙｓｉｓ）の頭字語、ＷＲはウォームリスタート（Ｗａｒｍ  Ｒｅｓｔａｒｔ）の頭字語、ＥＡはイベント集約（Ｅｖｅｎｔ  Ａｇｇｒｅｇａｔｉｏｎ）の頭字語である。最後の２列で、発見された最初の解および最適解の期間も説明する。
【００６５】
本開示の範囲から逸脱することなく上記に変更および改良を加えてもよいことが理解されるだろう。当然ながら、局部的かつ特殊な要件を満たすために、当業者は上述の解決法に多くの改良および変更を加えてもよい。特に、本開示を好適な実施形態を参照して特定の程度の詳細さで説明してきたが、形式および詳細における様々な省略、置き換えおよび変更や他の実施形態も実施可能であることを理解されたい。さらに、本開示の任意の開示された実施形態と関連して記載された特定の要素を、設計上の一般事項として別のいずれかの実施形態に採用してもよいことが特に意図される。
【００６６】
例えば、構成要素が異なる構造または同等の装置を有する場合、同様の留意事項が適用される。また、当業者であれば、本発明を拡張してもよいことは容易に理解するであろう。
【図３ａ】
2015510107.tif 000014
【図３ｂ】
2015510107.tif 000015
【図４ａ】
2015510107.tif 000016
【図４ｂ】
2015510107.tif 000017
【図４ｃ】
2015510107.tif 000018
【図５】
2015510107.tif 000019
【図１】
2015510107.tif 000020
【図２】
2015510107.tif 000021
【図６】
2015510107.tif 000022
【国際調査報告】
2015510107.tif 000023
2015510107.tif 000024