Block scheduling in practice: An optimal decomposition strategy for nonidentical operating rooms
针对医院手术室排程中分块（两个科室共享手术室）带来的周转成本与患者流出的权衡问题，提出两阶段分解方法，将科室分配至天和手术室，减少分块65%，提升约束满足度。
Abstract We develop and implement a Master Surgery Schedule for a real‐life hospital, assigning operating room (OR) time to surgical specialties over a multi‐week horizon. Through action research, we identify a critical operational challenge: the issue of split blocks. Split blocks allow two specialties to share an OR on the same day—one in the morning, one in the afternoon. While this can improve consistent patient outflow, it also incurs additional turnaround costs. To address this trade‐off, we introduce an optimal two‐level decomposition approach. The first level assigns specialties to days using a mixed‐integer linear program with goal programming for the outflow. The second level refines these day‐level assignments by matching them to ORs through a series of small, independent problems. These can be solved efficiently by formulating it as a min‐cost max‐flow model, which assigns ORs to morning and afternoon blocks, respects specialty‐specific OR eligibility, and penalizes split blocks when needed. By separating the assignment to days from the assignment to rooms, the approach eliminates redundant, symmetric solutions and circumvents the combinatorial explosion that would otherwise result from jointly enumerating all specialty‐day‐OR combinations. From a practical perspective, we report on the implementation process, highlighting the essential role of hospital management's commitment, the use of iterative design rounds, and an internal advocate's support. We also illustrate the use of Pareto frontiers to communicate trade‐offs between turnaround costs and patient outflows. The implemented schedule reduces split blocks by 65%, improves constraint adherence, and demonstrates the value of operations research in healthcare.