考慮多因素條件下的擇期手術(shù)排程約束規(guī)劃模型

孟凡睿 陳淮莉

(上海海事大學(xué)物流科學(xué)與工程研究院 上海 201306)

0 引 言

醫(yī)療衛(wèi)生行業(yè)的發(fā)展在我國一直是社會關(guān)注的焦點。盡管醫(yī)療體制改革正在日益深化，但是人口基數(shù)大與人口老齡化現(xiàn)象逐漸加劇的社會現(xiàn)狀，仍舊造成了社會醫(yī)療資源嚴重緊缺的問題。手術(shù)室作為醫(yī)院資源存在最為密集的地方，其投入資金占醫(yī)院財政支出的10%[1]，利潤占醫(yī)院總盈利的40%[2]。據(jù)不完全統(tǒng)計，手術(shù)的進行會關(guān)系到醫(yī)院70%的部門[3]。因此，對手術(shù)室的合理利用可以有效地提高資源利用率，從而降低醫(yī)院的運營成本。

擇期手術(shù)排程，即在一個排程周期內(nèi)對已知將要進行的手術(shù)在有限的手術(shù)室及醫(yī)護人員等資源下進行合理安排。幾十年來，諸多學(xué)者從多種角度對該問題進行了研究。文獻[4]首先提出將手術(shù)排程分為前期計劃和分配排程，前期計劃即為確定某臺手術(shù)的手術(shù)日期，而分配排程則是就某一天的所有手術(shù)進行排序，即確定手術(shù)的開始時間。文獻[5]將待手術(shù)的患者按病情嚴重程度劃分為不同的優(yōu)先級，在考慮醫(yī)護人員加班和手術(shù)延期的雙重成本下進行擇期手術(shù)日期指派，并依照優(yōu)先級進行手術(shù)。文獻[6]在模型中考慮了術(shù)前準備時間及術(shù)后清潔時間，使模型更貼近實際手術(shù)流程。文獻[7]將不同技術(shù)類別的醫(yī)護人員，如麻醉師、醫(yī)生、護士組成一個手術(shù)小組，在手術(shù)室優(yōu)化與調(diào)度的同時完成了醫(yī)護人員的調(diào)度。文獻[8]基于防止醫(yī)護人員因過勞而造成醫(yī)療事故，引入了休息日等限制條件，使得手術(shù)排程更人性化。文獻[9]在考慮醫(yī)護人員和醫(yī)療器械的資源限制下，研究了多手術(shù)室調(diào)度問題，建立了最大化患者滿意度和最小化醫(yī)院運作成本的多目標數(shù)學(xué)模型。

在解決問題的方法上，文獻[10]在MIP模型中利用0-1變量確定某一天內(nèi)的手術(shù)和手術(shù)室的匹配情況。文獻[11]開發(fā)了改進的遺傳算法，目標是提醫(yī)療器械的使用效率，減少患者的等待時間。文獻[12]采用蒙特卡洛模擬來評估手術(shù)順序在諸多方面產(chǎn)生的影響，并基于此提出了一種“按手術(shù)時長分類排程”的方法，并采用蒙特卡洛模擬，取得了較好的研究成果。文獻[13]將手術(shù)排程抽象為柔性車間調(diào)度問題，建立了兩階段隨機規(guī)劃模型，并先后開發(fā)了遺傳算法和啟發(fā)式?jīng)Q策規(guī)則以求解手術(shù)開始時間和麻醉復(fù)蘇床位的使用時間。文獻[14-15]利用不同的改進遺傳算法分別對醫(yī)患滿意度和手術(shù)室利用效率進行了優(yōu)化。

針對這一典型NP-hard問題，前人多是考慮單一手術(shù)階段且利用遺傳算法等智能算法來解決。本文將綜合考慮上述多種影響因素，采用約束規(guī)劃模型和ILOG CPLEX中的CP求解器，對手術(shù)及手術(shù)室的匹配，手術(shù)與麻醉恢復(fù)床位的匹配，以及單一手術(shù)室內(nèi)的手術(shù)順序進行決策，以實現(xiàn)手術(shù)室的高效利用。

1 問題描述與假設(shè)

1.1 問題描述

本文綜合考慮手術(shù)和術(shù)后觀察兩個階段。對于手術(shù)室而言，手術(shù)階段又包括術(shù)前準備、手術(shù)執(zhí)行以及術(shù)后清潔。以一個工作日為排程周期，對單日內(nèi)開放的所有手術(shù)室和麻醉恢復(fù)室床位與預(yù)先確定的待執(zhí)行手術(shù)進行匹配。所有手術(shù)室為有差別資源，由于配備的醫(yī)療器械類型不同等，可接納的手術(shù)類型也不同。同時手術(shù)的分配還受執(zhí)刀醫(yī)生的影響，執(zhí)刀醫(yī)生不能同時進行兩臺以上的手術(shù)。在手術(shù)與手術(shù)室的匹配確定之后，對單一手術(shù)室內(nèi)將進行的所有手術(shù)進行排序，根據(jù)手術(shù)類型的不同，兩臺連續(xù)進行的手術(shù)之間存在時長不等的準備時間。根據(jù)實際醫(yī)院對手術(shù)的管理規(guī)定，手術(shù)的執(zhí)行具有優(yōu)先級，對于擇期手術(shù)而言，時間較長，難度較大的手術(shù)具有高優(yōu)先級，對手術(shù)室造成的污染程度最高的手術(shù)具有最低的優(yōu)先級，高齡和低齡患者的手術(shù)具有較高優(yōu)先級。在術(shù)后階段，大部分全身麻醉或術(shù)后未能達到意識恢復(fù)標準的患者需要在麻醉恢復(fù)室(PACU)進行生命體征的觀察。國內(nèi)大型醫(yī)院的麻醉恢復(fù)床位數(shù)量約為手術(shù)臺數(shù)量的一半，因此只有PACU有空余床位時，患者才可以被轉(zhuǎn)送去PACU，否則要在手術(shù)室滯留，直至有空余麻醉恢復(fù)床位。每臺手術(shù)的兩階段手術(shù)流程如圖1所示。如果手術(shù)安排不合理，就會導(dǎo)致手術(shù)室和麻醉恢復(fù)床位利用率低。

圖1 每臺手術(shù)的兩階段手術(shù)流程

1.2 問題假設(shè)

本文做如下假設(shè)：

(1) 在擇期手術(shù)中，不考慮耗時過長的科室聯(lián)合大型手術(shù)。

(2) 手術(shù)一旦開始，就不再中斷。

(3) 待排手術(shù)的手術(shù)時長和麻醉恢復(fù)時長是通過經(jīng)驗豐富的醫(yī)生和護士長的判斷預(yù)先確定的，在排程中不考慮現(xiàn)實手術(shù)過程和麻醉恢復(fù)過程中的不可控因素。

(4) 對手術(shù)時長的預(yù)估已將術(shù)后清潔時間包括在內(nèi)，且術(shù)前準備時間根據(jù)醫(yī)院歷史數(shù)據(jù)，假設(shè)兩臺接臺手術(shù)為同類型時，準備時間為15 min，否則為30 min。

(5) 手術(shù)所需的所有醫(yī)護人員和器械資源都是充足的并且能夠準時到位，同時病人也具備能夠按時進行手術(shù)的條件。

(6) 每個手術(shù)室排成日內(nèi)的第一臺手術(shù)的術(shù)前準備時間不予考慮。

其中假設(shè)(1)避免了大型手術(shù)可能會占用手術(shù)室時間過長，導(dǎo)致該手術(shù)室無法安排其他手術(shù)。

2 約束規(guī)劃排程模型

2.1 約束規(guī)劃與模型特征

約束規(guī)劃是專門用來解決實際優(yōu)化調(diào)度和規(guī)劃中的有限域約束問題，它是人工智能的重要組成部分。約束規(guī)劃算法綜合了人工智能中一致性算法和啟發(fā)式搜索算法，將求解問題的重點由算法的設(shè)計與實現(xiàn)轉(zhuǎn)向?qū)栴}的模型建立，并采用約束推理方法,很好地解決了約束條件多，搜索時間長的問題。

本文所建立的CP模型是利用IBM ILOG CPLEX Optimization Studio 12.2平臺中自帶的OPL語言實現(xiàn)的。其優(yōu)勢在于OPL語言針對排程調(diào)度問題提出了區(qū)間變量和區(qū)間序列變量的概念，作為決策變量，區(qū)間變量表示一項任務(wù)或活動，具有起點、終點和過程長度等內(nèi)在屬性。在本文中，手術(shù)、手術(shù)室以及麻醉恢復(fù)床位均為區(qū)間變量，具有開始時間、結(jié)束時間和時長等屬性。

2.2 模型構(gòu)建

2.2.1 參數(shù)設(shè)定

Oi為所有已知待排手術(shù)，i=1…I；

Rj為所有開放的待排手術(shù)的手術(shù)室，j=1…J；

Ba為所有待安排術(shù)后患者的麻醉恢復(fù)床位，a=1…A；

Dk為所有待排手術(shù)的執(zhí)刀醫(yī)生，k=1…K；

Ti為手術(shù)i的手術(shù)過程持續(xù)時間，i=1…I；

ATi為手術(shù)i的患者麻醉恢復(fù)持續(xù)時間，i=1…I；

Pj為手術(shù)室j的正常開放時長，j=1…J；

S根據(jù)兩臺接臺手術(shù)的不同類型所產(chǎn)生的術(shù)間準備時間集合；

Qulifiedi為可執(zhí)行手術(shù)i的手術(shù)室集合，i=1…I;

ODi為每臺手術(shù)i對應(yīng)的執(zhí)刀醫(yī)生集合，i=1…I。

2.2.2 定義決策變量

定義區(qū)間變量如下：

①oi表示任務(wù)集合中在手術(shù)室執(zhí)行的手術(shù)i。

在OPL語言中，該區(qū)間變量定義為：

dvar interval o[i in Oi] size T[i]

其中size定義了第i個區(qū)間變量的值。

②ani表示任務(wù)集合中在麻醉恢復(fù)室進行觀察恢復(fù)的手術(shù)i。在OPL語言中，該區(qū)間變量定義為：

dvar interval o[i in Oi] size AT[i]

③roomj表示任務(wù)集合中待安排手術(shù)的手術(shù)室j。

④beda表示任務(wù)集合中待安排術(shù)后患者的麻醉恢復(fù)床位a。

⑤ORij為二維區(qū)間變量，表示任務(wù)執(zhí)行手術(shù)i的手術(shù)室j的時間窗口。在OPL語言中，該二維區(qū)間變量定義為：

dvar interval OR[i in Oi][j in Rj] optional

其中optional表示該二維區(qū)間變量是一個可選擇變量。

⑥OAia為二維區(qū)間變量，表示進行了手術(shù)i的患者進行術(shù)后觀察的麻醉恢復(fù)床位的時間窗口。在OPL語言中，該而為變量定義為：

dvar interval OA[i in Oi][a in Ba] optional

定義區(qū)間序列變量如下：

⑦Qj表示手術(shù)室j中的手術(shù)進行順序，在OPL語言中定義為：

dvar sequence Q[j in Rj] in all(i in Oi) OR[i][j]

⑧Aa表示麻醉恢復(fù)床位a上進行術(shù)后觀察的手術(shù)患者的順序，在OPL語言中定義為：

dvar sequence A[a in Ba] in all (i in Oi) OA[i][a]

2.2.3 約束條件

① 分配約束：

altervative(Oi,(ORi1,ORi2，…，ORij)) ?i∈Oi,j∈Ri

(1)

altervative(Oi,(OAi1,OAi2，…，OAia)) ?i∈Oi,a∈Ba

(2)

在OPL語言中利用alternative函數(shù)定義任務(wù)分配的唯一性，約束式(1)表示如果第i臺手術(shù)oi出現(xiàn)在最終的排程調(diào)度中，那么執(zhí)行手術(shù)i的j個手術(shù)室ORij中，只能有一個出現(xiàn)在最終排程結(jié)果中。同樣，約束式(2)表示如果第i臺手術(shù)Oi出現(xiàn)在最終的排程調(diào)度中，那么用來進行手術(shù)i術(shù)后觀察的a個麻醉恢復(fù)床OAia中，也只能有一個出現(xiàn)在最終排程結(jié)果中。

由于手術(shù)室為有差別資源，因此約束式(3)表示手術(shù)oi只能在可接納該手術(shù)類型的手術(shù)室roomj內(nèi)執(zhí)行。

(roomjnot inQualifiedi)?ORij≠j?i∈Oi,j∈Ri

(3)

由于醫(yī)生資源有限，因此存在一名醫(yī)生需要執(zhí)刀兩臺以上手術(shù)的情況。約束式(4)表示一名醫(yī)生在同一時刻只能在一個手術(shù)室進行一臺手術(shù)。

(ODi=ODu=k)?

(endOf(oi)

(endOf(Oi)>startOf(Ou)) ?i,u∈Oii≠u,k∈Dk

(4)

② 時間約束：

span(roomj,(OR1j,OR2j,…,ORij)) ?j∈Rj

(5)

span(beda,(OA1a,OA2a,…,OAia)) ?a∈Ba

(6)

約束式(5)、式(6)利用span函數(shù)確保手術(shù)室roomj的開放時間和麻醉恢復(fù)床beda的總利用時間覆蓋所有被分配到該手術(shù)室執(zhí)行的手術(shù)ORij和被分配到該麻醉恢復(fù)床的手術(shù)OAia的總持續(xù)時間。

約束式(7)、式(8)利用noOverlap函數(shù)確保區(qū)間序列變量Qj和Aa中的手術(shù)任務(wù)在時間上不重疊，且由于兩臺連續(xù)的手術(shù)因手術(shù)類型的不同存在時長不等的準備時間，因此在約束式(4)中，約束規(guī)劃求解器會將相繼的兩臺手術(shù)的類型與S集合中的元組匹配，從而得到相對應(yīng)的準備時間。

noOverlap(Qj,S) ?j∈Rj

(7)

noOverlap(Aa) ?a∈Ba

(8)

③ 順序約束：

endBeforeStart(ORij,ORuj) ?i,u∈Oi且i≠u,j∈Rj

(9)

每臺手術(shù)都具有一定的優(yōu)先級，約束式(9)利用endBeforeStart函數(shù)表示在分配到手術(shù)室roomj的若干臺手術(shù)中，具有高優(yōu)先級的手術(shù)需要在具有低優(yōu)先級的手術(shù)開始之前完成。

在大型醫(yī)院，患者從手術(shù)室轉(zhuǎn)送到PACU進行術(shù)后觀察的轉(zhuǎn)移時間通常不超過5 min，因此約束式(10)表示手術(shù)ani的術(shù)后觀察時間在手術(shù)oi執(zhí)行結(jié)束后的第5 min時開始。

endBeforeStart(ORij,OAia,5) ?i∈Oi，j∈Ri,a∈Ba

(10)

2.2.4 目標函數(shù)

(11)

目標函數(shù)式(11)表示最小化所有手術(shù)室的超時占用時間。

3 算例分析

3.1 算例數(shù)據(jù)

為驗證第2節(jié)提出的約束規(guī)劃模型的有效性，選取某地方三甲醫(yī)院的某日待排手術(shù)信息，模擬手術(shù)排程，確定最優(yōu)的手術(shù)順序。具體手術(shù)相關(guān)信息如表1所示。在手術(shù)排程日內(nèi)，待排手術(shù)列表上共有40臺手術(shù)，該醫(yī)院共開放10間手術(shù)室，其中手術(shù)持續(xù)時長及麻醉恢復(fù)持續(xù)時長均為醫(yī)護人員根據(jù)手術(shù)類型、患者身體情況等預(yù)估所得。表2 為該醫(yī)院根據(jù)手術(shù)室配備的不同醫(yī)療器械等規(guī)定的每間手術(shù)室可接納手術(shù)類型，如骨科手術(shù)只能在配備X光設(shè)備的手術(shù)室進行。

表1 待排手術(shù)相關(guān)信息表

續(xù)表1

表2 待排手術(shù)室可執(zhí)行手術(shù)類型

3.2 運算結(jié)果

本節(jié)報告數(shù)值實驗結(jié)果，將約束規(guī)劃模型用IBM ILOG CPLEXOptimizationStudio 12.2中的OPL語言實現(xiàn)，并用CP求解器求解。測試硬件平臺為Intel Corei3-2370M，2.40 GHz CPU，4 GB內(nèi)存。通過改變默認參數(shù)設(shè)置及搜索策略，提高CP求解器的求解效率，ILOG OPL語言提供了豐富的變量啟發(fā)式及值啟發(fā)式搜索策略，包括搜索階段的設(shè)定、變量或值的選擇器等。其中，搜索階段可以令CP求解器優(yōu)先搜索某一區(qū)間變量。我們在CP求解器中嘗試了幾種不同的搜索次序，最終發(fā)現(xiàn)先固定operation區(qū)間變量數(shù)組，再固定room區(qū)間變量數(shù)組，能夠有效地提升CP求解器的求解效率。搜索階段在用OPL定義如下：

cp.setSearchPhases

(f.searchPhase(o),f.searchPhase(room))

所有手術(shù)室正常開放時間均為8小時，以8點作為0時刻，16點作為480時刻，超過480時刻的使用時間均算作超時占用。在允許最大失敗100 000次的條件下，編程求解后得到最優(yōu)解。對應(yīng)目標函數(shù)最小值為826，CP求解器求解速度如圖2所示?？梢奀P求解器收斂速度快，在求解大規(guī)模排程問題時，能夠在較短的時間內(nèi)求得問題的最優(yōu)解。除6號手術(shù)室外，其余9間手術(shù)室存在超時占用時間，在最優(yōu)解的情況下，手術(shù)與手術(shù)室和手術(shù)與麻醉恢復(fù)床位排程方案的甘特圖如圖3和圖4所示。其中圖3中斜線圖案填充部分表示由于沒有空閑的麻醉恢復(fù)床位，第15臺和第33臺手術(shù)只能分別在手術(shù)室占用15 min和30 min來進行術(shù)后觀察，待有空余床位或麻醉結(jié)束后再移送麻醉恢復(fù)室或結(jié)束麻醉恢復(fù)。在尋求得到的排程方案下，麻醉恢復(fù)床位利用率如表3所示。

圖2 CP求解器求解速度

圖3 手術(shù)室排程方案甘特圖

圖4 麻醉恢復(fù)室排程方案甘特圖

麻醉恢復(fù)床位編號開始占用時間結(jié)束占用時間占用時長麻醉恢復(fù)床位利用率112574027043.90%218569516532.35%318559024059.26%418557521053.85%518554526072.22%

3.3 對比分析

表4 不同規(guī)模差異情況下最優(yōu)目標值對比

4 結(jié) 語

手術(shù)室的成本對于醫(yī)院的運營起著至關(guān)重要的作用。本文以最小化手術(shù)室超時占用時間為目標，降本升效，充分考慮手術(shù)的術(shù)中和術(shù)后兩個階段，以及手術(shù)優(yōu)先級、依賴于手術(shù)序列的術(shù)間準備時間、醫(yī)生資源的有限性和手術(shù)室資源的差異性，建立了約束規(guī)劃排程模型。利用CPLEX的CP求解器對模型進行求解，通過對算例的求解分析，驗證了約束規(guī)劃模型對于解決排程問題的可行性與高效性。但是在現(xiàn)實醫(yī)院的手術(shù)排程過程中，存在著更多的潛在約束條件和諸多不確定性因素，因此，日后可就此做更深入的研究。