Staff Rostering algorithms

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

From stackoverflow Devan

• 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

  From aku

• 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)
  From Lasse V. Karlsen

• 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.

  From Leigh Caldwell

• Or by using OR ;)

  tovare : -1 Although issues schduling algorithms would be relevant to Operation Research, just mentioning OR without elaborating is not an answer. It's like saying Why not use AI, mathematics or alorithms

  Jonke : Point taken, I feel embarrassed. But to my defense the OR is alink and with a short question without any constraints about the problem domain there is not easy to give a elaborate answer.

  tovare : Yeah, as penalty you need to find some good GA sample-code and post the link ;-)

  Jonke : Well, why stop, I usually prefer Hybrids: http://www.cpaior.org/ but now we run into the commercial things so I better be quiet.
  From Jonke

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

  From realcals