Scheduling Surgical Cases in a Day-Care Environment : A Branch-and-Price Approach

In this paper we will investigate how to sequence surgical cases in a day-care facility so that multiple objectives are simultaneously optimized. The limited availability of resources and the occurrence of medical precautions, such as an additional cleaning of the operating room after the surgery of an infected patient, are taken into account. A branch-and-price methodology will be introduced in order to develop both exact and heuristic algorithms. In this methodology, column generation is used to optimize the linear programming formulation of the scheduling problem. Both a dynamic programming approach and an integer programming approach will be specified in order to solve the pricing problem. The column generation procedure will be combined with various branching schemes in order to guarantee the integrality of the solutions. The resulting solution procedures will be thoroughly tested and evaluated using real-life data of the surgical day-care center at the university hospital Gasthuisberg in Leuven (Belgium). Computational results will be summarized and conclusions will eventually be formulated