We study the problem of integrated staffing and scheduling under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. The here-and-now decision is to find initial staffing levels and schedules, well ahead in time. The wait-and-see decision is to adjust these schedules at a time epoch closer to the actual date of demand realization. We find mixed-integer rounding inequalities for the second stage problem, which are shown to convexify the recourse function. As a result, we present a tight formulation that describes the convex hull of feasible solutions in the second stage. We develop a modified multicut approach in an integer L-shaped algorithm with a prioritized branching strategy. Using 3.5 years of patient volume data from Northwestern Memorial Hospital, we generate twenty instances of the staffing and scheduling problem in a realistic setting. We find that the stochastic programming based solutions save the cost of hiring more than three full-time nurses, when compared with schedules generated using the point forecast of patient census. Computational experiments show that our new approach significantly improves the computational efficiency both in terms of the required number of nodes and the computation time to solve the problem to optimality.
View A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management