CODEWITHSUNDEEP
algorithm
Raghnarok
Raghnarok

Reputation: 11

Assignment problem with multiple persons needed on each job

First, sorry if my English isn't so good, I'm not a native English speaker.

I'm facing an assignment problem.

I have a list of jobs, with a certain number of persons needed for each job. Each person will let me know on how many jobs they want to be and their preferences.

I tried to do that with the Hungarian Algorithm but it seems I'm unable to get it done. With a large number of jobs and spots, some persons got multiple time the same job, which isn't ok. I think it's all due to the fact I considered each spot as an individual job and I listed each person as many times as they need to be placed.

Do you know a better algorithm or a way to do it?

(It's not a coding problem, I'm doing it in Octave/Matlab for now, but I think I'll switch to Python.)

Thanks for your help.

Upvotes: 1

Views: 1383

Answers (2)

Henrik4
Henrik4

Reputation: 484

Assignment problems can be solved with linear programming:

Let xij = 1 if person i is assigned to job j and 0 otherwise. Let aij be the rank for person i of job j : aij = 1 for the job he wants most, aij = 2 for the next and so on. If he only wants k jobs you put aij to a very high number for all jobs beyond those k.

If you need at least bj workers on job j you have the constraint

x1j + ... + xmj >= bj (j = 1,...,n)

You also have the constraints xij >= 0 and xij <= 1 .

The linear function to minimize is

sum( aij xij ) over all i,j

Upvotes: 0

Thomas Ahle
Thomas Ahle

Reputation: 31604

In addition to Henrik's suggestion to use Linear Programming, your specific problem can also be solved using Minimum cost maximum flow.

You make a bipartite graph between people and jobs (like in the Hungarian algorithm), where the cost on the middle edges are the preference scores, and the capacity is 1. The capacity of the edges from the jobs to the sink is the number of people you need for that job.

Upvotes: 1

Related Questions