摘要
手术计划是优化医疗资源配置的重要组成部分,涉及众多的不确定性,是目前医疗管理领域研究的热点和难点问题.本文聚焦于考虑急诊病人随机手术时长需求的择期病人手术计划问题研究,在各个手术室具有异质性的情况下,优化手术室的超时成本和闲置成本,并为一个计划周期内的择期手术进行手术室和手术日期的分配.建立了一个0-1整数规划模型,针对问题情境和手术计划特有的约束条件提出了满足问题特性的分支定界和列生成相结合的精确型分支定价求解算法.其中在分支定界算法上,通过对比选择适合问题特性的节点选择策略,并且提出了分步分支策略加快搜索过程.为加快列生成算法的求解,通过数值积分和等价转换将带有不确定性的子问题转变为一个0-1背包问题的变形,然后设计动态规划算法进行求解.数值实验表明,根据问题特性设计的分支定价算法可有效求解具有不同实例规模下的手术计划问题,和CPLEX相比,大规模情形下能够在可接受的计算时间内得到问题最优解.
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-andbound 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 largescale operating room planning problem within acceptable time.
作者
王建军
缪鸿儒
李播
姜万维
WANG Jianjun;MIAO Hongru;LI Bo;JIANG Wanwei(Institute of Systerns Engineering,Dalian University of Technology,Dalian 116023,China;The Second Department of Anesthesia,Affiliated Zhongshan Hospital of Dalian University,Dalian 116001,China)
出处
《系统工程理论与实践》
EI
CSSCI
CSCD
北大核心
2018年第9期2348-2362,共15页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(71672019,71271039)~~
关键词
手术室计划
急诊病人
0-1整数规划
列生成
分支定价
operating room planning
emergent patients
binary integer programming
column generation
branch-and-price
