equal distribution within given set of users

Question

I have a requirement where I have a list of entity and users who that entity can be assigned

E1 can be distributed by U1 or U2

E2 must be distributed by U5

E3 can be distributed by U2 or U3 or U4

I have such 50K entities and for each entity there might be 1 or more users. In case of 1 user, its clear and entity will be assigned to that user only. In case of multiple users, it can be assigned to any one them.

We want to distribute it such that each user gets equal amount of entities. and there are minimal possible/unavoidable skewed distributions, also each user might already posses some entities : U1 has 2K and U2 has 3K entitis already, so the distribution should take care of this fact as well.

EDIT 1

We have already tried a solution of going sequentially and assigning one entity at a time as per the allocation to users at that point in time, but that producing skewed results, because we are getting users who have less allocation earlier but more allocation later or viceversa...

E1 to E25 "must be handled by any of" U1 & U2

E26 to E50 "must be handled by any of" U2 & U3

if we go sequentially, in the end : U1 gets 12 (from E1-E25), U2 gets 19 (13 from E1-E25 & 6 from E26-E50) & U3 gets 19(from E26-E50). So all in all 50 allocated. fine. but see the skewed results

EDIT2

Why do we have different users per entity? there are multiple products to be distributed. Some users handle multiple products and some users handle single product, but still all the users need to be load balanced.

Answer 1

This brings back memories of an Operations Research class I had in college a very long time ago. You might want to do some googling on the Assignment problem and the Generalized Assignment problem for some background info and more rigorous solutions.

Having said that, I'd do the following:

1. Put all the entities that can be processed by the same set of users into a "bucket". Bucket 1 might contain all the entities that can be processed by U1 or U2. Bucket 2 might contain all the entities that can be processed by U2 or U3. Bucket 3 (not in your examples) might contain all the entities that can only be processed by U4.
2. Process all the "single entity" buckets (Bucket 3). There are no choices to be made here, and you may as well get this out of the way first. You mentioned that 80% of your entities may fall into this category.
3. At this point, stop looking at buckets and entities, and process users. Find the user with the least number of entities assigned and have them pick one entity from the most full bucket (bucket with the largest number of entities).
4. Repeat step 3 until all entities are assigned.

This will definitely require testing - I reserve the right to be wrong :-)