算法再平衡的循環任務

Question

我有以下屬性的系統：

1. 有跡象表明，對就業工作的工人。工人可以被添加或刪除。每個工作人員可以同時運行多個工作。

2. 有工作。這些工作永遠運行（無限期）並分配給工人。可以添加或刪除作業。

我正在使用循環法將作業分配給啓動時的工作人員，這項工作非常好。

但是，當添加和刪除工作人員以及添加和刪除作業時，我想重新分配分配給工作人員的作業。

儘管可能在發生上述任何變化時使用循環算法重新分配所有內容，但它會進行比所需更多的更改。

換句話說，是否有任何循環重新平衡算法在那裏會導致對作業的差異/變化的最小量？

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 

遞減的最後一名工人

如果你想添加一個工人，做如下：選擇最後一名員工的上一份工作，並將其分配給新員工，直到新員工的工作數量等於或少於第一名員工的工作數量。

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

爲了減少或優化的作業運動的次數：雙（worker和numOfJobsAssigned）的

創建列表（比如，workers），並分別保持一個可變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 

之後，拆除工人可以通過從離開的工人+另外一個工作，以保持工人逐一做拆除作業的完成。