重新平衡循环分配的算法

Question

我的系统具有以下属性：

有工人在工作。可以添加或删除工人。每个工人可以同时运行多个工作。
有工作。这些工作运行永远（无限期）并分配给工人。可以添加或删除作业。

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

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

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

换句话说，是否有任何循环再平衡算法可以使分配的 diffs/changes 最少？

Answer 1

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

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

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

如果您要删除作业（例如上例中的 J7），请执行以下操作：首先，删除作业：

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

然后选择最后一个工人的最后一个工作，并重新分配给失去工作的工人（除非被删除的工作是最后一个工作）：

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

递减最后一个worker

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

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

相应地更新最后一个工人。

如果您已经具备以上所有条件，则删除工人非常简单：只需取出其所有工作并一次添加一个。例如。如果你删除 W2:

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

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

Answer 2

减少或优化作业移动次数：

创建一个列表（比如，workers）（worker和numOfJobsAssigned），并单独维护一个变量maxJobsToAnySingleWorker。

达到平衡状态后（即所有 workers 都有相同数量的工作），将 maxJobsToAnySingleWorker 增加 1，然后添加新工作。

Start with maxJobsToAnySingleWorker = 0

For addition of a Job:
    Set Done to false
    for each worker in workers 
        if numOfJobsAssigned < maxJobsToAnySingleWorker
            Increase worker.numOfJobsAssigned by 1
            Set Done to true
            break
    if Done is false (equilibrium state)
        increase maxJobsToAnySingleWorker by 1
        Increase FirstWorker.numOfJobsAssigned by 1


For removal of a Job from a worker, say myWorker:
    Done = false
    Remove Job
    if myWorker.numOfJobsAssigned == maxJobsToAnySingleWorker-1
         Do nothing
    else
        for each worker in workers 
            if (numOfJobsAssigned > 1) and (numOfJobsAssigned == maxJobsToAnySingleWorker)
                Delegate Job from worker to myWorker
                Decrease worker.numOfJobsAssigned by 1
                Done = true
                break
        if worker is lastWorkerInList
            Decrease maxJobsToAnySingleWorker by 1

按照上述逻辑，移除一个工人可以通过从离职工人中移除一个工作+增加一个工作来完成留工人员一一

重新平衡循环分配的算法

Algorithms for rebalancing round robin assignments

algorithm

round-robin