Help with day job: 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.

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 http://www.sersc.org/journals/IJAST/vol14/1.pdf).

What has everyone here found useful? Open source / free alternatives are a big plus. This also sounds like an optimization problem, can I fire up C++, R, etc to plug into some optimization library for this?