2

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.

  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask – gnat Apr 3 '15 at 6:31
  • Not sure I understand you - are you saying that an entity can be assigned to exactly one user? In your example, E1 can be assigned to U1 or U2 (but not both), but cannot be assigned to U5. Is that correct? – Dan Pichelman Apr 3 '15 at 13:47
  • @DanPichelman check my edits, hope that makes it clear. let me know if not – harishr Apr 3 '15 at 14:43
3

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 :-)

  • 2
    This algorithm may not produce the ideal solution, but it should produce a good solution in a reasonable amount of time. More specifically, the ideal algorithm is NP but this one is P. I approve. – user22815 Apr 3 '15 at 15:20
  • I am getting the concept... but still not able to get my head around on how will this work or solve the issue.. i will try to simulate this.. thanks a lot for the answer and a big thank you for giving the names of algorithm I need to study – harishr Apr 3 '15 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.