I'm developing an application that optimally assigns shifts to nurses in a hospital. I believe this is a linear programming problem with discrete variables, and therefore probably NP-hard:
- For each day, each nurse (ca. 15-20) is assigned a shift
- There is a small number (ca. 6) of different shifts
- There is a considerable number of constraints and optimization criteria, either concerning a day, or concerning an emplyoee, e.g.:
- There must be a minimum number of people assigned to each shift every day
- Some shifts overlap so that it's OK to have one less person in early shift if there's someone doing intermediate shift
- Some people prefer early shift, some prefer late shift, but a minimum of shift changes is required to still get the higher shift-work pay.
- It's not allowed for one person to work late shift one day and early shift the next day (due to minimum resting time regulations)
- Meeting assigned working week lengths (different for different people)
So basically there is a large number (aout 20*30 = 600) variables that each can take a small number of discrete values.
Currently, my plan is to use a modified Min-conflicts algorithm
- start with random assignments
- have a fitness function for each person and each day
- select the person or day with the worst fitness value
- select at random one of the assignments for that day/person and set it to the value that results in the optimal fitness value
- repeat until either a maximum number of iteration is reached or no improvement can be found for the selected day/person
Any better ideas? I am somewhat worried that it will get stuck in a local optimum. Should I use some form of simulated annealing? Or consider not only changes in one variable at a time, but specifically switches of shifts between two people (the main component in the current manual algorithm)? I want to avoid tailoring the algorithm to the current constraints since those might change.
Edit: it's not necessary to find a strictly optimal solution; the roster is currently done manual, and I'm pretty sure the result is considerably sub-optimal most of the time - shouldn't be hard to beat that. Short-term adjustments and manual overrides will also definitely be necessary, but I don't believe this will be a problem; Marking past and manual assignments as "fixed" should actually simplify the task by reducing the solution space.