Calendar/Planning algorithm

Question

I'm facing a problem I'm not sure how to approach. I have to generate a calendar for employees, each of them having specific work constraints (some personal, some common)

What I'm working with :

• I have Doctors
• Each doctor has to work 5 day/week.
• Each doctor has to work 1 night/week
• Each doctor has to work an equal amount of nights compared to other doctors (or as close as possible)
• Each doctor has to work an equal amount of thursday nights and sunday nights compard to other doctors (or as close as possible)
• Some doctors can't work certain days/nights (input by user)
• Some doctors would like to work certain days/nights (input by user)
• Some doctors would like to not work certain days/nights (input by user)

The user in question is the person dealing with the calendar, I'm trying to build a solution that will automatically generate a calendar that obeys all constraints. The solution is just a big settings input "add doctors" and "add constraints" for each doctor, then a "generate calendar" button. It's really basic for the user.

My problem :

I'm not sure how to generate the actual planning, I've been reading about Neural Networks, Genetic Algorithms, and so on, and they all seem kind of the right solution but also not really.

When I look at GA's, they're made to find a solution with a given population (my problem), but the starting population has to already obey the given set of constraints, which would then be optimized. In that case, my starting population is already the solution. I don't need it to be "optimized". It doesn't matter that a single person works 3 monday nights in a row, as long as it's actually correct and that others work the same amount, that means others will also work 3 monday nights at some point and it's fine. Which makes me think that GA's are too "advanced" for me, as my problem is already solved with the starting point of a GA.

But then again, GA's really really looks like they're made for this, so I might not be understanding it correctly ?

Anyway, as I've never used GAs (or neural networks, or anything of the kind), I'd like to be sure I'm going for the correct approach before engaging in a learning curve like that one.

My question :

What do you think is a good approach / algorithm / technique for a problem like mine? GA's? Neural networks? Something else entirely different?

I'm all ears and open for more details if necessary, but I think i've made myself pretty clear :)

Answer 1

Genetic Algorithms and Neural Networks are not suitable here. They are meta-heuristics for finding a good-enough, approximate solution to a problem. Notably, both require you to find a cost function to rate candidate solutions. Once you have such a cost function, it might be easier to manually come up with an algorithm that optimizes for this cost.

This is an important thought: given two schedules, we need a way to decide whether schedule A or schedule B is “better”. You have listed various criteria, but it's not clear how they relate. Does failing to fulfil one criterion fail the whole solution? Or does partially failing a constraint just make it a worse solution than others?

At a most basic level, you can just partition the week into discrete time slots, and brute-force all slot–doctor combinations. However, you can use hard-failing constraints to reduce this search space to a more manageable size. The restrictions on work time and night shifts seem to be suited for such a search space limiting. You are then left with hundreds of candidate solutions.

To select the best candidate solution, you will need to rank them. This is fairly easy if one soft constraint has clear precedence over all other soft constraints, e.g. if a doctor can't work a certain shift, that is given more importance than a doctor not wanting to work that shift. But I can't decide these rules for you – that is a managerial decision. It is more difficult if two soft constraints don't have clear precedence, in which case you will have to come up with some kind of cost function that unifies the importance of two constraints in a single metric.

---

I would probably construct a greedy algorithm that fills in a blank time table according to some prioritized criteria. This might not be the most optimal solution, but it's way easier than philosophising about what “optimal” actually means.

As a first step, you could fill in the night shifts on weekends, and trying to select those doctors that haven't done a weekend night shift for the longest time, also taking into account the “I can't work there” user wishes. Assuming that these wishes are per-week and not continuous, this means a doctor that can't work on weekend nights for one week would be picked next week.

A similar procedure can be used for the other nights: after trying to respect user wishes, you fill in doctors according to who hasn't been doing night shifts for the longest amount of time. The procedure repeats similarly for the third kind of time slot, the day shifts. If two user wishes can not be reconciled, you could keep track of how often a users wish was granted, and then prioritizing the doctor with fewer granted wishes.

Unfortunately, I can see a couple of ways to game this system: e.g. if a doctor would be picked to work a weekend night shift but puts in a “can't work there” request, their pick would be delayed one week – reducing their frequency of weekend night shifts at the cost of their colleagues. If a wish resolution procedure is implemented that looks at the number of turned down requests, a user could put in a couple of impossible requests to boost one request they want to go through. However, assuming good faith (and the flexibility for doctors to swap shifts among each other), such an algorithm should result in a good-enough solution.

Answer 2

You can use simulated annealing.

I did something like that before I landed my first job - see https://vimeo.com/20610875 (demo starting at 2:50, algorithm explained from 6:15).

Simulated annealing is a type of a genetic algorithm, and maybe it was not suitable in theory (as @amon maintains in his answer), but it worked very well in practice, and it was about the same use case as yours.

Source code is available (C#), but while it works, it's terrible I'm afraid, it was a few years back and being an autodidact, I didn't know a thing about maintainability. It yielded very nice results though.

How it works in a nutshell anyway:

• Generate 1 possible (it may be not very good, but physically possible) time schedule as a starting point. Genetic algorithm isn't necessary at this point - you can just bruteforce your way to the first solution you can find. I used backtracking. Computational complexity can be overcome by solving the rota for each day separately. If there is no solution at all (as the case might be), it is at this point that you detect it.

• Make a pool of solutions - say, 100 copies of this entry-level solution for a start.

• Mutate every solution at random: have doctors swap shifts between eachother, take a random doctor off their shift and put a random available person on it etc.

• Evaluate each solution with a fitness function that determines how good it is. One guy works more nights than another? Subtract penalty points. Someone wanted to do Monday but they don't? Subtract penalty points again.

• Take - say - 20 best solutions and copy each of them 5 times, overwriting the remaining 80 with them, thereby carrying them to the next generation. Survival of the fittest.

• Rinse & repeat.

Numbers are obviously arbitrary, you may need to fiddle with parameters to find out the optimal settings for your scenario.

As for mutating a solution, simulated annealing introduces something called temperature. Basically it means that in the beginning you should mutate your solutions quite hard (say, always make 10 attempts of swapping shifts in one go) and gradually get less aggressive with subsequent iterations, so they become more of a fine-tuning (say, down to just 2 attempted tweaks per generation).

Answer 3

Genetics Algorithms do apply here. During my undergraduate program, one of my colleagues wrote a paper to very similar problem of yours.

You can look for Job Shop Scheduling and also Open Shop Scheduling or Flow Shop Scheduling can be interesting starting points

To use a genetic algorithm you don't need a perfect solution, you can start with N random candidates, and apply a fitness function to each of them, for example:

• The difference of nights assigned between the most busy doctor and the less busy worked is a penalization in the cost function
• Each time a doctor works more than 5 days per week or 1 night per week, you apply a penalty
• Each of your constraints, etc...

Generating N candidates you would pick the X best of them, they would be the ones the inflict the constraints the less. Working with them, crossing and mutating over several generations one can end up with a good solution.

Having talked all of that, every time I used a Genetic Algorithm that relied more on mutation that on crossing, I could develop a Simulated Annealing that would perform far better, with an easier implementation. The cost/fitness and the mutation function for genetic algorithm will probably be very similar to one used in a Simulated Annealing. I would start there, look at @Konrad Morawski answer

Google search find good results for Job Shop and GA

Answer 4

This is exactly the problem ASP was developed to solve. It is an optimized brute-force method thus the objectively optimal solution/s are derived with reasonable computational resources.

The downside? It's a weird programming paradigm, learning it is like learning Haskell for a C developer. But if you have extensively studied mathematical logic in your CS courses, you'll be fine (same for group theory and Haskell).