アルゴリズム

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 

デクリメント最後のワーカー

あなたは労働者を追加したい場合は、行います次のようにします：最後の労働者の最後の仕事を選び、新しい労働者の仕事の数が最初の労働者の仕事の数と等しいか1になるまで、新しい労働者に割り当てます。

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

それに応じて最後のワーカーを更新します。

すでにすべての作業が完了している場合、作業者を削除することは非常に簡単です。すべてのジョブを1度に1つずつ追加するだけです。例えば。削除する場合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 

ロジックの上に続き、労働者の除去は、滞在労働者の一つ 1に労働者+ジョブの追加を残してからジョブの除去を行うことによって達成することができます。