Solving midterm and short-term nurse scheduling problems

As in many service organizations, hospitals use a variety of shift types when scheduling nurse resources. In general, the operational decisions of workforce planning can be divided into two interrelated problems: (1) midterm planning in terms of shift assignments for up to six weeks at a time, and (2) the short-term daily adjustment of schedules. Individual nurse profiles are a function of a unit's skill requirements, labor laws, and other qualifications, and are results of the long-term planning decision. At the midterm level, the goal is to match nurse resources with the expected workload over the planning horizon. Rosters are designed to maximize personnel preferences as well as minimize cost. To investigate this problem, a large-scale integer program model was developed and solved with two methodologies. The first is based on Lagrangian Relaxation based heuristic, which uses a combination of subgradient optimization and Bundle methods, with variable fixing strategy and IP-based heuristic. The second methodology is a branch-and-price algorithm that makes use of several new branching rules, an extremely effective rounding heuristic, a dual bound procedure, and specialized aggregation scheme. To extend the algorithms to solve different levels of nursing skills, a downgrading strategy is used by giving scheduling priorities to higher level of worker. The midterm schedules provide a blueprint for the monthly work assignments of the staff. Because of absenteeism and unpredicted demand fluctuations, though, a hospital-wide reallocation of resources is needed on a daily basis. While the overall goal is to ensure adequate coverage at minimize cost, a secondary goal is to minimize changes to the assigned rosters. Nevertheless, to allow more flexibility, nurses are permitted to work in several units during a shift rather than just their home unit. An IP-based column generation methodology was developed to solve this problem and applied within a rolling horizon framework. The idea is to consider 24 hours at a time, but implement the results for only the first 8 hours. All algorithms were tested on data obtained from a 400-bed US hospital. The results show an order-of-magnitude improvement over current approaches in terms of solution quality and computation times.