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

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.