Dumbing Things Up

Improving nurse scheduling by example: part 2

written by ben on 2012-08-19

The code still be here

The distinction between an engineer, and a scientist/mathematician is that the latter must come to a precise answer or be considered a failure, whereas the former need only improve on the existing situation/solution. As I mentioned in the previous post, I had already determined I couldn't "solve" the problem, all I can do is make it better (+1 engineer, -1 scientist).

What is quickly observable is that determining whether or not the all of the request can fit within the schedule constraints are successful is a relatively easy problem to solve.  The following function is sufficient. It assumes there is a function kosher() which determines whether or not the schedule fits within the parameters.

private boolean good(NurseList nurses) {
    Integer[] days = schedule.clone();
    for (Nurse n : nurses) {
        for (Integer d : n.getRequest()) {
            days[d]++;
        }
    }
    return kosher(days);
}

Such an event, where the staff chooses a qualifying schedule is quite rare. Since it takes a significant amount of human time to figure out, it's also easily overlooked. So the simple function above already improves on the current situation.

Without further adieu, here is the meat of the algorithm. What we do is try our best, and as soon as something fails we give up and ask for human intervention giving as much information as possible. Basically, "return null" means we need human intervention. If the GUI got developed further it would have been some kind of exception thrown with the relevant information in there.

First, see if everyone can get what they want.

if (this.good(nurses))
    return do_build(nurses);

Then we give priority to the charge nurses. If their schedule doesn't work, we need human intervention.

set(nurses.getChargeNurses());
if (above_max(schedule)) {
    System.err.println("Charge nurse fail");
    return null;
}
// Charge nurses are done. Take em out.
nurses.removeAll(nurses.getChargeNurses());

There are two ways to solve the scheduling problem. If we use "unhappiness" as a description of how far off a schedule was compared to the request, we can: 1) spread out the unhappiness evenly, or 2) make fewer people unhappy. Since the latter seemed easier to program we did that with the idea being that we'd keep track of the unhappy nurses and give them priority in the next week (similar to how we prioritize charge nurses above.

What the below does is randomize the list of nurses requests and adds them one by one until there is a failure. It then takes the number of unhappy nurses to use as a metric for overall success of the list. Say for example, 2 nurses don't get their schedule. The algorithm will attempt to get all combinations of 2 nurses which satisfy the problem. It would then allows the person at the interface to pick and choose things as they desire.

int unhappy = nurses.size();
ArrayList potential_winners = new ArrayList<>();
NurseList temp;

for (int i = 0; i < iterations; i++) {
    Collections.shuffle(nurses);
    temp = new NurseList(nurses);
    int temp_count = unhappy_count(temp, schedule.clone());
    temp = new NurseList(nurses);

    if (temp_count

Because the algorithm is really dumb, we recorder a bunch of non-optimal solutions. We can simply remove those before we give the user any choices.

Iterator iter = potential_winners.listIterator();
while (iter.hasNext()) {
    NurseList nlist = iter.next();
    if (nlist.size() != unhappy) {
        iter.remove();
    }
}

Then we remove any duplicates, again because our implementation was naive.

Set templist = new LinkedHashSet(potential_winners);
potential_winners.clear();
potential_winners.addAll(templist);

Finally, this is where we'd pop up a GUI showing the potential people we can make unhappy, and what the schedule looks like if we remove those people.

    /*
    for (NurseList nlist : potential_winners) {
        System.out.print("If you were to remove " + nlist + "n");
        NurseList temp1 = new NurseList(nurses);
        temp1.removeAll(nlist);
        System.out.println(Arrays.toString(do_build(temp1)));
        System.out.print(nurses + "nn");
    }
    */
    return null;

That's all. The code can be improved a lot, but what you get is a list of people to make unhappy, and with a GUI it would show gaps in the schedule. The nurse doing the scheduling could then approach those people and ask them to pick empty spots in the schedule (assuring them they will get their choice next ).

I'm sorry if you read all that.