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 >= n). 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. Each worker is to do the same number of jobs. I have to find maximal possible sum of happines, knowing that n >= max(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?
PS. Guy from another site recommended me using Hungarian Algorithm, but it assumes that n == k, and I do not know how to make it working with n <= k
PS2 an exaple:
a1:
job1 job2 job3 job4
wokrer1 1 3 4 2
worker2 9 8 1 2
worker3 6 7 8 9
a2:
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
This looks like the Transportation Problem to me. It can be solved using the Hungarian Algorithm though. First let's set up the matrix for the Hungarian Algorithm.
The Hungarian Algorithm is used to find the minimum sum. To make it solve a maximum sum problem you would first have to invert all of your happiness values.
J1 J2 J3 J4
W1 1 3 4 2
W2 9 8 1 2
W3 6 7 8 9
Subtract each value by the greatest value in the matrix.
The greatest value in this matrix is 9.
J1 J2 J3 J4
W1 9-1 9-3 9-4 9-2
W2 9-9 9-8 9-1 9-2
W3 9-6 9-7 9-8 9-9
J1 J2 J3 J4
W1 8 6 5 7
W2 0 1 8 7
W3 3 2 1 0
Now, as you noted, the Hungarian Algorithm only works on square matrices. To make it work on a rectangular matrix, we must make it square. We can do this by adding dummy rows or columns filled with zeroes.
J1 J2 J3 J4
W1 8 6 5 7
W2 0 1 8 7
W3 3 2 1 0
WD 0 0 0 0
Now that we have it in a usable form, we can solve for the minimum sum. I'm going to skip to the solution as instructions on how to use the Hungarian Algorithm are readily available elsewhere.
W1 -> J3
W2 -> J1
W3 -> J4
WD -> J2 (Except this is a dummy row so it doesn't count.)
We have now assigned one job to each of our workers. This is where your second array comes into play.
J1 J2 J3 J4
1 2 2 1
We have assigned a worker to jobs 1, 3, and 4, so we will subtract 1 from their respective values.
J1 J2 J3 J4
0 2 1 0
Since we no longer need anyone to do jobs 1 or 4, we can remove their columns from our happiness matrix as well.
J2 J3
W1 6 5
W2 1 8
W3 2 1
We still have jobs to do though, so we go through the process again.
Add dummy columns to make the matrix square.
J2 J3 JD
W1 6 5 0
W2 1 8 0
W3 2 1 0
and solve. Remember that the columns are for jobs 2 and 3, not 1 and 2.
W1 -> JD
W2 -> J2
W3 -> J3
We have now gone through the algorithm twice, and have assigned five jobs.
W1 -> J3
W2 -> J1, J2
W3 -> J4, J3
We would now go through the entire process again. Since there is only one more job to assign, and one person to assign it to (W1 has only been assigned one job, but they must all be assigned the same number.), we can just go to our final solution.
W1 -> J3, J2
W2 -> J1, J2
W3 -> J4, J3
and the happiness values for this are:
W1 -> 4 + 3 = 7
W2 -> 9 + 8 = 17
W3 -> 9 + 8 = 17
for a total of 41.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments