An improved Lagrangian relaxation heuristic for the scheduling problem of operating theatres

•We have developed bi-objective model for the scheduling problem of operating theatres.•The objectives are the relative cost of the operating theatre and the satisfaction of patients.•A Lagrangian relaxation method has been proposed.•A branch and bound algorithm has been presented to solve the dual problems.•Experiments have been designed to analyze the performance of the Lagrangian relaxation algorithm.

Due to the greatest importance of operating theatres in hospitals, this paper focuses on generating an optimal surgery schedule of elective-patients in multiple operating theatres, which considers three stages: the preoperative, perioperative, and postoperative stage. The scheduling problems of operating theatres allocate hospital resources to individual surgical cases and decide on the time to perform the surgeries in each stage. The problem consists of assigning patients to different resources in any surgical stage in order to minimize related costs of the system and maximize the satisfaction of patients. This paper establishes an integer programming model and presents a new Lagrangian relaxation algorithm for this problem. In this algorithm, precedence constraints are relaxed by Lagrangian multipliers. In this way the relaxed problem can be decomposed into multiple stage level subproblems, each of which corresponds to a specific stage. A branch and bound algorithm is designed for solving these subproblems via developing a lower bound and dominance rules. The multipliers are then iteratively updated along a subgradient direction. Finally, the new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after precedence constraints are relaxed, decompose the relaxed problem into stage level subproblems and solve the subproblems by using the dynamic programming algorithms. Numerical results show that the designed Lagrangian relaxation method produces better schedules with much smaller duality gap in acceptable computational time, especially for large-scale problems. Also, the case study shows that the application of the proposed theory results in noticeable cost saving.