algorithm - 加权、负载均衡的资源调度算法

Question

我正在开发的一个软件应用程序需要能够根据用户当前拥有的任务数量将任务分配给一组用户，其中任务最少的用户最有可能获得下一个任务。然而，当前的任务负载应该被视为一个权重，而不是一个绝对的顺序定义。 IOW，我需要实现加权负载平衡算法。

假设有五个用户，任务数量如下:

答:4乙:5C: 0D:7乙:9

我想按照 CABDE 的顺序对用户进行下一个任务的优先级排序，其中 C 最有可能获得分配，而 E 最不可能。这里有两件重要的事情需要注意:

• 用户的数量可以从 2 到几十个不等。
• 分配给每个用户的任务数量可以从 1 到数百不等。

目前，我们可以平等对待所有任务，但我不介意将任务难度作为我将来可以使用的变量 - 但这纯粹是锦上添花。

到目前为止，我提出的想法在某些情况下并不是很好。如果有大量用户，它们可能会将用户加权得太紧密，或者如果用户没有当前任务，它们可能会持平，或者......

我试过在网上搜索，但运气不佳。谁能给我一个运行良好的算法的快速摘要？我不需要实际的实现——我会做那部分——只是一个很好的描述。或者，是否有可以免费访问的好网站？

此外，虽然我当然欣赏质量，但这在统计上不一定是完美的。所以，如果你能想到一个不错但不是很好的技术，我很感兴趣!

Answer 1

正如您所指出的，这是一个负载平衡问题。这并不是一个真正的调度问题，因为您并没有试图最小化任何东西(总时间、并发工作人员数量等)。没有特殊限制(工作持续时间、时间冲突、匹配的技能组合等)，所以您的问题实际上归结为选择合适的权重函数。

你说有些情况你想避免，比如用户权重太接近。你能提供更多细节吗？例如，让分配的机会与当前工作量成正比，并由其他 worker 的工作量归一化有什么问题？您可以将其可视化为一系列不同长度的 block (任务)，它们被打包到一组箱子(工作人员)中，您试图在其中尽可能保持箱子的总高度。

根据更多信息，我们可以针对适合您的功能提出具体建议。

编辑:负载均衡函数示例

根据您的评论，这里有一些简单的函数示例，可以为您提供不同的平衡行为。一个基本问题是您想要确定性行为还是概率性行为。我将分别举几个例子。

使用问题中的示例 - 当前分配了 4 + 5 + 0 + 7 + 9 = 25 个工作。你想选择谁得到工作 26。

1) 简单的任务农场。对于每个作业，总是选择当前待处理作业最少的 worker 。速度快的员工有更多工作要做，但每个人都差不多在同一时间完成。

2) 保证公平的工作量。如果 worker 以不同的速度工作，并且您不希望某些人比其他人做得更多，那么请跟踪每个 worker 的已完成和待处理工作的数量。分配下一份工作以保持这个数字均匀分布(快工获得免费休息时间)。

3) 基本线性归一化。选择每个 worker 可以拥有的最大工作数量。每个 worker 的工作量都标准化为该数字。例如，如果每个 worker 的最大工作数量为 15，则在达到容量之前可以再添加 50 个工作。所以对于每个 worker 来说，被分配到下一份工作的概率是

P(A) = (15 - 4)/50 = 0.22  
P(B) = (15 - 5)/50 = 0.2  
P(C) = (15 - 0)/50 = 0.3  
P(D) = (15 - 7)/50 = 0.16  
P(E) = (15 - 9)/50 = 0.12

如果您不想使用特定的最大阈值，您可以使用当前挂起作业数最多的工作人员作为限制。在这种情况下，那是 worker E，所以概率是

P(A) = (9 - 4)/20 = 0.25  
P(B) = (9 - 5)/20 = 0.2  
P(C) = (9 - 0)/20 = 0.45 
P(D) = (9 - 7)/20 = 0.1  
P(E) = (9 - 9)/20 = 0

请注意，在这种情况下，规范化确保不能为 worker E 分配任何工作 - 他已经达到了极限。此外，仅仅因为 C 无事可做并不意味着他一定会得到一份新工作(只是更有可能)。

您可以通过生成介于 0 和 1 之间的随机数 r 并将其与这些边界进行比较来轻松实现选择功能。因此，如果 r < 0.25，A 得到这份工作，0.25<r < 0.45，B 得到这份工作，等等。

4) 非线性归一化。使用对数函数(而不是线性减法)对数字加权是获得非线性归一化的简单方法。您可以使用它来扭曲概率，例如使没有很多工作的 worker 更有可能得到更多。

重点是，这样做的方法实际上是无限的。您使用的加权函数取决于您尝试启用的特定行为。希望这为您提供了一些可以作为起点的想法。