Optimization Online


A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management

Kibaek Kim (kibaek.kim***at***u.northwestern.edu)
Sanjay Mehrotra (mehrotra***at***iems.northwestern.edu)

Abstract: 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.

Keywords: two-stage stochastic integer programs, L-shaped method, Benders' decomposition, workforce planning, multicut aggregation, branching on thin directions

Category 1: Stochastic Programming

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 01/09/2014
Entry Accepted: 01/09/2014
Entry Last Modified: 02/21/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society