Operating rooms planning using Lagrangian relaxation technique

This paper addresses the elective surgery planning problem when the operating rooms' capacity is shared between elective and emergency patients. The planning problem consists in determining the set of elective patients that would be operated in each period over a planning horizon in order to minimize patients related costs and overtime costs of operating rooms. A stochastic integer programming model is proposed. Lagrangian relaxation is used to decompose the planning problem into period-level sub-problems that are solved by a dynamic programming method. The dual problem is solved iteratively using a sub-gradient algorithm. Feasible plans are derived from relaxed solutions using a heuristic and improved with a "local search heuristic". This approach results in both near-optimal solution and a lower bound to assess the degree of optimality. Numerical experimentations show that solutions within 1% of the optimum are obtained in a short computation time for problems of practical sizes.