1

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?

Dan
  • 195
  • 3
  • 12

1 Answers1

2

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?

Stef
  • 13,242
  • 2
  • 17
  • 28
  • Can a more well-balanced solution have more than one volunteer per slot? – Neil Feb 26 '23 at 16:29
  • 1
    @Neil Yes, you can change the constraint `forall s, sum over v of x[v,s] = 1` to your liking. For instance if each spot requires a specific number of volunteers, you can have a constant vector `n_volunteers_for_spot` such that `n_volunteers_for_spot[s]` gives the number of volunteers required for that spot, and then you use the constraints `forall s, sum over v of x[v,s] = n_volunteers_for_spot[s]`. Or you can use inequality constraints such as `forall s, sum over v of x[v,s] >= 1` and `forall s, sum over v of x[v,s] <= 3` to have between 1 and 3 volunteers for each spot. – Stef Feb 26 '23 at 16:33
  • You can also add "soft constraints" by including the number of volunteers per spot in the objective function. For instance, perhaps the ideal number of volunteers for a spot `s` is 2, and you add `(sum over v of (2-x[v,s])²)` to the objective function so that the solution will be penalised if the number of volunteers for that spot is different from 2 – Stef Feb 26 '23 at 16:35
  • Thank you so much! May I ask, mathematically I presume this would still work if there are fewer volunteers than number of slots? In which case some volunteers would need to take more than 1 slots. It wouldn't contradict the constraints and optimization problem right? – Dan Mar 07 '23 at 09:17