program logic for choosing correct person

Question

I am having issues choosing the correct way to resolve this problem with an algorithm. I appreciate any thoughts on the problem. This is not homework, this is an application I am writing for personal use. This is not the exact problem but it is an example of the logic I am trying to use to find the best way to solve.

Example: Say you have three people. All three people can mow, trim bushes and weed. One task can be performed by one person. The people are rated from a scale of 1 - 10 on their ability to perform a task, 10 being better. Person 1 can mow = 8, trim = 4, weed = 6. Person 2 can mow = 5, trim 4, weed 7. person 3 can mow = 7, trim 8, weed = 8. How do I find which person to do each task using a looping statement? I will use the sum of the abilities as the metric to choose. Please keep in mind if person 1 mows, person 2 & 3 must either trim or weed. Only one person can perform a task.

I thought about creating a 2d array. Something like array[person,ability] and looping through it but I am having issue understanding how the looping logic should work. Any help or point in the right direction will be appreciated!

Thanks

You have to define a *penalty function*: e.g. what's better: mow with ability 9 and weed with ability 5 or mow with ability 7 but weed with ability 8? Then you have to *minimize* this penalty function. — Dmitry Bychenko, Jun 07 '16 at 15:46
Sorry, I do not believe I was clear. I would like to choose the person based on the sum of the ability. So in your example, mow with ability 7 and weed with ability 8 would be better as the sum is 15. Where the alternate scenario's sum would be 14. — samuraiY, Jun 07 '16 at 15:55
in that case, the penalty `function = 30 - mower ability - trimmer ability - weeder ability`; you have *linear* rules and so you can solve the so called "assignment problem" via *Linear programming*. https://en.wikipedia.org/wiki/Linear_programming https://en.wikipedia.org/wiki/Assignment_problem — Dmitry Bychenko, Jun 07 '16 at 15:59
Thank you for the replies Dmitry. I am trying to perform this in a program, and I am having trouble implementing this. How is the best way to loop through this to find the best person to mow, trim, weed in a for loop? — samuraiY, Jun 07 '16 at 16:03
To be more clear, it I set it up like this: {performance[0, 0] = steve.mow; performance[0, 1] = steve.trim; performance[0, 2] = steve.weed; performance[1, 0] = sara.mow; performance[1, 1] = sara.trim; performance[1, 2] = sara.weed; performance[2, 0] = matt.mow; performance[2, 1] = matt.trim; performance[2, 2] = matt.weed;} What is the best way to loop through? — samuraiY, Jun 07 '16 at 16:22
read this, https://en.wikipedia.org/wiki/Hungarian_algorithm (the version for maximizing is explained here https://en.wikipedia.org/wiki/Hungarian_algorithm#Setting) — גלעד ברקן, Jun 07 '16 at 16:44

score 0 · Answer 1 · edited May 23 '17 at 12:08

If you check all the permutations of your people you can solve the problem.

If you make the permutations of an array of 3 (Number of people) you will have something like this(depending on your notation) :

ABC ACB BAC BCA CAB CBA

For example A means person 1, B means person 2 and C means person 3. So ABC means person 1 doing job 1, person 2 doing job 2 and person 3 doing job 3. For better understanding BCA means person 2 doing job 1, person 3 doing job 2 and person 1 doing job 3.

So when you made each permutation you can calculate the cost you want with the order and the data table you have.

To make permutations in C# you can use this : Listing permutations

meJustAndrew · Answer 2 · 2016-06-11T13:49:41.040

I see it like a class of person containing their abilities as properties. Considering this you may have a list of persons and you can iterate through it to find the best people at some jobs as follows:

    maxMow=0; 
    maxMowIndex=0;
    for(i=0;i<persons[i].Count;i++)
    {
        if(maxMow<persons[i].MowAbbility)
        {
           maxMow=persons[i].MowAbbility;
           maxMowIndex=i;
        }
    }

This is how ou determine the index of person with the best ability of mow, you can do the same to find out which is the best at each ability. There will be a problem when a person is the best at two or more things, then you should choose which job you should assign to him considering the abbilities of others, but in most cases this will work. A person as the problem looks, should be defined as follows:

class Person
{
   public int Mow;
   public int Trim;
   public int Weed;
}

program logic for choosing correct person

2 Answers2