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

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.