Random_Walk was pretty much correct: this problem lies in the focus of Operations Research and it is called the assignment problem. Here is a nice recipe on how to solve it.
You have n people and m jobs and each person can do only one job and each job can be done by exactly one person. You can also (intuitively or by some other policy) assign a cost c(i,j) of person j doing job i. Now, we make an integer linear program (ILP) out of this problem formulation.
Let x(i,j) denote the event that person j does job i. x(i,j) is a binary variable - it can either be zero or 1. We have the following constraints for x(i,j):
- Exactly one person can do a job, that is, for each job i=1..m we have a distinct constraint: sum_{j=1..n} x(i,j) = 1.
- Each person can do no more than one job, so for each person j=1..n we have yet another constraint: sum_{i=1..m} x(i,j) <= 1.
- And finally, for each (i,j) pair we have to make sure that x(i,j) is either zero or 1.
If you think after this constraint set, you will be surprized to find out that any setting of x(i,j) that satisfies all the requirements above gives rise to a possible assignment of people to jobs, this is why it is called the feasible region. You can also minimize the total cost of the assignment (in terms of c(i,j)) by setting the objective function:
minimize: sum_{i=1..m} sum_{j=1..n} c(i,j) x(i,j)
What you obtained (a set of variables, a set of constraints applied to the variables and an objective function to minimize) constitutes an integer linear program. So, here is again a perfect chance for me to advertise my module, which I coded and maintain (unfortunately, out of CPAN) to solve ILPs: Math::GLPK . Math::GLPK is an object-oriented Perl wrapper module for the GNU Linear Programming Toolkit (GLPK). Just feed the ILP to Math::GLPK as a matrix (it is pretty easy to do and the documentation is extensive) and leave the job of solving it to GLPK...
Good luck with OR!
Update: correct typos
| [reply] |
I'm unfamiliar with ILPs, but this sounds interesting. Thank you, I will take a look into this approach.
| [reply] |
