Algorithm to create a volunteer roster based on each person's availability

Question

I'm working with a group of volunteers, and we're trying to make a roster for taking care of cats in the area.

We have 21 time slots per week (3 per day), and we polled the volunteers to find out which time slots they are available. Currently all time slots have at least 1 person available. With this data, I want to craft a volunteer roster that covers all slots, while spreading the work as evenly as possible. There are more than 21 persons, so this means each person only have to take 1 slot maximum per week. For now, we don't take into consideration for preference, though it would be good to have that as a feature. Could someone point me at an algorithm to solve this problem?

Answer 1

Integer programming

Call x[v,s] the variable equal to 1 if volunteer v takes slot s, 0 otherwise.

Constraints

"Every time-slot must have one volunteer"

• forall s, sum over v of x[v,s] = 1

Objective

"Spread the work as evenly as possible"

This can be written either as:

• minimise max over v of (sum over s of x[v,s]);
• or minimise sum over v of (sum over s of x[v,s])².

Solvers

There exist solvers for integer programming in the form of libraries for any of your favourite programming languages, for instance PuLP for python.

There also exist solvers for integer programming where you can write your problem directly in pseudo-code in a text file, and the solver will read that file and find a solution. See for instance: Best open source Mixed Integer Optimization Solver?