python - ホストでのタスクの割り当て/割り当て

Question

私は一連のホストと一連のタスクを持っています。
各ホストには cpu、mem、およびタスクの容量があり、各タスクには cpu、mem の要件があります。
各ホストはレイテンシ クラスに属し、特定のレイテンシ値で他のホストと通信できます。
各タスクは、特定の値以下のレイテンシで別のタスクと通信する必要がある場合があります。
私の問題入力の例を次の画像に示します。 ここで、タスク t1 はタスク t2、t3、および t4 とそれぞれ 3、3、および 5 以下のレイテンシで通信する必要があり、ホスト h1 はレイテンシ クラス 3 に属し、h2、h3、および h4 とレイテンシ 2、5、および 5 で通信します。それぞれ3。
Hungarian/munkres アルゴリズムを使用してこの問題を解決しようと考えていましたが、コスト関数を適切に設定するにはどうすればよいですか? これを解決するためのより良い割り当てアルゴリズムはありますか?
ありがとう。

Answer 1

ご存知のように、この問題は QAP (二次代入問題) のケースであり、これは完全な NP です。つまり、この問題を解決するための最適なアルゴリズムは、少なくとも多項式時間では存在しません。詳細はこちら

対処するアプローチはいくつかありますが、遺伝的アルゴリズム (GA) や ACO などの AI からのいくつかの簡単な方法を試してみましたが、素晴らしい結果が得られました。GAをお勧めします。