随机急诊需求下基于分支定价算法的手术计划研究

手术计划是优化医疗资源配置的重要组成部分,涉及众多的不确定性,是目前医疗管理领域研究的热点和难点问题.本文聚焦于考虑急诊病人随机手术时长需求的择期病人手术计划问题研究,在各个手术室具有异质性的情况下,优化手术室的超时成本和闲置成本,并为一个计划周期内的择期手术进行手术室和手术日期的分配.建立了一个0-1整数规划模型,针对问题情境和手术计划特有的约束条件提出了满足问题特性的分支定界和列生成相结合的精确型分支定价求解算法.其中在分支定界算法上,通过对比选择适合问题特性的节点选择策略,并且提出了分步分支策略加快搜索过程.为加快列生成算法的求解,通过数值积分和等价转换将带有不确定性的子问题转变为一个0-1背包问题的变形,然后设计动态规划算法进行求解.数值实验表明,根据问题特性设计的分支定价算法可有效求解具有不同实例规模下的手术计划问题,和CPLEX相比,大规模情形下能够在可接受的计算时间内得到问题最优解.

A branch-and-price algorithm for operating room elective surgery planning under stochastic demand of emergency

As a critical part of allocation of healthcare resources, operating room planning is a hot and hard issue due to the various effects of uncertainty on surgical schedules. This study focuses on operating room planning problem and considers the uncertain demands of emergent patients at the same time, in order to provide a robust and profitable planning scheme for the hospitals. We assume that operating rooms are heterogeneous and multi-functional. The objectives are to minimize the sum of overtime and idle time of all operating rooms, and scientifically assign dates and rooms to elective surgeries within a planning horizon. A binary integer programming model is presented and an exact branch-and-price algorithm is developed based on the definitions of the problem and characteristics of the model, which embeds the branch-and-bound and the column generation. We compare and select an appropriate node-selection strategy and propose a step-by-step branch strategy to accelerate the searching process in branch-and-bound algorithm. In order to accelerate the column generation program, we use numerical integration and equivalent conversion to transform the sub-problem with uncertainty into a variant of binary knapsack problem. Then we solve it by dynamic algorithm. Numerical results show that the branch-and-price algorithm can efficiently obtain the exact optimum solutions for the proposed operating room planning problems under different practical scales, comparing to CPLEX, the presented algorithm can solve large-scale operating room planning problem within acceptable time.