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.
Medical system is facing a state of change. For patients, as the population aging in many countries, the number of patients is increasing rapidly. Regarding the technical constraints and human resource constraints in hospitals, a large part of patients cannot be processed immediately. The longer they wait, the less satisfied they are. Whereas on another side, hospitals, especially public ones, suffer from a great amount of budget deficit. They seek to increase the medical service efficiency and decrease the medical service cost in order to balance the budget.
Litvak and Long (2000) pointed out that the operating theater can be seen as the engine of a hospital. Many other resources like anesthetists and patient beds highly depend on the operating room planning. The control of operating rooms becomes more and more important in the decade years. But in reality, the operating rooms, as key resources, often lead to a great time waste. Weinbroum, Ekstein, and Ezri (2003) investigated 10 operating rooms in a medical center and found that the waste time reached 15% of the total time. So, appropriate scheduling of operations and matching patient requirements with operating rooms and surgeons, in order to increase the efficiency of the operating rooms, are significant research topics in medical care.
In the past decade, researchers focused on the operating room scheduling problems from both modeling and algorithmic points of view. Fei, Chu, and Meskens (2008) used a heuristic method based on column generation to minimize the total cost of operations. Kuo, Schroeder, Mahaffey, and Bollinger (2003) considered the availability of surgeons and the operating room opening hours as constraints, established a linear programming model and solved it by Excel software. Marcon, Kharraja, and Simonnet (2001) proposed an integer linear programming model, solved by Cplex software. Dexter, Macario, Traub, Hopwood, and Lubarsky (1999) used computer simulation to model operating room scheduling to find an optimal scheduling strategy to maximize the use of operating room block time. Kharraja, Chaabane, and Marcon (2004) realized the minimum makespan of operating rooms. Sier, Tobin, and McGurk (1997) took into account more constraints, like the patients’ age, the patients’ priority, the operations’ allocation rule. The obtained mathematical model is nonlinear.
With respect to its great significance for both patients and hospitals, there is quite little research on operating room management. In this paper, we focus on Fei et al.’s models (Fei et al., 2008 and Fei et al., 2010). These models are close to the reality and consider both block scheduling and open scheduling strategies. As block scheduling is a special case of open scheduling, we study only the open scheduling model and develop a heuristic algorithm. This algorithm comes from the dynamic programming idea by aggregating states to avoid the explosion of the number of states. This idea was successfully applied by Chu and Antonio (1999) to solve a one-dimensional cutting stock problem. In general, it keeps a global view of the overall optimization problem, in contrast to other myopic methods where the solution is constructed very locally in a step-by-step manner. This algorithm can also be used in meta-heuristics or branch-and-bound procedures to generate one of the initial solutions.
The paper is organized as follows. Section 2 describes the open scheduling strategy. Section 3 presents the general method. Section 4 states the detailed procedure for solving subproblem. Section 5 gives a numerical example. Section 6 reports computational results to evaluate the performance of this algorithm. Section 7 concludes the paper.
This paper uses a new heuristic algorithm to solve operating room scheduling problem with open scheduling strategy. This problem is very common in operating room planning for hospitals and the research is far from being enough. Our algorithm stems from the idea of dynamic programming by aggregating states to avoid the explosion of the number of states. This idea was firstly proposed by Chu and Antonio (1999) to solve a cutting stock problem. The computational results show that this algorithm is effective. Compared with Fei et al.’s results, we found feasible solutions for all test instances while Fei et al. failed, especially for large size instances. These results make us believe that this algorithm should be paid attention and would become a useful general method to solve a series of set partitioning problems. It could also become a method used in meta-heuristics or a branch-and-bound procedure to generate one of the initial solutions.
