A GRASP-based algorithm for solving the emergency room physician scheduling problem

This paper addresses a physician scheduling problem in an Emergency Room (ER) requiring a long-term work calendar to allocate work days and types of shift among all the doctors. The mathematical model is created without simplifications, using the real calendar, including holidays. This precludes the possibility of cyclic-type solutions, and involves numerous and varied constraints (demand, workload, ergonomics, fairness, etc.). An effective solution to this very difficult practical problem cannot be obtained, for large instances, with exact solution methods. We formulate a mathematical representation of a real-world ER physician scheduling problem featuring a hybrid algorithm combining continuous linear programming with a greedy randomized adaptive search procedure (GRASP). Linear programming is used to model a general physician-demand covering problem, where the solution is used to guide the construction phase of the GRASP, to obtain initial full schedules for subsequent improvement by iterative application of Variable Neighborhood Descent Search (VNDS) and Network Flow Optimization (NFO). A computational study shows the superiority of our approach over the Integer Linear Programming method in a set of instances of varying size and difficulty inspired by a real setting. The methodology is embedded in a software tool for generating one-year-ahead physician schedules for a local ER. These solutions, which are now in use, outperform the manually-created schedules used previously.