22

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.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
  • I remember a certain keyword that might help (but not sure, since memory faded): column generation technique – Anonymous Feb 21 '09 at 20:25
  • I've read that this problem is *very* hard to solve in general. Also, there is a non-trivial possibility that it can actually be over-constrained. Best of luck. – dmckee --- ex-moderator kitten Feb 21 '09 at 20:36
  • What is the typical number of nurses required per shift? How many days will you typically schedule for? – j_random_hacker Feb 23 '09 at 11:16
  • A typical requirement is between 1 (night shift) and 5 (early shift on a working day). I'm currently planning to do the schedule for one month at a time, though I'll have to incorporate at least one constraint on the shift change between months. – Michael Borgwardt Feb 23 '09 at 12:53
  • Simulated Annealing shouldn't get stuck in local min's. CSP's are OK but honestly SA seems to beat them everytime for me. Added bonus of SA being super cheap. – ldog Jul 22 '10 at 07:07
  • I think your min-conflicts approach is a really good way to make the problem manageable. – Pete855217 Jan 05 '16 at 14:42

9 Answers9

13

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.

luapyad
  • 3,860
  • 26
  • 20
  • Wow, I hadn't thought that this would be the subject of that much reseach work. Thanks, I'll definitely look at some of those papers. Will edit the question to specify some of the factors you mention. – Michael Borgwardt Feb 21 '09 at 21:18
4

Umm, did you know that some ILP-solvers do quite a good job? Try AIMMS, Mathematica or the GNU programming kit! 600 Variables is of course a lot more than the Lenstra theorem will solve easily, but sometimes these ILP solvers have a good handle and in AIMMS, you can modify the branching strategy a little. Plus, there's a really fast 100%-approximation for ILPs.

nes1983
  • 15,209
  • 4
  • 44
  • 64
  • thanks for the pointer - I'll look into these and see if I can use them. – Michael Borgwardt Feb 21 '09 at 21:13
  • Good pointer, those solvers have been studied in much more depth than the OP will study his problem. You should probably point out that the ILP use heuristic searches as well (I think branch and bound.) – ldog Jul 22 '10 at 07:12
3

I solved a shift assignment problem for a large manufacturing plant recently. First we tried generating purely random schedules and returning any one which passed the is_schedule_valid test - the fallback algorithm. This was, of course, slow and indeterminate.

Next we tried genetic algorithms (as you suggested), but couldn't find a good fitness function that closed on any viable solution (because the smallest change can make the entire schedule RIGHT or WRONG - no points for almost).

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

  1. Randomize the input set (i.e. jobs, shift, staff, etc.).
  2. Create a valid tuple and add it to your tentative schedule.
  3. If not valid tuple can be created, rollback (and increment) the last tuple added.
  4. Pass the partial schedule to a function that tests could_schedule_be_valid, that is, could this schedule be valid if the remaining tuples were filled in a possible way
  5. If !could_schedule_be_valid, simply rollback (and increment) the tuple added in (2).
  6. If schedule_is_complete, return schedule
  7. Goto (2)

You incrementally build a partial shift this way. The benefit is that some tests for valid schedule can easily be done in Step 2 (pre-tests), and others must remain in Step 5 (post-tests).

Good luck. We wasted days trying the first two algorithms, but got the recommended algorithm generating valid schedules instantly in under 5 hours of development.

Also, we supported pre-fixing and post-fixing of assignments that the algorithm would respect. You simply don't randomize those slots in Step 1. You'll find that the solutions doesn't have to be anywhere near optimal. Our solution is O(N*M) at a minimum but executes in PHP(!) in less than half a second for an entire manufacturing plant. The beauty is in ruling out bad schedules quickly using a good could_schedule_be_valid test.

The people that are used to doing it manually don't care if it takes an hour - they just know they don't have to do it manually any more.

Andy
  • 11,215
  • 5
  • 31
  • 33
  • My requirements are different - the result is not either right or wrong, it can be anywhere on a continuous scale from "horrible" over "acceptable" to "perfect" - actually, a combination of individual scales for each person and day. – Michael Borgwardt Feb 21 '09 at 22:01
  • I assume that with "tuple" you mean the combinatin of assignments for one day or one worker? You describe a basic backtracking algorithm, with step 4 apparently a crucial optimization, but I don't see how do implement it efficiently - I guess it might be very specific for your requirements. – Michael Borgwardt Feb 21 '09 at 22:04
  • Yea, what I'm saying is that this algorithm is not optimal but is "good enough". It's quite simple, but works. It is O(N*M), at the very least. For this problem that doesn't equate to long runtimes because N,M are small. The optimization is in not building entire schedules before eliminating them. – Andy Feb 21 '09 at 22:33
  • If your schedules vary on a continuous scale, you can still use a branch and bound algorithm to keep track of the score of the current solution, backtracking when it gets worse than the current "best score". Update the global "best score" any time you find a better solution. – j_random_hacker Feb 22 '09 at 06:09
  • Interestingly, the B&B algorithm works much faster if, given a choice of what order to make decisions in, you make the worst possible choices as early as possible, since then the score of the current solution gets bad quickly, rapidly passing the cutoff and pruning the search space faster. – j_random_hacker Feb 22 '09 at 06:12
  • I'm not sure I can use a B&B algorithm since I think the number of variables means it's hard or even impossible to find a useable partition and calculate meaningful bounds on the remainder's fitness. – Michael Borgwardt Feb 22 '09 at 12:04
  • @Michael: I see. In that case consider branch & cut, which is much more powerful but hugely more complicated. (Synopsis: it's B&B, but you solve a linear relaxation of the problem remainder at each node.) AFAIK, the biggest optimisation problems are solved using either B&C or column generation. – j_random_hacker Feb 23 '09 at 11:13
2

Mike,

Don't know if you ever got a good answer to this, but I'm pretty sure that constraint programming is the ticket. While a GA might give you an answer, CP is designed to give you many answers or tell you if there is no feasible solution. A search on "constraint programming" and scheduling should bring up lots of info. It's a relatively new area and CP methods work well on many types of problems where traditional optimization methods bog down.

Grembo
  • 1,223
  • 7
  • 6
  • In my experience, Constraint Programming should indeed be able to handle the size of this problem. – willem Feb 01 '12 at 16:49
0

Using CSP programming I made programms for automatic shitfs rostering. eg:

  1. 2-shifts system - tested for 100+ nurses, 30 days time horizon, 10+ rules
  2. 3-shifts system - tested for 80+ nurses, 30 days time horizon, 10+ rules
  3. 3-shifts system, 4-teams - tested for 365 days horizon, 10+ rules,

and a couple of similiar systems. All of them were tested on my home PC (1.8GHz, dual-core). Execution times always were acceptable ie. for 3/ it took around 5 min and 300MB RAM.

Most hard part of this problem was selecting proper solver and proper solving strategy.

dlpx
  • 1
0

Metaheuristics did very well at the International Nurse Rostering Competition 2010.

For an implementation, see this video with a continuous nurse rostering (java).

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
0

I think you should use genetic algorithm because:

  • It is best suited for large problem instances.
  • It yields reduced time complexity on the price of inaccurate answer(Not the ultimate best)
  • You can specify constraints & preferences easily by adjusting fitness punishments for not met ones.
  • You can specify time limit for program execution.

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

    Genetic Algorithms Definition

    Genetic Algorithms Tutorial

    Class scheduling project with GA

Also take a look at :a similar question and another one

Community
  • 1
  • 1
Betamoo
  • 14,964
  • 25
  • 75
  • 109
  • Genetic programming is of little use with this kind of problem. To claim it as a valid solution, you need to do more than quotes its broad benefits, instead explaining its applicability to this kind of set coverage problem (the example you linked to is very different to this problem). Unfortunately, they're not there : genetic algorithms solve completely different kinds of problems. The difficult part of this problem is reducing the number of columns in its 0/1 matrix so that an LP solve is practical, but heuristics can help here. – Pete855217 Jan 05 '16 at 14:35
0

Dynamic programming a la Bell? Kinda sounds like there's a place for it: overlapping subproblems, optimal substructures.

Charlie Martin
  • 110,348
  • 25
  • 193
  • 263
  • I don't think the technique is applicable, since the subproblems influence each other and are therefore not independant and the solutions not reusable. – Michael Borgwardt Feb 21 '09 at 21:11
  • Dynamic programming is not applicableto this kind of problem. The problem is both common, and difficult to solve, with heavy use of heuristics. Research set covering problem, and the use of 0/1 matrices as the constraints for more information. Constraint programming as a technique is a possibility, but less appropriate than LP with well defined constraints. The objective function definition is where all the work is. Airlines face this problem with crew assignment (after LP generation of shifts ie. Patterns or trips/tours) and there are a number of software providers eg Carmen (see papers). – Pete855217 Jan 05 '16 at 14:19
  • (Cont). These kinds of problems end up with huge numbers of columns (eg. 300,000) and much of the processing is focussed on reducing the size of the problem heuristically. I have used GLPK successfully, but other commercial LP solvers are good too eg. Gurobi and CPLEX. – Pete855217 Jan 05 '16 at 14:22
0

One thing you can do is to try to look for symmetries in the problem. E.g. can you treat all nurses as equivalent for the purposes of the problem? If so, then you only need to consider nurses in some arbitrary order -- you can avoid considering solutions such that any nurse i is scheduled before any nurse j where i > j. (You did say that individual nurses have preferred shift times, which contradicts this example, although perhaps that's a less important goal?)

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169
  • Preferred shifts are not very important, but there are other differences between people that cannot be ignored, such as someone being exempt from night shifts due to medical conditions. – Michael Borgwardt Feb 21 '09 at 21:15
  • How can you word a constraint for a solver where nurse i can only be scheduled on shift n if nurse i is first scheduled with nurse j on some shift occurring before shift n? – RouteMapper Dec 23 '18 at 23:04
  • @RouteMapper: It depends what kind of solver you're using. In any case, you most likely need to quantify the variables i, j and n, e.g., "For a given n, and for every i < j, ...". BTW, if you mean for all i < j and for all n, then there's a contradiction here (no solution). If you mean for all i < j and a fixed n, I think you need n > j-i (and possibly higher than that) to avoid a contradiction. – j_random_hacker Dec 23 '18 at 23:40
  • @j_random_hacker I think I need to clarify. Every nurse i possesses different competences c. Each shift s has two nurses. Each s requires that nurses with certain competences c are scheduled to work that shift. Competences expire, at which time a nurse with expired competence c can no longer work a shift s requiring c. However, a nurse can be scheduled for s requiring c so long as there exists a shift s earlier in the week during which a nurse with requisite competence c is working alongside a nurse with the expired competence (so the expired one can be renewed). – RouteMapper Dec 23 '18 at 23:57
  • @RouteMapper: If competences "expire", then they are really functions of time (and perhaps other things). It's not clear what "a nurse with expired competence c" means -- does that mean that she does not have competence c at that time? – j_random_hacker Dec 24 '18 at 02:06
  • @j_random_hacker Yes, a nurse with an expired competence c means she does not have competence c at that time. – RouteMapper Dec 24 '18 at 02:07
  • @RouteMapper: In general, see if you can describe whether a nurse i has competence c at time t as a function NurseHasCompetence(i, c, t) that has value true or false. You may need other parameters, possibly up to a parameter s describing the complete schedule before time t. – j_random_hacker Dec 24 '18 at 02:09
  • @j_random_hacker - That sounds like exactly what I need. The schedule parameter s prior to any time t will be a bunch of IntVars representing shifts filled prior to t. Do you know of any examples where I can see this sort of structure? – RouteMapper Dec 24 '18 at 02:22
  • @RouteMapper: I'm afraid not. If you don't already have a solver in mind, I'd suggest MiniZinc as a good place to start -- constraints like this can be expressed quite easily in the Zinc language. – j_random_hacker Dec 24 '18 at 18:56