Weighted Scheduling Algorithm for Load Balancing Resources
The software application I'm working on should be able to assign tasks to a group of users based on how many tasks they currently have, where the users with the lowest tasks are most likely to get the next task. However, the current workload on tasks should be viewed as a weighting, not a determination of an absolute order. IOW, I need to implement a weighted load balancing algorithm.
Suppose there are five users with the following number of tasks:
A: 4 B: 5 C: 0 D: 7 E: 9
I want to prioritize users for the next task, in CABDE order, where C is most likely to get assigned and E is least likely. There are two important things here:
- The number of users can vary from 2 to dozens.
- The number of tasks assigned to each user can vary from 1 to hundreds.
Currently, we can treat all tasks as equal, although I would not mind including the task as a variable that I can use in the future, but this is purely icing on the cake.
The ideas I came up with are not very good in some situations yet. They can aggregate users too much if there are a large number of users, or they can crash if the user has no current tasks, or ....
I've tried shaking the net but haven't had much luck. Can anyone give me a quick summary of an algorithm that will work well? I don't need a real implementation - I'll do this part - just a good description. Alternative, is there a good website that is freely available?
Also, while I certainly value quality, it doesn't have to be statistically perfect. So if you can think of a good but not great technique, I'm wondering!
source to share
As you note, this is a load balancing issue. This is not a scheduling issue as you are not trying to minimize anything (total time, number of concurrent workers, etc.). There are no particular restrictions (duration of work, temporary encounters, skills, etc.). Therefore, your problem comes down to choosing the appropriate weighing function.
You say that there are some situations that you want to avoid, such as user scales that are too close to each other. Can you provide more details? For example, what's wrong with the ability to assign just proportional to the current workload, the normalized workload of other workers? You can visualize this as a sequence of blocks of different lengths (tasks) being packed into a set of bins (workers) where you try to maximize the overall height of the bins.
With more information, we could make specific recommendations for features that might work for you.
Edit: example of load balancing functions
Based on your comments, here are some examples of simple functions that can give you different balancing behavior. The main question is whether you want deterministic or probabilistic behavior. I will give a few examples of each of them.
To use the example in the question - there are 4 + 5 + 0 + 7 + 9 = 25 assignments currently assigned. You want to choose who gets the job 26.
1) Simple task farm. For each job, always select the employee with the lowest currently employed vacancies. Fast workers get more work, but they all finish at about the same time.
2) Ensure a fair workload. If workers are working at different speeds and you don't want some to do more than others, then track the number of completed + pending jobs for each worker. Assign the next job to distribute this number evenly (fast workers get free breaks).
3) Basic linear normalization. Choose the maximum number of jobs each worker can have. Each workload is normalized to this number. For example, if the maximum number of jobs / workers is 15, then another 50 jobs can be added before capacity is reached. Thus, for each employee, the probability of assigning the next task is -
P(A) = (15 - 4)/50 = 0.22 P(B) = (15 - 5)/50 = 0.2 P(C) = (15 - 0)/50 = 0.3 P(D) = (15 - 7)/50 = 0.16 P(E) = (15 - 9)/50 = 0.12
If you don't want to use a certain maximum threshold, you can use the worker with the highest current pending jobs as the limit. In this case, this worker is E, so the probabilities will be
P(A) = (9 - 4)/20 = 0.25 P(B) = (9 - 5)/20 = 0.2 P(C) = (9 - 0)/20 = 0.45 P(D) = (9 - 7)/20 = 0.1 P(E) = (9 - 9)/20 = 0
Note that in this case, normalization ensures that worker E cannot be assigned any tasks - he is already at the limit. Also, just because C has nothing to do with it doesn't mean it's guaranteed a new job (most likely).
You can easily implement a select function by generating a random number r between 0 and 1 and comparing it to those bounds. Therefore, if r is <0.25, A gets the job, 0.25 <r <0.45, B gets the job, etc.
4) Non-linear normalization. Using the logarithm function (instead of linear subtraction) to weight your numbers is an easy way to get non-linear normalization. You can use this to distort probabilities, for example. to make it much more likely that workers who do not have many jobs get more.
The bottom line is that the number of ways to do this is almost unlimited. Which weighting function you use depends on the specific behavior you are trying to enable. Hopefully this gives you some ideas that you can use as a starting point.
source to share