Optimal shift scheduling algorithm

Question

I have been trying for some time solve a scheduling problem for a pool that I used to work at. This problem is as follows...

There are X many lifeguards that work at the pool, and each has a specific number of hours they would like to work. We hope to keep the average number of hours away from each lifeguards desired number of hours as low as possible, and as fair as possible for all. Each lifeguard is also a college student, and thus will have a different schedule of availability.

Each week the pool's schedule of events is different than the last, thus a new schedule must be created each week.

Within each day there will be so many lifeguards required for certain time intervals (ex: 3 guards from 8am-10am, 4 guards from 10am-3pm, and 2 guards from 3pm-10pm). This is where the hard part comes in. There are no clearly defined shifts (slots) to place each of the lifeguards into (because of the fact that creating a schedule may not be possible provided the availability of the lifeguards plus the changing weekly pool schedule of events).

Therefore a schedule must be created from a blank slate provided only with...

• The Lifeguards and their information (# of desired hours, availability)
• The pool's schedule of events, plus number of guards required to be on duty at any moment

The problem can now be clearly defined as "Create a possible schedule that covers the required number of guards at all times each day of the week AND be as fair as possible to all lifeguards in scheduling."

Creating a possible schedule that covers the required number of guards at all times each day of the week is the part of the problem that is a necessity and must be completely solved. The second half about being as fair as possible to all lifeguards significantly complicates the problem leading me to believe I will need an approximation approach, since the possible number of way to divide up a work day could be ridiculous, but sometimes may be necessary as the only possible schedule may be ridiculous for fairness.

Edit: One of the most commonly suggested algorithms I find is the "Hospitals/Residents problem", however I don't believe this will be applicable since there are no clearly defined slots to place workers.

Answer 1

One way to solve this is with constraint programming - the Wikipedia article provides links for several constraint programming languages and libraries. Here is a paper describing how to use constraint programming to solve scheduling problems.

Another option is to use a greedy algorithm to find a (possibly invalid) solution, and to then use local search to make the invalid solution valid, or else to improve the sub-optimal greedy solution. For example, start by assigning each lifeguard their preferred hours, which will result in too many guards being scheduled for some slots and will also result in some guards being assigned a ridiculous number of hours; then use local search to un-assign the guards with the most hours from the slots that have too many guards assigned.

Answer 2

You need to turn your fairness criterion into an objective function. Then you can pick from any number of workplace scheduling tools.For instance, you describe wanting to minimize the average difference between desired and assigned hours. However, I'd suggest that you consider minimizing the maximum difference. This seems fairer (to me) and it will generally result in a different schedule.

The problem, however, is a bit more complex. For instance, if one guard is always getting shorted while the others all get their desired hours, that's unfair as well. So you might want to introduce variables into your fairness model that represent the cumulative discrepancy for each guard from previous weeks. Also, a one-hour discrepancy for a guard who wants to work four hours a week may be more unfair than for a guard who wants to work twenty. To handle things like that, you might want to weight the discrepancies.

You might have to introduce constraints, such as that no guard is assigned more than a certain number of hours, or that every guard has a certain amount of time between shifts, or that the number of slots assigned to any one guard in a week should not exceed some threshold. Many scheduling tools have capabilities to handle these kinds of constraints, but you have to add them to the model.