医院手术调度问题的两阶段鲁棒优化方法研究

王 昱，唐加福

（1.东北大学流程工业综合自动化国家重点实验室，辽宁 沈阳110819；2.沈阳农业大学经济管理学院，辽宁 沈阳110866；3.东北财经大学管理科学与工程学院，辽宁 大连116025）

医院手术调度问题的两阶段鲁棒优化方法研究

王 昱1,2，唐加福3

（1.东北大学流程工业综合自动化国家重点实验室，辽宁 沈阳110819；2.沈阳农业大学经济管理学院，辽宁 沈阳110866；3.东北财经大学管理科学与工程学院，辽宁 大连116025）

手术服务时间受患者身体状况，医生技术水平等因素影响，具有不确定性.如何有效地调度患者手术成为医院管理的一大挑战.研究了医院的手术调度问题，以院方收益最大为目标，在考虑患者最迟手术日期限制的情况下，建立了手术调度问题的确定型模型.进一步考虑手术服务时间的不确定性，将手术的服务时间表示为有界区间，考虑了管理者风险偏好对患者服务时间不确定集的影响，在确定型模型的基础上，提出了区间型手术调度问题的两阶段鲁棒优化方法.数值实验结果表明，将鲁棒优化运用于手术调度问题，能够减小服务时间不确定性给医院效益带来的影响.同时，考虑最迟手术日期会降低医院收益，最大收益差可达到10.7%.

1 引 言

近年来，我国医改各项工作不断推进，随着医疗体制改革的深化，医疗服务业引发了全社会的关注.医疗机构自负盈亏，在有限的医疗服务资源和激烈的市场竞争双重压力下，医院管理者越来越重视医院效率和服务品质.手术部在医院利润中所占的比例最大［1,2］，且服务品质直接关系到患者的健康乃至生命，因此，手术部受到管理者和病人的高度重视.优化安排患者手术日程，提高医院收益，减少患者调度过程中的不合理现象，创造一个良好的就诊环境成为手术部管理者的目标.所谓手术调度问题，实质上是根据患者需求和医院的手术能力，产生一段时间内，满足一定约束条件的手术时间表的过程.广义的手术调度除手术时间的调度外，还包括手术地点、医护人员、手术器械等相关资源的调度.科学、合理、高效的手术安排更加人性化，使患者在较为合理的时间段进行手术，良好的控制病情的发展；同时高效的利用的手术资源，为医院带来了巨大的经济效益.

医院的手术服务时间具有较大的不确定性，手术时长受医生技能水平、疲劳程度、患者身体状态等多方面因素影响，难以准确给出手术服务时长的确定值.因此，在考虑手术服务时间为定长情况下的手术调度方案鲁棒性较差，在医院实际运作中往往偏差较大甚至无法实施.手术服务的内在不确定性给院方手术调度带来了巨大的困扰，近年来，手术调度问题也吸引了学者的关注.随机规划和鲁棒优化方法是解决不确定问题的强大工具.随机规划方法需要已知随机参数的分布函数.通过对大量的历史数据的分析，Strum等［3］发现手术服务时间可以近似用对数正态或者正态分布来描述.Lamiri等［4］假定手术需求服从正态分布，提出了手术室能力分配的随机规划模型，并使用蒙特卡罗近似法模拟患者的需求情景，将随机规划模型转换为标准的混合整数规划模型进行求解.Batun等［5］获取了爱尔兰某医院的患者就诊数据，模拟患者服务时间的分布函数，以医院最小运作成本为目标建立了两阶段随机规划模型，决策患者的手术顺序、时间及地点.

随机规划方法依赖于历史数据和分布规律.然而，在医院的实际调度当中，患者的就诊数据往往是不充足的，难以准确描述患者服务时间的分布.因此，我们使用鲁棒优化方法来求解手术调度问题.不确定优化问题的鲁棒解是最坏不确定情景下使目标函数具有最优值的解，它的一个重要特点是对于任何具体的情景，鲁棒解只是近似最优解，但是对于整个不确定集合是最优的［6,7］.传统的优化方法在系统的内部参数或者外部环境变化时往往显得无能为力，得到的优化结果与实际偏差很大.鲁棒优化方法在系统的内部结构和外部环境发生变化时，仍然能够保持系统的功能［8］.因此，鲁棒优化在求解不确定优化问题时凸显了其巨大的优势.

在手术调度系统中，来自手术操作过程、术中突发状况等不确定性都会直接影响到调度方案能否顺利实施.在这些不确定因素的作用下，鲁棒性成为能否确保医院手术部收益和患者服务质量的重要因素.在国际上，鲁棒优化在医院管理中的应用还处于起步阶段.迄今为止，使用鲁棒优化方法求解手术室优化调度问题的文章只有3篇.2010年，Denton等［9］首次将鲁棒优化方法应用到医院手术室优化调度中，文章考虑了手术时长的不确定性，以最小化手术室运作成本为目标的建立了手术室分配问题的鲁棒优化模型，并解析的推导出手术室最优开放数量的上下界.2012年，Mannino等［10］提出了医院手术班次调度的新型模式，以最小化手术室的超时开放成本为目标建模，使用light robustness的方法减小手术需求波动给医院运作成本带来的不利影响；2013年，Holte和Mannino［11］在手术班次调度的模式下，研究了手术室资源的优化分配问题，文章考虑了各科室的患者需求的不确定性，以患者等待的队列最短为目标，建立了问题的鲁棒优化模型，并开发了行列生成算法求解此问题.

本文在Denton等［9］工作的基础上，进一步人性化地考虑了患者的最迟手术日期限制，采用“收益管理”的思想对医院手术室调度问题建模，并分析了管理者风险偏好系数和最迟手术日期对医院收益和运作成本的影响.文章主要完成了以下几个部分工作：1）在考虑患者最迟手术日期限制的情况下，建立了手术调度问题的确定型模型.2）将患者的手术服务时间表示为有界区间，利用Bertsimas［12,13］等的思想，引入管理者风险控制参数，建立了区间型手术调度问题的相对鲁棒优化模型.使用对偶理论将Max-min形式的鲁棒优化模型转化为标准的混合整数规划模型，使用优化软件ILOG CPLEX求解.3）在实验设计部分，使用鲁棒优化和随机规划两种方法求解算例，比较鲁棒优化方法的求解性能.应用鲁棒优化方法求解了医院的实际案例.

2 手术调度问题

考虑医院某科室一周（D=5天）的手术安排.科室有N个患者等待手术，主治医生根据患者病情及入院时间给定患者的最晚手术日期Di.为确保患者在等待手术期间病情稳定且等待时间不会过长，医院要求在最晚手术日期前一定要为患者安排手术.科室设有手术室K个，手术室日规定开放时长为T小时，开放一个手术室的固定成本为cf.若手术计划在手术室规定开放时间内未能完成，则需要加班，单位加班费用为cv，由于医务人员加班费用昂贵，cv＞cf/T.患者i的手术时长为ti，医院为患者i手术可获得收入为ci.决策患者的手术日期和地点，使医院在一周的总收益最大.

定义决策变量如下：

xikd=1表示安排患者i在手术室k的第d天手术；否则xikd=0；

ykd=1表示手术室k在日期d开放；否则ykd=0.

okd为中间变量，表示手术室k在第d天的加班时长.

2.1 手术调度问题的确定性模型

假定患者的手术服务时间为常数，即患者的手术时长为确定已知的，手术调度模型（surgery scheduling model，SSM）如下

目标（1）分为两部分，第一部分表示院方获得的手术总收入，第二部分表示与开放手术室数量及加班时长相关的手术室运作成本，目标（1）表示最大化一个调度周期内医院的总收益.约束（2）和（3）表示当患者的最迟手术日期在当前调度周期内时，患者在最迟手术日前一定被安排手术且只安排一次.约束（4）表示若患者的最迟手术时间晚于当前调度周期，患者至多被安排一次手术.约束（5）为手术室的日手术能力约束.约束（6）表示决策变量的关系.

图1 患者的实际手术时长与上下界的关系Fig.1 The relationship between the actual surgery duration and its upper and lower bound

2.2 手术调度问题的两阶段鲁棒模型

在SSM模型中，患者的手术时间被设置为定长.但在实际手术调度中，由于患者的手术时长ti受医生技术水平、疲劳程度、患者身体状况等众多因素影响，在术前是无法准确预测的，患者的预期服务时长和实际值往往存在偏差，患者的服务时间稍有波动就可能使得原有的调度方案远离最优，甚至不可行.因此，作者采用鲁棒优化方法求解不确定服务时间下的手术调度问题.鲁棒优化考虑的是最坏情况下的最好，它代表了一种保守的观点，得到的优化方案并不一定是“最优”的.但是当不确定参数发生扰动时，得到的解仍然可行.本文假定患者的手术服务时间为连续的区间数，以最大化手术科室收益为目标，将不确定服务时间下的手术调度问题描述为一个极大化极小的优化模型，并通过对偶等理论将模型转化为标准的混合整数线性规划模型.

主治医生根据诊疗经验给出每位患者服务时间的上下界，则患者的服务时长可表示为连续的区间数，令δikd为患者i分配到手术室k的第d天的实际手术时长，则.定义参数ϖ =，ϖ表示患者的服务时长偏离下界的程度，如图1.ϖ=0时，所有患者的手术时间取下界（最好值）；ϖ=1时，所有患者的手术时间取得上界ti（最差值），ϖ的取值范围是［0，1］.

本文使用了Bertsimas和Sim［12,13］的思想来控制鲁棒模型的保守程度.对于周期D内所有调度的患者引入约束

式（8）表示最多有Γ个患者的手术时间同时达到最差值（上界）.参数Γ的取值大小由管理者事先给定，反映了医院管理者的风险偏好程度，0≤Γ≤N.Γ=0时，此问题为确定型问题，表示所有患者的手术时间均为下界（最好情况）；Γ=N时，表示所有患者的手术时间均为上界（最差情况）.根据决策者的风险偏好程度，调整Γ的取值.若决策者较为保守，则设定Γ取值较大；反之取值较小.

由此，患者手术时长的不确定集表示为

重新建立鲁棒优化模型（robust surgery scheduling model，RSSM）：鲁棒优化是求得一个这样的解，使得最坏情况下的目标函数最优，最大化最坏情况下的医院手术部的利润，即

约束（14），（15）组成了手术服务时间的不确定集合.目标（10）表示在不确定集合取得最差情景下，医院的收益最大.在模型RSSM中，发现只有目标函数（10），约束（14）和（15）受手术服务时长不确定性的影响，因此，RSSM模型可以表示为两阶段鲁棒优化模型，第一阶段的决策变量为xikd，ykd，第二阶段的决策变量为δ.

其中F（x,y）是与手术室超时开放时长相关的费用，即

2.2.1模型转化

为了使得F（x,y）可以代入原模型中直接求解，需要引入对偶理论对模型F（x,y）进行变换，首先使用Denton等［9］方法化简F（x,y）的表达式.引入决策变量zkd，zkd=1表示有手术室k在第d天有超时开放现象发生，否则zkd=0.重新建模F（x,y），即

由约束（28）可知，zkd=0，则δikd=0.因此，目标函数可以化简为

F（x,y）由非线性化简为线性规划问题，即

模型F（x,y）可以重新表达为

上述模型为线性规划模型，由于线性规划问题的基可行解对应于可行域的顶点.若可行域有界，线性规划问题的目标函数一定可以在其可行域顶点上达到最优，因此，由命题1可知，F（x,y）的线性松弛的解等价于原问题的解，即

由于上述线性规划问题式（35）～式（39）是可行且有界的，通过强对偶定理可知，原最大化问题可以等价转化为最小化问题.定义ħ,ikd（i∈1,2,...,N；k=1,2,...,K；d=1,2,...,D）,ℓkd（k=1,2,...,K；d=1,2,...,D）为约束式（36），式（37），式（38）的对偶变量.则式（35）～式（39）的对偶线性规划问题为

将式（44）～式（47）代入到初始模型RSSM中，得到RSSM的鲁棒对等模型RSSM1

3 数值仿真

数值实验在运行环境Dell Optiplex GX620，Intel（R）Pentium（R）D CPU 2.80GHz 2.00Gb下进行.由于模型RSSM1为标准的混合整数线性规划模型，可以使用优化软件ILOG CPLEX求解.在Visual studio2008平台下使用计算机语言C#调用CPLEX12.2进行数据测试.

表1 鲁棒优化与随机规划方法求解性能的比较Table 1 Comparison between the robust method and stochastic programming

为了测试鲁棒优化方法的求解性能，首先将鲁棒优化方法与随机规划方法进行比较.取指数分布函数的40%和60%为患者手术时间的上下界，患者的手术时长为有界区间，上下界取值在区间［20，200］随机产生.假定患者的手术服务时间服从正态分布，取上下界的均值为正态分布的均值，在给定分布下采样模拟患者手术时长的可能情景，样本数量取值为50，使用随机规划和鲁棒优化两种方法求解手术调度问题.问题的其他参数设定如下：N=15,T=8,cv=1,cf=4,K=2,Dcycle=5，患者的最迟手术日期在［1，10］之间取值.随机产生6组实例进行测试，由表1可见，当Γ=4，随机规划与鲁棒优化的求解结果近似相同；然而，两种方法的求解效率相差很大.鲁棒优化方法的平均求解时间为41 s，随机规划的平均求解时间为370 s.因此，鲁棒优化方法在问题的求解效率上凸显了优势.

为了说明Γ取值对鲁棒优化方法的影响，使用大连大学附属新华医院肛肠科1获得的6组实例，在两种参数设定cf/T＜cv＜ci/，cf/T＜ci/i＜cv情况下进行实验.当cf/T＜cv＜ci/i，ci/i∈（1，2），患者数为45时，求解结果如表2、图2所示.根据决策者的风险偏好程度改变参数Γ的取值，Γ取值越大，表示决策者越保守，Γ取值越小，表示决策者越偏好风险.由表2、图2可以得到如下结论：

表2 cf/T＜cv＜ci/i时，参数Γ对医院收益的影响Table 2 The influence of the parameter Γ on hospital's revenue with cf/T＜cv＜ci/i

表2 cf/T＜cv＜ci/i时，参数Γ对医院收益的影响Table 2 The influence of the parameter Γ on hospital's revenue with cf/T＜cv＜ci/i

鲁棒目标值实例 Γ=0 Γ=12 Γ=24 Γ=36 Γ=45 1 112.25 103.68 95.28 294.48 93.88 2 141.43 120.35 114.20 110.43 110.43 3 182.37 166.07 157.57 156.52 155.77 4 152.12 131.52 126.05 122.98 122.98 5 128.89 110.09 102.76 102.76 102.76 6 147.31 127.51 121.24 117.78 117.78均值 143.84 126.56 119.53 117.49 117.26方差 21.54 20.31 19.95 19.78 19.66最大值 182.37 166.0 157.57 156.52 155.77最小值 112.95 102.68 95.28 94.48 93.88

表3 cf/T＜ci/i＜cv时，参数Γ对医院收益的影响Table 3 The influence of the parameter Γ on hospital's revenue with cf/T＜ci/i＜cv

表3 cf/T＜ci/i＜cv时，参数Γ对医院收益的影响Table 3 The influence of the parameter Γ on hospital's revenue with cf/T＜ci/i＜cv

Γ=36 Γ=45 32.07 32.07 25.65 25.46 31.20 31.20 22.18 22.18 28.54 28.54 24.70 24.70 27.39 27.36 3.87 3.89 32.07 32.07最小值 48.22 30.51 24.22 22.18 22.18

图2 cf/T＜cv＜ci/i时，参数Γ对利润、收入和成本的影响Fig.2 The influence of the parameter Γ on revenue，income and cost with cf/T＜cv＜ci/i

图3 cf/T＜ci/i＜cv时，参数Γ对利润、收入和成本的影响Fig.3 The influence of the parameter Γ on revenue，income and cost with cf/T＜ci/＜cv

解的保守性随着Γ的增加而增强.随着Γ的增加，医院的利润呈现单调非增的趋势，即管理者规避风险降低了医院的收益.医院的管理者可以根据不同的风险偏好程度选择Γ的取值，进而获得医院的患者手术调度方案.

当医院的手术能力充足，且cf/T＜cv＜ci/i时，对于所有的风险偏好系数Γ取值，医院的总收入相同（见图2），这是由于所有患者都被安排手术时医院的总收益值达到最大.随着Γ的增加，医院的手术成本以及开放手术室的数量呈现单调非减的趋势.

当cf/T＜ci/i＜cv，ci/i∈（0.5,1），患者数为45时，求解结果如表3、图3所示.根据表3和图3的实验结果，可以得到如下结论：

解的保守型随着Γ的增加而增强.随着Γ的增加，医院的利润呈现单调非增的趋势，即管理者规避风险降低了医院的收益.

随着Γ的变化，医院的手术收入呈现不规则变化（如图3），这说明即使医院的手术能力充足，在cf/T＜ci/i＜cv范围内，并非所有的患者都被安排手术，而且存在着患者选择.随着Γ的增加，医院的手术成本呈现不规则变化，有增加的趋势.

为了避免患者入院后迟迟安排不上手术，或者患者入院后因未及时治疗导致的病情恶化，本文的模型中，更加人性化的引入了患者最迟手术日期.患者入院检查后，由其主治医生根据患者入院时间和病情规定最迟手术时间，确保患者在最迟手术日期前接受治疗.为了进一步说明考虑最迟手术时间对医院收益、运作成本等因素的影响，将引入最迟手术日期的模型与不考虑此因素的方法进行比较，独立重复进行十组实验.图4为不同Γ下，十组实验中手术科室的平均收入、成本和利润.根据表4和图4的实验结果可以发现，考虑最迟手术时间会降低医院的收益，最大收益差为10.7%.考虑最迟手术时间时，手术室的平均运作成本更高.

表4 最晚手术日期对医院利润的影响Table 4 The influence of surgery deadline on hospital's revenue

图4 最晚手术日期对手术部的利润、收入和成本的影响Fig.4 The influence of surgery deadline on revenue，income and cost

4 结束语

本文在考虑患者最迟手术日期情况下，对区间型患者服务时长的手术调度问题进行研究.在引入管理者风险控制参数的情况下，以最大化医院收益为目标，建立了手术调度问题的鲁棒优化模型.该方法在应对患者服务时间波动时，具有良好的鲁棒性.将提出的鲁棒优化方法与随机规划方法进行比较，验证了方法在求解效率上的优势.实验结果表明，将鲁棒优化运用于手术调度问题，能够减小服务时间不确定性给医院效益带来的影响.同时，考虑最迟手术日期会降低医院收益，最大收益差可达到10.7%.

［1］Bowers J，Mould G.Ambulatory care and orthopaedic capacity planning.Health Care Management，2005，8（1）：41—47.

［3］Strum D P，Jerrold M D，May H，et al.Modeling the uncertainty of surgical procedure times comparison of log-normal and normal models.Anesthesiology，2000，92（4）：1160—1167.

［4］Lamiri M，Grimaud F，Xie X L.Optimization methods for a stochastic surgery planning problem.International Journal of Production Economics，2009，120（2）：400—410.

［5］Batun S.Operating room pooling and parallel surgery processing under uncertainty.INFORMS Journal on Computing，2011，23（2）：220—237.

［6］吴小欢，朱金福，吴薇薇.航线网络区间型相对鲁棒优化设计.系统工程学报，2012，27（1）：69—78. Wu X H，Zhu J F，Wu W W.Relative interval robust optimization of airline network designing.Journal of Systems Engineering，2012，27（1）：69—78.（in Chinese）

［7］许晓晴，崔文田，林 军，等.基于最小最大遗憾的同型并行机鲁棒调度模型.系统工程学报，2013，28（6）：729—737. Xu X Q，Cui W T，Lin J，et al.Robust identical parallel machines scheduling model based on min-max regret criterion.Journal of Systems Engineering，2013，28（6）：729—737.（in Chinese）

［8］田文迪，胡慕海，崔南方.不确定性环境下鲁棒性项目调度研究综述.系统工程学报，2014，29（1）：135—144. Tian W D，Hu M H，Cui N F.Review of studies on robust project scheduling under uncertainty.Journal of Systems Engineering，2014，29（1）：135—144.（in Chinese）

［9］Denton B T，Miller A J，Balasubramanian H J.Optimal allocation of surgery blocks to operating rooms under uncertainty.Operations Research，2010，58（4）：802—816.

［10］Mannino C，Nilssen E J，Nordlander T E.Apattern based，robust approach to cyclic master surgery scheduling.Journal of Scheduling，2012，15（5）：553—563.

［11］Holte M，Mannino C.The implementor/adversary algorithm for the cyclic and robust scheduling problem in health-care.European Journal of Operational Research，2013，226（3）：551—559.

［12］Bertsimas D，Sim M.The price of robustness.Operations Research，2004，52（1）：35—53.

［13］Bertsimas D，Sim M.Robust discrete optimization and network flows.Mathematical Programming，2003，98（1/3）：49—71.

A two-stage robust optimization method for solving surgery scheduling problem

Wang Yu1,2，Tang Jiafu3
（1.State Key Lab of Synthetic Automation of Process Industry，Northeastern University，Shenyang 110819，China；2.The College of Economics and Management，Shenyang Agricultural University，Shenyang 110866，China；3.College of Management Science and Engineering，Dongbei University of Finance and Economics，Dalian 116025，China）

The surgery service duration，which is influenced by individuals' physical conditions，the surgeon's skills，and so on，is uncertain in advance.How to effectively schedule surgeries is a challenge for managers in hospitals.This paper studies a surgery scheduling problem with regard to surgery deadline.Firstly，a deterministic surgery scheduling model is built with the objective of maximizing the revenue of surgery department.Then，the uncertain surgery service durations are represented as bounded intervals，and a two-stage robust optimization approach for solving surgery scheduling is described with a risk-preference parameter.The computational experiments prove that the proposed robust optimization method helps to reduce the influence of uncertainty on the hospital's revenue.In view of surgery deadline，the hospital's revenue reduces with a maximum level of 10.7%.

robust optimization；uncertain surgery duration；operating room scheduling；hospital management

10.13383/j.cnki.jse.2016.04.001

王 昱（1987—-），女，辽宁铁岭人，博士生，研究方向：优化与调度，鲁棒优化，医疗服务业运作管理，Email：wangyuguomei@ 163.com.

2014-01-17；

2014-09-04.

国家自然科学基金资助项目（71021061）；教育部博士点专项基金资助项目（20120042110023）；

唐加福（1965—-），男，湖南东安人，博士，教授，博士生导师，研究方向：制造系统生产与物流运作管理，服务系统运作优化等，Email：jftang@mail.neu.edu.cn.