私のプロジェクトの 1 つでは、負荷分散を実行できるアルゴリズムを実装する必要があるシナリオがあります。ここで、CS 理論 (NP 困難) に存在する一般的な負荷分散問題とは異なり、タスクは M 負荷を N サーバー (M >> N) に割り当てて、任意の 1 つのサーバーの最大負荷を最小化します。私が扱っているケースはもう少し一般的です。私の場合、負荷分散の問題はある意味でより一般的です - という形でより多くの制約があります - そのようなジョブはそのようなサーバーにのみ割り当てることができます (たとえば、ジョブ M_{i} にはいくつかの特別なものがあるとしましょう)セキュリティ要件を満たしているため、安全なサーバー N_{j} でのみ割り当て/実行できます。
ここで、Kleinberg/Tardos の本を見て、より一般的な負荷分散の問題 (制約を伴う負荷分散) に関するセクション (11.7) を見つけました。この問題が、現在の状況に完全に一致することがわかりました。一般的な負荷バランシングの問題は、IP から LP に変換されました。これは、LP ではジョブがマシンに部分的に割り当てられる可能性があるという事実を利用しており、後で四捨五入され、プロセスに O(MN) の時間が追加されます。この近似解は、可能な最小値から 2 倍以内であることが示されています。
このアルゴリズムが実装されている C/Java/Python/MATLAB コードを教えてもらえますか? KL book では例やサンプルの疑似/実際のコードがほとんど提供されていないため、アルゴリズムを完全に内部化するのは難しい場合があります。また、問題の線形計画法の部分については、どのような実装がそれに適していますか - シンプレックス/内部ポイント? この LP 部分の複雑さが問題 (部分再割り当て部分) に追加されると、どのくらいの違いが生じるでしょうか? 残念ながら、KL の本はこれらの点であまり完全ではありません。
この完全なアルゴリズムの実際の実装を示すいくつかのサンプル C/Java/Python/MATLAB コード (またはコードへのポインター) は非常に役立ちます。
編集: 元の論文は「David B. Shmoys, Éva Tardos: An approximation algorithm for the generalized assignment problem. Math. Program. 62: 461-474 (1993)」です。