Tuesday, May 11, 2010

Automated nurse rostering based on hard and soft constraints with Drools Planner

The optimal solution for a planning problem is the solution with the highest score. But how do we calculate and compare scores?

In a previous blog, I have shown that there's no easy way to find the optimal solution in for example the bin packaging use case. Today I 'll use the nurse rostering use case to explain scoring based on hard and soft constraints.

The use case

In the nurse rostering rostering use case, we assign nurses to work shifts in a hospital. We want to increase quality of service, minimize staff size and maximize staff contentment.


In the example above, on the Monday morning we need 1 maternity nurse. Both solutions assign nurse C to that shift. As you can see, the solution on the right is better, because it breaks less constraints.

Each solution has a score and Drools Planner will look for the solution with the highest score. In some use cases the score is a single integer (SimpleScore), but in other use cases, such as this one, there are both hard and soft constraints (HardAndSoftScore).

Hard constraints

Hard constraints need to be fulfilled. We always look for the solution with the least hard constraints broken.

The example above shows 2 hard constraints. The solution is feasible when none of the hard constraints are broken. The hospital can work with any feasible solution, but still they prefer some feasible solutions over others...

Soft constraints

Soft constraints should be fulfilled as much as possible. Of all the feasible solutions, we look for the solution with the least soft constraints broken.

The example above shows some of the soft constraints of the nurse rostering use case. But if you talk to a business analyst, you 'll discover that there are many more and you need something which makes adding extra constraints easy. Something like Drools Planner.

No comments:

Post a Comment