A column generation-based algorithm for midterm nurse scheduling with specialized constraints, preference considerations, and overtime

Abstract This paper presents an augmented mixed-integer programming formulation for the nurse scheduling problem designed to accommodate overtime and several practical considerations that are part of the rostering process but have been absent in previous work. The goal is to minimize the sum of weighted uncovered demand and nurse preference violations over a one-month period. Model features include maximum number of consecutive working days and days off, minimum number of rest hours between shifts, vacations and birthdays. Preference violations are measured by the number of times certain days-off and days-on patterns appear in a nurse’s schedule, and the number of times an assignment contains a shift transition on two consecutive days. In addition, the formulation accounts for each nurse’s working status in the last few days of the previous month to ensure that constraints aren’t violated when new schedules are developed, and that preference violations are properly counted. The problem is solved in two stages due to the complexity of dealing with regular time and overtime in an integrated model. In Stage 1, a mixed integer program is used to assign shifts to nurses without exceeding their contracted regular hours. Column generation is applied to derive solutions. In Stage 2, a heuristic is developed to add overtime to the rosters found in Stage 1. This is done with the goal of minimizing total overtime hours while trying to balance each nurse’s workload. Experimental results are provided for instances with up to 60 nurses based on data obtained from a 1000-bed hospital. We conclude with a sensitivity analysis of the uncovered demand weight to determine its impact on solution quality and computational effort.