割当アルゴリズム

Question

次の最適化条件を満たしながら、私はMの計算ノードにNエンティティ（可能な両親との可能な子供たちとそれぞれ）を割り当てる必要があります。エンティティの

1. 子供が同じ計算ノードに割り当てることにしたいです
2. エンティティの分布は、可能な限り同じでなければなりません（つまり、単一のノードの過負荷がない）。

この問題を解決するためのヒューリスティックな方法に関するいくつかの提案を探しています。

私はhttp://en.wikipedia.org/wiki/Assignment%5Fproblemと読みました。

ありがとうございました。

Answer 1

に取得することについてJob Schedulingをお読みください。その場合、最初の手順として、エンティティをconnected componentsにグループ化する必要があります。そうでない場合は、1と2の間のトレードオフが何であるかを指定する必要があります。コスト関数として。

各ノードをN/Mエンティティに限定すると、計算ノードにコンポーネントを配置するのはbinpacking problemです。

1. ソート彼らは限り、あなたは、2で行われたときに、各ノードがまだ
2. 利用可能な容量を持っているとして、ノードに
3. 場所を降順でエンティティの数によってコンポーネント、：良い近似は、以下のアルゴリズムであります配置されていないコンポーネントがある可能性があります。これまでの負荷が最も小さいノードにそれらを配置します。

Answer 2

もちろん、各プロセスの平均子供数（または合計負荷）を予測する必要があります。古典的な割り当てアルゴリズムを使用するよりも、通常はかなりシンプルです。

最も重要な問題は、もちろん、最小限に抑えたいものを決めることです。通常、私たちは遅れを最小限に抑えたいと思っていますが、いつもそうではありません。

編集：事前にすべての子供/両親を知っていて、プロセスの子どもたちは同じマシンにいなければなりませんプロセスとそのすべての子プロセスが、同じプロセスであると考えることができます。その後、非常に単純なアルゴリズムを使用して、最小限に抑えたいものを最小限に抑えることができます。

編集＃2：私は1は、ハード要件であるかどうかわからないんだけど、良いアイデア