I have N persons that I want to assign to M tasks. For each person I have a list of possible tasks that I consider suited for him/her. A person may only be assigned to the tasks on his/her list.
Each person also has some background characteristics, for instance gender (male or female), educational level (low, medium, high), and age class (< 25, 25-50, > 50).
I want to assign a fixed number of males (respectively females) to each of the tasks, a fixed number of persons with a low educational level (respectively medium and high) to each of the tasks, and a fixed number of persons below 25 (respectively between 25-50, and > 50) to each of the tasks. In other words, I want to assign N_males(i) males to task i (i=1,…,M), N_females(i) females to task i (i=1,…,M), N_low(i) persons with a low educational level to task i (i=1,…,M), and so on
My problem is: how can I easily determine whether an instance of this problem with given lists of people who can be assigned to the tasks, and fixed numbers (N_males(i), N_females(i), N_low(i) and so on) for each of the categories of the background variables has a solution?
There may, of course, be more (or less) than three background variables, and these variables may have more (or less) categories than I mention in my example.
.
sounds as a variant of the "multiply constrained assignment problem"
(not to say that this problem has an efficient solution ... at least, it has a (long) name !)
.
see section 2.13 in the survey attached
this survey is certainly outdated (2005) but has some pointers to the litterature
see also :
http://www.aporc.org/LNOR/12/ISORA2010F20.pdf
http://benthamopen.com/toorj/articles/V002/25TOORJ.pdf
.
Dear Peter,
Thank you for your answer.
Yes, this is a generalized Hall marriage problem, or a generalized "Harem" problem where men are allowed to be married with several women at the same time (see Anderson 1989, A First Course in Combinatorial Mathematics). There's a simple algorithm to check whether an instance of the Harem problem has a solution (again, see Anderson 1989). I had hoped that a simllar algorithm would exist for "my" problem, but it may indeed be too messy for that.
Dear Fabrice,
Thank you for your answer. I'll study the literature that you attached. I'm glad the problem at least has a name.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics