在我的一个项目中 - 我有一个场景，我需要实现一种能够进行负载平衡的算法。现在，与 CS 理论中存在的一般负载平衡问题不同（这是 NP 难题）——任务是在 N 个服务器中分配 M 个负载（M >> N），以使任何一台服务器中的最大负载最小化，我正在处理的案例更通用一些。在我的情况下，负载平衡问题在某种意义上更通用 - 它具有更多形式的约束 - 这样和这样的作业只能分配给这样的服务器（例如，作业 M_{i} 有一些特殊的安全要求，因此只能在安全服务器 N_{j} 上分配/执行。
现在我查看了 Kleinberg/Tardos 的书，发现了一节 (11.7) 关于更通用的负载平衡问题（带约束的负载平衡），我发现这个问题与我所处的情况完全匹配。通用负载平衡问题已从 IP 转换为 LP，这是利用 LP 可能导致将作业部分分配给机器的事实，这些机器后来被四舍五入，为该过程增加了额外的 O(MN) 时间。然后，该近似解已显示在可能的最小值的 2 倍以内。
有人可以指出一些 C/Java/Python/MATLAB 代码已经实现了这个算法吗？由于 KL 书几乎没有给出任何示例或示例伪/实际代码，因此有时很难将算法完全内化。同样对于问题的线性规划部分 - 什么样的实现适合它 - 单纯形/内点？当这个 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)”