CODEWITHSUNDEEP
javaalgorithm
Jijo Thomas K
Jijo Thomas K

Reputation: 53

Alogrithm for balancing the load in multiple worker threads

I have a HashMap with key1 to keyn, and the value for each key is a list of objects with varying number of objects on each.

I also know the total number of objects (which is distributed among various keys).

My objective is to load the data into T threads, with K as the average number of records in each thread.

Constraint: The list of objects for a single key should go to single thread. (or cannot be splitted). However, we can group different list of records with different keys.

Is there any proven algorithm which is doing the same task?

Example:

Total size is = 1000
Request Map =

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

Now the output can be:

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

Upvotes: 3

Views: 102

Answers (1)

Roberto Attias
Roberto Attias

Reputation: 1903

This is known as the Bin Packing Problem where V = total-size/thread-count

Upvotes: 1

Related Questions