An Exploration of Mixed Integer Programming Techniques as Applied to the Residency Scheduling Problem

Abstract

Upon graduation from medical school, doctors enroll in residency programs in order to get the necessary training to become a board certified doctors in a specific specialty. During each year of residency, doctors rotate between different sub specialties or clinics in order to meet different educational requirements, elective desires, and staffing demands. The process of creating an annual schedule for a residency program is an extremely tedious one that is usually done manually and more often than not falls on the shoulders of one individual - either the chief resident or a member of the hospital staff. Given the difficulties of creating such a robust schedule manually, there is strong motivation for the development automated processes that can create optimal schedules for residency program. However, proposed methods fail to solve the problem to optimality in a guaranteed reasonable amount of time. This thesis explores various mixed integer programming techniques for solving the residency scheduling problem - namely the use of an SMT optimization solver on the problem and the decomposition of the problem using a column generation scheme.