考慮臨時(shí)床位的病床聯(lián)合分配問(wèn)題*

周曉鳴 葉春明 王 爽

（1.上海理工大學(xué) 上海 200082）（2.江蘇大學(xué) 鎮(zhèn)江 212013）

1 引言

1.1 問(wèn)題的由來(lái)

手術(shù)室的調(diào)度包括了很多范圍，不僅僅局限于手術(shù)室內(nèi)。由于手術(shù)后創(chuàng)口的愈合以及麻醉的恢復(fù)都需要較長(zhǎng)的一段時(shí)間，因此引申出了手術(shù)后的病床管理。病房管理的目的就是為了接受完手術(shù)以及做術(shù)前準(zhǔn)備等待手術(shù)的患者提供更加舒適、合理的環(huán)境，以及能夠最大化地利用有限的空間使更多的患者入住以獲得更高的經(jīng)濟(jì)效益［3］。

病房管理主要包括住院管理、病床管理、衛(wèi)生、飲食等［4］。其中病床管理是造成目前醫(yī)院供不應(yīng)求的主要因素，因此本文主要研究病床管理即本章的病床分配問(wèn)題的研究。

1.2 病床分配問(wèn)題的研究現(xiàn)狀

對(duì)于整個(gè)醫(yī)療調(diào)度的研究，國(guó)外都要早于國(guó)內(nèi)，病床的資源調(diào)度問(wèn)題也不例外。相比較國(guó)外已經(jīng)取得了一定的成果并且已應(yīng)用到實(shí)際管理中，國(guó)內(nèi)在此方面的研究還處于探索階段。

Handyside 等對(duì)擇期患者和急診患者使用病床的比例分配問(wèn)題做出了綜述［5］。在這之前，Young等著重從計(jì)算患者的平均使用病床時(shí)間等多種角度研究，來(lái)控制患者人數(shù)以緩解緊急床位需求問(wèn)題［6］。有了之前研究的基礎(chǔ)，Chavis 等使用仿真的技術(shù)方式研究了緊急情況下的床位需求，針對(duì)每日平均住院率以及緊急使用床位率進(jìn)行模擬，并以此預(yù)測(cè)了排班對(duì)于床位使用率的影響［7］。

Bettinelli 等使用了語(yǔ)言編碼經(jīng)過(guò)計(jì)算機(jī)仿真后得到醫(yī)療系統(tǒng)規(guī)劃的新數(shù)值，這個(gè)研究也為醫(yī)院的擴(kuò)張計(jì)劃給予了理論上的指引。目前已被某重點(diǎn)醫(yī)院在實(shí)際病床管理中實(shí)現(xiàn)了［8］。

Harrois 等對(duì)住院系統(tǒng)的管理現(xiàn)狀寫(xiě)了比較全面的綜述，并提出了迭代分配模型［9］；Lizotte發(fā)表的一篇綜述中提出了能夠用于定期靜態(tài)調(diào)度系統(tǒng)模型以及持續(xù)動(dòng)態(tài)調(diào)度系統(tǒng)［10］。

Harper 等提出了病床占用率和住院拒絕率兩個(gè)指標(biāo)，他們認(rèn)為醫(yī)院作為一套完整的系統(tǒng)，其內(nèi)部是一個(gè)動(dòng)態(tài)的、復(fù)雜的非線性結(jié)構(gòu)，因此對(duì)于病床的管理必須在不確定的并且資源受限的情況下［11］。

Tutuncu 等在該領(lǐng)域研究了較長(zhǎng)一段時(shí)間后，首次把迪杰斯特拉算法和遺傳算法應(yīng)用于短期確定性的病床分配問(wèn)題中，優(yōu)化了每個(gè)時(shí)間段內(nèi)的床位類(lèi)型。他們認(rèn)為手術(shù)室資源的優(yōu)化和控制是為了滿足患者的需求，提高資源的使用效率。但是，服務(wù)行業(yè)的需求變化過(guò)快，之前的數(shù)據(jù)不一定符合當(dāng)下的情況，需求和預(yù)測(cè)不一定能夠得到準(zhǔn)確的結(jié)果［12］。

病床的優(yōu)化調(diào)度分配問(wèn)題，國(guó)外學(xué)者的研究已領(lǐng)先很多，而國(guó)內(nèi)的研究尚處于起步階段。直到近五六年，有關(guān)病床分配和患者入院安排問(wèn)題的相關(guān)文獻(xiàn)才漸漸豐富起來(lái)，研究的難度和寬度也日益上升［13］。近來(lái)，有學(xué)者將病床分配問(wèn)題與收益管理思想相結(jié)合，用收益管理的存量控制方法實(shí)現(xiàn)對(duì)病床的分配。該論文運(yùn)用了兩階段容量控制模型，開(kāi)啟了床位分配問(wèn)題中運(yùn)用收益管理思想的先河［14］。

綜上所述，無(wú)論是研究還是應(yīng)用，在病床分配問(wèn)題上我國(guó)都落后于一些發(fā)達(dá)國(guó)家。因此，有必要吸取他們的經(jīng)驗(yàn)和成果，結(jié)合我國(guó)實(shí)際情況進(jìn)行探索［15］。就目前已有文獻(xiàn)來(lái)看，大多都局限于某家醫(yī)療系統(tǒng)內(nèi)部，尚未有病床聯(lián)合調(diào)度的先例。

1.3 問(wèn)題描述

在我國(guó)經(jīng)濟(jì)和科技的飛速發(fā)展以及醫(yī)療技術(shù)的迅猛進(jìn)步下，人們對(duì)于醫(yī)院的依賴也變得日益嚴(yán)重。因此，近年來(lái)國(guó)內(nèi)相關(guān)部門(mén)投入了大量的精力研究關(guān)于怎樣能夠更充分地利用病床資源的問(wèn)題，并且已有了一些顯著的效果。然而由于我國(guó)人口基數(shù)過(guò)大、研究起步較晚，想要短時(shí)間內(nèi)解決好此類(lèi)問(wèn)題還存在較大難度［16］。就目前研究而言，幾乎所有研究都局限于某一家醫(yī)院內(nèi)嘗試各種模型以及各類(lèi)算法來(lái)尋求最優(yōu)解［17］。然而，現(xiàn)實(shí)存在的問(wèn)題是某些醫(yī)院每天人數(shù)超過(guò)最大負(fù)荷，甚至出現(xiàn)提前三天排隊(duì)、夜里到醫(yī)院排隊(duì)、黃牛代排隊(duì)等一系列社會(huì)問(wèn)題，而有些醫(yī)院的患者量卻遠(yuǎn)低于其能接納人數(shù)的上限，造成了很多醫(yī)療資源的浪費(fèi)。造成這種情況發(fā)生的原因也有很多，比如醫(yī)師的水平、醫(yī)院的規(guī)模、醫(yī)院的宣傳力度和口碑以及醫(yī)院的交通便利程度等［18～20］。綜上種種因素，能夠發(fā)現(xiàn)，完全可以考慮將兩家甚至多家醫(yī)院的病床聯(lián)合調(diào)度。

經(jīng)過(guò)研究，本文在已有的研究的基礎(chǔ)上考慮了聯(lián)合調(diào)度的思想，為避免一些現(xiàn)實(shí)中難以預(yù)測(cè)的問(wèn)題，本文并非直接用兩家醫(yī)院直接聯(lián)合調(diào)度。而是引入了“臨時(shí)床位”，即在某家醫(yī)院已有的固定床位以外，假設(shè)了存在一套醫(yī)療環(huán)境相當(dāng)，并且數(shù)量不限的臨時(shí)床位。

2 模型的描述

模擬手術(shù)病人使用病床的過(guò)程，每位病人依次到達(dá)，一共有三種情況：

1）病人到達(dá)醫(yī)院后，存在已開(kāi)設(shè)且空余并符合要求的床位，將該病人安排于此病床；

2）病人到達(dá)醫(yī)院后，若符合要求的病床已有病人使用，或者該病床的上一位病人離開(kāi)時(shí)間小于45min，則將此病人依次安放在下一個(gè)符合要求的病床；

3）病人到達(dá)醫(yī)院后，若已無(wú)符合要求的床位空余，或無(wú)床位距上一位病人離開(kāi)時(shí)間大于等于45min，則將該病人安排在臨時(shí)床位處。本文不考慮臨時(shí)床位個(gè)數(shù)。

本題只考慮病人-床位的分配，要求盡可能多地分配病人到合適的病床，并且在此基礎(chǔ)上最小化被使用床位的數(shù)量。

2.1 模型假設(shè)

1）有限時(shí)間段假設(shè)。一個(gè)醫(yī)院中的患者住院出院活動(dòng)屬于連續(xù)性離散事件，前一時(shí)段患者的分配狀態(tài)為當(dāng)前工作的初始條件。本文假設(shè)以2018年1月20日的一晝夜為時(shí)間窗。

2）信息完備假設(shè)。床位分配問(wèn)題的研究對(duì)象是患者和病床，其中患者信息包括進(jìn)入和離開(kāi)床位時(shí)刻，床位占用時(shí)間，性別以及病情的傳染性等。病床信息包括病床的數(shù)量，病床的男女分類(lèi)，以及該患者分配前病床的初始狀況，研究時(shí)需要的信息均假設(shè)已知。

3）床位容量假設(shè)?，F(xiàn)有多數(shù)床位分配問(wèn)題的研究是基于容量允許假設(shè)，即醫(yī)院床位資源是充足的，不考慮資源受限問(wèn)題。即對(duì)于任意一個(gè)患者，總存在至少一個(gè)可用的床位。本文中將床位分為固定床位和臨時(shí)床位兩種，即在有限的固定床位無(wú)法滿足的前提下才會(huì)啟用臨時(shí)床位且數(shù)量不受限制。

4）進(jìn)入該醫(yī)院里的患者只能分配到與之屬性相吻合的床位。

5）每位患者的住院和出院兩個(gè)時(shí)刻必須在同一床位，期間不能挪移別處。

6）分配在同一床位的兩個(gè)患者之間的空檔時(shí)間必須大于或等于45min。

7）本文所有問(wèn)題只考慮手術(shù)患者。

8）假設(shè)所有患者按既定時(shí)間手術(shù)、恢復(fù)，沒(méi)有延誤。

9）不考慮患者的異質(zhì)性。

10）不考慮手術(shù)室到病床的距離。

11）本文涉及所有時(shí)間以分鐘為單位。

2.2 模型建立

問(wèn)題優(yōu)化模型的建立是基于一定的前提和假設(shè)條件的，以便抓住問(wèn)題的主要矛盾，忽略對(duì)問(wèn)題本質(zhì)沒(méi)有影響或影響不大的因素。病人-病床分配問(wèn)題的研究基于有限時(shí)間段假設(shè)、信息完備性假設(shè)，以及床位容量狀況假設(shè)等。

第一階段優(yōu)化模型：

第二階段優(yōu)化模型：

式（1）表示目標(biāo)函數(shù)取安排在固定床位的病人占總病人數(shù)比值的最大值；式（2）表示唯一性約束，即一位病人只能安排在一個(gè)床位，且中途不能挪移；式（3）和（4）對(duì)yi，j，k的取值作出定義；式（5）表示獨(dú)占性約束，即一個(gè)病床在同一時(shí)段內(nèi)只能被安排一位病人，但是允許不同的病人分批安排在同一病床；式（6）表示兩位連續(xù)安排在同一病床的病人之間的空檔時(shí)間不小于45min；式（7）和（8）表示每位病人只能按照既定的男/女、長(zhǎng)期/短期、傳染/不傳染等功能屬性停在與之屬性相吻合的床位；式（9）表示對(duì)各變量的約束。式（10）表示所有被使用床位的空閑時(shí)間總和，對(duì)于一般的分配問(wèn)題，在每種分配方式中，共有N+M 個(gè)空閑時(shí)間，其中N 為病人數(shù)，M 為床位數(shù)。每個(gè)病人恰好對(duì)應(yīng)一個(gè)緊前床位空閑時(shí)間Si，共N 個(gè)。每個(gè)床位最后各有一個(gè)空閑時(shí)間Sk無(wú)病人對(duì)應(yīng)，共M 個(gè)，所以目標(biāo)函數(shù)可以表示為式（11）。該公式計(jì)算比前者復(fù)雜度低，因此選擇式（11）為目標(biāo)函數(shù)；式（12）～（19）與第一階段約束類(lèi)似；式（20）～（22）表示對(duì)目標(biāo)函數(shù)變量的定義；式（23）表示第二階段模型建立在第一階段的基礎(chǔ)上。

2.3 模型的符號(hào)說(shuō)明

模型中的各符號(hào)的含義說(shuō)明如表1所示。

表1 符號(hào)說(shuō)明

3 算法設(shè)計(jì)

本題采用兩階段優(yōu)化分步優(yōu)化方法建立模型，第一階段模型設(shè)立被分配在固定床位的患者數(shù)與患者總數(shù)的比值最大為目標(biāo)函數(shù)，在此基礎(chǔ)上設(shè)立固定床位的空閑時(shí)間最小化作為第二階段的目標(biāo)函數(shù)。在確定的患者數(shù)的基礎(chǔ)上保證被使用的床位的使用效率最大（即空閑時(shí)間最?。┘纯烧f(shuō)明使用了最少量的床位。選用遺傳算法對(duì)其進(jìn)行求解，具體步驟如下。

3.1 編碼

這里我們采用簡(jiǎn)單易用的整數(shù)編碼方法。對(duì)于有n 個(gè)患者的病床分配問(wèn)題，將n 個(gè)患者隨機(jī)賦予0 或1，0 表示該患者被安排至臨時(shí)床位，1 表示該患者被安排至固定床位。例如有10 個(gè)患者的分配問(wèn)題，｛0，1，1，0，1，0，1，1，0，1｝就是一個(gè)合法的染色體，表示第2，3，5，7，8，10 個(gè)患者被安排在固定床位，而1，4，6，9號(hào)患者被安排在臨時(shí)床位。

3.2 產(chǎn)生初始群體和適應(yīng)度函數(shù)

利用遺傳算法尋優(yōu)，就是要找到適應(yīng)度最大的染色體，本章模型要求盡可能多的分配患者到固定的床位，因此可以直接以分配到固定床位的患者的總數(shù)量作為適應(yīng)度函數(shù)進(jìn)行，函數(shù)表達(dá)式為式（24）。

通過(guò)隨機(jī)的方式產(chǎn)生初始群體，采用輪盤(pán)賭選擇的方法進(jìn)行選擇。

3.3 遺傳算子設(shè)計(jì)

1）采用正交交叉方式進(jìn)行交叉算子設(shè)計(jì)。記當(dāng)前的第K 代種群為先，然后對(duì)種群進(jìn)行兩兩配對(duì)，種群依據(jù)預(yù)先產(chǎn)生的正交陣對(duì)進(jìn)行交叉，得到種群Bk。

2）按照提前約定的變異概率對(duì)交叉后得到的種群Bk中的每個(gè)體Xi進(jìn)行變異。

3）變異后產(chǎn)生的種群中最差的S 個(gè)體需要更新操作，并得的種群為Dk。

3.4 終止條件

遺傳算法本身具有較大的隨機(jī)性，因此使用幾條基于啟發(fā)式規(guī)則作為條件實(shí)現(xiàn)終止。

1）若算法迭代到5000代，則終止算法。

2）若某一代群體中的染色體平均適應(yīng)度與當(dāng)代的最佳染色體適應(yīng)度的比值大于0.9，那么算法終止。

3）若最佳染色體連續(xù)保持200 代，則終止算法。

3.5 算法流程圖

根據(jù)上述算法的步驟，作出算法流程圖如圖1所示。

4 實(shí)驗(yàn)結(jié)果

4.1 參數(shù)設(shè)置

使用python 語(yǔ)言實(shí)現(xiàn)該算法的求解過(guò)程。首先設(shè)計(jì)了多組實(shí)驗(yàn)對(duì)算法的交叉率和變異率進(jìn)行選擇，一般情況下，交叉率的取值范圍為0.6～0.9，變異率的取值范圍為0.01～0.1。本文經(jīng)過(guò)多次迭代，選擇變異率為0.07，交叉率為0.8。

圖1 基于經(jīng)典遺傳算法的流程圖

4.2 實(shí)例求解

為驗(yàn)證模型和算法的實(shí)用性，現(xiàn)以某大型三甲醫(yī)院的手術(shù)間資源數(shù)據(jù)為依據(jù)進(jìn)行測(cè)試。數(shù)據(jù)如下：時(shí)間窗為一周，該醫(yī)院每周平均預(yù)約住院人數(shù)為303（將其進(jìn)行編號(hào)1～303），醫(yī)院目前已有固定床位（代號(hào)T）30 張，臨時(shí)床位（代號(hào)S）37 張?；颊叩念?lèi)型及住院預(yù)計(jì)時(shí)間等數(shù)據(jù)均已知。

在Intel Core i5-4590 CPU，主頻3.30GHz，內(nèi)存8GB 的操作系統(tǒng)下，使用python 語(yǔ)言，參數(shù)設(shè)置為交叉率0.8，變異率0.07，運(yùn)行得出目標(biāo)函數(shù)的最優(yōu)解為：接待患者223人，使用固定床位28張，臨時(shí)床位32 張，T 和S 的床位的使用數(shù)目和被使用床位的平均使用率（床位占用時(shí)間比率），通過(guò)Python程序的算法實(shí)現(xiàn)，得出其線狀圖如圖2所示。

圖2 被使用床位平均使用率

為證明此模型的合理性和求解算法的實(shí)用性，隨機(jī)調(diào)取了該醫(yī)院過(guò)去一年內(nèi)十個(gè)時(shí)間窗的預(yù)約人數(shù)和實(shí)際安排住院人數(shù)的柱狀圖，如圖3 所示；以及十個(gè)時(shí)間窗的床位平均使用率如圖4（圖中最右邊點(diǎn)橫坐標(biāo)表示實(shí)驗(yàn)組）所示。由圖3 及4 可以看出，與過(guò)去相比該實(shí)驗(yàn)組的患者入住率以及床位的使用率都有所增加，驗(yàn)證了本章模型的實(shí)用性。

圖3 患者入院率對(duì)比圖

圖4 床位平均使用率

5 結(jié)語(yǔ)

本章針對(duì)患者住院信息已知的情況下，如何將固定病房床位與臨時(shí)床位聯(lián)合調(diào)度的問(wèn)題進(jìn)行了討論。根據(jù)固定床位與臨時(shí)床位的不同特點(diǎn)，建立了以盡可能安排最多的患者住院為第一優(yōu)先級(jí)，以最大化被使用床位的使用率為第二優(yōu)先級(jí)的目標(biāo)函數(shù)，結(jié)合病床的使用特點(diǎn)進(jìn)行約束，以保證在盡可能不浪費(fèi)醫(yī)療資源的基礎(chǔ)上最大化接受住院患者數(shù)量。使用了解決此類(lèi)調(diào)度問(wèn)題最經(jīng)典的遺傳算法進(jìn)行求解，分析了算法中各參數(shù)的選擇對(duì)求解結(jié)果的影響，并求出最優(yōu)解。隨機(jī)選取了該醫(yī)院以往的安排情況與求解結(jié)果進(jìn)行對(duì)比，發(fā)現(xiàn)此結(jié)果都有較明顯的優(yōu)勢(shì)，證明了該模型和算法的有效性和實(shí)用性。

本章的研究還存在一定的局限性，例如對(duì)時(shí)間窗的選擇不夠長(zhǎng)、假設(shè)的許多因素也許比現(xiàn)實(shí)完美、目標(biāo)函數(shù)的沒(méi)有考慮經(jīng)濟(jì)因素等。其中對(duì)研究對(duì)象的選擇范圍是本文研究的主要因素，考慮了帶有臨時(shí)床位的聯(lián)合調(diào)度即相當(dāng)于兩家病床的聯(lián)合調(diào)度，因此考慮n 家醫(yī)院的手術(shù)室資源聯(lián)合調(diào)度成為下一步研究的重點(diǎn)。