Problem with finding maximal sum of happiness

[MatHek]

Hi, I have a problem to solve, and do not see any optimal solution :/ The problem is:

I have n workers and k jobs. Each job is to be done by specified number of workers, and each worker has his level of happines for each job. I have to to make a work schedule so that workers would be as happy as possible.
So, I have array a1 of int[n,k]. k-th column of i-th row contains preference (number from 0 to 10) of i-th worker for k-th job. I also have array a2 of int[k], where i-th element contains number of people who will be doing that job. I have to find maximal possible sum of happines, knowing that n >= min(a2).
My solution is to use recursion. Select first worker for first combination of jobs, add preferences to the sum, check if sum is higher then maximal already found, and if it is, go to the next worker. When back, check the next combination for the first worker etc. This works fine for small amount of workers, but has to high computational complexity to solve bigger problems. Have You got any idea for better solution?

[Rabbit]

What you have is called an assignment problem: http://en.wikipedia.org/wiki/Assignment_problem.

And that can be solved using the Hungarian Algorithm: http://en.wikipedia.org/wiki/Hungarian_algorithm

In your situation, your cost is "unhappines s" and you can use the algorithm to find the combination that will give you the least "unhappines s" in polynomial time.

[MatHek]

I do not see any way to comment Your answer, so I am writing as a 'reply'. This algorithm is very nice, but my problem is a little bit more complicated. The assumption in HA is that we have n people and n jobs. I have k jobs, where k >= n. What is more, one job is to be done exactly by specified number of people, so I cannot just duplicate workers, because one worker would be selected for one job multiple times...

[Rabbit]

Perhaps you need to provide an example because I don't see any problem with using the algorithm. All you do is first use the algorithm on n jobs. Then use the algorithm again on the remaining k - n jobs.

[MatHek]

You are right, I have to think it out concerning my special case. Thank You for Your help, I will write when I get to know more.

[Rabbit]

Let us know if you run into any problems implementing the algorithm. The base algorithm is described in the article and the links below that article have implementations in a bunch of different languages. So the base implemenation shouldn't be too difficult to work out. And it may benefit you to first do it as the simple version where n = k.

Once you're confident that's working, you can work on the more difficult part of expanding the algorithm to where n < k. Off the top of my head, my thought is that you can use an n x k matrix with a carefully crafted cost assignment to ensure mutual exclusivity on those jobs that require more than one person. Then, after running the algorithm once, you reassign costs to ensure mutual exclusivity to fill in the remaining k-n jobs.

[MatHek]

As far as I am concerned, Your idea is not right. Using algorithm on a part of jobs, and then on the next part, etc, requires assumption that nobody does more than one job in each part. That is why every combination of jobs in each part needs to be checked, which makes my algorithm NP. Similar problem raises up while trying to calculate one-personal jobs firstly. The best solution for all jobs does not have to contain the best solution for only a part of them.
There is also one more thing that I have forgotten to write about: I want all my workers to do the same amount of jobs (number of all workplaces is an integral multiple of number of workers)

[Rabbit]

I still think an example would help. But if I understand the question correctly, you can still use the algorithm even if you don't want to run it multiple times. You just need to generalize it by removing the n=k restriction and use additional variables to keep track of assignments per job and assignments per worker.

[MatHek]

ok, here are arrays:

         job1 job2 job3 job4
wokrer1    1    3    4    2
worker2    9    8    1    2        
worker3    6    7    8    9

       job1 job2 job3 job4
count    1    2    2    1

example solution:
worker1: job2, job3 (7)
worker2: job1, job2 (17)
worker3: job3, job4 (17)

sum: 41

I still do not see any way to change the original algoritm, but I will try

[Rabbit]

That helps make things clearer.

Yes, I believe you can still use the algorithm. The algorithm assigns the first created 0 to a worker to minimize costs. If you take that base algorithm, all you need to do is assign the first x zeroes, where x is an additional variable that keeps track of how many workers need to be on a job. That way it assigns the first 2 created zeroes to a job, i.e. the 2 lowest cost workers.

And if need be an additional variable to keep track of assignments per worker so you don't exceed the 2 jobs per worker limit you want to enforce.

[MatHek]

That sounds better, I will try to implement that