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

题

一个软件应用程序，我的工作需要能够将任务分配给一组用户基础的如何许多的任务，它们目前拥有的，那里的用户最少的任务的最有可能获得下一个任务。然而，目前的任务负荷应被视为一个加权，而不是一个绝对的顺序的定义。IOW，我需要执行一个加权、负载均衡算法。

让我们说有五个用户，以下数量的任务：

A:4 B:5 C:0 D:7 E：9

我要优先用户的下一个任务的顺序CABDE，其中C为最有可能获得的分配和E中，至少有可能的。有两个重要的事情要在这里指:

现在，我们可以治疗所有任务作为平等的，虽然我并不介意包括的任务的困难，因为一个变量，我可以使用在未来-但这纯粹是锦上添花。

的想法，我已经想出了迄今为止不是很好在一些情况。他们能量用户太紧密结合在一起如果有大量的用户，或者它们可能落空，如果用户没有目前的任务。

我已经尝试戳各地的网络，但是还没有多少幸运的。任何人都可以给我一个快速的摘要的一个算法，将工作?我不需要实际执行情况--我将做到这一点的一部分--仅仅是一个很好的说明。替代方案，是有一个很好的网站的可自由访问的?

此外，虽然我肯定更好的质量，这需要的不是统计学上完美的。所以如果你能想到的一个良好的但不是伟大的技术，我感兴趣！

解决方案

正如你指出，这是一个负载平衡的问题。它不是一个真正的调度问题，因为你不是试图尽量减少任何东西(总次数并发工人、等等)。有没有特别的限制(工作持续时间、时间冲突的技能相匹配，等等。) 所以真的是你的问题归结为选择适当的加权函数。

你说有些情况下你想要避免的，如用户的权重，这是太靠近在一起。你能提供更多的细节？例如，什么是错误的使用机会的分配只按比例目前的工作量、标准化的工作负荷的其他工作?你可以想象这样一个序列块的长度不同(任务)，被包装成套箱(工人)，其中你要保持高度的仓为，甚至成为可能。

更多信息，我们可以提出具体建议的职能可能对你的工作。

编辑：例的负载平衡的功能

根据你的意见了，这里有一些实例的简单的功能，可以给你的不同平衡的行为。一个基本的问题是，是否你想要的确定性或概率的行为。我给几个例子。

使用例子中的问题-没有4 + 5 + 0 + 7 + 9 = 25 工作目前分配。你想挑谁工作的26个。

1)简单的任务农场。 对于每一工作，总是挑选工作人员最少的工作岗位目前正待审理。快速工人得到更多的工作要做，但每一个人完成在大约同一时间。

2)保证公平的工作量。 如果员工工作，在不同的速度，并且你不想要一些这样做比其他人更多，那么追踪的号码的完成+待职工作对于每个工作人员。分配的下一步工作，以保持这个数字均匀地传播(快速工作者得到免费的休息).

3)线性基本正常化. 选择最大数量的就业岗位每个工作人员可以拥有。每个工作人员的工作量标准化。例如，如果最大数量的就业机会/工作人员为15，然后50更多的就业机会可以加入你之前达到能力。因此，对于每个工作人员的概率被分配的工作是下一个

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

如果你不想使用一个特定的最大阈值，可使用该工作人员的最高目前待审的工作为限度。在这种情况下，这是工作电子，因此将概率

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

请注意，在这种情况下，正常化，确保工作人员的电子不能分配的任何作业-他已经在限制。此外，仅仅因为C没有任何东西做并不意味着他是保证赋予了新的工作(这只是更有可能).

你可以很容易实现的选择功能产生随机数量 r 0和1之间和比较这些边界。所以如果 r 是 < 0.25，得到工作，0.25< r < 0.45，B会的工作，等等。

4)非线性的正常化. 使用日志的功能(而不是线性减)重你的号码是一个简单的方法来获得一个非线性的正常化.你可以使用这种歪曲的概率，例如让它更有可能的工作人员没有许多工作给予更多。

点数的方式做这几乎是无限的。什么加权函数中使用取决于具体的行为你正在尝试启用。希望这是给你的一些想法你可以用它作为一个起点。

许可以下： CC-BY-SA 和归因