Nurse scheduling with built-in flexibility

The nurse scheduling problem (NSP) involves assigning nurses to shifts while balancing institutional staffing requirements and individual preferences. Traditional approaches often produce rigid schedules that do not account for unforeseen last-minute constraints faced by nurses. To address this, we introduce novel flexibility mechanisms: shift flips and nurse swaps. A shift flip allows a nurse to interchange a working day with a day off, provided that the new schedule remains feasible. A nurse swap extends this concept by allowing two nurses to exchange assignments, ensuring mutual benefit without compromising staffing needs. We first solve the NSP without flexibility using a Column Generation algorithm to generate individual rosters. Because flips and swaps have to be mutually beneficial, their pricing cannot be embedded in the Column Generation framework. Then, a preprocessing step lists for each roster all the feasible flips and swaps. We formulate a mixed-integer programming (MIP) model, composed of the column generation restricted master problem to which is added a set of flexibility constraints. The model ensures a minimum level of swap opportunities while optimizing overall scheduling costs and respecting demand constraints. We propose different swap pricing strategies and analyse the balance between flexibility and operational costs. Experimental results demonstrate the possibility of incorporating flexibility without being detrimental to operating costs. By embedding these concepts into scheduling frameworks, we provide a practical solution for hospitals and healthcare institutions seeking to improve both efficiency and staff well-being.