Staff Rostering algorithms

Question

We are embarking on some R&D for a staff rostering system, and I know that there are some suggested algorithms such as the memetic algorithm etc., but I cannot find any additional information on the web.

Does anyone know any research journals, or pseudocode out there which better explains these algorithms?

Thanks, Devan

Answer 1

Here is a useful document:

Memetic Algorithms for Nurse Rostering (pdf)

It contains a little bit of theory and pseudo-code.

Scheduling problem is NP-hard and usually being solved using genetic algorithms (GA).
You can start learning GA from Wikipedia article

Answer 2

There are many many many issues to consider when setting up a roster schedule, so aku's tip about genetic algorithms is the best one.

You need a good evaluation function to determine the quality of the roster for such an algorithm, and you can, and should, consider things like the following (but not limited to):

• have you solved the workload problem with this roster? (ie. do you have enough people at work at all times?)
• if not, can you live with the consequences? (for hospitals, you might have to postpone lunch 15 min one day in order to have enough people available for it, or just drag it slightly out in time)
• is the roster a good one, considering things like shift stability for each person, their days off, whether or not they get weekends off with some regularity
• is the roster legal? taking things like local regulations into account, that regulate things like how much time must pass between one shift and another (downtime), how much can each person work inside a given interval (day, week, month)

Answer 3

You may also want to look at a technique called "simulated annealing". Like genetic algorithms, this uses an evaluation function to determine the quality of candidate solutions - but the generating of the candidates tends to be simpler. Each type of algorithm gives better results in certain circumstances - from a brief Google survey it feels like genetic has the edge, but annealing will be quicker to implement.

Here is a comparison paper (for a different domain, not scheduling): http://www.ee.utulsa.edu/~tmanikas/Pubs/gasa-TR-96-101.pdf

We have used simulated annealing in a large scheduling application and it did work well.

To be honest, if the volume of staff is less than about 40, I would recommend giving a visual representation of the roster and letting the user finalise the schedule. Perhaps you would use an algorithm to produce a candidate schedule to start with, and then let the user play with it. You could still use the evaluation function to check the user's work and give feedback on how good their solution is.

Answer 4

Or by using OR ;)

Answer 5

I read a rostering algo paper by these guys a while back.