基于兩階段隨機(jī)仿真優(yōu)化算法的體檢顧客預(yù)約調(diào)度

劉 丹，耿 娜

（1.上海交通大學(xué)工業(yè)工程與管理系，上海200240；2.上海交通大學(xué)中美物流研究院，上海200230）

0 概述

隨著社會經(jīng)濟(jì)的發(fā)展，我國人民健康意識增強(qiáng)，大眾的健康觀念從看病轉(zhuǎn)向保健，從治病轉(zhuǎn)向防病，有越來越多的人定期進(jìn)行健康體檢。據(jù)國家衛(wèi)生健康委員會數(shù)據(jù)顯示，2018年，我國體檢人次數(shù)突破5.8 億次，相較2012年的3.7 億人次增長了56.8%。體檢機(jī)構(gòu)顧客排隊(duì)現(xiàn)象日益嚴(yán)重，在上海的一家大型醫(yī)院的體檢中心進(jìn)行調(diào)研發(fā)現(xiàn)，顧客在排隊(duì)等待中耗費(fèi)的時(shí)間甚至超過了在體檢機(jī)構(gòu)花費(fèi)的總時(shí)長的80%。因此，采取合理的方式減少顧客的等待時(shí)間并提高資源利用率己經(jīng)成為完善體檢機(jī)構(gòu)管理工作的當(dāng)務(wù)之急。

醫(yī)療服務(wù)系統(tǒng)的預(yù)約調(diào)度可以預(yù)先分配醫(yī)療資源的服務(wù)能力，匹配供求關(guān)系，緩解系統(tǒng)擁堵，提高資源利用效率。目前我國大型公立醫(yī)院已經(jīng)普及預(yù)約就診服務(wù)，然而對于體檢機(jī)構(gòu)等其他體療服務(wù)機(jī)構(gòu)的預(yù)約調(diào)度卻沒有得到廣泛應(yīng)用。顧客在進(jìn)行體檢時(shí)，除了空腹項(xiàng)目由于可用檢查時(shí)間結(jié)束較早需要盡快完成外，多數(shù)體檢項(xiàng)目沒有硬性的順序約束。目前，大多數(shù)體檢機(jī)構(gòu)不對顧客體檢順序進(jìn)行安排，在實(shí)際體檢服務(wù)過程中，由顧客自行選擇檢查項(xiàng)目的順序。由于缺乏顧客預(yù)約調(diào)度及體檢項(xiàng)目順序的優(yōu)化，因此顧客的等待時(shí)間過長，使顧客滿意度下降。同時(shí)，對于體檢機(jī)構(gòu)而言，醫(yī)學(xué)檢查儀器是昂貴的成本構(gòu)成。如何在不增加設(shè)備和人員投入的基礎(chǔ)上，提升服務(wù)能力，減少顧客等待時(shí)間，提高醫(yī)療資源的利用效率，成為各體檢機(jī)構(gòu)面對的重要管理問題。

本文從預(yù)約調(diào)度及檢查項(xiàng)目順序調(diào)度2 個(gè)方面進(jìn)行研究，考慮隨機(jī)服務(wù)時(shí)長，提出了一種兩階段隨機(jī)仿真優(yōu)化算法，包括粗糙仿真評估階段和精確仿真評估階段。運(yùn)用序優(yōu)化（Ordinal Optimization，OO）策略，將基于親和度評估的多種群遺傳算法（Multipopulation Genetic Algorithm，MPGA）作為迭代策略，并在粗糙評估階段中使用最優(yōu)計(jì)算量分配

（Optimal Computational Budget Allocation，OCBA）

方法優(yōu)化仿真預(yù)算分配來減少計(jì)算時(shí)間。

1 相關(guān)研究

目前關(guān)于醫(yī)學(xué)檢查系統(tǒng)中的顧客調(diào)度問題的研究大都僅考慮一個(gè)檢查科室［1-2］，對多個(gè)檢查科室串聯(lián)的系統(tǒng)研究較少。BARON 等［3］研究了加拿大的一家預(yù)防保健服務(wù)中心的顧客調(diào)度問題，該中心的檢查服務(wù)由10～20 個(gè)不同項(xiàng)目組成，使用了幾種基本的調(diào)度策略來實(shí)時(shí)調(diào)度顧客，其目標(biāo)有2 個(gè)層次：傳統(tǒng)宏觀層面的目標(biāo)，如最小化總系統(tǒng)時(shí)間或最大限度減少延遲顧客總數(shù)；非傳統(tǒng)的微觀層面的目標(biāo)，即減少流程中任何工作站的等待時(shí)間過長的事件的發(fā)生。劉陽等［4］考慮了2 類檢查項(xiàng)目和2 類不同緊急程度的門診患者的預(yù)約調(diào)度問題，建立了有限時(shí)域馬爾科夫決策過程模型，利用啟發(fā)式策略對門診患者進(jìn)行調(diào)度。HU 等［5］研究了門診患者的4 項(xiàng)基本檢查，為門診檢查制定了一些調(diào)度規(guī)則，以最大程度地減少總等待時(shí)間。CHERN 等［6］提出了一個(gè)基于最長處理時(shí)間優(yōu)先調(diào)度策略的啟發(fā)式模型來解決體檢顧客項(xiàng)目順序調(diào)度問題，包含20 多個(gè)不同的檢查項(xiàng)目，目標(biāo)是在考慮資源限制的情況下盡可能地減少顧客或醫(yī)生的等待時(shí)間和整體檢查時(shí)間。上述研究大都使用啟發(fā)式調(diào)度策略，其調(diào)度的質(zhì)量取決于所選擇的策略。

本文考慮的隨機(jī)服務(wù)時(shí)長下的體檢顧客調(diào)度問題屬于離散隨機(jī)優(yōu)化問題范疇。在解決離散隨機(jī)優(yōu)化問題方面，仿真優(yōu)化方法［7-8］受到越來越多的關(guān)注。離散隨機(jī)優(yōu)化問題的解空間往往非常大，并且對解性能的準(zhǔn)確評估也會非常耗時(shí)。OO 策略和OCBA 方法通過從大量解中抽樣，并評估較少數(shù)量的解來克服解空間過大的難題［9］。多服務(wù)臺串聯(lián)的體檢調(diào)度問題與多工作站串聯(lián)的車間調(diào)度問題具有類似的特征。在車間調(diào)度問題中，已有許多文獻(xiàn)將OO、OCBA 和全局搜索方法集成運(yùn)用。SONG 等［10］使用基于OO 的進(jìn)化策略來減少調(diào)度解評估的計(jì)算時(shí)間。HORNG 等［11］提出將進(jìn)化策略嵌入到OO 中以解決作業(yè)車間調(diào)度問題，縮寫為ESOO，其目的是最小化倉儲費(fèi)用和延期罰款。YANG 等［12］將OCBA技術(shù)嵌入到ESOO 算法的探索階段，開發(fā)了用于解決作業(yè)車間調(diào)度問題的ESOO-OCBA 算法，以最小化提前和延遲成本。本文問題解空間更加復(fù)雜，對解空間搜索和抽樣更困難，在進(jìn)化策略的選擇上，使用改進(jìn)的MPGA 以改善算法搜索性能，在進(jìn)化過程中維持種群染色體多樣性［13］。車間調(diào)度問題的目標(biāo)大都是最小化最大完工時(shí)間［14-15］、總完成時(shí)間［16］、總拖期［17］等，而在醫(yī)療服務(wù)系統(tǒng)中，顧客等待時(shí)間是影響服務(wù)質(zhì)量的關(guān)鍵因素［18-19］。最常見的等待時(shí)間目標(biāo)是顧客總等待時(shí)間［20］，這屬于宏觀層面的目標(biāo)。此外，本文也考慮了微觀層面的目標(biāo)，即顧客在任一項(xiàng)目前的等待時(shí)間不超過某閾值。

2 問題描述

本文使用多人時(shí)間槽預(yù)約調(diào)度規(guī)則進(jìn)行顧客預(yù)約調(diào)度，即對顧客進(jìn)行分批次、等間隔預(yù)約安排，每批次預(yù)約人數(shù)相同，同時(shí)安排每位顧客的體檢項(xiàng)目順序。主要需要做出3 個(gè)決策：1）每批次預(yù)約人數(shù)；2）每個(gè)項(xiàng)目上顧客的排隊(duì)順序；3）每個(gè)顧客的檢查項(xiàng)目順序。

問題詳細(xì)描述如下：將體檢機(jī)構(gòu)允許顧客進(jìn)入的時(shí)間劃分為長度相同的預(yù)約時(shí)間槽，每個(gè)預(yù)約時(shí)間槽內(nèi)安排n位顧客，nmin≤n≤nmax。所有預(yù)約時(shí)間槽共可安排N位顧客，每位體檢顧客需要進(jìn)行m項(xiàng)檢查，每位顧客必須訪問每個(gè)檢查項(xiàng)目1 次，顧客可以按任何順序進(jìn)行檢查。1 項(xiàng)檢查每次只能服務(wù)1 位顧客，在完成當(dāng)前顧客的服務(wù)之前，不允許檢查項(xiàng)目接受新顧客。顧客i在項(xiàng)目j上的服務(wù)時(shí)間為si，j，顧客完成所有檢查后離開系統(tǒng)。制定以下假設(shè)：

假設(shè)1所有顧客是同質(zhì)的，需要接受相同的檢查。檢查項(xiàng)目不存在任何順序約束，也不存在完成時(shí)間約束。

假設(shè)2體檢機(jī)構(gòu)每日08：00-12：00 工作，但在11：00 后便不再允許新的顧客進(jìn)入系統(tǒng)。假設(shè)計(jì)劃工作時(shí)間為240 min，顧客必須在前180 min 進(jìn)入系統(tǒng)。

假設(shè)3每個(gè)檢查項(xiàng)目只有1 個(gè)服務(wù)臺，服務(wù)時(shí)長是獨(dú)立同分布的隨機(jī)向量。

假設(shè)4預(yù)約顧客嚴(yán)格按照安排的時(shí)間到達(dá)系統(tǒng)。

對于顧客調(diào)度問題，顧客等待時(shí)間指標(biāo)是優(yōu)化的重點(diǎn)。據(jù)研究，體檢機(jī)構(gòu)中顧客在任一項(xiàng)目前等待超過某一時(shí)長時(shí)，會顯著降低其滿意度［3］。本文的優(yōu)化目標(biāo)同時(shí)考慮人均等待時(shí)間、系統(tǒng)超時(shí)加班時(shí)間、所有顧客兩項(xiàng)檢查之間的等待時(shí)間超過給定閾值TW的總時(shí)長、服務(wù)臺平均空閑時(shí)間等。隨著每批次調(diào)度人數(shù)的增多，系統(tǒng)服務(wù)人數(shù)增加，前3 個(gè)指標(biāo)值會增大，服務(wù)臺空閑時(shí)間指標(biāo)值會減小，問題的本質(zhì)是優(yōu)化權(quán)衡這2 個(gè)部分指標(biāo)，目標(biāo)函數(shù)為其加權(quán)和，表示如下：

其中：i表示顧客索引，i∈｛1，2，…，N｝；j表示檢查項(xiàng)目索引，j∈｛1，2，…，m｝；Fi表示顧客i完成服務(wù)并離開系統(tǒng)的時(shí)間；H表示體檢機(jī)構(gòu)每日計(jì)劃工作時(shí)間；Wˉ表示所有顧客的平均等待時(shí)間；wi，j表示顧客i在項(xiàng)目j前的等待時(shí)間；TW表示顧客兩項(xiàng)檢查之間的等待時(shí)間閾值；Kˉ服務(wù)臺平均空閑時(shí)間；γ1、γ2表示目標(biāo)權(quán)重系數(shù)。

3 兩階段仿真優(yōu)化算法

由于檢查順序不受限制，且服務(wù)時(shí)間隨機(jī)，因此該問題的解空間非常大。運(yùn)用仿真方法對調(diào)度解進(jìn)行評估十分耗時(shí)，同時(shí)為了消除隨機(jī)因素對系統(tǒng)的擾動，需要對調(diào)度解重復(fù)仿真多次。為了有效地縮小解空間并解決隨機(jī)仿真耗時(shí)長的問題，本文給出了基于序優(yōu)化策略的兩階段仿真優(yōu)化算法框架，包含粗糙仿真評估階段和精確仿真評估階段，如圖1所示。粗糙仿真評估階段是仿真優(yōu)化算法的關(guān)鍵，將MPGA 作為迭代搜索策略，使用OCBA 方法自適應(yīng)地在搜索空間分配仿真次數(shù)。

圖1 兩階段仿真優(yōu)化算法結(jié)構(gòu)Fig.1 Structure of two-stage simulation optimization algorithm

3.1 多種群遺傳算法迭代策略

使用MPGA 從每一代各子種群選擇優(yōu)秀的候選解是迭代地進(jìn)行OO 策略的一種方法。本文在傳統(tǒng)MPGA 的基礎(chǔ)上加入親和度評價(jià)過程，以在迭代搜索過程中保持各子種群染色體的多樣性。

3.1.1 染色體編碼和解碼

本文采用分段實(shí)數(shù)編碼方式：1 個(gè)批次內(nèi)顧客數(shù)量為n，nmin≤n≤nmax，m表示檢查項(xiàng)目數(shù)，調(diào)度批次數(shù)目為d，每條染色體長度為d×nmax×m，染色體從左到右每n×m個(gè)基因代表1 個(gè)調(diào)度批次，1 個(gè)批次內(nèi)每位顧客的每個(gè)項(xiàng)目用1 到n×m的實(shí)數(shù)唯一表示，不足的位用0 補(bǔ)齊；假設(shè)有2 項(xiàng)檢查，2 個(gè)調(diào)度批次，每批次最多調(diào)度3 人，圖2 給出了每批次調(diào)度2 位顧客的情況下生成的一條染色體。Oi，j表示顧客i在項(xiàng)目j的檢查服務(wù)。

圖2 2×3×2 問題染色體表示Fig.2 Chromosome representation of 2×3×2 problem

染色體編碼完成后，需要對其進(jìn)行解碼以得到適應(yīng)度值。對于同一批次內(nèi)的顧客，采用半活動解碼方法［21］，使每個(gè)項(xiàng)目在不延遲其他已解碼的項(xiàng)目的情況下盡可能早地被加工。解碼過程描述如下：

步驟1從染色體中提取1 個(gè)基因，求出其對應(yīng)的Oi，j，服務(wù)時(shí)長為si，j。

步驟2按時(shí)間先后順序遍歷當(dāng)前項(xiàng)目j上所有的空閑時(shí)間區(qū)間［Sj，Ej］。根據(jù)式（2）可以得到Oi，j的最早開始時(shí)間θi,j。其中ci，j-1表示顧客i上一個(gè)被解碼的項(xiàng)目的結(jié)束時(shí)間。如果Oi，j是顧客i被安排的第1 項(xiàng)檢查，ci，j-1=0：

步驟3假設(shè)Oi，j的開始時(shí)間為其最早開始時(shí)間θi,j，根據(jù)式（3）判斷Oi，j是否可以插入到項(xiàng)目j的空閑時(shí)間內(nèi)，若可以插入，則更新項(xiàng)目j的這一空閑區(qū)間的開始時(shí)刻Sj為(θi,j+si,j)；如果不滿足式（3），則根據(jù)式（4）重新計(jì)算Oi，j的開始時(shí)間：

其中：Uj表示當(dāng)前項(xiàng)目j上最后一位顧客完成檢查的時(shí)刻。更新項(xiàng)目j的空閑區(qū)間。

步驟4若染色體中所有基因都已經(jīng)安排，則結(jié)束程序，否則返回步驟1。

圖3 為半活動解碼方式的示意圖。項(xiàng)目1 的空閑時(shí)間為［S1，E1］。若O2，1的開始時(shí)間等于S1，當(dāng)O2，1的結(jié)束時(shí)間不大于E1時(shí)，則可將O2，1插入?yún)^(qū)間［S1，E1］，如圖3（a）所示；相反，當(dāng)O2，1的結(jié)束時(shí)間大于E1時(shí)，則不能將O2，1插入此時(shí)間區(qū)間，如圖3（b）所示。此時(shí)需重新計(jì)算O2，1的開始時(shí)間。在項(xiàng)目1 上安排的最后一位為3 號顧客，其完成檢查的時(shí)刻為U1，于是令O2，1的開始時(shí)間為U1。

圖3 半活動解碼示意圖Fig.3 Schematic diagram of semi-active decoding

在不同批次間，若某項(xiàng)目上前一名顧客的服務(wù)超過當(dāng)前顧客的預(yù)約到達(dá)時(shí)間，則當(dāng)前顧客需要等待前一名服務(wù)結(jié)束后才能開始服務(wù)；如果一個(gè)項(xiàng)目前一批次所有服務(wù)結(jié)束時(shí)還未到當(dāng)前顧客預(yù)約時(shí)間，在當(dāng)前顧客到來之前服務(wù)臺空閑。

3.1.2 初始種群

依據(jù)實(shí)際問題的需要，建立（nmax-nmin+1）個(gè)輔助子種群和1 個(gè)主種群，每個(gè)子種群對應(yīng)1 種批次人數(shù)。對于每個(gè)子種群，依據(jù)最短隊(duì)列優(yōu)先和先到先服務(wù)的啟發(fā)式規(guī)則生成2 個(gè)初始解。另外2 個(gè)初始解通過完全隨機(jī)的方法生成。將這些初始解交叉、變異產(chǎn)生新的個(gè)體，新的個(gè)體再交叉、變異，最終生成大小為Z的初始種群。主種群又稱為最優(yōu)保存種群，用來存放子種群的最優(yōu)解。

3.1.3 交叉和變異

變異算子為隨機(jī)交換一條染色體上代表某1 批次的基因段上的2 個(gè)基因。由于不同初始子種群中的個(gè)體代表的批次人數(shù)不同，并且顧客不能重復(fù)檢查同1 個(gè)項(xiàng)目，本文設(shè)計(jì)了基于批次和顧客的交叉方法。對于2 條親本染色體，隨機(jī)確定1 個(gè)調(diào)度批次，在2 條染色體代表這一調(diào)度批次內(nèi)的基因段上進(jìn)行交換。將1 條染色體基因段上代表同一顧客全部項(xiàng)目的基因，與另1 條染色體基因段上對應(yīng)同一顧客全部項(xiàng)目的基因進(jìn)行交換。交叉和變異的概率分別為pc和pm。

圖4所示為包含2 項(xiàng)檢查的交叉算子。親本染色體P1 代表每批次預(yù)約3 人，P2 代表每批次2 人，交換第2 個(gè)批次內(nèi)代表編號1 顧客項(xiàng)目的全部基因，得到子代C1 和C2。交叉和變異的概率分別為pc和pm。

圖4 基于批次和顧客的交叉方法Fig.4 Crossover method based on batch and customer

3.1.4 選擇機(jī)制

本文采用α+β選擇機(jī)制。在每個(gè)子種群中，根據(jù)每個(gè)個(gè)體仿真獲得適應(yīng)度值均值的排名，選擇最優(yōu)的α個(gè)個(gè)體進(jìn)行精確仿真評估。據(jù)觀測，對一個(gè)體進(jìn)行LS=105次仿真，可以得到十分穩(wěn)定的觀測值，將LS=105作為精確評估的仿真次數(shù)。其他β個(gè)個(gè)體通過輪盤賭選擇獲得。

3.1.5 基于親和度評估的子種群交流方法

基于親和度評估的子種群交流方法如圖5所示。從每個(gè)子種群中選擇那些可以提高算法性能的個(gè)體，被稱為移民算子，在子種群之間進(jìn)行交流，從而打破不同子種群之間的隔離機(jī)制，提高種群染色體多樣性。在交流時(shí)采用單向環(huán)狀拓?fù)?，? 個(gè)種群的交流對象為其后繼種群，最后1 個(gè)種群的后繼種群為第1 個(gè)種群。

圖5 基于親和度的子種群交流方法Fig.5 Population communication method based on affinity

在算法的每一代，子種群選出的α個(gè)個(gè)體精確仿真后，其最優(yōu)解為該子種群這一代的最優(yōu)解，作為移民算子。計(jì)算移民算子與目標(biāo)種群這一代選擇的（α+β）個(gè)個(gè)體的親和度值。依據(jù)親和度，評估目標(biāo)種群中的（α+β）個(gè)個(gè)體與該移民算子的親緣關(guān)系，選擇關(guān)系最遠(yuǎn)且適應(yīng)度值不如該移民算子的個(gè)體，用移民算子替換掉它。這樣做使得每次交換為目標(biāo)種群引入外來優(yōu)勢基因的同時(shí)，保留一部分自身的基因，外來優(yōu)秀個(gè)體不會很快成為主導(dǎo)，能夠保持種群的多樣性。

假設(shè)有某2 條長為L的染色體：1 條染色體是X（x1，x2,…,xL）；另外1 條染色體是Y（y1，y2,…,yL），xi、yi分別代表X、Y染色體上的第i個(gè)位置對應(yīng)的基因，則它們的親和度為：

其中：maxi代表所使用的編碼方式在這一位上可取到的最大值；mini代表在這一位上可取到的最小值。在本文中，maxi為m×nmax，mini為0。AAcev（X，Y）越大說明染色體X、Y之間的親緣關(guān)系越近。

3.1.6 算法迭代終止條件

在每一代中，各子種群的最優(yōu)解貢獻(xiàn)給主種群。主種群的最優(yōu)解為算法這一代的最優(yōu)解。重復(fù)迭代優(yōu)化過程，直到一定數(shù)量的連續(xù)代，genmax、最優(yōu)適應(yīng)度值均沒有改進(jìn)，算法停止。

3.2 仿真資源分配策略

在算法的粗糙評估階段中，對于每一子種群中的個(gè)體，使用OCBA 方法根據(jù)個(gè)體的均值和方差，漸進(jìn)地優(yōu)化分配給定仿真計(jì)算預(yù)算。在使用OCBA 方法時(shí)，可能存在一些個(gè)體會吸收大部分仿真預(yù)算，而其他個(gè)體則很難獲得任何仿真預(yù)算，這些個(gè)體被稱為“超級個(gè)體”。“超級個(gè)體”的存在將降低正確選擇的可能性，因此，需要對OCBA 方法進(jìn)行改進(jìn)。

將LS設(shè)置為仿真次數(shù)的閾值來檢測超級個(gè)體?！俺墏€(gè)體”的集合為Θ，其規(guī)模為nnum。從原始種群中刪除所有“超級個(gè)體”，從給定的仿真總次數(shù)中減去“超級個(gè)體”所占用的仿真次數(shù)。最后，將現(xiàn)有的仿真次數(shù)分配給剩余個(gè)體。將Lη，η=1,2,…,κ定義為分配給調(diào)度解η的仿真次數(shù)，并將T定義為每次迭代分配的總仿真次數(shù)。由以上改進(jìn)的OCBA 方法得到的調(diào)度解η的仿真次數(shù)如式（6）所示：

其中：Ta表示已經(jīng)消耗的仿真次數(shù)；是調(diào)度解Sη的樣本方差；Sb是目前的最佳調(diào)度解；δb,η是Sη和Sb適應(yīng)度值的均值之差。

3.3 仿真優(yōu)化算法的實(shí)施步驟

本文仿真優(yōu)化算法的實(shí)現(xiàn)步驟如下：

步驟1生成初始種群，包含（nmax-nmin+1）個(gè)子種群和1 個(gè)用于保存最優(yōu)解的主種群，種群規(guī)模為Z。

步驟2對每個(gè)初始子種群的每個(gè)個(gè)體都分配相同的基本仿真次數(shù)T0，計(jì)算每個(gè)個(gè)體的樣本均值和方差，獲得初始信息。

步驟3在每個(gè)子種群中，根據(jù)個(gè)體均值和方差的統(tǒng)計(jì)指標(biāo)，迭代地使用OCBA 方法將仿真次數(shù)預(yù)算分配給每個(gè)個(gè)體。每次分配的仿真次數(shù)增量為T。計(jì)算2 次分配后仿真獲得的最優(yōu)值之間的差ggap，與給定閾值DOCBA比較。如果ggap＞DOCBA，則繼續(xù)執(zhí)行迭代OCBA；如果ggap≤DOCBA，則停止OCBA 迭代并執(zhí)行步驟4。

步驟4從總體中選擇最優(yōu)的α個(gè)個(gè)體。首先對α個(gè)個(gè)體進(jìn)行仿真次數(shù)為LS=105的精確評估。然后選擇最優(yōu)個(gè)體作為該子種群這一代的最優(yōu)解，貢獻(xiàn)給主種群。當(dāng)主種群數(shù)量達(dá)到Z時(shí)，需要對子種群貢獻(xiàn)個(gè)體進(jìn)行評估，若優(yōu)于目前主種群中的最差調(diào)度解，則替代該調(diào)度解。每一代主種群的最優(yōu)解為算法這一代的最優(yōu)解。通過輪盤賭選擇方法獲得其他β個(gè)個(gè)體。

步驟5將每個(gè)子種群的最優(yōu)個(gè)體作為移民算子，與目標(biāo)子種群的（α+β）個(gè)個(gè)體之間基于親和度進(jìn)行交流。

步驟6在每個(gè)子種群中，交流后的（α+β）個(gè)個(gè)體使用交叉和變異操作來產(chǎn)生新種群，種群大小是Z。新種群的每個(gè)個(gè)體都被分配了相同的基本仿真次數(shù)T0，計(jì)算每個(gè)個(gè)體的樣本均值和方差。

步驟7重復(fù)步驟3～步驟6，直到在一定數(shù)量的連續(xù)代，genmax、最優(yōu)值沒有改進(jìn)，停止迭代輸出當(dāng)前最優(yōu)解。

4 數(shù)值實(shí)驗(yàn)與結(jié)果分析

在MATLAB 中實(shí)現(xiàn)上述仿真優(yōu)化算法，在配置為（Intel?CoreTMi7-9700 3.00 GHz CPU 16 GB RAM）的計(jì)算機(jī)上運(yùn)行。使用來自某大型醫(yī)院體檢中心的真實(shí)數(shù)據(jù)，該體檢中心常規(guī)項(xiàng)目中包含8 項(xiàng)檢查。分析并擬合實(shí)際的測量數(shù)據(jù)，每項(xiàng)檢查的服務(wù)時(shí)間遵循指數(shù)分布，服務(wù)時(shí)間的數(shù)學(xué)期望分別為｛3，4，5，2，3，2，6，10｝min。假設(shè)每個(gè)檢查科室只有1 個(gè)服務(wù)臺。顧客可以進(jìn)入系統(tǒng)的時(shí)間為系統(tǒng)開放的前180 min。將調(diào)度批次時(shí)間間隔設(shè)置為30 min，故可以安排7 個(gè)批次顧客到達(dá)。優(yōu)化一個(gè)批次內(nèi)顧客到達(dá)人數(shù)n及每位顧客的檢查項(xiàng)目順序。

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

對于每個(gè)批次內(nèi)顧客到達(dá)人數(shù)n的取值范圍，考慮到服務(wù)時(shí)間最長的項(xiàng)目的時(shí)長均值為10 min，調(diào)度批次時(shí)間間隔30 min 內(nèi)可安排3 位顧客。為了避免系統(tǒng)超時(shí)加班時(shí)長過多及服務(wù)臺空閑時(shí)間過長，將n的取值范圍定為2≤n≤5，子種群個(gè)數(shù)為4。在基礎(chǔ)算例中，等待時(shí)間閾值TW設(shè)置為15 min，之后會針對此閾值進(jìn)行算法敏感度分析。OCBA 初始仿真次數(shù)T0以及每次迭代中增加的仿真次數(shù)預(yù)算T的設(shè)置為T0=30，T= 66 000［11］。

設(shè)計(jì)對比實(shí)驗(yàn)以得到以下參數(shù)值：1）種群大小Z=100，150 或200；2）OCBA 閾值DOCBA=0.5 或1；3）交叉概率pc=0.7，0.8，0.9 或1.0，以及變異概率pm=0.2，0.3，0.4，0.5；4）每代選擇的最好的調(diào)度解數(shù)量α=3，5，以及通過輪盤賭選擇的解數(shù)量β=Z/2-α或Z/5-α；5）停止規(guī)則中沒有改進(jìn)的代數(shù)genmax=30，40，50；6）2 組不同權(quán)重系數(shù)：γ1=1,γ2=5 或γ1=1,γ2=10。同時(shí)，考慮解的質(zhì)量和運(yùn)行時(shí)間，所獲得的最適當(dāng)參數(shù)值如表1所示。

表1 參數(shù)設(shè)置Table1 Parameter settings

4.2 數(shù)值實(shí)驗(yàn)結(jié)果

根據(jù)上述參數(shù)設(shè)置，使用仿真優(yōu)化算法計(jì)算問題實(shí)例得到：在單服務(wù)臺情況下，每個(gè)批次的最優(yōu)人數(shù)為3，工作時(shí)間內(nèi)服務(wù)21 人，顧客平均等待時(shí)間為29.1 min，顧客超時(shí)等待時(shí)間之和為120.6 min，科室平均空閑時(shí)間為99.8 min。圖6所示為適應(yīng)度的最優(yōu)值隨著迭代次數(shù)的變化情況。最優(yōu)值在100 代左右收斂。

圖6 適應(yīng)度函數(shù)最優(yōu)值收斂情況Fig.6 Convergence of fitness function optimal value

為了驗(yàn)證所提出的仿真優(yōu)化算法的有效性，模擬實(shí)際中不對體檢顧客進(jìn)行調(diào)度的情況建立離散事件仿真模型，將仿真優(yōu)化算法（SOA）的調(diào)度結(jié)果與離散事件仿真結(jié)果對比。在仿真模型1 中，顧客自由到達(dá)，到達(dá)過程服從泊松分布，顧客完成一項(xiàng)檢查后，在未完成檢查中選擇隊(duì)列長度最短的加入隊(duì)列；在仿真模型2 中，顧客自由到達(dá)，對于顧客體檢項(xiàng)目順序的調(diào)度使用幾種啟發(fā)式調(diào)度策略。在每個(gè)項(xiàng)目上，顧客優(yōu)先規(guī)則為：最長剩余服務(wù)時(shí)間優(yōu)先（A1）；最短剩余服務(wù)時(shí)間優(yōu)先（A2）。當(dāng)顧客完成一項(xiàng)檢查時(shí)，下一項(xiàng)檢查的選擇規(guī)則為：最長服務(wù)時(shí)間優(yōu)先（B1）；最短服務(wù)時(shí)間優(yōu)先（B2）?？紤]到實(shí)際中顧客在系統(tǒng)開放的初期集中到達(dá)的特點(diǎn)，設(shè)置自由到達(dá)的顧客在系統(tǒng)開放前30 min 遵循參數(shù)為2λ的泊松分布，隨后在150 min 內(nèi)遵循參數(shù)為λ的泊松分布。仿真實(shí)驗(yàn)考慮與仿真優(yōu)化算法最優(yōu)調(diào)度解相同的顧客總數(shù)，利用與仿真優(yōu)化算法相同的服務(wù)時(shí)間隨機(jī)種子，運(yùn)行LS=105次。表2所示為仿真優(yōu)化算法（SOA）、不進(jìn)行任何調(diào)度的仿真（DES）以及顧客自由到達(dá)情況下使用最優(yōu)順序調(diào)度策略（A2B2）的結(jié)果對比。

表2 仿真優(yōu)化算法與離散事件仿真結(jié)果對比Table 2 Comparison of simulation optimization algorithm and discrete event simulation results

由表2 可以看出，考慮隨機(jī)服務(wù)時(shí)間，與DES得到的結(jié)果相比，SOA 得到的結(jié)果雖然加班時(shí)間有所增加，但顧客平均等待時(shí)間減少25.8%，顧客在一個(gè)科室前等待超過15 min 的總超時(shí)等待時(shí)長減少71.2%。與A2B2 調(diào)度策略的結(jié)果對比，SOA算法的顧客平均等待時(shí)間減少19.4%，使顧客在一個(gè)科室前等待超過15 min 的總超時(shí)等待時(shí)長減少70.9%。可以看出，本文所提的調(diào)度策略及仿真優(yōu)化算法顯著緩解了體檢系統(tǒng)的顧客排隊(duì)現(xiàn)象。

4.3 敏感度分析

為了進(jìn)一步驗(yàn)證算法的有效性，針對不同的最長等待時(shí)間閾值進(jìn)行敏感度分析。保持其他參數(shù)不變，取最長等待時(shí)間閾值TW為5 min、10 min、15 min、20 min。仿真優(yōu)化算法（SOA）、不進(jìn)行任何調(diào)度的仿真（DES）以及使用最優(yōu)順序調(diào)度策略（A2B2）的結(jié)果對比如表3所示。

表3 等待時(shí)間閾值敏感度分析Table 3 Sensitivity analysis of waiting time threshold

由表3 可以看出，在4 組不同的最長等待時(shí)間閾值實(shí)驗(yàn)中，SOA 的調(diào)度結(jié)果均優(yōu)于DES 和A2B2 算法的結(jié)果。在2 個(gè)等待時(shí)間指標(biāo)上，無論等待時(shí)間閾值設(shè)置為多少，SOA 的結(jié)果均優(yōu)于另外2 種算法的結(jié)果。尤其是超時(shí)等待指標(biāo)，SOA 算法的結(jié)果較啟發(fā)式調(diào)度策略結(jié)果至少減少55.5%。這說明本文所提出的調(diào)度策略及仿真優(yōu)化算法，可以有效地解決體檢機(jī)構(gòu)顧客排隊(duì)時(shí)間過長的問題。最長等待時(shí)間閾值為5 min、10 min 和15 min 時(shí)，仿真優(yōu)化算法所求出的最優(yōu)批次人數(shù)為3；當(dāng)?shù)却龝r(shí)間閾值為20 min 時(shí)，最優(yōu)批次人數(shù)為4。這說明隨著最長等待時(shí)間閾值的增加，顧客在一個(gè)項(xiàng)目前等待時(shí)間超過閾值時(shí)間減少，每批次可以調(diào)度的顧客數(shù)量增加。同時(shí)也可以看出，當(dāng)每批次調(diào)度人數(shù)增加時(shí)，系統(tǒng)加班時(shí)間、顧客平均等待時(shí)間、顧客超時(shí)等待時(shí)間均增加，科室平均空閑時(shí)間減少。在實(shí)際應(yīng)用中，管理者可以根據(jù)需要適當(dāng)放寬顧客等待時(shí)間限制，以服務(wù)更多的顧客。

5 結(jié)束語

本文考慮了服務(wù)時(shí)間隨機(jī)的體檢顧客調(diào)度問題，使用多人時(shí)間槽預(yù)約調(diào)度規(guī)則，從預(yù)約調(diào)度批次人數(shù)和顧客體檢項(xiàng)目順序2 個(gè)方面進(jìn)行調(diào)度優(yōu)化。提出了一種兩階段仿真優(yōu)化算法，采用序優(yōu)化策略提高仿真效率，多種群遺傳算法作為迭代優(yōu)化策略，最優(yōu)計(jì)算量分配算法被嵌入到算法的粗糙仿真評估階段，形成了仿真資源的全局和自適應(yīng)優(yōu)化分配機(jī)制。與不進(jìn)行任何調(diào)度的真實(shí)情況以及啟發(fā)式調(diào)度規(guī)則對顧客體檢順序的結(jié)果進(jìn)行比較，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出的調(diào)度策略及仿真優(yōu)化算法的有效性。本文研究不僅可以為類似體檢機(jī)構(gòu)這樣多科室串聯(lián)的服務(wù)機(jī)構(gòu)管理者提供有效的顧客調(diào)度方法，還可以輔助體檢機(jī)構(gòu)管理者進(jìn)行決策，增加關(guān)鍵科室的設(shè)備或人員投入，平衡擁堵科室和非擁堵科室的服務(wù)能力。下一步研究將多服務(wù)臺、檢查項(xiàng)目的部分順序約束或某項(xiàng)檢查完成時(shí)間的約束以及顧客的不按時(shí)到達(dá)或爽約行為，以此提高體檢系統(tǒng)的整體服務(wù)水平。