Algorithms for rebalancing round robin assignments

Question

I have a system with the following properties:

1. There are workers that work on jobs. Workers can be added or removed. Each worker can run multiple jobs concurrently.

2. There are jobs. These jobs run forever (infinite duration) and are assigned to workers. Jobs can be added or removed.

I am using round robin to assign jobs to workers on start up and this work pretty well.

However, I want to rebalance jobs assigned to workers when workers are added and removed and when jobs are added and removed.

While it is possible to reassign everything using the round robin algorithm when any of the above changes happen, it would be making more changes than required.

In other words, are there any round robin rebalancing algorithms out there that will result in minimal amount of diffs/changes to the assignments?

Answer 1

I assume, your round-robin approach assigns the jobs in the following manner:

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

Adding a new job is quite simple. You just have to remember the worker that you assigned the last job (the state of the round-robin algorithm, will be referred to as last worker in the following) and assign the new job to the next worker. Increment the last worker.

If you want to remove a job (e.g. J7 in the example above), do the following: First, remove the job:

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

Then pick the last job of the last worker and re-assign it to the worker that lost a job (unless the erased job was the last job):

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

Decrement the last worker

If you want to add a worker, do the following: Pick the last job of the last worker and assign it to the new worker until the number of jobs of the new worker is equal or one less than the number of jobs of the first worker.

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

Update the last worker accordingly.

Removing a worker is quite simple if you already have all of the above: Just take all of its jobs and add it one at a time. E.g. if you remove W2:

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

Depending on the size of your data, you should use appropriate data structures to make this efficient. But I am sure you know what structures to use.