Algorithmic staff scheduling solutions

Question

At a gross level, the problem is simple: schedule an army of staff for one-person-per-day coverage, at any given day the staff is split into 3 pools, each staff has a vacation requirement, each staff has at most 2 shifts per week, etc.

I'd hate to do this manually as it has been done at my organization for centuries. I'd love to do something cool like genetic algorithms (eg [1] http://www.sersc.org/journals/IJAST/vol14/1.pdf).

Are there any reliable Open source / free alternatives out there? This also sounds like an optimization problem, can I fire up C++, R, etc to plug into some optimization library for this?

thanks

Answer 1

This is an optimisation problem. It's known as a Scheduling problem, strangely. :-D Depending on the size of the data, you may have to go for Metaheuristics like genetic algorithms, ant swarm optimisation etc, but I would start here by rolling your own rule based heuristic.

Basically, define rules as associations between things (person A cannot be simultaneously on vacation and at work), or conditions on the schedule (only three people at any given time). Then create a schedule, and insert all your staff one by one. If on insertion a rule is broken, then don't insert and pick another staff.

This should, if you do it right, come up with a valid, but less-than-optimal schedule, and you can then do cool stuff like defining operators (swap, move, 3-swap), which will give you a neighbourhood (all the valid schedules which can be reached by application of an operator). You can then choose the best schedule in the neighbourhood, and repeat. This is neighbourhood descent. But there are lots of neighbourhood-based methods to choose from. I believe Simulated Annealing is good when applied to scheduling problems.

Answer 2

You could try OptaPlanner (was previously called Drools Planner), it's based on Java and open source.