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 🙂
Best Answer
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.