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 :)

Probably worth looking at literature around the nurse rostering problem https://en.wikipedia.org/wiki/Nurse_scheduling_problem — Renaud M., Aug 13 '15 at 09:57
I am not an expert in this area, however if what you are looking for is an approach that would make you save some time on the development, it might be worth trying to model the problem as a Mixed Integer Programming Problem (https://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns) and then input it to a MIP solver, or as a constraint programming problem and then input it to a CP solver, such as OR-tools (https://developers.google.com/optimization/). This way all you have to do is express your problem. — Renaud M., Aug 13 '15 at 10:01
Do you have any previous scheduling data along with the constraints applied during that time? — JeffO, Aug 13 '15 at 11:05
[*Linear Programming*](https://en.wikipedia.org/wiki/Linear_programming) is guaranteed to derive the **optimal** solution! — recursion.ninja, Aug 13 '15 at 14:03
@RenaudM. It is a shame how few professional programmers understand this amazingly useful field of mathematics. Whenever someone suggests simulated annealing or genetic algorithms out side of the A.I. field, my gut response is: *Probably can be better modeled as a Linear Program optimization* — recursion.ninja, Aug 13 '15 at 14:18
Indeed, however with the exact approaches scaling might be an issue if the problem size tend to grow, it then requires quite some hindsight to improve the performances ;) — Renaud M., Aug 13 '15 at 14:21
@RenaudM. Agreed, simulated annealing is useful *after* you have determined that the Simplex algorithm for solving the Linear Program representation is not scaleable for your given problem. — recursion.ninja, Aug 13 '15 at 14:23
Between 20 and 60, for now. But ideally we will sell our product to different companies (not specifically doctors, but that is irrelevant), so ideallly, the algorithm should scale as much as possible. — Gil Sand, Aug 13 '15 at 16:40
Though id it's significantly more difficult, we could go for something less optimal and deliver an update at a later stage. This really depends on the approaches we will eliminate during the next few weeks. By the way, thank you all for your participation — Gil Sand, Aug 13 '15 at 16:42
@recursion.ninja Not really. It is guaranteed to derive the solution that minimizes/maximizes a cost function. Problem is: you don't really know which cost function is the best for the actual outcomes, you have to guess what you think is important and weight the different objectives. Moreover linear programming is bounded to linear objective functions, while a lot of times you'd want non linear such functions so it the "best" objective function may not even be expressible. — Bakuriu, Aug 13 '15 at 17:46
@Bakuriu I agree in spirit. When modeling the Linear Program you will have to make decisions on how to weight various objectives, and how to define the minimization function. However, you would need to do same thing by defining a fitness function for a genetic algorithm or by defining a heuristic function for simulated annealing. However, only Linear Programming is guaranteed to give you the *optimal* solution based on your chosen definitions. — recursion.ninja, Aug 13 '15 at 17:49

score 15 · Accepted Answer · answered Aug 13 '15 at 10:28

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.

Thanks for your answer, i'll dig a bit more into that with my colleague :) To give you more information : yes, we can rank most of the solutions/criteria, and we can decide if some have precedence over others. Also, they're really working on good faith now, and it's working well. They're dong it by hand and dont' use the " i can't work taht day " too much. It's quite nice how they get this working now since they really do it _by hand_. So a "viable" solution will already mean the world to them, and save them a LOT of brainstorming time of who can work when — Gil Sand, Aug 13 '15 at 10:34
@Zil the people currently creating the schedules are already probably using an informal algorithm. You could just speak to them and try to understand their decision process, then formalize and implement that. This would be way easier than setting up and training a neural network. — amon, Aug 13 '15 at 10:43
That's our first step :p we have a meeting with them already set up ! Thanks for all your help :) — Gil Sand, Aug 13 '15 at 10:44
For this use case, Genetics Algorithms are consistently inferior to Tabu Search and Simulated Annealing, as proven by the research competitions International Nurse Rostering Competitions. (But of course, they are still better than just a greedy algo.) — Geoffrey De Smet, Aug 14 '15 at 07:12

score 14 · Answer 2 · edited Apr 12 '17 at 07:31

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

I have used OptaPlanner (nee Drools Planner) with Simulated Annealing for a college timetable. Declare the models - a Shift has a time and a Doctor. Write declarative rules for the fitness function - hard constraints (a Doctor cannot take overlapping shifts) and penalties (Ann hates Mondays). Write declarative (thats the point!) swaps of shifts. OptaPlanner will create the starting state at random (may be infeasible), calculate the fitness function from the rules and even operate the swaps according to the optimization algorithm. You can choose and tune parameters like annealing schedule. — Jesvin Jose, Aug 13 '15 at 12:07

RMalke · Answer 3 · 2015-08-13T14:18:14.000

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

Vorac · Answer 4 · 2020-07-17T15:26:30.230

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

Calendar/Planning algorithm

4 Answers4