Improving nurse scheduling by example: part 2 “fudging a solution”

Update: Karin seems to have lost interest in this, and therefore I shant be working any further on it. However since I started writing this post a couple of weeks ago, I may as well finish. Also as a side note, I officially spent more time writing the blog entry than I did writing any code, so poop.

The code still be here: git://gitorious.org/nurse-scheduler/nurse-scheduler.git

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.

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.

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

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.

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.

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

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.

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.

Download PDF

2 thoughts on “Improving nurse scheduling by example: part 2 “fudging a solution”

  1. Tonight while lonely and therefore re-reading my blog post, I noticed I screwed up pasting some of the code. If anybody notices, and actually asks; I will fix it.

  2. So I imported this blog entry after moving servers, and the code is totally messed up. Please see the gitorious links if you want actual code. kthxbye

Leave a Reply

Your email address will not be published.

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

This site uses Akismet to reduce spam. Learn how your comment data is processed.