Which algorithm for assigning shifts (discrete optimization problem)
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.
Answer
This is a difficult problem to solve well. There has been many academic papers on this subject particularly in the Operations Research field - see for example nurse rostering papers 2007-2008 or just google "nurse rostering operations research". The complexity also depends on aspects such as: how many days to solve; what type of "requests" can the nurse's make; is the roster "cyclic"; is it a long term plan or does it need to handle short term rostering "repair" such as sickness and swaps etc etc.
The algorithm you describe is a heuristic approach. You may find you can tweak it to work well for one particular instance of the problem but as soon as "something" is changed it may not work so well (e.g. local optima, poor convergence).
However, such an approach may be adequate depending your particular business needs - e.g. how important is it to get the optimal solution, is the problem outline you describe expected to stay the same, what is the potential savings (money and resources), how important is the nurse's perception of the quality of their rosters, what is the budget for this work etc.