Optimal shift scheduling algorithm
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
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.