Sequencing surgical cases in a day-care environment: An exact branch-and-price approach

In this paper we investigate how to sequence surgical cases in a day-care facility. We specify a multi-criteria objective function in which we minimize the peak use of recovery beds, the occurrence of recovery overtime and the violation of various patient and surgeon preferences. 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. We apply column generation to solve this combinatorial optimization problem and propose a dynamic programming algorithm to solve the pricing problem. The computational efficiency of this dynamic programming approach is validated through comparison with a mixed integer linear programming approach. In order to obtain integer variables, we embed the column generation loop in an enumerative branch-and-price framework. We elaborate on various branching strategies and branching schemes and examine their impact on the solution quality. The test instances for the computational experiments are generated using real-life data of the surgical day-care center at the academic hospital UZ Leuven Campus Gasthuisberg (Belgium). (C) 2008 Elsevier Ltd. All rights reserved.