使用线性规划(LP)的广义负载平衡(GLB)

Question

在我的一个项目中 - 我有一个场景,我需要实现一个能够进行负载平衡的算法.现在,与CS理论中存在的一般负载平衡问题(NP难度)不同 - 其中任务是在N个服务器(M >> N)中分配M个负载,使得任何一个服务器中的最大负载最小化,我正在处理的案例更为通用.在我的情况下,负载平衡问题在某种意义上更通用 - 它在形式上有更多的约束 - 这样的工作只能分配给这样一个这样的服务器(比方说工作M_ {i}有一些特殊的安全要求因此只能在安全服务器N_ {j}上分配/执行.

现在我查看了Kleinberg/Tardos的书,我发现了一个关于更通用的负载平衡问题(带有约束的负载平衡)的部分(11.7),我发现这个问题与我所处的情况完全匹配.通用负载平衡问题已经从IP转换为LP,利用LP可以导致将作业分数分配给机器的事实,这些机器随后被舍入为过程添加额外的O(MN)时间.然后,该近似解决方案显示在可能的最小值的2倍之内.

有人能指出我已经实现了这个算法的一些C/Java/Python/MATLAB代码吗？由于KL书几乎没有提供任何示例或样本伪/实际代码,因此有时难以完全内化算法.对于问题的线性规划部分 - 什么样的实现适合它 - Simplex/Interior Point？当这个LP部分的复杂性被添加到问题中时(对于分数重新赋值部分),它会产生多大的差异？不幸的是,KL书籍在这些方面并不十分彻底.

一些示例C/Java/Python/MATLAB代码(或指向代码的指针)显示了这个完整算法的一些实际实现将非常有帮助.

编辑:原始论文是"David B. Shmoys,ÉvaTardos:广义指派问题的近似算法.数学计划.62:461-474(1993)"

Answer 1

我这样做的一种方法是根据每台机器上的当前负载进行负载平衡。因此，如果有三台机器 A、B、C...A 的负载为 10，B 的负载为 5，C 的负载为 2，那么下一个任务（假设负载为 3）应该去 C(3+2 = 5 < 所有其他组合)。在相等的情况下，首先启动的任务通常首先完成（至少在大多数情况下），从每台机器中删除最旧的任务并重复上述过程...递归地执行此操作