次の最適化条件を満たしながら、N 個のエンティティ (それぞれ可能な親と可能な子を持つ) を M 個の計算ノードに割り当てる必要があります。
この問題を解決するためのヒューリスティックな方法に関する提案を探しています。
http://en.wikipedia.org/wiki/Assignment%5Fproblemを読みました。
ありがとう。
明らかに、各プロセスが平均して持つ子の数 (または単純に総負荷) を予測する必要があります。従来の割り当てアルゴリズムを使用できるよりも、通常は非常に単純です。
もちろん、最も重要な問題は、最小化するものを決定することです。通常、遅延を最小限に抑えたいと考えていますが (どれだけ「スケジュールが遅れているか」)、常にそうとは限りません...
編集:すべての子/親が事前にわかっていて、プロセスの子が同じマシンにある必要がある場合は、プロセスとそのすべての子を最初から同じプロセスと見なすことができます。次に、非常に単純なアルゴリズムを使用して、最小化したいものを最小化できます。
編集 #2:より良いアイデアを得るためにジョブ スケジューリングについて読む
1が難しい要件かどうかはわかりません。その場合、最初のステップとして、エンティティを連結コンポーネントにグループ化する必要があります。そうでない場合は、1 と 2 の間のトレードオフを指定する必要があります (たとえば、コスト関数として)。
コンポーネントを計算ノードに配置することは、各ノードを N/M エンティティに制限する場合、ビンパッキングの問題です。適切な近似は、次のアルゴリズムです。