重新平衡循环分配的算法

Question

我有一个具有以下属性的系统:

1. 有些 worker 在工作。可以添加或删除 worker 。每个工作人员可以同时运行多个作业。

2. 有工作。这些工作永远运行(无限期)并分配给 worker 。可以添加或删除作业。

我正在使用循环法在启动时将工作分配给工作人员，而且效果很好。

但是，我想在添加和删除工作人员以及添加和删除工作时重新平衡分配给工作人员的工作。

虽然在发生上述任何更改时可以使用循环算法重新分配所有内容，但它会进行比所需更多的更改。

换句话说，是否有任何循环再平衡算法可以使分配的差异/更改量最少？

Answer 1

我假设，您的循环方法按以下方式分配作业:

W1   W2   W3   W4
-----------------
J1   J2   J3   J4
J5   J6   J7   J8
J9

添加新工作非常简单。你只需要记住你分配上一个工作的 worker (循环算法的状态，在下文中将被称为最后一个 worker )并将新工作分配给下一个 worker .增加最后一个 worker 。

如果要删除作业(例如上面示例中的 J7)，请执行以下操作:首先，删除作业:

W1   W2   W3   W4
-----------------
J1   J2   J3   J4
J5   J6        J8
J9

然后选择最后一个 worker 的最后一个工作，并重新分配给失去工作的 worker (除非被删除的工作是最后一个工作):

W1   W2   W3   W4
-----------------
J1   J2   J3   J4
J5   J6   J9   J8

递减最后一个worker

如果要添加 worker ，请执行以下操作:选择最后一个 worker 的最后一个作业并将其分配给新 worker ，直到新 worker 的作业数等于或比其作业数少一个第一个 worker 。

W1   W2   W3   W4   W5
----------------------
J1   J2   J3   J4   J8
J5   J6   J9

相应地更新最后一个 worker 。

如果您已经具备以上所有条件，移除一个 worker 将非常简单:只需取出它的所有作业并一次添加一个。例如。如果删除 W2:

W1   W3   W4   W5
----------------------
J1   J3   J4   J8
J5   J9   J2   J6

根据数据的大小，您应该使用适当的数据结构来提高效率。但我相信您知道要使用什么结构。