A new heuristic algorithm for the operating room scheduling problem

Due to the great importance of operating rooms in hospitals, this paper studies an operating room scheduling problem with open scheduling strategy. According to this strategy, no time slot is reserved for a particular surgeon. The surgeons can use all available time slots. Based on Fei et al.’s model which is considered to be close to reality, we develop a heuristic algorithm to solve it. The idea of this heuristic algorithm is from dynamic programming by aggregating states to avoid the explosion of the number of states. The objective of this paper is to design an operating program to maximize the operating rooms’ use efficiency and minimize the overtime cost. Computational results show that our algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not.

► We study an operating room scheduling problem with open scheduling strategy. ► We develop a heuristic based on dynamic programming by aggregating states to avoid the explosion of the number of states. ► An operating program is designed to maximize the operating rooms’ use efficiency and minimize the overtime cost. ► The algorithm is efficient, especially for large size instances where our algorithm always finds feasible solutions while the algorithm of Fei et al. does not.