I'm writing a computer program to do work but there's a partitioning problem. In this program, there're workers and works. The main objectif is to give a balanced partition plan, so that works can be done as soon as possible.
x, number of work types
W, works to do
P, number of partitions (workers) to do work, given by the user.
W, the number of works, it is the sum of
x different work types. Each work type has its own works :
W = W1 + W2 + W3 + ... + Wx
P, it defines the number of partitions (workers) to do work. This value is given by the user, we can't change it. Notice that one partition is attached to a worker. Several workers can do the same type of work, but one worker can only do one type of work.
P = P1 + P2 + P3 + ... + Px
For example, there're 4 apples and 7 bananas. The mission is to eat them all. There're 3 participants (workers). And we assume that eat a banana takes the same time as eating an apple, which is 1 minute / fuit. Since one worker can only do one type of work, each person can only eat one kind of fruit. In order to "balance" the speed, 4 apples will be given to person A, 4 bananas will be given to person B and 3 bananas will be given to person C. So
x = 2categories: apple, banana.
W = W1 + W2 = 4 + 7 = 11works to do
P = P1 + P2 = 1 + 2 = 3partitions to do work, where 1 partition for eating apples and 2 partitions for eating 7 bananas.
The above plan is computed based on the partition capacity :
avg = W / P = 11 work / 3 partition ≈ 3.67 work / partition
My questions are :
- Is there a specific name for this kind of partitioning problem ?
- Is there any mathematical model / algorithm to handle it ?
- For calculating the partition capacity, is average a good approach ?
Actually, I'm dealing with databases and I need to handle data coming from different tables, probably with billions of rows.
Please edit my post and tags if you find any possible enhancement. Thanks !