We present a two-stage stochastic programming model for scheduling anesthesiologists to operating rooms under uncertainty in surgery durations. The proposed model takes a relief order to balance anesthesiologists’ workload as input and captures the trade-offs between anesthesiologist relief times, handoffs and under-staffing. To address the computational challenges of solving the proposed model, we derive supervalid equalities that exploit the structure of the second stage. Subsequently, we develop a tight monolithic reformulation whose size, in terms of variables and constraints, is independent of the number of scenarios. To further strengthen the formulation, we introduce valid inequalities for the first-stage problem and show that they describe convex hull of binary sets induced by subsets of the first-stage constraints. Our computational experiments, based on data from a tertiary medical center, show that the proposed reformulation significantly outperforms both the extensive form and the L-shaped algorithm. Compared with current practice, the proposed framework reduces handoffs and under-staffed periods while allowing anesthesiologists to be relieved earlier under uncertain surgery durations. Ultimately, the proposed approach supports data-driven workforce planning and policy design to align anesthesiologist schedules with institutional priorities to reduce handoffs and under-staffing.