考慮設備轉換成本的MRI檢查預約調度優(yōu)化

林 暉,王 杉

(1.上海交通大學 安泰經濟與管理學院,上海 200030;2.中山大學 管理學院,廣州 510275)

核磁共振成像(MRI)檢查是醫(yī)生確診患者病情的重要手段[1],目前MRI檢查的等待時間長達16～36天[2],是患者得到確診和治療的瓶頸環(huán)節(jié)。一方面,MRI設備昂貴,平均500萬元一臺,最高可達2 000萬元,是醫(yī)院的稀缺資源,無法簡單地通過增加設備數(shù)量來應對快速增長的MRI檢查需求[3]。另一方面,MRI檢查需針對檢查部位使用特定的線圈,一般最常用的線圈就有近10種[4]。當前后兩名患者檢查部位不同時,更換線圈會產生較長的裝卸時間和線圈損耗[3]。2018年的一項研究[5]顯示,更換MRI線圈的平均時間長達13.4 min,占平均檢查時間的55%,減少線圈更換次數(shù)可顯著提高MRI設備的利用率。另外,一臺MRI設備的線圈成本高達32萬美元[6],而裝卸線圈需要醫(yī)務人員十分嚴格且精細的操作[4]。已有文獻表明,頻繁更換線圈會加速線圈損耗,導致線圈故障,帶來高昂的維修甚至重新購置的費用[4,7]。在實踐中,許多醫(yī)院采用先到先服務的預約規(guī)則[8-9],但由于患者檢查需求的異質性,大大增加了線圈的裝卸次數(shù),產生了非常高的轉換成本。目前,已有醫(yī)院通過建立MRI預約規(guī)則來減少更換線圈的次數(shù)[4],如使用固定的日期或時間段來檢查特定部位[2,4],從而降低更換線圈帶來的轉換成本。但這又會影響患者預約的靈活性,使得MRI設備空置、患者長時間等待,導致醫(yī)療資源浪費、患者滿意度降低。因此,如何對MRI檢查預約進行合理的調度,在及時滿足患者需求的同時,降低更換線圈帶來的轉換成本,是一個亟待解決的重要問題。

關于醫(yī)院預約調度的文獻大多以盡快滿足患者需求為目標,同時考慮所消耗的資源成本。許多文獻考慮了患者爽約[10-14]、患者到達不及時[15]、未預約患者[16]、隨機服務時間[17]、醫(yī)患匹配度[18]等因素,但很少考慮到MRI設備的特殊性,即服務不同類型患者時會產生轉換成本[3]。潘興薇等[9]根據(jù)某三甲醫(yī)院的實際調研數(shù)據(jù),建立了MRI檢查預約仿真模型。Geng等[19]對MRI預約調度建立了馬爾可夫決策過程模型。但都沒有考慮MRI設備的轉換成本。Qiu等[3]考慮了MRI設備在不同類型患者間的轉換成本,在一個工作日內優(yōu)化患者的檢查次序和檢查時間。但沒有考慮跨工作日的預約排程,而現(xiàn)實中患者很少能在預約當天進行MRI檢查[2]。其他與MRI設備調度相關的文獻則通過仿真方法對調度規(guī)則進行檢驗,沒有通過數(shù)學建模的方式對問題進行分析和求解[2,20]。因此,已有的研究成果并不能被應用于MRI檢查的日間預約調度問題,同時實現(xiàn)降低MRI設備轉換成本和及時滿足患者需求兩個目標。

考慮到MRI檢查預約給理論和實踐帶來的挑戰(zhàn),本文將研究如何對MRI檢查需求進行預約調度,以最小化更換線圈產生的轉換成本以及患者等待或被拒絕的成本。針對該問題,本文建立了馬爾可夫決策過程模型[8,21-22],通過策略迭代算法[23]得到醫(yī)院的最優(yōu)排程。為了方便醫(yī)院實際應用,本文提出了3種預約調度規(guī)則:單日規(guī)則、開放獲取規(guī)則和短視規(guī)則。但由于轉換成本的引入,即使給定調度規(guī)則,該問題仍是一個復雜的組合優(yōu)化問題。因此,本文分析了各調度規(guī)則下的問題性質,設計并證明了最優(yōu)解算法。除此之外,本文還依據(jù)分而治之的思想提出了忽略容量約束的分解算法[21]。通過數(shù)值實驗發(fā)現(xiàn),在MRI設備的檢查能力緊張或患者等候成本高,即單日容量較小或等待成本較大時,最優(yōu)解傾向于不開放未來工作日的預約,以避免增加等待成本,此時采用單日規(guī)則可實現(xiàn)最優(yōu)調度。當醫(yī)院希望盡快滿足患者的檢查需求或MRI設備轉換耗時較短,即拒絕成本較高或轉換成本較低時,開放獲取規(guī)則與最優(yōu)解的性能差距僅為1.29%。在患者等待成本較低時,可以采用短視規(guī)則算法將部分患者安排到后續(xù)工作日,從而降低MRI設備轉換成本和拒絕成本,此時與最優(yōu)解的性能差距為10.75%。在MRI設備的檢查能力緊張或非常充足時,醫(yī)院可以忽略檢查能力約束,對每個類型的病人單獨通過策略迭代算法進行調度,再通過本文提出的分解算法來構造符合檢查能力約束的排程,此時與最優(yōu)解僅有不超過1.5%的性能差距。通過使用上海某大型綜合醫(yī)院的實際數(shù)據(jù)進行模擬,并對比醫(yī)院的實際運營情況,本文發(fā)現(xiàn),使用本文設計的規(guī)則和算法,能在檢查容量配置、患者拒絕比例、患者平均等待天數(shù)、日平均患者類型數(shù)等指標上取得顯著改善。

本文的貢獻主要有:

(1) 所建立的模型具有較強的一般性,如僅需假設需求具有馬爾可夫性、轉換成本和等待成本單調遞增,能廣泛應用于不同環(huán)境和場景。

(2) 設計了易于應用的調度規(guī)則與算法,對不同規(guī)則的應用效果及其所適用的場景進行了比較和分析,為醫(yī)院MRI預約調度提供了管理洞見。

(3) 過往文獻在模型建立時沒有考慮MRI設備的轉換成本,本文同時考慮了設備轉換成本、患者等待成本和被拒絕成本,除了直接用于MRI檢查場景,還可用于其他具有類似轉換成本的預約調度問題,填補了預約調度文獻在這方面的空白。

1 模型構建與求解

1.1 數(shù)學模型

符號及含義:

T——可預約的時間范圍

J——檢查類型的數(shù)量

M——醫(yī)院每日檢查能力上限

St=——第t期初的排程表

Dt=}——第t期的檢查需求

At=}——對第t期需求的排程表

fc——轉換成本函數(shù)

fw——患者等待成本函數(shù)

cr——患者拒絕成本

gt(St,Dt,At)——醫(yī)院在第t期的成本

NN——醫(yī)院的總經營周期

δ——折現(xiàn)率

π={μ1,μ2,…,μNN}——醫(yī)院選擇排程表的策略

SDP——單日規(guī)則(Same Day Policy)

OAP——開放獲取規(guī)則(Open Access Policy)

MP——短視規(guī)則(Myopic Policy)

DA——分解算法(Decomposition Algorithm)

由于MRI設備檢查不同類型患者時需要更換線圈,這會造成一定的時間損耗,從而產生轉換成本。如果不能及時安排MRI檢查,則又會降低患者滿意度,甚至導致患者病情惡化。因此,醫(yī)院需權衡轉換成本與患者等待或被拒絕的成本。

本文對成本函數(shù)做出以下假設:

假設1若在同一個工作日內有n種不同的檢查類型,則產生轉換成本fc(n),是n的一般性單調遞增函數(shù);若一個患者從提出需求到接受檢查需等待m天,則產生患者等待成本fw(m),是m的一般性單調遞增函數(shù);每拒絕一位患者產生拒絕成本cr1)醫(yī)院可通過成本函數(shù)fc、fw 和參數(shù)cr 來體現(xiàn)對不同成本的重視程度。例如考慮線性函數(shù)fc(n)=cr n 和fw(m)=cw m,則:cw ＜cc,cr ＜cc,表示醫(yī)院非常重視MRI設備使用效率,反之則表示更重視患者就醫(yī)體驗。

在實踐中,每天能進行的檢查數(shù)量受MRI設備檢查能力的限制,假設每天最多進行M個檢查。這里,采用每天檢查數(shù)量的上限,而非每天檢查總時長的上限,有以下兩點原因:①在實踐中,MRI檢查所耗費的時間一般是固定的,因此控制檢查數(shù)量,近似于控制檢查總時長;②本文主要考慮轉換成本與延遲檢查之間的權衡,避免對檢查時長進行建模,能讓模型更清晰地捕獲問題的實質。此外,在數(shù)值實驗中,本文將問題拓展為給定每天檢查總時長的上限,考慮不同類型檢查耗費時間不同的情況,能得到相似的結論(見3.4節(jié))。

給定第t期的初始預約表St、檢查需求Dt和排程表At,可以計算醫(yī)院在第t期產生的成本,即

式中:第1部分表示排程表At產生的患者等待和拒絕成本;第2部分表示在第t期產生的轉換成本,其中,0-范數(shù)‖x‖0的取值為向量中非零元素的數(shù)量,即安排在第t期的患者類型的數(shù)量。

第t期結束后,醫(yī)院根據(jù)當前預約表St和排程表At更新預約表:刪除當期已經完成的預約,保留未被服務的預約,得到第t+1期開始前面臨的預約表St+1。則預約表的更新過程為

假設醫(yī)院考慮NN期的總成本2)當NN 充分大時,可以視為考慮無窮長時間上的總成本,即醫(yī)院整個經營周期的(折現(xiàn))總成本,折現(xiàn)率為δ,給定初始預約表S1、檢查需求D1和策略π={μ1,μ2,…,μNN},其中,μt表示在第t期對每種可能的預約表St及檢查需求Dt,執(zhí)行怎樣的排程At,即μt是預約表St及檢查需求Dt的函數(shù),則醫(yī)院從第1～第NN期的總成本為

因此,醫(yī)院面臨的優(yōu)化問題(P1)為:

其中:式(4)為正整數(shù)約束,即MRI設備的預約排程以每個檢查需求為單位;式(5)為檢查需求約束,即每個檢查需求都需要被安排或拒絕;式(6)為MRI設備檢查能力約束,即安排在同一期的檢查數(shù)量之和不超過M。

優(yōu)化問題(P1)求解的難度來自3個方面:①決策變量有時間和檢查類型兩個維度,而過往的預約調度文獻只有時間一個維度;②由于安排的檢查日期和患者類型都是整數(shù)變量,所以這是一個組合優(yōu)化問題;③由于0-范數(shù)的引入,導致目標函數(shù)是非線性的,無法將DP問題改寫為整數(shù)規(guī)劃問題。

1.2 最優(yōu)解求解

針對中小規(guī)模問題,可采用策略迭代算法得到最優(yōu)解。策略迭代算法可以用來求解包含有限種狀態(tài)和有限種控制的動態(tài)規(guī)劃問題。首先選擇初始策略π1,該策略規(guī)定了每種狀態(tài)下執(zhí)行的控制。其次計算在策略π1下每種狀態(tài)的性能勢(Potential),即在策略π1下每種狀態(tài)的長期成本。最后進行策略改進:對每種狀態(tài),選擇使執(zhí)行控制產生的當前成本與執(zhí)行控制后新狀態(tài)的性能勢之和最小控制。若改進后的策略與原策略不同,則計算新策略下每種狀態(tài)的性能勢,并繼續(xù)進行策略改進。曹希仁[23]證明了策略迭代算法能收斂到最優(yōu)策略(應用策略迭代算法求P1最優(yōu)策略的偽代碼見附錄A)。

2 近似算法

2.1 單日規(guī)則

雖然策略迭代算法能得到最優(yōu)解,但由于計算復雜度高,無法求解大規(guī)模問題,故參考醫(yī)院在MRI預約調度上的管理實踐,本文提出3種預約調度規(guī)則。

在實踐中,許多醫(yī)院為了方便管理,對每個檢查需求,只能選擇當天檢查或拒絕,不開放未來日期的預約,本文將該排程規(guī)則記為“單日規(guī)則”。在單日規(guī)則下,第t+1期初的預約表St+1不受第t期的決策At的影響。因此,動態(tài)規(guī)劃問題(P1)轉換為在每期初求解整數(shù)規(guī)劃問題(P2):

雖然通過Gurobi等求解器可以得到P2的最優(yōu)解,但在大規(guī)模問題中依然需要較長的求解時間。因此,根據(jù)P2最優(yōu)解的性質,設計了求解P2最優(yōu)解的多項式時間算法,記為“單日規(guī)則算法”(SDP algorithm)。單日規(guī)則算法偽代碼如下所示:

證明見附錄B。

由于在單日規(guī)則下只允許當天檢查或拒絕,醫(yī)院一旦選擇接受一個j類檢查,則多接受一個j類檢查不會增加轉換和等待成本,只會降低拒絕成本。因此,一旦接受一個j類檢查,醫(yī)院應盡可能多接受j類檢查,直到達到需求或容量約束。

命題2給定當前預約表St、檢查需求Dt和可行排程At,若At滿足

其中:nr為排程At中被拒絕的檢查需求數(shù)量;c1=為排程At中第1天的剩余容量;nc為在排程At下第t期服務的檢查類型數(shù)量,則增加第t期服務的檢查類型數(shù)量會增加總成本。

若從拒絕全部檢查需求開始,逐漸增加當期檢查的檢查類型,則命題2提供了這個過程的停止條件。為可能降低的拒絕成本的最大值,fc(nc+1)-fc(nc)為增加一個檢查類型所產生的轉換成本。若降低的拒絕成本小于增加的轉換成本,則不再增加當期的檢查類型。

則接受j0類檢查會增加總成本。

命題3提供了增加的檢查類型的條件,若

則接受j0類檢查所降低的拒絕成本,無法覆蓋其帶來的轉換成本的增加,因此不應該接受j0類檢查。

定理1單日規(guī)則算法能得到P2的最優(yōu)排程,計算復雜度為O(J),其中J為檢查類型數(shù)量。

2.2 開放獲取規(guī)則

盡管單日規(guī)則簡單方便,但不開放未來工作日的預約會導致許多檢查需求被拒絕,損害患者就醫(yī)體驗。同時,在檢查需求波動很大的情況下,也會導致產能的浪費。為了盡可能減少患者被拒絕的情況和產能的浪費,本文提出“開放獲取規(guī)則”,即只有在前一期安排的檢查數(shù)量達到容量上限時,才開放下一期的預約,當T期全部約滿時,才允許拒絕患者。由于開放獲取規(guī)則要求盡可能將患者往前安排,故考慮未來成本而調整排程的空間很小,因此,在開放獲取規(guī)則下忽略未來成本,得到整數(shù)規(guī)劃問題(P3),即:

其中,式(10)衡量了排程At在第t期產生的等待成本、拒絕成本和轉換成本。式(4)～(6)分別為正整數(shù)約束、檢查需求約束和醫(yī)院服務能力約束。式(8)、(9)保證了可準確衡量醫(yī)院當期服務的檢查類型數(shù)量,其中為充分大的正整數(shù)。式(11)～(13)為開放獲取規(guī)則約束。式(12)保證當排程表的第i行有安排檢查時,r i=1;式(11)保證當r i+1=1時,第i行安排的檢查數(shù)量達到容量約束M。通過研究,得到P3最優(yōu)解的性質:

由于開放獲取規(guī)則要求只有在前一期排滿時才開放下一期預約,故任一可行排程At都滿足:

換言之,對給定的預約表St和需求總量當期產生的等待成本與拒絕成本是確定的,只需要選擇使轉換成本最小的排程。

命題5給定當前預約表St和檢查需求Dt,將所有滿足的檢查類型記為集合JJ1,則存在最優(yōu)排程At滿足

若在當前預約表St中,已經安排了j類檢查在當期進行檢查,則在當期安排更多j類檢查不會增加轉換成本,因此,醫(yī)院的最優(yōu)選擇是優(yōu)先安排在集合JJ1中的檢查類型,直到達到容量或需求約束。安排滿當期檢查后,將剩余檢查安排到后續(xù)工作日不會在當期產生轉換成本,根據(jù)命題4,所有符合開放獲取規(guī)則的排程都產生相同的等待成本與拒絕成本。若集合JJ1中的檢查需求無法填滿當期容量,類似命題4,本文將不在集合JJ1中的檢查需求按照從大到小的順序安排在當期,直到達到容量或需求約束。根據(jù)命題4與命題5,設計了求P3最優(yōu)解的多項式時間算法。

定理2開放獲取規(guī)則算法(OAP algorithm)能得到P3的最優(yōu)解,計算復雜度為O(TJ)。開放獲取規(guī)則算法偽代碼如下所示:

開放獲取規(guī)則算法

2.3 短視規(guī)則

雖然開放獲取規(guī)則能避免醫(yī)院產能浪費,但會增加醫(yī)院成本。如當天剩余1個檢查名額,但有10個j類檢查尚未分配時,按照開放獲取規(guī)則,醫(yī)院要在當天進行其中1個j類檢查,再將剩余9個檢查安排在下一期,產生兩次轉換成本。顯然,當患者等待1天的成本小于轉換成本時,將10個檢查都安排在下一期更好。為了避免過度增加轉換成本,考慮短視規(guī)則(Myopic Policy),即忽略未來成本,在每期初最小化等待成本、拒絕成本與轉換成本之和,將P1轉換為整數(shù)規(guī)劃問題(P4),即:

P4與開放獲取規(guī)則下的問題(P3)基本相同,只是刪除了確?！爸挥性谇耙黄诎才诺臋z查數(shù)量達到容量上限時,才開放下一期的預約”的約束式(11)～(13)。同樣,本文也通過探究P4最優(yōu)解的性質來設計多項式時間的求解算法。

由于安排在第2～T+1行的檢查不在當期產生轉換成本,故最優(yōu)選擇是盡量把檢查往前安排。可以預見,短視規(guī)則應該在檢查需求不超過檢查容量太多的情況下使用,否則與開放獲取規(guī)則的差異不大,但在檢查需求不太大時,短視規(guī)則可以通過轉移部分需求到下一期來降低轉換成本?；诿}6,尋找P4 最優(yōu)解等價于找到排程表第1 行的最優(yōu)解。

命題7與命題5相同,增加已被安排在當期的檢查類型不會增加轉換成本。在開放獲取規(guī)則下,若集合JJ1中的檢查沒有填滿排程表的第1行,需繼續(xù)填入其余類型的患者,直到達到容量上限。但在短視規(guī)則下,需要通過比較接受多一類檢查增加的轉化成本與降低的等待成本來決定。

命題8與命題4類似,說明了應優(yōu)先接受需求量更大的檢查類型。由于,故只有當接受j類檢查降低的等待成本超過增加的轉換成本時才選擇接受,而檢查需求量大的檢查類型有更大的機會實現(xiàn)該條件。

定理3短視規(guī)則算法(MP algorithm)能得到P4的最優(yōu)解,計算復雜度為O(TJ)。短視規(guī)則算法偽代碼如下所示:

短視規(guī)則算法

2.4 分解算法

在單日規(guī)則、開放獲取規(guī)則和短視規(guī)則下,醫(yī)院能快速為新抵達的需求安排檢查時間,卻沒有考慮當期排程對未來成本的影響。而考慮未來成本的策略迭代算法在求P1最優(yōu)解時,控制的維度是時間×類型,算法復雜度非常高。根據(jù)分而治之思想,將原問題按照檢查類型分解為J個子問題,每個子問題的控制只有時間維度,算法復雜度大大降低。據(jù)此,本文設計了忽略容量約束的分解算法(Decomposition Algorithm),可在考慮未來成本的情況下近似求解P1。其每個子問題(P5-j)為:

衡量了j類檢查在第t期的等待成本、拒絕成本與轉換成本。式(15a)～(15c)分別為對j類檢查的整數(shù)約束、需求約束和容量約束。若M=+∞且f(n1)+f(n2)=f(n1+n2),則求解J個子問題(P5-j)等價于求解原問題(P1)。若M＜+∞,則J個子問題的最優(yōu)解不一定能組合為原問題的可行解。在分解算法中,優(yōu)先接受檢查數(shù)量大的類型,將檢查數(shù)量少的檢查類型往后推,能在降低轉換成本的同時,把J個子問題的最優(yōu)解轉換為原問題(P1)的可行近似解。分解算法偽代碼如下所示:

分解算法

3 數(shù)值實驗及案例分析

為檢驗上述4種算法的效果,本文設計了兩組數(shù)值實驗,分別比較了小規(guī)模問題中4種算法與最優(yōu)解的性能差距以及大規(guī)模問題中各算法在不同參數(shù)條件下的表現(xiàn)。最后,通過醫(yī)院實際數(shù)據(jù)分析比較各算法的效果。

3.1 小規(guī)模數(shù)值實驗

為了控制問題規(guī)模,使最優(yōu)解可以通過策略迭代算法得到,設置預約時間范圍T=2,即只能將患者安排在當期、下一期或拒絕;檢查類型數(shù)量J=2;檢查需求服從均值為λ=1的泊松分布,且限制最大值為2。在這種問題規(guī)模下,最大需求為8人,因此將檢查容量按1～8均勻取值,即M∈{1,2,…,8}。方便起見,成本使用線性函數(shù),即:fw(t)=cwt,fc(n)=ccn。將cw(1位患者等待1天的成本)的均值標準化為1;拒絕1位患者的成本應大于讓1位患者等待多日,因此將cr的均值設為6;將轉換成本cc的均值設為3,使其略大于將一類患者推遲一天產生的等待成本。在實驗中,cw、cr和cc根據(jù)其均值按均勻分布取值,即:cw∈{0,0.5,…,2},cr∈{2,4,…,10},cc∈{0,1,…,6}。

基于上述參數(shù)設置,根據(jù)策略迭代算法、單日規(guī)則算法、開放獲取規(guī)則算法、短視規(guī)則算法和分解算法求解最優(yōu)策略π,并使用值迭代計算各參數(shù)組合下的長期平均成本,所得結果如表1 與圖1 所示。其中,性能差距為各算法下長期平均成本超出最優(yōu)解的百分比,即

圖1 小規(guī)模數(shù)值實驗結果Fig.1 Results from small-scale numerical experiment

表1 小規(guī)模數(shù)值實驗結果Tab.1 Results from small-scale numerical experiment

由表1可以看出,每種近似算法的計算時間都遠低于策略迭代算法。隨著MRI檢查單日容量M的增加,策略迭代算法的運算時間從0.07 s快速上漲到17.8 s,而其他近似算法的運算時間始終不超過0.1 s。換言之,與策略迭代算法相比,本文提出的近似算法不存在維數(shù)災難問題。由表1和圖1可以看出,每個近似算法適用的情形不同,且在每種參數(shù)組合下,都存在至少一種表現(xiàn)優(yōu)異的算法。

在醫(yī)院檢查能力緊張時,單日規(guī)則算法與分解算法表現(xiàn)最佳,長期平均成本達到了最優(yōu)。這是因為在醫(yī)院檢查能力緊張時,幾乎每天新抵達的檢查需求都超出檢查能力限制,所以最佳選擇是不開放未來預約,在每期達到容量限制后拒絕剩余需求,這與單日規(guī)則一致。同時,在檢查需求大大超出檢查能力時,通常存在只需挑選一個類型的檢查,其需求就能填滿當天的檢查容量,因此將原問題按照檢查類型分解為J個子問題不影響最優(yōu)解。

隨著醫(yī)院檢查能力的提高,會出現(xiàn)需求時而大于容量、時而小于容量的情況,因此,最佳選擇是將當期抵達的需求安排到未來工作日,以撫平需求波動,這與單日規(guī)則存在較大差異,因此,其性能差距增大。同樣,在醫(yī)院檢查能力提高時,分解算法由于沒有考慮不同類型檢查間的相互影響,導致其性能差距增大,但其表現(xiàn)依然優(yōu)于其他算法,性能差距小于6.6%。當醫(yī)院檢查能力充分大時,排程不受檢查能力的限制,且由于數(shù)值實驗考慮的是等待成本與轉換成本線性增加,所以分解算法能得到最優(yōu)排程。

在拒絕成本較低時,最優(yōu)排程傾向于拒絕患者而非讓其等待并增加下一期的轉換成本,這與單日規(guī)則相似,此時單日規(guī)則的表現(xiàn)最好。當拒絕成本變大時,最優(yōu)排程傾向于不拒絕患者,這與開放獲取規(guī)則類似,故開放獲取規(guī)則的表現(xiàn)最好。

在MRI設備轉換成本較低時,最優(yōu)排程更有可能通過增加檢查類型來降低患者等待和拒絕成本,這與開放獲取規(guī)則類似,因此,其表現(xiàn)最佳。在轉換成本較高且某類檢查數(shù)量較多時,才為該類檢查花費轉換成本。在單日規(guī)則中,只有在接受某類檢查所降低的拒絕成本超過其增加的轉換成本時,才接受該類檢查,而降低的拒絕成本隨檢查數(shù)量遞增,因此,單日規(guī)則在此情形下表現(xiàn)良好。在分解算法中,求解每個子問題時,都權衡了該類檢查帶來的拒絕成本和轉換成本,因此,分解算法在此情形下也表現(xiàn)良好。

在等待成本較低時,由于短視規(guī)則受等待成本的影響較小,且比單日規(guī)則能通過讓患者等待來降低拒絕成本、比開放獲取規(guī)則能考慮到轉換成本的影響、比分解算法能考慮到不同類型檢查間的相互作用,故性能表現(xiàn)最好。在等待成本適中時,由于等待成本增加,短視規(guī)則比前一種情形更難通過讓患者等待來降低拒絕和轉換,并由于等待成本不夠高,故讓患者等待而非直接拒絕的開放獲取規(guī)則表現(xiàn)最佳。在等待成本較高時,最優(yōu)排程傾向于不讓患者等待,與單日規(guī)則較為相似,因此,其表現(xiàn)最佳。

通過小規(guī)模問題的數(shù)值實驗可以看出,在不同參數(shù)情況下,都能找到效果較好的近似解,因此,醫(yī)院可以根據(jù)MRI檢查能力的緊張與否,拒絕成本、等待成本及轉換成本的高低來選擇合適的算法為患者預約檢查日期。盡管單日規(guī)則算法和短視規(guī)則算法在某些情況表現(xiàn)極佳,但從平均性能差距來看,它們的總體表現(xiàn)劣于開放獲取規(guī)則算法和分解算法,因此,醫(yī)院在采用單日規(guī)則和短視規(guī)則時需要仔細辨別適用的場景。

3.2 大規(guī)模數(shù)值實驗

通過小規(guī)模問題證明了近似算法的有效性,本文對更方便應用的單日規(guī)則、開放獲取規(guī)則和短視規(guī)則進行規(guī)模較大的數(shù)值實驗,以探究3種規(guī)則在大規(guī)模情形下的表現(xiàn)。

大規(guī)模數(shù)值實驗的參數(shù)設置如下:一般醫(yī)院可預約時間范圍為一周,即T=7;在實踐中,一般會用到7種MRI線圈,即J=7;上海某三甲醫(yī)院日均MRI檢查需求約為100,故假設每類檢查需求服從均值λ=15的泊松分布;每日檢查能力設為M∈{85,105,125},分別對應檢查能力緊張、均衡和充分的情況;患者單位等待成本的均值標準化為1,故設cw∈{0.5,1,1.5};將拒絕成本設為等待成本的10倍(略大于將患者安排在最后一天的等待成本),故設cr∈{5,10,15};轉換成本應略大于將某類需求全部推遲一天的等待成本,故設cc={10,20,30}。基于上述參數(shù),使用Matlab進行仿真求解,部分結果如圖2所示(詳細結果見附表B1)。

圖2 大規(guī)模數(shù)值實驗結果Fig.2 Results from large-scale numerical experiment

由此可見,單日規(guī)則的效果幾乎不受患者等待成本的影響,但開放獲取規(guī)則和短視規(guī)則下的日平均成本隨等待成本的增加而顯著增加,并且等待成本越大,3種規(guī)則的表現(xiàn)效果差異越大。此外,隨著醫(yī)院檢查能力的增加,所有近似算法的日平均成本都會下降。在醫(yī)院檢查能力緊張和均衡時,單日規(guī)則表現(xiàn)最佳。在醫(yī)院檢查能力充足時,短視規(guī)則表現(xiàn)更好,三者差異不大,但隨著轉換成本的增加,3種規(guī)則的性能差異越發(fā)明顯。這說明,轉換成本對系統(tǒng)性能的影響非常顯著。在轉換成本較大時,即使醫(yī)院檢查能力充足,3種規(guī)則的性能差異也十分明顯?？傊?在患者等待成本越大、醫(yī)院檢查能力緊張、轉換成本較大時,醫(yī)院需要仔細選擇所使用的預約規(guī)則。

3.3 醫(yī)院實際案例分析

為了驗證現(xiàn)實中近似算法的效果,本文搜集并整理了上海某大型綜合醫(yī)院198 天共21 585 次MRI檢查的申請日期、檢查日期及檢查類型的數(shù)據(jù),對單日規(guī)則算法、開放獲取規(guī)則算法和短視規(guī)則算法的效果進行評價。

醫(yī)院案例數(shù)據(jù)中,患者檢查需求可按使用線圈的不同分為7種類型,而日均檢查類型為5.82種,檢查類型最少時為1種,可以看出,醫(yī)院在有意控制每天檢查類型的數(shù)量,但效果不佳。從每日產生的檢查需求來看,均數(shù)為108.43次,方差為3 119;從每日實際檢查數(shù)量來看,均值為100.36次,最大值為241次,方差為3 310。這說明,MRI的預約調度并沒有起到平滑需求波動的效果,每天的檢查工作量極不平衡,同時存在著設備的閑置和加班。從患者的就醫(yī)體驗來看,平均每個患者等待2.40天,最長等待時間為27天,并且還有7.47%的檢查需求被拒絕,就醫(yī)體驗不佳。

在案例分析中,將可預約的時間范圍設為一周,即T=7;根據(jù)MRI線圈類型,將J設為7;將實際數(shù)據(jù)中每日檢查數(shù)量的中位數(shù)設為檢查容量,即M=118;將每位患者等待1天的成本標準化為1,即cw=1;拒絕1名患者的成本應稍大于將患者安排到最后一天,故設cr=10;轉換成本應稍大于將某類需求全部推后一天產生的等待成本,故設cc=20。根據(jù)單日規(guī)則算法、開放獲取規(guī)則算法和短視規(guī)則算法,對實際歷史數(shù)據(jù)中的檢查需求求解預約調度,并計算各個算法下拒絕率、平均等待天數(shù)、日平均檢查類型數(shù)、日平均檢查量、日檢查量的方差等指標,并與醫(yī)院實際情況進行對比(見表2)。

表2 實際案例分析結果Tab.2 Analysis from real case

開放獲取規(guī)則和短視規(guī)則在每項指標上都優(yōu)于醫(yī)院實際情況,在降低醫(yī)院成本的同時提高了患者就醫(yī)體驗。單日規(guī)則通過減少日平均患者類型數(shù)降低了醫(yī)院成本,但提高了患者拒絕率,可能會損害患者的就醫(yī)體驗,更適合在檢查需求遠超于檢查能力的醫(yī)院中使用。

3.4 拓展模型數(shù)值實驗

前文使用“每天最多檢查的患者數(shù)量”來衡量醫(yī)院MRI設備的檢查能力,但實踐中可能出現(xiàn)不同類型檢查耗費的時間不同的情況,而相同的設備可能每天能進行10個I類檢查,但只能進行5個II類檢查。因此,通過簡單的數(shù)值實驗說明使用“每天最多檢查的患者數(shù)量”或“MRI設備總運行時間”來衡量醫(yī)院檢查能力并不會顯著影響本文的主要結論。

參考小規(guī)模數(shù)值實驗中的參數(shù)設置,進一步區(qū)分兩類檢查耗費的時間:假設II類檢查的耗費時間為1個單位時間,I類與II類檢查的耗費時間之比為{0.7,0.8,…,2},最后得到圖3所示結果。

圖3 拓展模型數(shù)值實驗結果Fig.3 Results from extended numerical model

由圖3可以發(fā)現(xiàn),3種算法的性能差距都在檢查時間之比為1時發(fā)生跳轉,在其他情況下保持穩(wěn)定。這是由于本文設置了檢查總時間M=2,即每天MRI設備最多運轉2個單位時間,在檢查時間之比小于1時,相當于檢查容量M=2;在檢查時間之比大于1時,相當于檢查容量M=1,所以性能差距發(fā)生改變?？梢?本文所提出近似算法的表現(xiàn)與檢查容量有關,而與檢查時間之比幾乎無關。

4 結論

本文考慮了醫(yī)院核磁共振檢查(MRI)在掃描患者不同部位時產生的轉換成本,以及未能及時滿足患者就醫(yī)需求而產生的等候及拒絕成本,對MRI設備的預約調度問題建立了馬爾可夫決策過程模型,以最小化醫(yī)院長期總成本,并通過策略迭代算法得到最優(yōu)排程。為了降低計算復雜度,本文考慮了單日規(guī)則、開放獲取規(guī)則和短視規(guī)則,但由于轉換成本的引入,即使在給定調度規(guī)則下,該問題仍是一個組合優(yōu)化問題。因此,本文分析了各調度規(guī)則下的問題性質,設計并證明了各求解規(guī)則下最優(yōu)解的多項式時間算法。在單日規(guī)則、開放獲取規(guī)則和短視規(guī)則下,最優(yōu)解算法的計算時間與患者總量無關,只隨患者類型數(shù)量J和預約時間范圍T線性增長,大大降低了計算復雜度。本文還依據(jù)分而治之的思想設計了分解算法,得到原問題的近似解。從數(shù)值模擬結果來看,本文提出的方法均能有效近似最優(yōu)解。從上海某大型綜合醫(yī)院的實際案例可以看出,本文設計的近似算法在檢查容量配置、患者拒絕率、平均等待天數(shù)、日平均檢查類型數(shù)等指標上取得顯著改善。

本文提出的算法對醫(yī)院MRI設備預約調度具有實踐指導意義。

一方面,本文提出的多項式時間算法計算復雜度低,能快速得到對應調度規(guī)則下的最優(yōu)排程;另一方面,本文只要求成本函數(shù)遞增,沒有對設備轉換成本和等待成本之間的關系做出假設。因此,醫(yī)院可以根據(jù)實際情況靈活選擇適合的調度規(guī)則及算法。

當MRI設備檢查能力緊張時,應采用單日規(guī)則,因為無法通過開放后續(xù)工作日預約來撫平需求波動,反而會增加轉換成本與患者等待成本。當醫(yī)院不希望拒絕患者的檢查需求或MRI設備轉換成本低時,可以采用開放獲取規(guī)則,充分利用MRI設備的檢查能力。當MRI設備檢查能力充足且患者檢查類型多、可預約時間范圍長時,應采用短視規(guī)則,通過將部分檢查需求移動到后續(xù)工作日來降低MRI設備的轉換成本,從而降低總成本。當MRI設備的檢查能力非常緊張或非常充足時,醫(yī)院可以忽略檢查能力約束,采用分而治之的方法,對每個類型單獨通過策略迭代算法進行排程,再組合為可行的排程表,此時與最優(yōu)解僅有不超過1.5%的性能差距。

從直覺上看,MRI設備的檢查能力越緊張,容量約束的影響越大。但在MRI設備的預約排程問題中,為了降低患者等待和拒絕成本,醫(yī)院應盡量將患者排在靠前的日期,而為了降低轉換成本,在每期應盡量先處理完一個類型的檢查后再考慮下一個類型的檢查,這與分解算法的思想是類似的,可以很好地近似最優(yōu)解。當MRI設備的檢查能力非常充足時,容量約束冗余,因此,分解算法也表現(xiàn)良好。

雖然本文研究的是MRI設備的預約排程問題,但提出的模型、算法和管理內涵同樣能應用于存在轉換成本的其他預約排程問題。例如,在場地出租企業(yè)中,若前后預約場地的顧客都用于開會,則無需重新布置場地;若前一位顧客預約場地用于開會,而后一位顧客預約場地用于演出,則產生了場地布置成本。

本文的研究有許多可拓展方向。例如考慮MRI設備的檢查能力存在硬性約束,規(guī)定了每天患者檢查數(shù)量的上限,未來研究可以考慮軟檢查能力約束,允許超出MRI設備檢查能力,但產生超時工作成本。另外,本文假設不同檢查需求的患者的等待成本函數(shù)一致,但在現(xiàn)實中,特定類型患者的就醫(yī)需求可能更為迫切。本文的模型、排程規(guī)則及算法可以作為未來更多相關問題的研究工具。

附錄A

策略迭代算法假設每個工作日的患者檢查需求Dt相互獨立,且所有可能的檢查需求Dt包含于有限集合DD,即Dt∈DD。假設第t期檢查需求為Dt的概率為P(Dt),且由于預約表St需滿足正整數(shù)約束與醫(yī)院服務能力約束,故存在有限集合SS包含所有可能的預約表St。同理,由于排程At需滿足正整數(shù)約束、檢查需求約束和醫(yī)院服務能力約束,故給定St∈SS,Dt∈DD,存在有限集合AA(St,Dt)包含所有滿足約束式(4)～(6)的排程At。通過如下所示偽代碼,求解優(yōu)化問題(P1)的最優(yōu)策略。

策略迭代算法

附錄B

大規(guī)模數(shù)值實驗詳細結果見附表B1。

附表B1 大規(guī)模數(shù)值實驗結果Tab.B1 Results from large-scale numerical experiment

附錄C

因此,當期需求總量相同的排程At1和At2安排在每期的檢查/拒絕總數(shù)相同,則

命題8的證明同命題6的證明。

命題9的證明同命題4的證明。

綜上可知,無法通過修改排程At得到成本更低的可行排程,因此,At是最優(yōu)排程。