What algorithm for assigning shifts (discrete optimization problem)

Question

I am 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:

• During each day, each nurse (approximately 15-20) is assigned a shift
• There are a small number (about 6) of different shifts
• There are a significant number of restrictions and optimization criteria regarding the day or relatively emplyoee, for example:
  • Every day there should be a minimum number of people assigned to each shift.
  • Some shifts overlap, so it’s normal if someone has fewer people at the start of the shift, if someone makes an intermediate shift
  • Some people prefer an early shift, some prefer a late shift, but a minimum of shift changes is required to get a higher shift paycheck.
  • It is not allowed that one person worked with a delay of one day and with an early shift the next day (due to the minimum rules for rest time).
  • Meeting with appointed work weeks (different for different people)
  • ...

Thus, basically there is a large number (from 20 * 30 = 600) of variables, each of which can take a small number of discrete values.

I am currently planning to use the modified Min-conflict algorithm

• start with random assignments
• have a fitness function for every person and every day
• choose the person or day with the worst fitness value
• select a random one of the appointments for this day / person and set it to a value that will result in an optimal fitness value
• repeated until the maximum number of iterations is reached or improvement is found for the selected day / person

Any better ideas? I am somewhat worried that he will be stuck in a local optimum. Should I use some form of simulated annealing ? Or take into account not only changes in one variable at a time, but, in particular, shift switches between two people (the main component in the current manual algorithm)? I want to avoid adapting the algorithm to current constraints, as they can change.

Edit: there is no need to find a strictly optimal solution; the list is currently manual, and I’m sure that the result is far from optimal in most cases - it should not be difficult to beat it. Short-term adjustments and manual overrides will also be needed, but I do not think this will be a problem; Marking past and manual appointments as “fixed” should actually simplify the task, reducing the solution space.

Answer 1

This is a complex problem that is well resolved. There was a lot of scientific work on this issue, especially in the Operations Research section - see, for example, reference materials for nurses 2007-2008. or just google "research on registration of nurses". Complexity also depends on such aspects as: how many days need to be resolved; what type of “requests” a nurse can make; is a circular registry; is it a long-term plan or should it handle a short-term “repair”, such as illness and swaps, etc. etc.

The algorithm you describe is heuristic . You may find that you can configure it to work well for one specific example of a problem, but once something has changed, it may not work as well (for example, local optimization, poor convergence).

However, this approach may be appropriate depending on your specific business needs - for example, how important it is to get the best solution, a sketch of the problem that you are expected to remain the same, what are the potential savings (money and resources), how important is the nurse’s perception of their quality registries, what is the budget for this job, etc.

Answer 2

Umm, did you know that some ILP solvers do pretty well? Try AIMMS, Mathematica, or the GNU programming kit! 600 Variables is, of course, much more than the Lenstra theorem, which will be easily solved, but sometimes these ILP solvers have a good handle, and in AIMMS you can slightly change the branching strategy. In addition, there is a really fast 100% approximation for ILP.

Answer 3

I solved the problem of assigning shifts for a large production plant recently. First, we tried to generate purely random graphs and return any passed is_schedule_valid test - a backup algorithm. It was, of course, slow and uncertain.

Next, we tried to use genetic algorithms (as you said), but could not find a good fitness function that closed on any viable solution (since the smallest change can make the entire schedule CORRECT or INCORRECT - no points for almost).

Finally, we chose the following method (which works great!):

• Randomize a set of input data (i.e. jobs, shift, personnel, etc.).
• Create the correct tuple and add it to the preliminary schedule.
• If the correct tuple could not be created, rollback (and increase) the last tuple added.
• Pass a partial schedule to a function that checks could_schedule_be_valid , that is, can this schedule be valid if the remaining tuples were filled in a possible way.
• If !could_schedule_be_valid , just rollback (and increase) the tuple added to (2).
• If schedule_is_complete , return schedule
• Go (2)

You gradually create a partial shift in this way. The advantage is that some tests for a valid schedule can be easily performed in step 2 (preliminary tests), while others should remain in step 5 (post-tests).

Good luck. We spent days trying the first two algorithms, but got the recommended algorithm that generates valid schedules instantly in 5 hours of development.

In addition, we supported pre-commit and post-commit assignments that the algorithm would follow. You simply did not randomize these slots in step 1. You will find that solutions should not be anywhere near optimal. Our O (N * M) solution is at least, but implemented in PHP (!) In less than half a second for the entire production factory. Beauty quickly eliminates bad graphics using the good could_schedule_be_valid test.

People who are used to doing it manually do not care if it takes an hour - they just know that they no longer need to do it manually.

Answer 4

Mike,

I don’t know if you have a good answer to this, but I’m sure that programming constraints is a ticket. While GA can give you an answer, CP is designed to give you many answers or tell you if there is no acceptable solution. A search for “restriction programming” and scheduling should contain a lot of information. This is a relatively new area and CP methods work well on many types of problems where traditional optimization methods are afraid.

Answer 5

Dynamic programming a la Bell? Kinda sounds like a place for him: overlapping subtasks, optimal substructures.

Answer 6

One thing you can do is try to find symmetries in the problem. For example. Can you consider all nurses as equivalent for the purpose of the problem? If this is the case, then you only need to consider the nurses in some arbitrary order - you can avoid considering the decisions so that any nurse I should be scheduled before any nurse j, where i> j. (You said that individual nurses prefer shift times, which contradicts this example, although perhaps this is a less important goal?)

Answer 7

I think you should use a genetic algorithm because:

• It is best suited for large instances of problems.
• This gives reduced time complexity at the price of an inaccurate answer (not the best)
• You can easily identify restrictions and preferences by adjusting fitness penalties for non-working people.
• You can specify time limits for program execution.

• The quality of the decision depends on how much time you intend to spend on the decision of the program.

  Definition of genetic algorithms

  Genetic Algorithm Tutorial

  Class Planning Project with GA

Also look at a similar question and another

Answer 8

Using CSP programming, I developed programs for automatically backing up shitfs. eg:

• 2-shift system - tested for over 100 nurses, 30-day horizon, 10+ rules
• System with 3 shifts - tested for 80+ nurses, 30-day horizon, 10+ rules.
• 3 second system, 4 teams - checked for the horizon of 365 days, 10+ rules,

and several similar systems. They were all tested on my home PC (1.8 GHz, dual core). The lead time was always acceptable, i.e. for 3 / it took about 5 minutes and 300 MB of RAM.

The most difficult part of this problem was choosing the right solver and the right solution strategy.

Answer 9

Metaheuristics did very well at the 2010 International Nursing Training Competition .

For implementation, see this video with a continuous list of nurses (java) .