Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Imagine a small local business (in my case a dog daycare) with a few dozen part-time employees . The goal is to automatically create weekly staff schedules. My question is about what algorithmic approaches to explore for this problem.

There are many constraints to keep in mind, chiefly (1) the availability of the staff and (2) the needs of each shift, not just how many staff for each shift but the skills needed for each shift (e.g. for a certain shift, you may need someone who knows how to drive to do pick-ups/drop-off of dogs, for another, someone who know how to give dogs baths, etc).

Other constraints include things like avoiding or requiring certain staff combos -- perhaps due to personality conflicts on one hand, or need for training by osmosis from a senior to junior staff on the other.

Also, there are preferences to take into account. Some staff prefer mornings, some two days in a row rather than say Monday and Thursday, etc. We know we can't always accommodate everyone's preferences. In fact we have a hierarchy of which employees get first dibs on their choices.

I have a hunch that there is a way to reduce or express this problem into an existing, already solved algorithm. But I don't know which algorithms to explore. Which existing, specific algorithms would be most promising?

share|improve this question
3  
3  
And as an aside, I've never found an algorithm that works for this problem beyond the very simplest constraints in the past beyond "put everyone down on the schedule randomly ignoring any other constraint and let them swap or take shifts as desired." –  MichaelT Apr 22 at 19:32
4  
There is a complete solution available from the JBoss Drools site: optaplanner.org -- you need to codify the scheduling constraints, such as maximum hours per week, etc. –  BobDalgleish Apr 22 at 21:47
    
I suspect this is equivalent to the SAT problem, which is known to be NP-complete, but there are no doubt good algorithms that get reasonable results. –  David Conrad Apr 25 at 19:24

1 Answer 1

up vote 3 down vote accepted

Algorithms such as Local Search (Tabu Search, Simulated Annealing, Late Acceptance) work very well on such problems.

As Bob suggests, if you're working in Java, take a look at OptaPlanner (open source). See this video on employee rostering.

share|improve this answer
2  
Could you either explain the algorithms or add links to someplace that does? If you add links, please also add a little bit of information from the page that is relevant. –  Adam Zuckerman Apr 25 at 18:50
    
Done. Note: many of these are explained on wikipedia too. –  Geoffrey De Smet Apr 28 at 7:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.