Preference scheduling for nurses using column generation

The purpose of this paper is to present a new methodology for scheduling nurses in which several conflicting factors guide the decision process. Unlike manufacturing facilities where standard shifts and days off are the rule, hospitals operate 24 hours a day, 7 days a week and face widely fluctuating demand. A more flexible arrangement for working hours and days off is needed, especially in light of the growing nursing shortage. To improve retention, management must now take into account individual preferences and requests for days off in a way that is perceived as fair, while ensuring sufficient coverage at all times. This multi-objective problem is solved with a column generation approach that combines integer programming and heuristics. The integer program is formulated as a set covering-type problem whose columns correspond to alternative schedules that a nurse can work over the planning horizon. A double swapping heuristic is used to generate the columns. The objective coefficients are determined by the degree to which the individual preferences of a nurse are violated. As part of the computational scheme, feasible solutions are refined to minimize the use of outside nurses, but when gaps in coverage exist, the outside nurses are distributed as evenly as possible over the shifts. The methodology was tested on a series of problems with up to 100 nurses using data provided by a large hospital in the US. The results indicate that high-quality solutions can be obtained within a few minutes in the majority of cases.