We present a two-stage stochastic integer program for assigning Certified Registered Nurse Anesthetists (CRNAs) to Operating Rooms (ORs) under surgery duration uncertainty. The proposed model captures the trade-offs between CRNA staffing levels, CRNA handovers and under-staffing in the ORs. Since the stochastic program includes binary variables in both stages, we present valid inequalities to tighten the second-stage formulation, relax the integer restriction in the second-stage, and implement the L-shaped Algorithm to solve the stochastic program. We demonstrate the strength of the proposed valid inequalities by showing that they characterize the convex hull of a binary set determined by a subset of the second-stage constraints. An extensive computational study, based on the data from our partner institution, reveals that our proposed solution approach solves realistic problem instances near-optimally, underscoring the effectiveness of the proposed valid inequalities. Additionally, through sensitivity analysis, we provide insights into the trade-offs between CRNA staffing levels, CRNA handovers and under-staffing.
Article