Hungarian algorithm and many factors

Question

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

Firstly, some background. This is for a non-profit organization that contributes to the history of watches for children who are hospitalized for any reason, so they depend on voluntary work for this. Therefore, since they rely on the goodwill of people, they give people the same work that people can / want to do, which changes, like:

• Some people can only do in the morning, and some other people can only do in the afternoon;
• Some people can only do Mondays and Thursdays, other people cannot go to August or December;
• Some people can walk only once a month, other people can walk 4 times (and even other people are given a “priority” in these actions because they are more experienced and may be available to do 10 times a month)

So, I figured out the first two. Since the Hungarian algorithm is about price, I would give them a stupidly high price for those times when they cannot go. However, how would you do the rest?

I was thinking of giving them some sort of score. Something like: one person who can do this once a month costs about 1000 points. If someone can walk 10 times a month, this person is worth 100 points (1000 basic divisions by 10). In addition, the way to disseminate this will be to increase the price each time a separate action is taken (for example, selected people have * at their respective cost):

First iteration

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

Second iteration

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

This will be a way to distribute accordingly among all people, paying more attention to those who can do this several times.

What do you think, and how would you do it?

Answer 1

This is a planning / optimization issue, so the key question is "how many are you trying to maximize"? I would suggest that you want to maximize the total number of hours spent in all your volunteers without collisions, subject to the restrictions on the schedule of volunteers. You also point out the priority of volunteers with more experience, so it sounds like you say: "Some volunteers prefer over others. "

This is a classic two-way matching problem . See p.498 of Algorithm Design Guide (2nd ed.), Stephen Skien. The main approach is to build a graph with vertices representing both a set of volunteers and a set of time intervals that you are trying to fill. Edges connect volunteers with valid time intervals. The optimal solution is the largest possible set of ribs where the second volunteer or time interval is not repeated. This is a match.

Some of your volunteers may run multiple slots; this can be modeled by repeatedly repeating this volunteer peak.

If you want to realize the priority of volunteers, then this effectively adds weight to each edge, simulating the experience of this volunteer for this task. In this case, as you thought, you will need something like a Hungarian algorithm. If you can do without this, you can convert the problem into an equivalent flow chart and apply a network flow algorithm. Below is an example of code that implements both weighted and unweighted matching .

If you want more detailed information, including other alternatives and other implementation references, I highly recommend that you get a copy of the Algorithm Development Guide - this is an amazingly clear and practical link.