Algorithmic staff scheduling solutions

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开发者_如何学Go.

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

---

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.

---

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

---

You might be also interested in constraint programming frameworks, many of which are open source such as Choco (Java), Gecode (C++) and others which have been used for these types of problems too, though I agree with ravloony that it might be worthwhile checking if an algorithm in the style he mentioned might do the trick for the problem you described.

---

As there is only one person per day, this seems like it could be setup as a integer/binary programming problem. There are many packages that do integer programming. The tricky part of these problems, regardless of what method you decide to use to solve them, is finding a concise way of specifying the constraints of the problem. In this case, what exactly are the vacation requirements, etc.