Midterm scheduling of physicians with flexible shifts using branch and price

A methodology is presented to solve the flexible shift scheduling problem of physicians when hospital administrators can exploit flexible start times, variable shift lengths, and overtime to cover demand. The objective is to minimize the total assignment cost subject to individual contracts and prevailing labor regulations. A wide range of legal restrictions, facility-specific staffing policies, individual preferences, and on-call requirements throughout the week are considered. The resulting model constructs shifts implicitly rather than starting with a predefined set of several shift types. To find high-quality rosters, a Branch-and-Price (B&P) algorithm is developed that uses two different branching strategies and generates new rosters as needed. The first strategy centers on the master problem variables and the second is based on the subproblem variables. Using data provided by an anesthesia department of an 1100-bed hospital as well as an extensive set of randomly generated test instances for 15 and 18 physicians, computational results demonstrate the efficiency of the B&P algorithm for planning horizons of up to 6 weeks.