Alogrithm for load balancing across multiple worker threads

I have a HashMap with key keyn and the value for each key is a list of objects with a different number of objects on each.

I also know the total number of objects (which are shared among the different keys).

My task is to load data into T streams , with K being the average number of records in each stream.

Constraint : List of objects for one key must go in one thread. (or cannot be split). However, we can group different lists of records with different keys.

Is there a proven algorithm out there that accomplishes the same task?

Example:

Total size = 1000
Request card =

k1 → 100
  k2 → 50
  k3 → 200
  k4 → 250
  k5 → 150
  k6 → 80
  k7 → 60
  k8 → 90
  k9 → 20

Now the output might be:

T1 = k4 (250)
  T2 = k3 + k2 (250)
  T3 = k1 + k5 (250)
  T4 = k6 + k7 + k8 + k9 (250)

+3


source to share


1 answer


This is called a bin packing problem , whereV = total-size/thread-count



+1


source







All Articles