论文研究-基于机会约束的手术计划随机模型与算法.pdf

所需积分/C币:10 2019-09-20 21:41:24 666KB .PDF
收藏 收藏
举报

论文研究-基于机会约束的手术计划随机模型与算法.pdf,  本文研究多服务台手术计划调度问题,考虑手术时间的不确定性,提出手术室加班时间的机会约束,以一定的概率保证病人的手术时间不超过手术室的开放时间,建立随机优化机会约束手术计划调度模型,确定手术室的开放和分配决策.基于手术时间离散的概率情景,引入0-1变量转化机会约束,得到了0-1整数线性规划的等价模型.为了提高模型的求解效率,提出两类有
第7期 王珊珊,等:基于机会约束的手术计划随机模型与算法 1723 2基于机会约束的随机手术计划模型 21问题描述 在手术室计划的确定模型中,所有的参数都是已知的包括惠者的手术时间,然而在实际中存在较多的不 确定性,基于确定手术时间的手术计划往往会误导管理者,从而导致错误的决策.因此如何有效地处理这些 不确定性成为硏究的关键·本文考虑患者的手术时间是不确定的,将不确定参数当做随机变量,在不确定模 型中引入机会约束,基于手术时间离散的概率情景,研究手术空开放和分配问题.提出的机会约束用来衡量 在不确定情况下手术室加班时间的概率,机会约束的理论及应用近年来得到了一定的发展,但由于其求解复 杂尤其是大规模优化冋题,在一定程度上限制∫在运营晉理领域的应用 本文研究多服务台手术计划调度问题,假设同一个手术室同一时间只能进行一台手术,手术室可以为不 同类型的手术服务;每天安排的患者人数固定,手术时间的离散的概率情景已知.基于此,研究不同患者类型 和服务时间不确定下的手术计划调度问题,确定手术室的开放和分配策略.2.2节建立一个机会约束手术室 计划调度模型研究最优的开放和分配决策.符号说明具体为: 集合与参数:I:表示计划周期内手术病人的集合,1∈I;J:表示手术室的集合,j∈J;g:表示情景的集 分,u∈g;(:为手术病人的手术时间;p:为情景c发生的概率;:为手术病人在情景下的手术 时间:0;:为手术室j一天的开放时间:c:为手术室的开放成本;c2:为手术病人分配到手术室j的分 配成本;ε:为手术室发生加班概率的风险参数,其值体现决策者的风险态度,ε∈0,1·决策变量:x:二元 变量,x=1如果开放手术室j,岙则x=0;yy:二元变量,=1如果手术病人分配到手术室j,否则 yij 22机会约束手术计划调度模型 由于手术时间是不确定的,手术计划调度为了减少手术室的加班时间,考虑每个手术室以至少1-c的 概率保证手术室手术结束的时间小于手术室的开放时间,即 Prot ;i≤ 1-E,Vj∈J. i∈r 基于此,建立机会约束手术计划模型为 CC-SPI min ∑cx+∑c j∈J ∈I,∈J s.t.3/ v∈1,j∈J, ∑v=1,Y∈I Po(∑(≤o)≥1-,∈J 3∈{0,1},Y∈Ij∈J 目标式为使得手术计划中总成本最小,包括手术室总的开放成本和手术病人分配到手术室总的分配成本;第 个约束式表示只有开放的手术室才能安排手术病人;第二个约束式表示每个手术病人只能分配到一个手术 室中;第三个约束式为手术室加班的机会约束,表示每个手术室加班的概率不超过一个风险参数e;第四个为 决策变量的0-1约東.由于机会约束定义的可行域是非凸的且涉及多元微分的计算,求解机会约束往往十分 困难.接下来本文引入一个二元变量求解机会约束,将模型转化为一个混合整数规划问题,为了保证不等式 成立,则需要引入一个很大的数,即通常称为大M法 引入一个二元变量,2j-1保证手术室j在情景u下没有加班,即约束∑≤0;成立.由 于对任何一个手术室j,没有发生加班的概率至少满足1-,不等式∑∈72≥1-ε成立.模型CC_SP 转化为 1724 系统工程理论与实践 第39卷 ICC-FSPI mIn ∑cx+∑ st.9≤m,V∈I,∈J, ∑ v∈I, 1→∑<w≤o,ⅵi∈J,∈只 2j≥ ∈ ,y,2j∈{0,1},Y∈1,j∈J,w∈9 大M法在模型CFSP基础上进一步引入一个足够大的常数M,当z=0时保证不等式仍然成立将模 型CCSP转化为一个0-1整数规划问题,即为 CC_MSP ∑x;+∑c2 0∈J ∈1,)∈J S.t.∷;≤ v∈I,∈ 1,Vi∈I ∈,J ∑≤0+(M-0)(1-2y),∈J,∈9 Pw rjw vj∈J, 心∈S2 xjy,∈{0.1},V∈I,j∈J.u∈ 由上式可知,M应满足M≥max{Sy:y∈Y},其中Y为 CC-MSP中除机会约束外其他关于变 量y的约束定义的y的可行域.一个保守的取值可令M=∑∈·由于M保守的取值对变量y的可 行域进行了松弛处理,将导致一个比较弱的约束条件,需要较长的模型求解时间,尤其当情景较多时.为此, 本文将介绍一类有效的不等式,能有效的提高模型的求解效率. 3求解算法 为了提高模型 CC MSP的求解效率,本文利用分支切割算法进行模型求解,并提出了有效不等式及算 法的一些加强策略.具体地,3.1节首先介绍了分支切割算法,接着提出了有效不等式并证明其有敚性,最后 利用改进的算法分离有效不等式.3.2节提出了一些有效的算法加强策略 31分支切割算法 分支切割算法是求解0-1整数规划问题十分有效的精确算法,其在分支定界算法的基础上,根据问题结 构,提岀一系列有效不等式,切割松弛问题的可行域而不影响整数规划问题的可行域,进而减少算法寻找最 优解的时间,加快算法的求解效率.具体地,给定一个节点和相应 CCLMSP的线性松弛问题,利用线性规划 间题求解算法(如单纯形法或者对偊单纯形法)对该松弛问题进行求解得到最优解(,ψ,).如果最优解(α, ,2)为整数解,则该解为 CC_MSP的可行解,更新 CC_MSP的上界;如果最优解(,y,2)为分数解,判断 是否满足有效不等式,如果满足则算法继续对分数解进行分支求解,否则将不等式添加到松弛间题重新求解. 进一步,为了得到模型(C-MSP的有效个等式,首先定义一个函数h为,对任意的j∈J,心,k∈ h=max∑<uv ik y 第7期 王珊珊,等:基于机会约束的手术计划随机模型与算法 1725 给定∈g,求解参数需计算×92个最大化问题,当J或者Ω较大时,通常需要较长的求解时间 为了进一步减少求解时间本文将决策变量y∈Y松弛为y∈{0,1},此时通过对系数进行排序能有效 的求解参数b·同Dng和Shcn1的求解方法类似,具体求解参数b的步骤见算法1 algorithm1求解参数hk 1:forj∈J,∈9 fork∈g 令r(i)=(u/,对r()进行排序即r(i1)≥…≥r(io) ←1,←0,b←0 while b>0 q←min{1,b/a1k} ←+qizk b←b l←l+1 end while 12 cnd for 13: end for 给定j∈J,w∈g,对hk进行排序,使得hh1≤ 定义q满足 1s2 +1n>E,则有引理1成立 引理1给定的j和ω,不等式 ∑ 是问题 CC_MSP的有效不等式 证明当2j=1时,不等式(6)为 ∑%≤b i∈ 根据h的定义不等式(7)显然成立当2=0时,只需证明h,是∑∈ry的上界.令y是间题 CC_MSP的可行解,由q的定义可知,∑rSx≤o至少有一个′∈[k1,…,k+成立,否则机会约 束将不能满足.则h。+1≥b≥∑;∈ruyx·所以引理1成立 由引理1可得定理1中另一类有效不等式(8) 定理1给定的j和,令T={t1,…,t}s{k1,…,k},则不等式 ∑伽+∑ )zyt12≤ba 是问题 CC MSP的有效不等式,其中h1+:=hkn+ 证明为了证明不等式(8)是有效的,需证明:(a)问题 CC MSP的任何可行解(y,2)满足不等式(8); (b)如果(y,z)不满足问题 CC_MSP,则(y,z)也不满足不等式(8).首先证明(a)成立.令=min{∈ }则∑∈r ∑狗+∑(h 14+1-5t)2.<ht。+ ∑(h汽+1-hn)21≤n 接下来证明(b)成立.如果x=1,∑∈rS9>o由u=1,可知b≤o1如果l≤hn, 则对于某个i=1,…,p.u=k,令T={t}={u},不等式(8)变为 ∑〈+(hA+-b3)21≤h 1726 系统工程理论与实践 第39卷 即为 ∑<≤b≤0 (11) 同∑∈Scy;>o矛盾,所以(g,x)也不满足不等式().如果hu>h+,则 ∑<uy+∑ h2t1)2t≤b 由于∑=1-h,)≥0,所以不等式(12)同∑∈>03矛盾,所以(v,2)也不满足不等式 (8).综上可知(8)为问题 CC_MSP的有效不等式 由于有效不等式(⑧)为一类指数级增长的不等式,在分支切割算法求解中,为了添加有效不等式应求解 相应的分离问题.分离问题是指验证是否存在一个有效不等式使得松弛问题的最优解(3,2违反该不等式 给定松弛主问题的解,求解分离问题,如果存在违反的有效不等式,则将相应的不等式添加到松弛问题中重 新求解.固定点(3,2),基于无环图中寻找最长路径方法,提出分离算法.该分离算法最早由 Atamtiirk等7 提出,由于定理1提出的有效不等式与[17]中的有效不等式不同,本文根据定理1的有效不等式对[17提 出的分离算法进行了相应的修改分离算法的具体步骤见算法2. AlgorithIn2分离算法 1:给定j∈,J,u∈9 2:初始化oa←0,m←1 3: while o≤q+1 中hxn←maxb>hm,a,+(h为n-h):,并记录对应的参数 m←m+1 7: cnd whilc s:i∑(a9分+中x,>hk2=1 9:添加相应的割平面(8)到松弛问题 10: end if 对于存在机会约束的手术计划调度问题,常用的求解方法有引入大M直接转化机会约束、分解算法、分 支切割算法等.引入大M直接转化机会约束导致较差的上界约束,从而影响模型的求解时间.本文提出的分 支切割算法在节点处求解松弛问题,利用分离算法生成满足一定条件的有效不等式,作为分支切割树的割平 面,且由最大路径算法求得的有效不等式为该松弛解下最大的违反不等式.由于分支切割算法添加一系列有 效不等式,减小了松弛间题的可行域进而加快了最优解的寻找,极大地提高了模型的求解效率.分支切割分 解算法具休步骤: 分支切割算法3中δ代表算法终止的条件,表示上下界相对相差水平的阈值.模型的上下界和节点集合 会随着迭代发生改变,进而影响算法的求解 32算法加强策略 由于问题 CC MSP变量(a,y,z)均为0-1变量,当I,|或!2很大时,分支切割算法需要求解一个 规模庞大的分支切割树,为了进一步提高问题的求解效率,本文采用了几种分支切割算法通用的策略,旨在 减少分支切割树的规模,加快最优解的寻找算例分析验证了提出的策略的有效性.策略一,初始化分支切割 算法的下界.由于(,y,x)均为θ-1变量,分支切割算法最初求解线性松弛问题时,将(x,y,z)均松弛为0 到1区间的连续变量,这将导致初始的下界值非常的小,以至于需要较长的时问达到与上界相差阈值δ的收 敛水平.因此,本文求解以下松弛问题,得到一个较好的下界債,作为分支切割算法下界的初始值. 第7期 王珊珊,等:基于机会约束的手术计划随机模型与算法 1727 Algorithm3分支切割算法 1:初始化令UB=+∞,LB=-∞,N={m},其中n是分支结点,初始化主问题为线性松弛问题 2: while N非空&&(UB-LB)/UB>6 N←N/{m} 4:在节点η处求解松弛主叫题,得到最优解(,纩,2)和目标值lob if lob<U乃 f(x,y,2)是整数 则(x,g,2)为模型 CC-MSP的可行解,UB=min{UB,lob门},转到步骤2 else利用分离算法添加有效不等式,如果存在有效不等式,转到步骤4 9 end if 10 更新LB,选择一个分数点分支,生成结点n*和n* N←NU{n*,m**} d if 13 end while 1:得到最优解(*,y,z*)和目标值UB CC-_LSPI ImIn ∈了 s.t.≤x,M∈1,∈J =1,V∈Ⅰ, ∑≤0+(M-0)(1-),∈小∈9 iel P vj∈J, r;,y;∈{0,1},ⅵ∈I,j∈J, zj∈[0,1.u∈ 策略二,确定分支变量的优先级.由于问题 CC MSP均为0-1变量,分支变量的优先级影响算法的求解时间, 由于本文需要确定分配决策和开放决策,而当分配决策已知,开放决策也已知,因此本文分支优先级为:决策 变量y的优先级>变量c的优先级>变量z的优先级 4算例分析 表1不同科室的统计信息 本文算例实验的数据来自北京某公立医院收集到2015 均值标准差 年1月到2015年10月共5721条手术数据.根据数据统计出 (时)(1个数所占比例患者 各个科室手术时间的均值和标准差,外科手术的个数,所占的科1113168629475 比例见表1.根据手术数据,8个手术室平均每天进行18例 乳腺科1.61.082714463 淋巴外科3.21.178713.763 外科手术,我们选取18个手术病人,分别记为P1,…,P18,耳鼻喉科281.772312642 根据外科手术所的比例,计算出每个科室惠者的数量,同泌尿外科2.31.74167.2 时保证每个科室都有患者,如表1所示,以妇科和乳腺科为血管外科261.5401701 例,图1为手术时间的频率直方图根据手术时间的历史数产科1.50.53646361 据拟合出概率分布,基于概率分布生成手术时间离散的情景,关节外科28133546.191 骨外科3.21.81632851 情景的概卒相等.该医院共有8个手术室为这些外科科空服 务,每个手术室的工作时间是10个小时,手术空不区分手术 1728 系统工程理论与实践 第39卷 类型,即手术室可以进行不同类型的外科手术.手术室的开放成本设置为200,分配成本为3,变化风险参数 c=0.05,相对gapδ=0.01.算法运行的时恒限制设置为3600秒.本文数量单位是个相对gap的单位是 所有的算例的算法代码通过C实现并调用求解器 CPLEX进行求解、在 windows64位系统 Intel(R)280HZ 处理器16GRAM电脑上运行 0.35 0.35 0.25 0.25 0 L nL⊥ 时 (a)妇科 (b)乳腺科 图1妇科和乳腺科手术时间的频率直方图 算法有效性分析.为了验证算法的有效性,分別运行两组情景规模|2|=50,100.每个情景规模下分別 生成4组实例每个实例用-*表示,如表2第列所示所有的算法均利用加强策略一和二,即初始化 下界和分支变量的优先级.表2为不同规模和实例下,算法总的运行时问(秒)、终止时的相对gap、分支节 点的数量及添加有效不等式的个数,其中,gap-(UB-LBUB,M1.M2,M3分别指大M法,大M法 基础上添加有效不等式(6)和添加有效不等式(8).随着情景数的增加,算法的求解时间和分支节点数也随 之增加.且增加的趋势比较明显,这是由于随着情景的增加,模型变量和约束的数量显著增加,提高了算法的 求解负担.相同规模下,求解时间和节点数有一定的波动,说明数据对模型的求解时间有一定的影响.大部 分算法的相对g⊕均能在时间限制达到1%,整体收敛性较好.同时,同M1法相比,M2和M3方法能明显 减少模型的平均求解时间和分支节点的数量,说明了添加的不等式在求解该类问题时的有效性.由于有效不 等式(8)是在(6)的基础上提出,但通过在表1中M2和M3的比较,有效不等式(8)相比(6)的优势性 和有敚性没有得到很好的展现,这主要是因为求解器 CPLEX添加的有效不等式和默认的搜索机制,添加有 效不等式会改变CPLEⅩ添加的有效不等式和默认的搜索机制,从而导致不可预测的结果.同时,有效不等 式(8)添加的个数多于有效不等式(6),在分支切割树中,如何选择保留有效不等式也十分的困难,我们采用 PLEⅹ默认的设置保留这些有效不等式,但是如果保留过多的有效不等式叮能会增加判断是否满足不等式 的时间,从而影响模型的求解时间 表2不同情景数量下算法结果比较 M1 M2 M3 时间gap节点数时间gap节点数不等式数时间gap节点数不等式数 5012761.01901451280.054970 374 1140.046661 571 150 0.1 44065 740.022586 352 1400 95522 620 5032340.01194341130.048097 374 1060.238600 5041680. 722871700.770151 382 600.021185 497 100111400.42280636880.0104284 743 18490.72283344499 100-2360015.95164270322020.941757977713580.0257352 100314631.051076811470.0198636 783 11840.0178716 3799 100-418870.7960060712020.0221112 772 7770.0124291 1153 表3为不同情景下求解参数h的时间T1秒)和下界问题 CC_LSP的时间T2(秒,求得的下界值, 第7期 王珊珊,等:基于机会约束的手术计划随机模型与算法 1729 CC-SP的最优目标值和下界值同最优目标值的相对gαp1,其中gαp1=(最优目标值一下界值)/最优目标值 相同情景下求解参数及下界的时间相似,且不同情景数求解时间均比较短,这说明求解参数及将变量≈松弛 后的模型均比较容易求解.下界的目标值同最优目标值相比.gαp1为31.9%,见表3,说眀下界值的质量较 好,初始化下界值能有效的缩小最优解的寻找范围,减小分支切割树的规模.图2为在501下,随着分支节 点数量的增加不同算法上下界的变化情况,随着迭代次数的增加上下界逐渐趋于相等,M2和M3上下界趋 于相等的速度快于M1.在根节点处,M2和M3的相对gap为41.27%,而M1则在70个节点数才能达到 4127%.类似地,达到相同的gap,M2和M3分支的节点数明显小于M1分支的节点数,说明M2和M3 添加的有效不等式能减少分支数,缩小线性松弛问题的可行域 表3不同情景下求解时间及下界 T1T2下界值最优目标值gap1 0-12.541.95854 1254 1.9 5022.061.91 1254 31.9 5032.151.328 L254 31.9 5042.061.03854 1254 31.9 1008473.348 1254 31.9 8.233.27 1254 31.9 10037.9429484 31.9 10048.213.26854 1254 31.9 上界 节点数 节点数 (a)M1 (b)M2 上界 下界 节点 数 )M3 图2上界和下界随着节点数的变化 1730 系统工程理论与实践 第39卷 开放数 开放数 (a)50情景 (b)100情景 图3不同情景下的成本和手术室开放个数 图3为不同ε下50-1和100-1的总成本及手术室的开放个数.随着ε的逐渐减小,手术室不会出现 加班的概率越来越大,50情景下ε=0.1,0.15,0.2时总成本和手术室的开放个数相等,类似地,100情景下 ε=0.1,0.15,0.2,0.25时总成本和手术室的开放个数乜相等,算法表明在ε的某个范围内,不用增加新的手 术室就可以保证手术加班概率较低.当E-0.25时,100情景下开放的手术室个数和总成本均高于50情景 下的、当情景较多时,为了满足更多的情景可能导致较大的开放数和总成本 接下来,利用测试样本验证模型开放和分配决策解的质量.首先基于手术时间的概率分布随机生成200 个测试样本,根据不同情景规模下的开放决策和分配决策计算在测试样本下手术室的加班时间(时),即每个 测试样本下都对应着开放手术室的加班时间.进一步计算测试样本下手术室平均加班的概率,加班时间的均 值,标准差.50分位数,75分位数,及90分位数,见表4.不同情景规模下手术室的加班概率在0.02左右,均 明显小于ε,说明 CC MSP的决策能较好的控制手术室的加班概率.测试样本下加班时间和标准差均较小 加班时间的75分位数均为0,说明测试样本下至少有75%的情景手术室没有出现加班的情况.100个情景 的平均加班慨率低于50个情景的平均加班概率,且加班时间的95分位数也有同样的趋势,情景数量较多的 决策在测试样本下表现较好.表5为50-1和100-1下不同ε下测试样本下手术室平均加班的桃率,加班时 间的均值.标准差,及各个分位数.不同ε下,测试样本的加班概率大多都小于ε,且不同的ε卜,加班时间的 均值、标准差及各个分位数值都较小.由于50情景下ε=0.1,0.15,0.2时总成本和手术室的开放个数相等, 类似地,100情景下ε=0.1,0.15,0.2,0.25时总成本和手术室的开放个数也相等.因此,随着c的增加,加班 概率并没有呈现不减的规律. 表4测试样本下加逊结果比较 表5测试样本下不同ε加班结果比较 概率均值标准差50%75%95% ε概率均值标准差50%75%95% 50-10.0330.0370.1150.0000.0000.275 0.050.0330.0370.1150.0000.0000.27 50-20.0100.0030.0030.0000.0000.038 0.10.0550.0320.0670.0000.0000.150 5030.0230.0110.0160.0000.0000.238500.150.0330.0340.1370.0000.0000.100 5040.0200.0110.0210.0000.0000.175 0.20.0330.0220.0540.0000.0000.063 100-10.0240.0300.0570.0000.0000.138 0.250.0880.0900.2570.0000.0000.550 10020.0090.0140.0310.0000.0000.000 0.050.0060.0080.0160.0000.0000.000 100-30.0110.0130.0180.0000.0000.000 0.10.0090.0090.0140.0000.0000.000 10040.0110.0130.0180.0000.0000.0001000.150.0200.0370.1600.0000.0000.113 0.20.0230.0250.0410.0000.0000.050 0.250.0160.0200.0390.0000.0000.050 5结论 本文针对手术计划调度问题,考虑手术时间的不确定性,基于手术时间的概率分布信息,提出了手术室

...展开详情
试读 11P 论文研究-基于机会约束的手术计划随机模型与算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743968 欢迎大家使用并留下宝贵意见
2019-09-20
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-基于机会约束的手术计划随机模型与算法.pdf 10积分/C币 立即下载
1/11
论文研究-基于机会约束的手术计划随机模型与算法.pdf第1页
论文研究-基于机会约束的手术计划随机模型与算法.pdf第2页
论文研究-基于机会约束的手术计划随机模型与算法.pdf第3页

试读结束, 可继续读1页

10积分/C币 立即下载 >