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

Question

在我的一个项目中，我需要实现一种能够进行负载平衡的算法。与计算机科学理论中存在的一般负载平衡问题（NP难）不同，该问题的任务是将M个负载分配到N个服务器上（M >> N），以使任何一个服务器中的最大负载最小化。我处理的情况更加通用。在我的情况下，负载平衡问题更加通用，因为它具有更多的约束条件，例如：某个作业只能分配给某个服务器（例如，作业Mi具有某些特殊安全要求，因此只能在安全服务器Nj上分配/执行）。

现在我查看了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：广义分配问题的近似算法。数学程序。62：461-474（1993年）”

- user396089

---

你有没有考虑将其视为随机过程？你可以计算当前任务所需的预期服务器使用量。如果该任务具有特殊的安全限制，则可以计算条件期望值。此外，如果你注意到某个服务器表现不佳，可以使用贝叶斯定理更新分布，以相应地减少其概率。 - algolicious

看一下一些单纯形点LP算法，然后只需调整一个并添加约束条件。这就是我会做的。 - algolicious

你能在这里发布目标函数和约束条件吗？或者提供一个公共URL链接？这似乎是一个有趣的问题。 - greeness

实际上，我在最近的一篇研究论文中使用了这个特定的算法。该论文仍在同行评审中。事实上，我最终使用的算法是最小成本(C)负载平衡问题(L)。这也被称为“双标准”问题，这意味着我们必须确保目标函数f(C;X)小于C_{total}，使得分配给任何服务器的总负载在[0，L]范围内的某个值之内，其中L = sum_{i} W_{i}，W_{i}是单个对象的大小。 - user396089

GLPK是一个很好的起点。它运行速度快，且描述语言易于学习。祝你好运！ - greeness

Answer 1

一种我实现这个的方法是根据每台机器的当前负载进行负载均衡。所以如果有三台机器A、B、C... A的负载为10，B的负载为5，C的负载为2，那么下一个任务（假设负载为3）应该分配给C（3+2=5 < 所有其他组合）。如果存在相等的情况，通常先开始的任务通常会较早完成（至少大部分时间如此），则从每台机器中移除最旧的任务，并重复上述过程... 递归地执行此操作。

- prashant