考慮多因素條件下的擇期手術排程約束規劃模型

孟凡睿 陳淮莉

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

0 引 言

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

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

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

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

1 問題描述與假設

1.1 問題描述

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

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

1.2 問題假設

本文做如下假設：

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

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

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

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

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

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

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

2 約束規劃排程模型

2.1 約束規劃與模型特征

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

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

2.2 模型構建

2.2.1 參數設定

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

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

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

Dk為所有待排手術的執刀醫生，k=1…K；

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

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

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

S根據兩臺接臺手術的不同類型所產生的術間準備時間集合；

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

ODi為每臺手術i對應的執刀醫生集合，i=1…I。

2.2.2 定義決策變量

定義區間變量如下：

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

在OPL語言中，該區間變量定義為：

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

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

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

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

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

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

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

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

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

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

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

定義區間序列變量如下：

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

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

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

(3)

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

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

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

noOverlap(Qj,S) ?j∈Rj

(7)

noOverlap(Aa) ?a∈Ba

(8)

③ 順序約束：

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

(9)

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

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

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

(10)

2.2.4 目標函數

(11)

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

3 算例分析

3.1 算例數據

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

表1 待排手術相關信息表

續表1

表2 待排手術室可執行手術類型

3.2 運算結果

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

cp.setSearchPhases

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

所有手術室正常開放時間均為8小時，以8點作為0時刻，16點作為480時刻，超過480時刻的使用時間均算作超時占用。在允許最大失敗100 000次的條件下，編程求解后得到最優解。對應目標函數最小值為826，CP求解器求解速度如圖2所示。可見CP求解器收斂速度快，在求解大規模排程問題時，能夠在較短的時間內求得問題的最優解。除6號手術室外，其余9間手術室存在超時占用時間，在最優解的情況下，手術與手術室和手術與麻醉恢復床位排程方案的甘特圖如圖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 不同規模差異情況下最優目標值對比

4 結 語

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