劉 丹，耿 娜

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

0 概述

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

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

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

（Optimal Computational Budget Allocation，OCBA）

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

1 相關(guān)研究

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

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

2 問題描述

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

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

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

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

假設(shè)3每個檢查項目只有1 個服務臺，服務時長是獨立同分布的隨機向量。

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

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

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

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

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

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

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

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

3.1.1 染色體編碼和解碼

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

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

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

步驟1從染色體中提取1 個基因，求出其對應的Oi，j，服務時長為si，j。

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

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

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

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

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

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

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

3.1.2 初始種群

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

3.1.3 交叉和變異

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

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

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

3.1.4 選擇機制

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

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

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

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

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

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

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

3.1.6 算法迭代終止條件

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

3.2 仿真資源分配策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

設(shè)計對比實驗以得到以下參數(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ī)則中沒有改進的代數(shù)genmax=30，40，50；6）2 組不同權(quán)重系數(shù)：γ1=1,γ2=5 或γ1=1,γ2=10。同時，考慮解的質(zhì)量和運行時間，所獲得的最適當參數(shù)值如表1所示。

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

4.2 數(shù)值實驗結(jié)果

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

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

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

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

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

4.3 敏感度分析

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

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

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

5 結(jié)束語

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