Hungarian Algorithm and multiple factors

Question

I have a situation where I need to allocate people to several events. If we just had a price as a factor, it would be fine, but there is a number of factors that come in.

First, some background. This is for a non-profit organization that promotes story hours for children that are hospitalized for any reason, so they depend on voluntary work to do so. So, since they rely on people's good will, they give people as much work as people can / want to do, which varies like:

• Some people can only do mornings, and some other people can only do afternoons;
• Some people can only do Mondays, and Thursdays, other people can't go on August or December;
• Some people can only go once a month, other people can go 4 times (and even other people are given "priority" in these actions because they're more experienced and can are available to do 10 times a month)

So, I kinda figured out the first two. Since the Hungarian Algorithm is about price, I'd give them a stupidly high price for the times they can't go. However, how would you do the others?

I thought about giving them some sort of score. Something along the lines of: one person who can do this once a month costs something like 1000 points. If someone can go 10 times a month, that person costs 100 points (1000 basis dividing by 10). Also, the way to distribute this would be to increase the price whenever a separate action would be done, like so (selected people have a * on their associated cost):

First iteration

         | August 1st 2009
Person A | 1000
Person B | 500 *

Second iteration

         | August 8th 2009
Person A | 1000 *
Person B | 1000

This would be the way to distribute accordingly between all the people, giving more priority to those that can do this several times.

What do you think and how would you do it?

Answer 1

This is a scheduling/optimisation problem, so the key question is "what quantity are you trying to maximise"? I'd guess you are looking to maximise the total number of hours worked across all your volunteers without clashes, subject to each volunteer's timetabling constraints. You also mention prioritising volunteers with more experience, so it sounds like you are saying "some volunteers are preferred over others".

This is then a classic bipartite matching problem. See e.g. p.498 of The Algorithm Design Manual (2nd ed.), by Steven Skiena. The basic approach is to construct a graph with vertices representing both the set of volunteers, and the set of time slots you are trying to fill. Edges link volunteers to valid time slots. The optimum solution is then the largest possible set of edges where no volunteer or time slot is repeated. This is a matching.

Some of your volunteers may be able to do more than one slot; this can be modeled by replicating that volunteer vertex multiple times.

If you want to implement the prioritising of volunteers, then this effectively adds a weighting to each edge, modeling the experience of that volunteer for that task. In this case, as you thought, you will need something like the Hungarian algorithm. If you can get away without this, then you can transform the problem into an equivalent flow graph, and apply a network flow algorithm. Here is one example of code that implements both weighted and unweighted matching.

If you want more details, including other alternatives, and more links to implementations, I do strongly recommend getting yourself a copy of the Algorithm Design Manual - it is an amazingly clear and practical reference.