JP7440964B2 - 決定論的論理を用いた遺伝的アルゴリズム - Google Patents

Description

本願は、２０１９年１０月９日に出願された米国特許出願第１６／５９７，１５５に対する優先権の利益を主張し、参照によりその全体が本明細書に組み込まれる。
発明の分野
本発明の分野は、スケジューリングシステムである。

企業が複数のタスクを実行するために利用できる一連のリソースを有している場合、管理者は通常、１つ又は複数のタスクを実行するために用いられるリソース（例えば、従業員、製造設備等）を決定する。例えば、Ｍｉｃｒｏｓｏｆｔ Ｏｕｔｌｏｏｋ（登録商標）などのコンピュータスケジューリングシステムは、このようなリソースの可用性を視覚化するのに役立ち得る。例えば、スケジューラは、コンピュータスケジューリングシステムを使用して、特定の複数のタスクを実行するために特定の複数のリソースをブロックし（block off）、特定の複数のリソースを特定の複数のタスクに割り当てることができる。各従業員は、日、週、月ごとに実行するタスクのカレンダーを有し、容易に視覚化および整理することができる。しかしながら、スケジューラが特定の複数の従業員を各タスクに割り当てるには、管理者が各リソースを手動で追跡し、各リソースを適切なタスクに割り当てる必要がある。

スケジューラは、どのように複数のリソースをスケジューリングして割り当てるかを決定するだけでなく、リソース割り当ての効率を最大化するために各リソースの特性を判定する必要がある。例えば、スケジューラは、前のタスクと次のタスクとの間に最大間隔がある複数のリソースを特定することにより、事前にスケジューリングされたジョブ間の特定の複数のタスクに特定のリソースの使用をスケジューリングすることができ、これにより、追加の複数のタスクをリソーススケジュールに組み込むことができる。各タスクは、システムの全体的な効率を高めるために、リソースの１つまたは複数の特性に基づいて複数のリソースに割り当てられる。しかし、特定のリソース割り当てとリソース優先順位の組み合わせの数は、多くの場合、人間が効率を最大化するためにすべての組み合わせをテストするには多すぎる。さらに、多数の組み合わせにより、タスクを完了するのに十分なタスク割り当てとタスク優先順位の複数の可能性のある組み合わせが生成される可能性がある。最後に、リソースの複数の特性に基づいて複数のタスクに複数のリソースを割り当てるステップは、システムに人間の判断／人為的エラーを導入するため、望ましくない変数を追加する。

遺伝的アルゴリズムは、人間または実際には他のルーティンよりも大きな探索空間を探索して、最大限に効率的なリソース割り当てスケジュールを見つけることができる。しかし、純粋な遺伝的アルゴリズムは、複数のゲノム（例えば、複数のリソース割り当てスケジュール）をランダムに作成、組み換え、および突然変異させて、組み換えおよび／または突然変異のためにより一層効率的なゲノムを見つけようとするため、遺伝的アルゴリズムは、最適なリソース割り当てスケジュールを見つけるのにかなりの時間を要する。さらに、従来の遺伝的アルゴリズムは、組み換えが行われると、ゲノムの集合内の遺伝的多様性の喪失と密接に関連する局所最小値に早期に収束するゲノムを生成する可能性がある。したがって、従来の遺伝的アルゴリズムは、最適解に到達するためにかなりのリソースを必要とし、局所最小値への早期収束のために、最適解を見つけることをさらに妨げる可能性がある。

従来技術は、従来の遺伝的アルゴリズムにおける局所最小値への収束の問題を認識し、それが発生した後に問題を修正しようと試みる。従来技術には、局所最小値への早期収束の問題がそもそも発生するのを防ぐために、決定論的論理を遺伝的アルゴリズムに適用するための教示、提案、または動機付けが存在しいように思われる。

Ｓｙｓｗｅｒｄａの特許文献１は、ハードおよびソフトタスク制約に基づいて１つまたは複数の遺伝的アルゴリズムでタスク割り当てを管理するためのコンピュータ実装方法を教示している。ただし、特許文献１は、リソースの代わりに、タスクに関連付けられたハード制約とソフト制約を使用する方法を開示している。このように、特許文献１は最適解に収束するためにかなりのリソースを必要とするが、それは各タスクに関連付けられた複数の変数が、最適解に到達する際に考慮されなければならず、遺伝的アルゴリズムに基づくシステムおよび従来のシステムにおいてリソースの数をはるかに超えているからである。しかし、タスクベースのゲノムの誘導進化（guided evolution）が、複数のリソースに限定された探索空間と比較して非常に大きな探索空間と関連付けられるため、特許文献１は、遺伝的アルゴリズムの非効率性を完全には対処していない。

Ｇａｂｒｉｎｅｒの特許文献２は、スケジューリングシステムを管理するコンピュータシステムを教示し、このシステムは、タスク制約をリソース能力と照合して、タスクを完了できるか否かを判定する。次に、システムは、タスクを実行するために、利用可能な複数のリソースをタスクと照合する。しかし、特許文献２のコンピュータシステムは、遺伝的アルゴリズムを使用してスケジュールを決定する際に、複数のリソース制約に焦点を当てていない。特許文献２は、決定論的論理を使用しない従来の遺伝的アルゴリズムについて説明する。

特許文献１，２および本明細書で説明する他のすべての外因性の資料は、個々の外因性の資料が参照により組み込まれることが特定的におよび個別に示されている場合と同程度に参照により組み込まれる。組み込まれた参照文献における用語の定義または使用が一貫していないか、または本明細書で提供されているその用語の定義に反している場合、本明細書で提供されているその用語の定義が適用され、参照文献におけるその用語の定義は適用されない。

したがって、遺伝的アルゴリズムが局所最小値に早期に収束するのを防ぐために、決定論的論理フレームワークで強化された遺伝的アルゴリズムが依然として必要である。

米国特許第５３１９７８１号明細書 米国特許第５８４８４０３号明細書

リソース指向コンピュータシステム（resource-orientated computer system）は、決定論的論理フレームワーク（deterministic logical framework）を使用して複数のリソースの属性に焦点を当て、ゲノム（genome）が早期に局所最小値（local minima）に収束することなく、最適解（optimized solution）に収束することにより、複数のリソース制約（例えば、人、設備、ツール、部屋、バーチャルルーム、コンピュータなど）に基づいて複数のタスクの日時を決定する（calendar）スケジュールを可能にする。本発明の主題の別の態様は、遺伝的アルゴリズムが早期に局所最小値に収束するのを防ぐことさえ可能であるという認識（自己生成されるか又は別のものから情報を受信することによる）である。

遺伝的アルゴリズムが局所最小値に早期に収束するのを防ぐシステム及び方法に焦点を当てることにより、現在特許請求の範囲に記載された主題は一般的でなく、ルーティンではないと考えられる。

本明細書において使用される場合、早期収束は、最適化問題のための遺伝子の親集合が、閾値遺伝的多様性（threshold genetic diversity）を下回ることを意味し、その結果、親遺伝子を上回ることができない子孫遺伝子が生じる。

とりわけ、本発明の主題は、遺伝的アルゴリズムが複数のタスクスケジュールを複数のリソース属性を用いて組み換えして（recombine）突然変異させ（mutate）、効率の悪いスケジュールに早期に収束させるのではなく、最適解に到達する際のシステムの全体的な効率を高めるために決定論的論理フレームワークを適用する装置、システム、および方法を提供する。本明細書において使用される場合、「リソース」は、物理的又は仮想的、生きているか又は生きていないかにかかわらず、任意のリソースである。複数の例は、部屋、建物、消耗品、携帯用工具、場所に固定されている機器、人、または動物などを含む。各リソースは、典型的には、リソースに関連付けられた一連の固有の属性および非固有の属性を含む。用語が示すように、固有の属性はその特定のリソースに固有の属性であり、非固有の属性は複数のリソースに共通の属性である。例えば、リソースが特定の複数の時間にのみ利用可能である場合（例えば、個人または可用性が制限されているマシン）、リソースの毎週の可用性はリソースの属性である。本明細書において使用される「複数のジョブ（jobs）」は、全体的な目的を達成するために必要とされる１つまたは複数のタスクの複数のサブセットを指す。

本発明の主題の種々のリソース、特徴、態様、および利点は、同様の参照番号が同様の構成要素を表す添付の図面とともに、以下の好適な実施形態の詳細な説明からより明らかになり得る。

本発明は、決定論的論理を適用することにより、遺伝的アルゴリズムが局所最小値に早期に収束するのを有利に防止する。

図１は、リソースゲノムを作成する際に、決定論的論理フレームワークを選択してリソース選択に適用するための方法の概略図である。 図２は、選択された決定論的論理フレームワークに基づいてリソースを選択するための方法の概略図である。

以下の説明は、コンピュータベースのスケジューリングシステムを対象としているが、様々な代替構成もまた適切であると考えられ、サーバ、インタフェース、システム、データベース、エンジン、コントローラ、または個別にまたは集合的に動作する他のタイプのコンピューティングデバイスを含む様々なコンピューティングデバイスを用いることができることに留意されたい。コンピューティングデバイスは、有形の非一時的なコンピュータ可読記憶媒体（例えば、ハードドライブ、ソリッドステートドライブ、ＲＡＭ、フラッシュ、ＲＯＭなど）に記憶されたソフトウェア命令を実行するように構成されたプロセッサを含むことを理解すべきである。ソフトウェア命令は、好ましくは、開示する装置に関して以下で説明されるような役割、責任、または他の機能を提供するようにコンピューティングデバイスを設定する。特に好ましい実施形態では、種々のサーバ、システム、データベース、またはインタフェースは、標準化されたプロトコルまたはアルゴリズムを使用して、ＨＴＴＰ、ＨＴＴＰＳ、ＡＥＳ、公開鍵－秘密鍵交換、ウェブサービスＡＰＩ、既知の金融取引プロトコル、またはその他の電子情報交換方法などに基づいてデータを交換する。データ交換は、パケット交換ネットワーク、インターネット、ＬＡＮ、ＷＡＮ、ＶＰＮ、またはその他の種類のパケット交換ネットワークで実行することが好ましい。

開示された技術は、複数のイベントのスケジューリングを可能にすること、１つまたは複数の商品の効率的な製造を可能にすること、および当該技術分野で知られている遺伝的アルゴリズムの他の任意の応用を含む多くの有利な技術的効果を提供することを理解すべきである。

以下の説明は、本発明の主題の多くの例示的な実施形態を提供する。各実施形態は本発明の要素の単一の組み合わせを表すが、本発明の主題は、開示された要素のすべての可能な組み合わせを含むと見なされる。従って、１つの実施形態が要素Ａ，Ｂ，Ｃを含み、第２の実施形態が要素Ｂ，Ｄを含む場合、本発明の主題は、明示的に開示されていなくても、Ａ，Ｂ，Ｃ，Ｄの他の残りの組み合わせも含むとみなされる。

図１は、リソースゲノム（resource genome）を作成する際に、決定論的論理フレームワークを選択してリソース選択に適用するための方法の概略図である。
論理エンジン１００は、目的（objective）に関連付けられた１つまたは複数のリソースを特定する（ステップ１０２）。

本明細書において定義されるように、目的とは、１つまたは複数のリソースを用いて１つまたは複数のタスクを実行することによって達成可能な任意の最終目標を指す。タスクとは、ジョブや商品の製造などの目的を達成するために必要なアクションである。目的は、複数のタスクを備えることができる。例えば、ウィジェットの作成をスケジューリングする場合、各目的はウィジェットのサブコンポーネントの作成に関連付けられ、ウィジェットの複数のサブコンポーネントの作成はそれぞれ複数のタスクを備える。

論理エンジン１００は、目的に関連付けられたリソースの１つまたは複数のプリコンパイルされたリストを用いる。別の実施形態では、論理エンジン１００は、複数のリソースおよび全体的な目的に関連付けられた少なくとも１つの変数に基づいて、利用可能な複数のリソースから１つまたは複数のリソースを決定する。例えば、論理エンジン１００は、ウィジェット内の複数の構成部品およびウィジェットの各コンポートネントを作成するために必要な複数の作成リソースに基づいて、全体的な目的を達成するために必要な複数のリソースを決定することができる。

代替的には、論理エンジン１００は、機械学習技術を使用して複数の履歴傾向を分析し、全体的な目的を達成するために必要である利用可能な複数のリソースを予測する。例えば、論理エンジン１００は、教師あり学習分類器（supervised learning classifier）を使用して、ラベル付けされたトレーニングデータ（例えば、トレーニング例のセット）から関数を推測することができる。別の例では、論理エンジン１００は、時系列予測を使用して、１つまたは複数のリソースによる複数のタスクの同時実行を最大化することを決定し、全体的な目的を達成するための時間を最小化する。論理エンジン１００は、当該技術分野において知られている任意の技術を使用して、全体的な目的に関連付けられた１つまたは複数のジョブを特定することができることが企画される。

論理エンジン１００は、完了すべきタスクの集合を特定する（ステップ１０４）。
複数のタスクは、ジョブを完了するために必要な任意のアクションを含む。例えば、論理エンジン１００は、自動車モータの製造を完了するために品質制御ステップが必要であることを特定し、未処理の電力出力をチェックし、ダイナモメータを用いて適切な複数のパワーバンドを確認し、複数のシリンダ内の正確な圧縮レベルを検証すること等の品質制御ステップに関連付けられたタスクの集合を生成することができる。

論理エンジン１００は、リソースゲノムに適用するために、目的に基づいて決定論的論理フレームワークを選択する（ステップ１０６）。
決定論的論理フレームワークは、目的に関連付けられた１つまたは複数の全体的優先順位などのタスクの実行をガイドする任意の論理を備えることができる。

例えば、決定論的論理フレームワークは、（１）時間枠内での最大リソース使用率（most resource utilization）、（２）時間枠内での最小リソース使用率（least resource utilization）、（３）リソースについての前のタスクの完了から次のタスクの開始までの最短時間間隔、（４）リソースについての前のタスクの完了から次のタスクの開始までの最長時間間隔、（５）ジョブでのリソースの再利用、（６）ジョブでのリソースの除外、（７）タスクを実行するためのリソースコスト、（８）タスクを実行する際のリソース効率、および（９）目的を達成するためのタスク進行における第１のリソースの第２のリソースへの近接性（proximity）のうちの１つ以上を含み得る。

しかしながら、企図される主題は、前述の決定論的論理フレームワークに限定されず、個別にまたは組み合わせて、当該技術分野で知られている任意の決定論的論理フレームワークを含むことができる。複数のリソースは、目的を達成するためのタスクを完了するために使用されるすべてのものを含み得る。たとえば、複数のリソースは、人、機械、ツール、消耗品、ソフトウェア、および消耗リソースを含み得るが、これらに限定されない。

一実施形態では、論理エンジン１００は、ユーザが選択した複数の目的に基づいて決定論的論理フレームワークを選択する。例えば、ユーザは、例えば、出荷のための発泡充填剤の製造等の高い精度を必要としない製造タスクにおいて、精度よりも速度を優先させることができる。この例では、論理エンジン１００は、複数の製造タスクを迅速に実行することができる複数のリソースの選択を導くために、前のタスクの完了と次のタスクの開始との間の最短時間間隔の決定論的論理フレームワークを選択して使用することができる。

代替の実施形態では、論理エンジン１００は、全体的な目的に関連付けられた１つまたは複数のパラメータに基づいて、適用する決定論的論理フレームワークを自動的に決定する。例えば、論理エンジン１００は、例えば、特殊な医療装置の製造等の高レベルの精度および製造失敗率の最小化を必要とする製造目的に基づく製造時間枠内の最小使用率に基づいて複数のリソースを選択する決定論的論理フレームワークを適用することができる。

決定論的論理を複数のリソースゲノムに適用することにより、リソーススケジューリング探索空間は、局所最小値に早期に収束する可能性がある純粋な遺伝的アルゴリズムよりも、有利に完全に探索されることができる。さらに、決定論的論理を適用することは、有利には、論理エンジン１００が関連する複数の優先順位に焦点を合わせることを可能にすることによって、より一層良い複数のリソーススケジュールを見つける際にかなりの時間を節約する。例えば、論理エンジン１００は、高精度を必要としない単純な製造用途において低い製造失敗率を優先する複数のリソースゲノムを探索する必要なしに、生産速度を最大化する複数のリソースを対象とすることができる。

論理エンジン１００は、決定論的論理を用いて１つまたは複数のリソースを選択する（ステップ１０８）。一実施形態では、決定論的論理が、前のタスクの完了から次のタスクの開始までの時間を最小化することを優先する場合、論理エンジン１００は、製造順序に基づいて、互いに最も近接しているリソースのグループを選択する。これにより、論理エンジン１００は、第１の製造プロセスを完了する第１のリソースから次の製造プロセスを開始する第２のリソースへの製造中間体（manufacturing intermediates）の移動時間（movement time）を短縮することによって効率を高める複数のリソースをコンパイルする（completing）ことができる。

さらに別の実施形態では、決定論的論理が、前のタスクの完了から次のタスクの開始までの時間を最大化にすることを優先する場合、論理エンジン１００は、リソース間の製造中間体の移動時間を増大させるために、相互間の距離が必要以上に長いリソースのグループを選択する。例えば、製造用途において、論理エンジン１００は、（例えば、コンクリート、接着剤などの）硬化するために最小時間を必要とする複数のリソース中間体が次の製造ステップの前に完全にセットされることを可能にするのに互いに十分に遠く離れている複数のリソースを選択することができる。

論理エンジン１００は、複数の全体的なサービス目的に適用される決定論的論理に基づいて複数のリソースを選択できることも企図されている。例えば、論理エンジン１００は、利用可能な最低失敗率に基づいて複数のリソースを選択する決定論的論理を適用することにより、最高成功率での高リスク手術のために、複数のリソースと見なされる複数の医療専門家を選択することができる。この例では、本発明の主題は、特定の分野では直観に反する（counter-intuitive）かもしれないが、他の分野では価値のある戦略に適合するように調整されることができる。

論理エンジン１００は、選択された１つまたは複数のリソースをリソースゲノムにコンパイルする（compiles）（ステップ１１０）。
リソースゲノムは、論理エンジン１００によって適用される決定論的論理フレームワークに基づいてリソーススケジュールを定義する。論理エンジン１００は、特定の複数の決定論的論理フレームワークに影響されない特定の複数のリソースを指定することができ、それによって、それらを特定の複数の決定論的論理フレームワークに基づいて選択された複数のリソースを制限する任意のリソースゲノムに組み込むことができる。例えば、論理エンジン１００は、（アイテム（item）の寸法に関係なく、完了するのに同じ時間を必要とし、同時に複数のリソースゲノムについて複数の電気めっき工程を実行することができる）電気めっき工程を完了するリソースを、前のタスクの完了から次のタスクまでの時間の影響を受けないリソースとして指定することができる。

いくつかの実施形態では、論理エンジン１００は、複数の決定論的論理フレームワークをリソースのリストに適用して、複数のリソースを選択してリソースゲノムにコンパイルする。好ましい実施形態では、論理エンジン１００は、特定の決定論的論理フレームワークをリソースのリストに適用して、複数のリソースを選択してリソースゲノムにコンパイルする。そのような実施形態では、異なる決定論的論理フレームワークに基づいて選択された異なるリソースゲノムは、当該技術分野で知られている任意の方法で突然変異、組み換え、および／または操作され得ることが企図される。複数の決定論的論理フレームワークに基づいてコンパイルされた複数のリソースゲノムは、当該技術分野で知られている任意の方法で突然変異、組み換え、および／または操作され得ることも企図されている。一例では、論理エンジン１００は、高速および高精度のバランスのとれたリソースゲノムを生成することを試みるために、最小の製造時間を優先する製造プロセスの第１のリソースゲノムを、最低のリソース不良率を優先する第２のリソースゲノムと組み換えすることを選択できる。

論理エンジン１００は、タスク集合からのタスクを、選択されたリソースに割り当てる（ステップ１１２）。
論理エンジン１００は、完全に自動化されたシステムにおいて直接的に実行するために各タスクを割り当てることが企図されている。例えば、論理エンジン１００は、複数のプログラム命令を送信して、複数の製造リソース（例えば、複数の自動製造ロボット）に各タスクを実行させることができる。論理エンジン１００は、１人または複数の個人に各タスクを実行させるように指示することも企図される。例えば、論理エンジン１００は、論理エンジン１００によって指定された方法で自動車エンジンブロックの製造に関連付けられた各タスクを実行するように複数の工作機械オペレータに指示することができる。しかしながら、論理エンジン１００は、純粋に自動化されたシステムまたは純粋なユーザーベースのシステムに限定されず、任意の手段または利用可能な複数の手段の組み合わせによって各タスクを実行させることができる。

論理エンジン１００は、タスクを実行するために、選択されたリソースに複数の命令を送信する（ステップ１１４）。
論理エンジン１００は、選択されたリソースに直接的に複数の命令を送信できることが企図されている。いくつかの実施形態では、選択されたリソースに送信された複数の命令が、自動的に実行される。例えば、製造リソースは、論理エンジン１００から受信した複数の命令に基づいて製造プロセスを自動的に開始することができる。他の実施形態では、論理エンジン１００は、複数の命令のパラメータ内でタスクの完了を独立して開始することができる選択されたリソースに複数の命令を送信することができる。例えば、製造リソースは、論理エンジン１００から複数の命令を受信して、製造プロセスを開始し、指定された時間枠内にそのプロセスを完了することができる。製造リソースは、複数の命令のパラメータ内で、後で製造プロセスを開始することができる（例えば、工程５の後に製造工程を開始する、又は午前８時から午前１０時までの間に製造プロセスを開始して完了する）。別の例では、自動車整備士は、論理エンジン１００から、その日の午後１２時前に特定の車両のタイヤのローテーションを完了するように複数の命令を受け取ることができる。その後、自動車整備士は、その日の午後１２時までにいつでもそのサービスを完了することを選択できる。

論理エンジン１００は、リソースゲノムの値スコアを決定する（ステップ１１６）。
値スコアは、完了時間、プロセスの精度、製造コストなど、１つ又は複数のメトリック（metric）を達成する際のゲノムの全体的な成功を示す。論理エンジン１００は、好ましくは、適応度関数（fitness function）を用いてリソースゲノムの値スコアを決定する。適応度関数は、特定のタイプの目的関数であり、特定の解が設定された目的をどれだけ達成しているかを単一の性能指数として示すために使用される。論理エンジン１００がリソースゲノムの値スコアを決定すると、リソースゲノムを破棄、突然変異、または他のリソースゲノムと組み換えすることができる。

図２は、選択された決定論的論理フレームワークに基づいて複数のリソースを選択するための方法の概略図である。
論理エンジン１００は、所望のリソースゲノムの目的を特定する（ステップ２０２）。

たとえば、ウィジェットの作成をスケジューリングする場合、リソースゲノムは、ウィジェットの作成に関連付けられたすべての利用可能なリソースを含み得る。複数のリソースは、タスクを実行するために使用される任意のエンティティを含み得る。例えば、リソースは、人間のサービス、製造装置、ソフトウェア、消耗品、消耗サービス（consumable service）、またはその他のリソースを含むが、これらに限定されない。リソースゲノムは、全体的な目的に関連付けられた１つ又は複数のタスクの完了に用いられる複数のリソースのコンパイル（compilation）を含む。

論理エンジン１００は、全体的な目的に関連付けられた１つまたは複数の所定のタスクリストを用いて、どの複数のリソースが全体的な目的に関連付けられているかを特定する。代替的には、論理エンジン２００は、機械学習技術を用いて複数の履歴傾向を分析し、全体的な目的を達成するために必要な複数のジョブを予測する。例えば、論理エンジン１００は、教師あり学習分類器を使用して、ラベル付けされたトレーニングデータ（例えば、トレーニング例のセット）から関数を推測することができる。別の例では、論理エンジン２００は、時系列予測を使用して、複数のジョブの同時実行を最大化することを決定し、全体的な目的を達成するための時間を最小化する。論理エンジン１００は、当該技術分野において知られている任意の技術を使用して、全体的な目的に関連付けられた１つまたは複数のジョブを特定することができることが企画される。

論理エンジン１００は、目的を分析して、適用する決定論的論理フレームワークを選択する（ステップ２０４）。
複数のタスクは、ジョブを完了するために必要な任意のアクションを含む。例えば、論理エンジン２００は、自動車モータの製造を完了させるために品質制御ステップが必要であることを特定し、未処理の電力出力をチェックし、ダイナモメータを用いて適切な複数のパワーバンドを確認し、複数のシリンダ内の正確な圧縮レベルを検証すること等の品質制御ステップに関連付けられたタスクの集合を生成することができる。

論理エンジン１００は、目的に関連付けられた１つまたは複数のリソースを特定する（ステップ２０６）。
論理エンジン１００は、目的に関連付けられたリソースの１つまたは複数のプリコンパイルされたリストを用いる。別の実施形態では、論理エンジン１００は、複数のリソースおよび全体的な目的に関連付けられた少なくとも１つの変数に基づいて、利用可能な複数のリソースから１つまたは複数のリソースを特定する。例えば、論理エンジン１００は、ウィジェット内の複数の構成部品およびウィジェットの各コンポートネントを作成するために必要な複数の作成リソースに基づいて、全体的な目的を達成するために必要な複数のリソースを特定することができる。

代替的には、論理エンジン１００は、機械学習技術を使用して複数の履歴傾向を分析し、全体的な目的を達成するために必要である利用可能な複数のリソースを予測する。例えば、論理エンジン１００は、教師あり学習分類器を使用して、ラベル付けされたトレーニングデータ（例えば、トレーニング例のセット）から関数を推測することができる。別の例では、論理エンジン１００は、時系列予測を使用して、全体的な目的を達成するための時間を最小化するために、どのリソースを同時に実行できるかを決定する。論理エンジン１００は、当該技術分野において知られている任意の技術を使用して、全体的な目的に関連付けられた１つまたは複数のリソースを特定することができることが企画されている。

論理エンジン１００は、複数のリソースおよび各リソースに関連付けられた複数の変数を分析する（ステップ２０８）。
論理エンジン１００は、指定された目的を達成するリソースゲノムをコンパイルするために、各リソースに関連付けられた１つまたは複数の変数を分析することが企図されている。

複数の変数は、リソースに関する任意の特性または特性の集合を含み得る。製造プロセスでは、複数の変数は、平均完了時間、成功率、失敗率、特定の時間枠内の最大使用率、特定の時間枠内の最小使用率、リソースによって完了できるタスクの種類、及び複数のタスクを同時に実行する能力を含み得るが、これらに限定されない。サービスの管理では、複数の変数は、平均完了時間、成功率、失敗率、特定の時間枠内の最大使用率、特定の時間枠内の最小使用率、リソースによって完了できるタスクの種類、複数のタスクを同時に実行する能力、専門的な資格、関連する経験の量、及びサービスプロバイダ（service provider）が利用できる期間を含み得る。

論理エンジン１００は、１つまたは複数の決定論的論理フレームワークから適用する決定論的論理フレームワークを選択する（ステップ２１０）。
例えば、論理エンジン１００は、全体的な目的を分析し、特定の時間枠内で最も完了したタスクを有する複数のリソースを選択する決定論的論理フレームワークを適用して、高い精度を必要としない製造タスクにおいて精度よりも速度を優先することができる。例えば、論理エンジン１００は、前述の決定論的論理フレームワークを、例えば、輸送用の発泡充填剤の製造等の粗製品を製造する製造プロセスに適用することができる。代替的な例では、論理エンジン１００は、複数の製造タスクを迅速に実行することができる複数のリソースの選択を導くために、前のタスクの完了と次のタスクの開始との間の最短時間間隔の決定論的論理フレームワークを選択して使用することができる。

代替の実施形態では、論理エンジン１００は、全体的な目的に関連付けられた１つまたは複数のパラメータに基づいて、適用する決定論的論理フレームワークを自動的に決定する。例えば、論理エンジン１００は、例えば特殊な医療装置の製造等の製造目的が高レベルの精度及び少量の生産を必要とする製造時間枠において、最小使用率に基づいて複数のリソースを選択することができる。

論理エンジン１００は、選択された決定論的論理フレームワークを、目的に関連付けられた１つまたは複数のリソースに適用する（ステップ２１２）。
論理エンジン１００は、有利には、全体的な目的に関連付けられたすべてのタスクを完了するために必要とされるリソースの集合の各リソースを選択する。しかしながら、論理エンジン１００はまた、複数のリソースの選択を導くために、論理エンジン１００のユーザ等の外部エンティティから特定の複数の命令を受け取ることができる。例えば、ユーザは、複数のリソースゲノムをコンパイルするときに、原材料を大量の使用可能な材料に精製することが可能なリソースなど、大きな制限なしに特定の複数のリソースを無視するように論理エンジン１００に指示することができる。

次に、論理エンジン１００は、１つまたは複数のリソースにタスクを実行するように指示する。論理エンジン１００は、例えば、特定の時間、特定の速度、および特定の順序など、特定の方法でタスクを実行するようにリソースに指示することができる。例えば、論理エンジン１００は、特定の順序で、且つ指定された時間枠内で自動車エンジンブロックの製造に関連付けられた各タスクを実行するように複数の工作機械オペレータに指示することができる。しかしながら、論理エンジン１００は、純粋に自動化されたシステムまたは純粋なユーザーベースのシステムに限定されず、任意の手段または利用可能な複数の手段の組み合わせによって任意のタスクを実行させることができる。

論理エンジン１００は、ゲノムの値スコアを決定する（ステップ２１４）。
値スコアは、完了時間、プロセスの精度、製造コストなど、１つ又は複数のメトリックを達成する際のリソースゲノムの全体的な成功を示す。論理エンジン１００は、好ましくは、適応度関数を用いてリソースゲノムの値スコアを決定する。適応度関数は、特定のタイプの目的関数であり、特定の解が設定された目的をどれだけ達成しているかを単一の性能指数として示すために使用される。論理エンジン１００がリソースゲノムの値スコアを決定すると、リソースゲノムを破棄、突然変異、または他のリソースゲノムと組み換えすることができる。

タスクスケジューリングの例
大きな病院の管理者は、最近心臓発作を起こした患者のために、開心術、具体的には大動脈弁置換術（つまり「タスク」）をスケジューリングする必要がある。この手術は、１名の心臓外科医と、１名の麻酔科医と、手術助手、機器監視助手、及び若手外科医を含む少なくとも３名の医療支援スタッフとを必要とする。この手術は、４時間の手術の間、医療チームの規模に対応でき、必要な機器、器具、消耗品（例えば、人弁ドナーまたは機械弁、輸血機、輸血に十分な血液量、心拍数モニター、除細動器、内視鏡ビデオカメラ、手術用ナイフおよび他の手術器具、消毒剤、ガーゼなど）を備えた手術室も必要とする。

管理者は、病院スタッフの最も効率的な割り当てを彼らの特性に基づいて見つけるために、本明細書において開示されている遺伝的アルゴリズムベースの方法およびシステムを使用することができる。管理者は、複数のジョブに関連付けられた全体的な目的を論理エンジン１００に入力する。管理者は、全体的な目的と全体的な目的に関する特定の複数の詳細に基づいて、決定論的論理フレームワークを指定する。管理者によって選択された決定論的論理フレームワークは、論理エンジン１００が、選択された決定論的論理フレームワークによって定義された複数のパラメータを最もよく達成する複数のリソースを選択することを可能にする。例えば、決定論的論理フレームワークが全体的な成功率を優先する場合、論理エンジン１００は、心臓胸部外科医および血管外科医について最高成功率を有するリソースを選択するが、用務員、外科助手、および若手外科医を、支援スタッフが選択された外科医とそれぞれ作業した最短時間に基づいて選択することができる。さらに、論理エンジン１００は、特定の複数のタスクを特定の複数の方法で実行するように各リソースに指示することができる。例えば、論理エンジン１００は、外科助手に手術室内の消耗品（例えば、注射器、生理食塩水、ガーゼ、血液など）の特定の量／数を集計するように指示することができる。目的が完了すると、論理エンジン１００は、リソースゲノムの値スコアを決定し、これは、好ましい実施形態では、リソースゲノムが目的の達成にどの程度成功したかを示す。

この例では、本明細書において開示される遺伝的アルゴリズムベースの方法およびシステムの使用は、遺伝的進化を次善の遺伝子（suboptimal gene）（例えば、非効率的または許容できない結果を生み出すリソースを示す遺伝子）から遠ざけることによって早期収束を回避する。このように、子孫の各世代は、１つまたは複数の所望の結果を達成する際に少なくとも閾値生存性（threshold viability）を満たすリソースを示す遺伝子を含むことが保証される。

医療処置がワクチンの単純な注射であり、選択された決定論的論理フレームワークが開始から終了までの最短完了時間を優先する場合、論理エンジン１００は、特定の時間枠内で最も医療予約を完了した医療スタッフを選択することができる。

現在説明されているスケジューリングシステムとは異なり、遺伝的アルゴリズムを使用する従来のスケジューリングシステムは、論理的な結論に到達しようと試みるために、ランダム化された優先順位で非常に大きな探索空間を探索する。そのため、決定論的論理を用いない遺伝的アルゴリズムを用いた従来のスケジューリングシステムは、大量のコンピューティングリソースを浪費し、局所最小値に収束することによって劣ったスケジュールを作成する可能性がある。局所最小値は、優れた遺伝子が遺伝子プールからフィルタリングされているために、劣った状態から進化することができない劣った遺伝子の小さなサブセットに限定された遺伝子プールの進化を示す。

遺伝的アルゴリズムを目的に関連する方向に導くことによって、関連性のないリソースゲノムは迅速に除外される。上記の例では、論理エンジン１００は、論理エンジン１００が最適化されたリソーススケジュールに到達するために必要な処理能力および時間の量を大幅に低減させる、正確性および長い動作時間を必要とする心臓手術のための迅速な完了レート（completion rate）を有する複数のリソースについて探索空間を探索する必要がない。

組み換え（Recombination）の例
タスクスケジューリング例が複数回完了され、作成された様々なゲノムが値スコアに関連付けられると、論理エンジン１００は、同様の値スコアを有する２つのリソースゲノムを選択することができる。好ましくは、論理エンジン１００は、組み換えするために２つの最高スコアのリソースゲノムを選択することができる。代替的には、組み換えエンジン３００は、第１の決定論的論理フレームワークに導かれた最も高いスコアのリソースゲノムを選択し、それを第２の決定論的論理フレームワークに導かれた最も高いスコアのリソースゲノムと組み換えすることができ、第２の決定論的論理フレームワークは、第１の決定論的論理フレームワークとは異なる。例えば、組み換えエンジン３００は、ウィジェットについての最速作成時間を達成するためにコンパイルされた第１のリソースゲノムを選択し、それをリソースあたりの最高成功率を達成するためにコンパイルされた第２のリソースゲノムと組み換えすることができる。

組み換えの多くのサイクルにわたって、リソースゲノムを適応度評価にかけることによって、全体的な目的を達成する方法は、１つまたは複数の決定論的論理フレームワークに基づいて最も効果的な解を最終的に得るために継続的に改良される。この組み換えの例は、本明細書において説明されている本発明の方法およびシステムが、特定の人またはリソースの可用性を調整することをはるかに超えていることを示す。むしろ、論理エンジン１００は、リソースコンパイルプロセスを自動化して、遺伝子組み換えおよび進化の原理ならびに関連する適応度関数を使用することによって、全体的な目的を達成するための最も効果的な方法を見つける。

本明細書の発明概念から逸脱することなく、上述したものに加えてさらに多くの変形が可能であることは、当業者には明らかである。従って、本発明の主題は、添付の特許請求の範囲の思想を除いて制限されるべきではない。さらに、明細書とクレームの両方を解釈する際に、すべての用語は文脈と一致する可能な限り最も広い方法で解釈されるべきである。特に、「含む（comprises）」および「含むこと（comprising）」という用語は、参照される要素、コンポーネント、またはステップが存在、利用、または、明示的には参照されていない他の要素、コンポーネント、またはステップと組み合わせられる可能性があることを示す、非排他的方法での要素、コンポーネント、またはステップを指すものと解釈されるべきである。明細書および特許請求の範囲が、Ａ，Ｂ，Ｃ，…Ｎから成るグループから選択された何かの少なくとも１つに言及している場合、その文章は、ＡとＮまたはＢとＮなどではなく、グループから１つの要素のみを必要とすると解釈されるべきである。

Claims (6)

1. 局所最小値への早期収束を防ぐために決定論的論理を適用して遺伝的アルゴリズムの複数のリソースゲノムについての複数のリソースを選択するための方法であって、
   論理エンジンが、目的に関連付けられた複数のリソースを特定すること、ここで、前記目的は、リソースゲノムに関連付けられており、
   前記論理エンジンが、特定された前記複数のリソースのうちの１つ又は複数のリソースによって完了されるタスク集合の全体を特定すること、
   前記論理エンジンが、時系列予測分析を実行すること、ここで、前記論理エンジンは、前記複数のリソースに関連付けられた履歴リソースタイミングデータを分析するようにさらに構成されており、
   前記論理エンジンが、前記目的に基づいて、１つ又は複数の決定論的論理フレームワークから決定論的論理フレームワークを選択すること、ここで、前記決定論的論理フレームワークは、前のタスクの完了から次のタスクの開始までの時間間隔を備えており、
   前記論理エンジンが、選択された前記決定論的論理フレームワークに基づいて、特定された前記１つ又は複数のリソースから１つ又は複数のリソースを選択すること、
   前記論理エンジンが、選択された前記１つ又は複数のリソースを前記リソースゲノムにコンパイルすること、
   前記論理エンジンが、前記タスク集合からの１つ又は複数のタスクを、前記選択された１つ又は複数のリソースに割り当てること、ここで、前記選択された１つ又は複数のリソースへの前記１つ又は複数のタスクの前記割り当ては、前記目的を達成するために必要な時間量を最小化するように設定されており、
   前記論理エンジンが、前記１つ又は複数のタスクを実行するために前記選択された１つ又は複数のリソースに複数の命令を送ること、
   前記論理エンジンが、前記リソースゲノムの値スコアを決定すること、を備え、
   前記値スコアは、前記目的に達するまでの時間を最小化することにおける成功の尺度を示す、方法。
2. 前記決定論的論理フレームワークは、前記目的に関連付けられた前記特定された複数のリソースに適用される選択基準を定義する、請求項１に記載の方法。
3. 前記論理エンジンが、前記特定された複数のリソースに関連する１つまたは複数の変数を分析することをさらに備え、
   前記１つまたは複数の変数は、少なくとも１つのリソース能力に関連付けられている、請求項１に記載の方法。
4. 前記論理エンジンが、前記リソースゲノムを第２のリソースゲノムと組み換えすることであって、前記第２のリソースゲノムは、第２の値スコアに関連付けられている、前記組み換えすること、
   前記論理エンジンが、組み換えされた前記リソースゲノムの第３の値スコアを決定すること、をさらに備える請求項１に記載の方法。
5. 前記値スコアは、適応度関数を用いて決定され、前記適応度関数は、前記リソースゲノムが単一の性能指数として前記目的を達成するのにどれだけ近いかを示す、請求項１に記載の方法。
6. 前記リソースは、人、機械、および消耗リソースからなる群から選択される、請求項１に記載の方法。