Aggregated state dynamic programming for operating theater planning

This paper studies operating room planning which is now a very important topic for hospitals due to budget restrictions and aging population. Both block scheduling and open scheduling strategies are considered. Based on the model of Fei et al. which is considered to be close to reality, we develop a heuristic that can be applied to each of these strategies. This heuristic stems from the idea of dynamic programming by aggregating states to avoid the exponential increasing of the number of states. Our objective is to develop a general method based on this idea to solve a series of set partitioning problems. Computational results show that our algorithm is competitive and requires less computation time than existing methods.