Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria

In some hospitals, an ‘open scheduling’strategy is applied to solve the operating room planning problem; i.e., surgeons can choose any workday for his surgical cases, and the staffing of anaesthetists and nurses is adjusted to maximize the efficiency of operating room utilization. In this paper, we aim at obtaining an efficient operating program for an operating theatre with several multifunctional operating rooms by using this ‘open scheduling’strategy. First, a mathematical model is constructed to assign surgical cases to operating rooms within one week. This model complies with the availability of operating rooms and surgeons, and its objective is not only to maximize utilization of operating rooms, but to minimize their overtime cost. Then a column-generation-based heuristic (CGBH) procedure is proposed, where four different criteria are compared with each other so as to find a solution with the best performance. In addition, the best approximate solution, obtained by this CGBH procedure after running all the criteria proposed, is compared with the lower bound obtained by an explicit column generation (CG) procedure, LP, to evaluate the distance between the approximate solution obtained and the optimum one. Although no criterion, according to the experimental results, is found superior to all other three in both robustness and quality of the solution obtained, it is found that the best solution obtained among those four criteria is often very close to LP, which means that the proposed algorithm can obtain a near optimal solution. In one word, the CGBH procedure proposed in this paper can obtain an efficient assignment of the surgical cases if the other resources (anaesthesia and nursing staff, equipment, beds in the recovery room etc.) are well organized.