A column generation-based approach to solve the preference scheduling problem for nurses with downgrading

The demand for nurses in virtually all western countries has been outpacing the supply for more than a decade. The situation is now at the point where the rules for good practice are being stretched to the limit and patient care is in jeopardy. The purpose of this paper is to present several ideas for maximizing the use of the available staff and to quantify the resultant benefits. Two approaches are investigated for substituting nurses with higher level skills for those with lower level skills where there is sufficient idle time to do so. Idle time is usually due to scheduling constraints and contractual agreements that prevent a hospital from arbitrarily assigning nurses to shifts over the week. When the substitution is skill-related, as it is here, it is often called downgrading. The models that we develop are for preference scheduling, which means that individual preferences are taken into account when constructing monthly rosters. There are several reasons for doing this in today's environment, the most important is the need to boost staff morale and increase retention. The problem is modeled as an integer program and solved with a column generation technique that relies on intelligent heuristics for identifying good candidate schedules. The computations show that high quality solutions, as measured by the reduction in the need for non-unit nurses as well as the degree to which preferences are satisfied, can usually be obtained in a matter of minutes.