A dedicated fix-and-relax decomposition method for operating room scheduling problem

This paper presents a heuristic approach for the operating room (OR) scheduling problem, building upon existing mixed-integer linear programming (MILP) formulations. The proposed method employs a planning horizon decomposition strategy, in which the overall scheduling horizon is divided into smaller sub-horizons. Within each sub-horizon, a fix-and-relax strategy is applied: decisions in earlier periods are progressively fixed, while later periods remain flexible to accommodate future adjustments. This decomposition-based heuristic enables the use of mixed integer programming techniques to efficiently find feasible high-quality solutions. Enhancements such as pre-assignment preprocessing and dynamic weight adjustments based on scheduling urgency further improve performance. Computational experiments demonstrate that this approach provides near-optimal solutions with significantly reduced computation times, making it a practical and scalable tool for real-world healthcare scheduling applications.