孟凡睿 陳淮莉

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

0 引 言

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

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

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

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

1 問題描述與假設

1.1 問題描述

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

圖1 每臺手術的兩階段手術流程

1.2 問題假設

本文做如下假設：

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

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

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

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

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

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

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

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

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

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

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

2.2 模型構建

2.2.1 參數(shù)設定

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

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

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

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

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

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

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

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

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

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

2.2.2 定義決策變量

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

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

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

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

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

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

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

③roomj表示任務集合中待安排手術的手術室j。

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

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

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

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

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

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

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

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

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

⑧Aa表示麻醉恢復床位a上進行術后觀察的手術患者的順序，在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ù)定義任務分配的唯一性，約束式(1)表示如果第i臺手術oi出現(xiàn)在最終的排程調(diào)度中，那么執(zhí)行手術i的j個手術室ORij中，只能有一個出現(xiàn)在最終排程結果中。同樣，約束式(2)表示如果第i臺手術Oi出現(xiàn)在最終的排程調(diào)度中，那么用來進行手術i術后觀察的a個麻醉恢復床OAia中，也只能有一個出現(xiàn)在最終排程結果中。

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

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

(3)

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

(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ù)確保手術室roomj的開放時間和麻醉恢復床beda的總利用時間覆蓋所有被分配到該手術室執(zhí)行的手術ORij和被分配到該麻醉恢復床的手術OAia的總持續(xù)時間。

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

noOverlap(Qj,S) ?j∈Rj

(7)

noOverlap(Aa) ?a∈Ba

(8)

③ 順序約束：

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

(9)

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

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

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

(10)

2.2.4 目標函數(shù)

(11)

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

3 算例分析

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

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

表1 待排手術相關信息表

續(xù)表1

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

3.2 運算結果

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

cp.setSearchPhases

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

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

圖2 CP求解器求解速度

圖3 手術室排程方案甘特圖

圖4 麻醉恢復室排程方案甘特圖

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

3.3 對比分析

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

4 結 語

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