醫(yī)院手術(shù)調(diào)度問(wèn)題的兩階段魯棒優(yōu)化方法研究

王 昱，唐加福

（1.東北大學(xué)流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽(yáng)110819；2.沈陽(yáng)農(nóng)業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院，遼寧 沈陽(yáng)110866；3.東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧 大連116025）

醫(yī)院手術(shù)調(diào)度問(wèn)題的兩階段魯棒優(yōu)化方法研究

王 昱1,2，唐加福3

（1.東北大學(xué)流程工業(yè)綜合自動(dòng)化國(guó)家重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽(yáng)110819；2.沈陽(yáng)農(nóng)業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院，遼寧 沈陽(yáng)110866；3.東北財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，遼寧 大連116025）

手術(shù)服務(wù)時(shí)間受患者身體狀況，醫(yī)生技術(shù)水平等因素影響，具有不確定性.如何有效地調(diào)度患者手術(shù)成為醫(yī)院管理的一大挑戰(zhàn).研究了醫(yī)院的手術(shù)調(diào)度問(wèn)題，以院方收益最大為目標(biāo)，在考慮患者最遲手術(shù)日期限制的情況下，建立了手術(shù)調(diào)度問(wèn)題的確定型模型.進(jìn)一步考慮手術(shù)服務(wù)時(shí)間的不確定性，將手術(shù)的服務(wù)時(shí)間表示為有界區(qū)間，考慮了管理者風(fēng)險(xiǎn)偏好對(duì)患者服務(wù)時(shí)間不確定集的影響，在確定型模型的基礎(chǔ)上，提出了區(qū)間型手術(shù)調(diào)度問(wèn)題的兩階段魯棒優(yōu)化方法.數(shù)值實(shí)驗(yàn)結(jié)果表明，將魯棒優(yōu)化運(yùn)用于手術(shù)調(diào)度問(wèn)題，能夠減小服務(wù)時(shí)間不確定性給醫(yī)院效益帶來(lái)的影響.同時(shí)，考慮最遲手術(shù)日期會(huì)降低醫(yī)院收益，最大收益差可達(dá)到10.7%.

1 引 言

近年來(lái)，我國(guó)醫(yī)改各項(xiàng)工作不斷推進(jìn)，隨著醫(yī)療體制改革的深化，醫(yī)療服務(wù)業(yè)引發(fā)了全社會(huì)的關(guān)注.醫(yī)療機(jī)構(gòu)自負(fù)盈虧，在有限的醫(yī)療服務(wù)資源和激烈的市場(chǎng)競(jìng)爭(zhēng)雙重壓力下，醫(yī)院管理者越來(lái)越重視醫(yī)院效率和服務(wù)品質(zhì).手術(shù)部在醫(yī)院利潤(rùn)中所占的比例最大［1,2］，且服務(wù)品質(zhì)直接關(guān)系到患者的健康乃至生命，因此，手術(shù)部受到管理者和病人的高度重視.優(yōu)化安排患者手術(shù)日程，提高醫(yī)院收益，減少患者調(diào)度過(guò)程中的不合理現(xiàn)象，創(chuàng)造一個(gè)良好的就診環(huán)境成為手術(shù)部管理者的目標(biāo).所謂手術(shù)調(diào)度問(wèn)題，實(shí)質(zhì)上是根據(jù)患者需求和醫(yī)院的手術(shù)能力，產(chǎn)生一段時(shí)間內(nèi)，滿足一定約束條件的手術(shù)時(shí)間表的過(guò)程.廣義的手術(shù)調(diào)度除手術(shù)時(shí)間的調(diào)度外，還包括手術(shù)地點(diǎn)、醫(yī)護(hù)人員、手術(shù)器械等相關(guān)資源的調(diào)度.科學(xué)、合理、高效的手術(shù)安排更加人性化，使患者在較為合理的時(shí)間段進(jìn)行手術(shù)，良好的控制病情的發(fā)展；同時(shí)高效的利用的手術(shù)資源，為醫(yī)院帶來(lái)了巨大的經(jīng)濟(jì)效益.

醫(yī)院的手術(shù)服務(wù)時(shí)間具有較大的不確定性，手術(shù)時(shí)長(zhǎng)受醫(yī)生技能水平、疲勞程度、患者身體狀態(tài)等多方面因素影響，難以準(zhǔn)確給出手術(shù)服務(wù)時(shí)長(zhǎng)的確定值.因此，在考慮手術(shù)服務(wù)時(shí)間為定長(zhǎng)情況下的手術(shù)調(diào)度方案魯棒性較差，在醫(yī)院實(shí)際運(yùn)作中往往偏差較大甚至無(wú)法實(shí)施.手術(shù)服務(wù)的內(nèi)在不確定性給院方手術(shù)調(diào)度帶來(lái)了巨大的困擾，近年來(lái)，手術(shù)調(diào)度問(wèn)題也吸引了學(xué)者的關(guān)注.隨機(jī)規(guī)劃和魯棒優(yōu)化方法是解決不確定問(wèn)題的強(qiáng)大工具.隨機(jī)規(guī)劃方法需要已知隨機(jī)參數(shù)的分布函數(shù).通過(guò)對(duì)大量的歷史數(shù)據(jù)的分析，Strum等［3］發(fā)現(xiàn)手術(shù)服務(wù)時(shí)間可以近似用對(duì)數(shù)正態(tài)或者正態(tài)分布來(lái)描述.Lamiri等［4］假定手術(shù)需求服從正態(tài)分布，提出了手術(shù)室能力分配的隨機(jī)規(guī)劃模型，并使用蒙特卡羅近似法模擬患者的需求情景，將隨機(jī)規(guī)劃模型轉(zhuǎn)換為標(biāo)準(zhǔn)的混合整數(shù)規(guī)劃模型進(jìn)行求解.Batun等［5］獲取了愛(ài)爾蘭某醫(yī)院的患者就診數(shù)據(jù)，模擬患者服務(wù)時(shí)間的分布函數(shù)，以醫(yī)院最小運(yùn)作成本為目標(biāo)建立了兩階段隨機(jī)規(guī)劃模型，決策患者的手術(shù)順序、時(shí)間及地點(diǎn).

隨機(jī)規(guī)劃方法依賴于歷史數(shù)據(jù)和分布規(guī)律.然而，在醫(yī)院的實(shí)際調(diào)度當(dāng)中，患者的就診數(shù)據(jù)往往是不充足的，難以準(zhǔn)確描述患者服務(wù)時(shí)間的分布.因此，我們使用魯棒優(yōu)化方法來(lái)求解手術(shù)調(diào)度問(wèn)題.不確定優(yōu)化問(wèn)題的魯棒解是最壞不確定情景下使目標(biāo)函數(shù)具有最優(yōu)值的解，它的一個(gè)重要特點(diǎn)是對(duì)于任何具體的情景，魯棒解只是近似最優(yōu)解，但是對(duì)于整個(gè)不確定集合是最優(yōu)的［6,7］.傳統(tǒng)的優(yōu)化方法在系統(tǒng)的內(nèi)部參數(shù)或者外部環(huán)境變化時(shí)往往顯得無(wú)能為力，得到的優(yōu)化結(jié)果與實(shí)際偏差很大.魯棒優(yōu)化方法在系統(tǒng)的內(nèi)部結(jié)構(gòu)和外部環(huán)境發(fā)生變化時(shí)，仍然能夠保持系統(tǒng)的功能［8］.因此，魯棒優(yōu)化在求解不確定優(yōu)化問(wèn)題時(shí)凸顯了其巨大的優(yōu)勢(shì).

在手術(shù)調(diào)度系統(tǒng)中，來(lái)自手術(shù)操作過(guò)程、術(shù)中突發(fā)狀況等不確定性都會(huì)直接影響到調(diào)度方案能否順利實(shí)施.在這些不確定因素的作用下，魯棒性成為能否確保醫(yī)院手術(shù)部收益和患者服務(wù)質(zhì)量的重要因素.在國(guó)際上，魯棒優(yōu)化在醫(yī)院管理中的應(yīng)用還處于起步階段.迄今為止，使用魯棒優(yōu)化方法求解手術(shù)室優(yōu)化調(diào)度問(wèn)題的文章只有3篇.2010年，Denton等［9］首次將魯棒優(yōu)化方法應(yīng)用到醫(yī)院手術(shù)室優(yōu)化調(diào)度中，文章考慮了手術(shù)時(shí)長(zhǎng)的不確定性，以最小化手術(shù)室運(yùn)作成本為目標(biāo)的建立了手術(shù)室分配問(wèn)題的魯棒優(yōu)化模型，并解析的推導(dǎo)出手術(shù)室最優(yōu)開(kāi)放數(shù)量的上下界.2012年，Mannino等［10］提出了醫(yī)院手術(shù)班次調(diào)度的新型模式，以最小化手術(shù)室的超時(shí)開(kāi)放成本為目標(biāo)建模，使用light robustness的方法減小手術(shù)需求波動(dòng)給醫(yī)院運(yùn)作成本帶來(lái)的不利影響；2013年，Holte和Mannino［11］在手術(shù)班次調(diào)度的模式下，研究了手術(shù)室資源的優(yōu)化分配問(wèn)題，文章考慮了各科室的患者需求的不確定性，以患者等待的隊(duì)列最短為目標(biāo)，建立了問(wèn)題的魯棒優(yōu)化模型，并開(kāi)發(fā)了行列生成算法求解此問(wèn)題.

本文在Denton等［9］工作的基礎(chǔ)上，進(jìn)一步人性化地考慮了患者的最遲手術(shù)日期限制，采用“收益管理”的思想對(duì)醫(yī)院手術(shù)室調(diào)度問(wèn)題建模，并分析了管理者風(fēng)險(xiǎn)偏好系數(shù)和最遲手術(shù)日期對(duì)醫(yī)院收益和運(yùn)作成本的影響.文章主要完成了以下幾個(gè)部分工作：1）在考慮患者最遲手術(shù)日期限制的情況下，建立了手術(shù)調(diào)度問(wèn)題的確定型模型.2）將患者的手術(shù)服務(wù)時(shí)間表示為有界區(qū)間，利用Bertsimas［12,13］等的思想，引入管理者風(fēng)險(xiǎn)控制參數(shù)，建立了區(qū)間型手術(shù)調(diào)度問(wèn)題的相對(duì)魯棒優(yōu)化模型.使用對(duì)偶理論將Max-min形式的魯棒優(yōu)化模型轉(zhuǎn)化為標(biāo)準(zhǔn)的混合整數(shù)規(guī)劃模型，使用優(yōu)化軟件ILOG CPLEX求解.3）在實(shí)驗(yàn)設(shè)計(jì)部分，使用魯棒優(yōu)化和隨機(jī)規(guī)劃兩種方法求解算例，比較魯棒優(yōu)化方法的求解性能.應(yīng)用魯棒優(yōu)化方法求解了醫(yī)院的實(shí)際案例.

2 手術(shù)調(diào)度問(wèn)題

考慮醫(yī)院某科室一周（D=5天）的手術(shù)安排.科室有N個(gè)患者等待手術(shù)，主治醫(yī)生根據(jù)患者病情及入院時(shí)間給定患者的最晚手術(shù)日期Di.為確?；颊咴诘却中g(shù)期間病情穩(wěn)定且等待時(shí)間不會(huì)過(guò)長(zhǎng)，醫(yī)院要求在最晚手術(shù)日期前一定要為患者安排手術(shù).科室設(shè)有手術(shù)室K個(gè)，手術(shù)室日規(guī)定開(kāi)放時(shí)長(zhǎng)為T小時(shí)，開(kāi)放一個(gè)手術(shù)室的固定成本為cf.若手術(shù)計(jì)劃在手術(shù)室規(guī)定開(kāi)放時(shí)間內(nèi)未能完成，則需要加班，單位加班費(fèi)用為cv，由于醫(yī)務(wù)人員加班費(fèi)用昂貴，cv＞cf/T.患者i的手術(shù)時(shí)長(zhǎng)為ti，醫(yī)院為患者i手術(shù)可獲得收入為ci.決策患者的手術(shù)日期和地點(diǎn)，使醫(yī)院在一周的總收益最大.

定義決策變量如下：

xikd=1表示安排患者i在手術(shù)室k的第d天手術(shù)；否則xikd=0；

ykd=1表示手術(shù)室k在日期d開(kāi)放；否則ykd=0.

okd為中間變量，表示手術(shù)室k在第d天的加班時(shí)長(zhǎng).

2.1 手術(shù)調(diào)度問(wèn)題的確定性模型

假定患者的手術(shù)服務(wù)時(shí)間為常數(shù)，即患者的手術(shù)時(shí)長(zhǎng)為確定已知的，手術(shù)調(diào)度模型（surgery scheduling model，SSM）如下

目標(biāo)（1）分為兩部分，第一部分表示院方獲得的手術(shù)總收入，第二部分表示與開(kāi)放手術(shù)室數(shù)量及加班時(shí)長(zhǎng)相關(guān)的手術(shù)室運(yùn)作成本，目標(biāo)（1）表示最大化一個(gè)調(diào)度周期內(nèi)醫(yī)院的總收益.約束（2）和（3）表示當(dāng)患者的最遲手術(shù)日期在當(dāng)前調(diào)度周期內(nèi)時(shí)，患者在最遲手術(shù)日前一定被安排手術(shù)且只安排一次.約束（4）表示若患者的最遲手術(shù)時(shí)間晚于當(dāng)前調(diào)度周期，患者至多被安排一次手術(shù).約束（5）為手術(shù)室的日手術(shù)能力約束.約束（6）表示決策變量的關(guān)系.

圖1 患者的實(shí)際手術(shù)時(shí)長(zhǎng)與上下界的關(guān)系Fig.1 The relationship between the actual surgery duration and its upper and lower bound

2.2 手術(shù)調(diào)度問(wèn)題的兩階段魯棒模型

在SSM模型中，患者的手術(shù)時(shí)間被設(shè)置為定長(zhǎng).但在實(shí)際手術(shù)調(diào)度中，由于患者的手術(shù)時(shí)長(zhǎng)ti受醫(yī)生技術(shù)水平、疲勞程度、患者身體狀況等眾多因素影響，在術(shù)前是無(wú)法準(zhǔn)確預(yù)測(cè)的，患者的預(yù)期服務(wù)時(shí)長(zhǎng)和實(shí)際值往往存在偏差，患者的服務(wù)時(shí)間稍有波動(dòng)就可能使得原有的調(diào)度方案遠(yuǎn)離最優(yōu)，甚至不可行.因此，作者采用魯棒優(yōu)化方法求解不確定服務(wù)時(shí)間下的手術(shù)調(diào)度問(wèn)題.魯棒優(yōu)化考慮的是最壞情況下的最好，它代表了一種保守的觀點(diǎn)，得到的優(yōu)化方案并不一定是“最優(yōu)”的.但是當(dāng)不確定參數(shù)發(fā)生擾動(dòng)時(shí)，得到的解仍然可行.本文假定患者的手術(shù)服務(wù)時(shí)間為連續(xù)的區(qū)間數(shù)，以最大化手術(shù)科室收益為目標(biāo)，將不確定服務(wù)時(shí)間下的手術(shù)調(diào)度問(wèn)題描述為一個(gè)極大化極小的優(yōu)化模型，并通過(guò)對(duì)偶等理論將模型轉(zhuǎn)化為標(biāo)準(zhǔn)的混合整數(shù)線性規(guī)劃模型.

主治醫(yī)生根據(jù)診療經(jīng)驗(yàn)給出每位患者服務(wù)時(shí)間的上下界，則患者的服務(wù)時(shí)長(zhǎng)可表示為連續(xù)的區(qū)間數(shù)，令δikd為患者i分配到手術(shù)室k的第d天的實(shí)際手術(shù)時(shí)長(zhǎng)，則.定義參數(shù)? =，?表示患者的服務(wù)時(shí)長(zhǎng)偏離下界的程度，如圖1.?=0時(shí)，所有患者的手術(shù)時(shí)間取下界（最好值）；?=1時(shí)，所有患者的手術(shù)時(shí)間取得上界ti（最差值），?的取值范圍是［0，1］.

本文使用了Bertsimas和Sim［12,13］的思想來(lái)控制魯棒模型的保守程度.對(duì)于周期D內(nèi)所有調(diào)度的患者引入約束

式（8）表示最多有Γ個(gè)患者的手術(shù)時(shí)間同時(shí)達(dá)到最差值（上界）.參數(shù)Γ的取值大小由管理者事先給定，反映了醫(yī)院管理者的風(fēng)險(xiǎn)偏好程度，0≤?！躈.Γ=0時(shí)，此問(wèn)題為確定型問(wèn)題，表示所有患者的手術(shù)時(shí)間均為下界（最好情況）；Γ=N時(shí)，表示所有患者的手術(shù)時(shí)間均為上界（最差情況）.根據(jù)決策者的風(fēng)險(xiǎn)偏好程度，調(diào)整Γ的取值.若決策者較為保守，則設(shè)定Γ取值較大；反之取值較小.

由此，患者手術(shù)時(shí)長(zhǎng)的不確定集表示為

重新建立魯棒優(yōu)化模型（robust surgery scheduling model，RSSM）：魯棒優(yōu)化是求得一個(gè)這樣的解，使得最壞情況下的目標(biāo)函數(shù)最優(yōu)，最大化最壞情況下的醫(yī)院手術(shù)部的利潤(rùn)，即

約束（14），（15）組成了手術(shù)服務(wù)時(shí)間的不確定集合.目標(biāo)（10）表示在不確定集合取得最差情景下，醫(yī)院的收益最大.在模型RSSM中，發(fā)現(xiàn)只有目標(biāo)函數(shù)（10），約束（14）和（15）受手術(shù)服務(wù)時(shí)長(zhǎng)不確定性的影響，因此，RSSM模型可以表示為兩階段魯棒優(yōu)化模型，第一階段的決策變量為xikd，ykd，第二階段的決策變量為δ.

其中F（x,y）是與手術(shù)室超時(shí)開(kāi)放時(shí)長(zhǎng)相關(guān)的費(fèi)用，即

2.2.1模型轉(zhuǎn)化

為了使得F（x,y）可以代入原模型中直接求解，需要引入對(duì)偶理論對(duì)模型F（x,y）進(jìn)行變換，首先使用Denton等［9］方法化簡(jiǎn)F（x,y）的表達(dá)式.引入決策變量zkd，zkd=1表示有手術(shù)室k在第d天有超時(shí)開(kāi)放現(xiàn)象發(fā)生，否則zkd=0.重新建模F（x,y），即

由約束（28）可知，zkd=0，則δikd=0.因此，目標(biāo)函數(shù)可以化簡(jiǎn)為

F（x,y）由非線性化簡(jiǎn)為線性規(guī)劃問(wèn)題，即

模型F（x,y）可以重新表達(dá)為

上述模型為線性規(guī)劃模型，由于線性規(guī)劃問(wèn)題的基可行解對(duì)應(yīng)于可行域的頂點(diǎn).若可行域有界，線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域頂點(diǎn)上達(dá)到最優(yōu)，因此，由命題1可知，F(xiàn)（x,y）的線性松弛的解等價(jià)于原問(wèn)題的解，即

由于上述線性規(guī)劃問(wèn)題式（35）～式（39）是可行且有界的，通過(guò)強(qiáng)對(duì)偶定理可知，原最大化問(wèn)題可以等價(jià)轉(zhuǎn)化為最小化問(wèn)題.定義?,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）的對(duì)偶變量.則式（35）～式（39）的對(duì)偶線性規(guī)劃問(wèn)題為

將式（44）～式（47）代入到初始模型RSSM中，得到RSSM的魯棒對(duì)等模型RSSM1

3 數(shù)值仿真

數(shù)值實(shí)驗(yàn)在運(yùn)行環(huán)境Dell Optiplex GX620，Intel（R）Pentium（R）D CPU 2.80GHz 2.00Gb下進(jìn)行.由于模型RSSM1為標(biāo)準(zhǔn)的混合整數(shù)線性規(guī)劃模型，可以使用優(yōu)化軟件ILOG CPLEX求解.在Visual studio2008平臺(tái)下使用計(jì)算機(jī)語(yǔ)言C#調(diào)用CPLEX12.2進(jìn)行數(shù)據(jù)測(cè)試.

表1 魯棒優(yōu)化與隨機(jī)規(guī)劃方法求解性能的比較Table 1 Comparison between the robust method and stochastic programming

為了測(cè)試魯棒優(yōu)化方法的求解性能，首先將魯棒優(yōu)化方法與隨機(jī)規(guī)劃方法進(jìn)行比較.取指數(shù)分布函數(shù)的40%和60%為患者手術(shù)時(shí)間的上下界，患者的手術(shù)時(shí)長(zhǎng)為有界區(qū)間，上下界取值在區(qū)間［20，200］隨機(jī)產(chǎn)生.假定患者的手術(shù)服務(wù)時(shí)間服從正態(tài)分布，取上下界的均值為正態(tài)分布的均值，在給定分布下采樣模擬患者手術(shù)時(shí)長(zhǎng)的可能情景，樣本數(shù)量取值為50，使用隨機(jī)規(guī)劃和魯棒優(yōu)化兩種方法求解手術(shù)調(diào)度問(wèn)題.問(wèn)題的其他參數(shù)設(shè)定如下：N=15,T=8,cv=1,cf=4,K=2,Dcycle=5，患者的最遲手術(shù)日期在［1，10］之間取值.隨機(jī)產(chǎn)生6組實(shí)例進(jìn)行測(cè)試，由表1可見(jiàn)，當(dāng)Γ=4，隨機(jī)規(guī)劃與魯棒優(yōu)化的求解結(jié)果近似相同；然而，兩種方法的求解效率相差很大.魯棒優(yōu)化方法的平均求解時(shí)間為41 s，隨機(jī)規(guī)劃的平均求解時(shí)間為370 s.因此，魯棒優(yōu)化方法在問(wèn)題的求解效率上凸顯了優(yōu)勢(shì).

為了說(shuō)明Γ取值對(duì)魯棒優(yōu)化方法的影響，使用大連大學(xué)附屬新華醫(yī)院肛腸科1獲得的6組實(shí)例，在兩種參數(shù)設(shè)定cf/T＜cv＜ci/，cf/T＜ci/i＜cv情況下進(jìn)行實(shí)驗(yàn).當(dāng)cf/T＜cv＜ci/i，ci/i∈（1，2），患者數(shù)為45時(shí)，求解結(jié)果如表2、圖2所示.根據(jù)決策者的風(fēng)險(xiǎn)偏好程度改變參數(shù)Γ的取值，Γ取值越大，表示決策者越保守，Γ取值越小，表示決策者越偏好風(fēng)險(xiǎn).由表2、圖2可以得到如下結(jié)論：

表2 cf/T＜cv＜ci/i時(shí)，參數(shù)Γ對(duì)醫(yī)院收益的影響Table 2 The influence of the parameter Γ on hospital's revenue with cf/T＜cv＜ci/i

表2 cf/T＜cv＜ci/i時(shí)，參數(shù)Γ對(duì)醫(yī)院收益的影響Table 2 The influence of the parameter Γ on hospital's revenue with cf/T＜cv＜ci/i

魯棒目標(biāo)值實(shí)例 Γ=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時(shí)，參數(shù)Γ對(duì)醫(yī)院收益的影響Table 3 The influence of the parameter Γ on hospital's revenue with cf/T＜ci/i＜cv

表3 cf/T＜ci/i＜cv時(shí)，參數(shù)Γ對(duì)醫(yī)院收益的影響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時(shí)，參數(shù)Γ對(duì)利潤(rùn)、收入和成本的影響Fig.2 The influence of the parameter Γ on revenue，income and cost with cf/T＜cv＜ci/i

圖3 cf/T＜ci/i＜cv時(shí)，參數(shù)Γ對(duì)利潤(rùn)、收入和成本的影響Fig.3 The influence of the parameter Γ on revenue，income and cost with cf/T＜ci/＜cv

解的保守性隨著Γ的增加而增強(qiáng).隨著Γ的增加，醫(yī)院的利潤(rùn)呈現(xiàn)單調(diào)非增的趨勢(shì)，即管理者規(guī)避風(fēng)險(xiǎn)降低了醫(yī)院的收益.醫(yī)院的管理者可以根據(jù)不同的風(fēng)險(xiǎn)偏好程度選擇Γ的取值，進(jìn)而獲得醫(yī)院的患者手術(shù)調(diào)度方案.

當(dāng)醫(yī)院的手術(shù)能力充足，且cf/T＜cv＜ci/i時(shí)，對(duì)于所有的風(fēng)險(xiǎn)偏好系數(shù)Γ取值，醫(yī)院的總收入相同（見(jiàn)圖2），這是由于所有患者都被安排手術(shù)時(shí)醫(yī)院的總收益值達(dá)到最大.隨著Γ的增加，醫(yī)院的手術(shù)成本以及開(kāi)放手術(shù)室的數(shù)量呈現(xiàn)單調(diào)非減的趨勢(shì).

當(dāng)cf/T＜ci/i＜cv，ci/i∈（0.5,1），患者數(shù)為45時(shí)，求解結(jié)果如表3、圖3所示.根據(jù)表3和圖3的實(shí)驗(yàn)結(jié)果，可以得到如下結(jié)論：

解的保守型隨著Γ的增加而增強(qiáng).隨著Γ的增加，醫(yī)院的利潤(rùn)呈現(xiàn)單調(diào)非增的趨勢(shì)，即管理者規(guī)避風(fēng)險(xiǎn)降低了醫(yī)院的收益.

隨著Γ的變化，醫(yī)院的手術(shù)收入呈現(xiàn)不規(guī)則變化（如圖3），這說(shuō)明即使醫(yī)院的手術(shù)能力充足，在cf/T＜ci/i＜cv范圍內(nèi)，并非所有的患者都被安排手術(shù)，而且存在著患者選擇.隨著Γ的增加，醫(yī)院的手術(shù)成本呈現(xiàn)不規(guī)則變化，有增加的趨勢(shì).

為了避免患者入院后遲遲安排不上手術(shù)，或者患者入院后因未及時(shí)治療導(dǎo)致的病情惡化，本文的模型中，更加人性化的引入了患者最遲手術(shù)日期.患者入院檢查后，由其主治醫(yī)生根據(jù)患者入院時(shí)間和病情規(guī)定最遲手術(shù)時(shí)間，確?；颊咴谧钸t手術(shù)日期前接受治療.為了進(jìn)一步說(shuō)明考慮最遲手術(shù)時(shí)間對(duì)醫(yī)院收益、運(yùn)作成本等因素的影響，將引入最遲手術(shù)日期的模型與不考慮此因素的方法進(jìn)行比較，獨(dú)立重復(fù)進(jìn)行十組實(shí)驗(yàn).圖4為不同Γ下，十組實(shí)驗(yàn)中手術(shù)科室的平均收入、成本和利潤(rùn).根據(jù)表4和圖4的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，考慮最遲手術(shù)時(shí)間會(huì)降低醫(yī)院的收益，最大收益差為10.7%.考慮最遲手術(shù)時(shí)間時(shí)，手術(shù)室的平均運(yùn)作成本更高.

表4 最晚手術(shù)日期對(duì)醫(yī)院利潤(rùn)的影響Table 4 The influence of surgery deadline on hospital's revenue

圖4 最晚手術(shù)日期對(duì)手術(shù)部的利潤(rùn)、收入和成本的影響Fig.4 The influence of surgery deadline on revenue，income and cost

4 結(jié)束語(yǔ)

本文在考慮患者最遲手術(shù)日期情況下，對(duì)區(qū)間型患者服務(wù)時(shí)長(zhǎng)的手術(shù)調(diào)度問(wèn)題進(jìn)行研究.在引入管理者風(fēng)險(xiǎn)控制參數(shù)的情況下，以最大化醫(yī)院收益為目標(biāo)，建立了手術(shù)調(diào)度問(wèn)題的魯棒優(yōu)化模型.該方法在應(yīng)對(duì)患者服務(wù)時(shí)間波動(dòng)時(shí)，具有良好的魯棒性.將提出的魯棒優(yōu)化方法與隨機(jī)規(guī)劃方法進(jìn)行比較，驗(yàn)證了方法在求解效率上的優(yōu)勢(shì).實(shí)驗(yàn)結(jié)果表明，將魯棒優(yōu)化運(yùn)用于手術(shù)調(diào)度問(wèn)題，能夠減小服務(wù)時(shí)間不確定性給醫(yī)院效益帶來(lái)的影響.同時(shí)，考慮最遲手術(shù)日期會(huì)降低醫(yī)院收益，最大收益差可達(dá)到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］吳小歡，朱金福，吳薇薇.航線網(wǎng)絡(luò)區(qū)間型相對(duì)魯棒優(yōu)化設(shè)計(jì).系統(tǒng)工程學(xué)報(bào)，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］許曉晴，崔文田，林 軍，等.基于最小最大遺憾的同型并行機(jī)魯棒調(diào)度模型.系統(tǒng)工程學(xué)報(bào)，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］田文迪，胡慕海，崔南方.不確定性環(huán)境下魯棒性項(xiàng)目調(diào)度研究綜述.系統(tǒng)工程學(xué)報(bào)，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—-），女，遼寧鐵嶺人，博士生，研究方向：優(yōu)化與調(diào)度，魯棒優(yōu)化，醫(yī)療服務(wù)業(yè)運(yùn)作管理，Email：wangyuguomei@ 163.com.

2014-01-17；

2014-09-04.

國(guó)家自然科學(xué)基金資助項(xiàng)目（71021061）；教育部博士點(diǎn)專項(xiàng)基金資助項(xiàng)目（20120042110023）；

唐加福（1965—-），男，湖南東安人，博士，教授，博士生導(dǎo)師，研究方向：制造系統(tǒng)生產(chǎn)與物流運(yùn)作管理，服務(wù)系統(tǒng)運(yùn)作優(yōu)化等，Email：jftang@mail.neu.edu.cn.