胡廉民，張九華，常永耘，黃 翰

（1.樂山師范學(xué)院物理與電子工程學(xué)院，四川 樂山 614000；2.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006；3.華南理工大學(xué)軟件學(xué)院，廣東 廣州 510006）

1 引言

隨著我國醫(yī)療衛(wèi)生體制改革工作的不斷深入，醫(yī)院信息系統(tǒng)已成為大中型醫(yī)院管理中不可缺少的現(xiàn)代化管理工具。一直以來，排班就是護(hù)理管理工作任務(wù)中的一項(xiàng)經(jīng)常性工作，目的在于提高護(hù)理人員在班時(shí)間的利用率。雖然沒有一種人員管理及排班方式能運(yùn)用于所有醫(yī)院或所有單位，但探索一種適合自身醫(yī)院特點(diǎn)的人員管理及排班模式則是必要的。合理的人力資源安排反映在排班的模式上，而排班模式的選擇對(duì)護(hù)理質(zhì)量有著重要的影響。

大多數(shù)護(hù)士排班問題NRP（Nurse Rostering Problem）都是NP-Hard問題，這個(gè)問題也被視作旅行商問題的復(fù)雜版[1]。隨著研究的發(fā)展，許多數(shù)學(xué)模型和方法[2]都被用來研究護(hù)士排班問題的求解。

最初，Margarida等人[3]提出的護(hù)士排班模型取得了一定的成功，隨后，Edmund[4]在Margarida研究的基礎(chǔ)上，發(fā)展出了循環(huán)護(hù)士排班的數(shù)學(xué)規(guī)劃模型。Warner的模型使護(hù)士對(duì)于排班的消極情緒最小化，并對(duì)護(hù)士排班問題建立了標(biāo)準(zhǔn)化公式，使得護(hù)士短缺與護(hù)士偏好之間得以平衡。Cheang 和Lim[5]發(fā)展了一種月?lián)Q班排班的啟發(fā)式規(guī)劃，該模型要求在嘗試著去滿足指定人員需求之前，一些特殊的請求必須先予以滿足。以Edmund 和Patrick[6]為代表的護(hù)理排班系統(tǒng)結(jié)合了循環(huán)方法的優(yōu)點(diǎn)以及計(jì)算機(jī)排班的彈性優(yōu)點(diǎn)，來幫助排班工作的開展。護(hù)士排班問題的求解難點(diǎn)在于存在大量約束條件，許多傳統(tǒng)的確定性方法[4～6]甚至需要以較高的計(jì)算復(fù)雜性來求得可行解。為了解決復(fù)雜性高的問題，許多研究學(xué)者[6～8]限制了問題的維度且使用簡單的啟發(fā)式算法來解決問題，但這也同時(shí)帶來了新的問題，就是求解效率不高。

針對(duì)護(hù)士排版問題的多約束難點(diǎn)，我們考慮用遺傳算法進(jìn)行處理；同時(shí)，為了提高算法的求解速度，將可變鄰域搜索[4]融入遺傳算法作為提速。因此，本文將提出一種遺傳算法GA（Genetic Algorithm）與可變鄰域搜索VNS（Variable Neighborhood Search）相結(jié)合的混合算法，以達(dá)到更好的全局求解性能。

2 護(hù)士排班問題描述

目前研究的護(hù)士排班問題是：給定一個(gè)排班周期（30天）內(nèi)的全部護(hù)理工作，并且給定固定人數(shù)（30人）的護(hù)士，要求滿足一系列醫(yī)院法規(guī)等約束，在可接受的時(shí)間內(nèi)，編制出一個(gè)有效（即盡可能滿足各種約束條件）的護(hù)士排班方案。

該問題具有以下特征：

（1）每天的護(hù)理工作分三個(gè)班次，分別為早班（A 班：0點(diǎn)～8點(diǎn)）、中班（P班：8點(diǎn)～16點(diǎn)）、晚班（N 班：16點(diǎn)～24點(diǎn)），每個(gè)班次的工作時(shí)間為連續(xù)八個(gè)小時(shí)。

（2）每天每個(gè)班次有最小護(hù)士人數(shù)需求。

（3）每位護(hù)士一日最多只能進(jìn)行一個(gè)班次的工作。

以上是護(hù)士排班模型的最基本特點(diǎn)。中國式護(hù)士排班問題還包括以下硬約束條件和軟約束條件。

硬約束條件（必須滿足）：

HC1：每天每個(gè)班次的護(hù)士人數(shù)滿足最小護(hù)士人數(shù)需求。

HC2：每位護(hù)士的工作天數(shù)不能超過規(guī)定的上限，亦不能少于規(guī)定的下限。

HC3：對(duì)于前一天上了晚班的護(hù)士，第二天不能安排早班。

軟約束條件（盡可能滿足）：

SC1：護(hù)士工作量公平。在整個(gè)周期中，每個(gè)護(hù)士不同班次的工作天數(shù)與平均值相差不超過1天。

SC2：每個(gè)護(hù)士的連續(xù)工作天數(shù)不能超過7天，不能低于3天。

SC3：每個(gè)護(hù)士的晚班連續(xù)工作天數(shù)不能超過5天。

SC4：完整周末。周末的2 天要么都工作，要么都休息。

SC5：周末工作的天數(shù)不能超過4天。

SC6：連續(xù)工作后至少能夠得到2天的休息。

因此，護(hù)士排班問題的完整數(shù)學(xué)模型如下：

其中，對(duì)于一個(gè)周期天數(shù)為T（T＝30）的排班安排，共涉及到的護(hù)士總數(shù)為N（N＝30）。護(hù)士集合用I來表示，排班天數(shù)集合用J 來表示，班次集合用K 來表示。那么，可以用xijk表示第i 個(gè)護(hù)士在第j 天的班次k 的排班安排。

在處理硬約束條件問題上，用rij表示第j 天班次k 的最小護(hù)士需求人數(shù)，workmin表示最少工作天數(shù)，workmax表示最多工作天數(shù)。而對(duì)于軟約束條件，p1～p6表示相應(yīng)的懲罰權(quán)重值，s1～s6表示所得解對(duì)軟約束條件的違反次數(shù)。

3 GA＋VNS混合算法設(shè)計(jì)

3.1 算法框架

為了有效地求解該護(hù)士排班問題，本文采用了混合的進(jìn)化算法策略。為了避免在進(jìn)化過程中進(jìn)行無效搜索，我們采用了一種基于約束下的雜交變異搜索方法。這種雜交變異的方式保證了搜索的高效率和有效性，同時(shí)也考慮了不同的排班表之間的維數(shù)和差異性。由于護(hù)士排班問題的約束過多，設(shè)計(jì)的混合算法采用了（1＋1）EA 算法框架[9]，而不采用（μ＋λ）EA 算法求解。這樣，排班表中的元素之間必然存在著直接或者間接的關(guān)聯(lián)，而且即使不同排班表適應(yīng)值相同，其編碼差異性同樣很大。這些因素必然導(dǎo)致不同排班表之間雜交產(chǎn)生的子代違反程度很高?；谏鲜鎏攸c(diǎn)，在（1＋1）EA 算法框架的基礎(chǔ)上，本文混合算法的求解過程分為以下幾個(gè)步驟：

第1步 初始解的生成：在此過程中產(chǎn)生一個(gè)種群的解，滿足醫(yī)院每天對(duì)各類護(hù)士需求的約束和每個(gè)護(hù)士總的工作量約束。

第2步 目標(biāo)解的分離和搜索：在此過程中，排班表按照某種規(guī)則進(jìn)行有效的調(diào)整，同時(shí)，通過分離減少算法的計(jì)算量來提高算法的效率。

第3步 目標(biāo)解的輸出：用GA＋VNS的混合策略得到一個(gè)近似解，使得近似最優(yōu)解滿足醫(yī)院和護(hù)士的硬約束，同時(shí)盡量滿足軟約束，甚至全部滿足。

3.2 初始解生成

本節(jié)給出核心算法的第一步：目標(biāo)初始解的生成。

在初始解的生成過程中采用帶有隨機(jī)性的確定性搜索方法，這一方面提高了算法搜索效率，同時(shí)也提高了算法的局部搜索能力。由于初始解只需要滿足醫(yī)院對(duì)各類護(hù)士的需求約束和各護(hù)士的工作總量約束，不要求滿足其它的約束，因此可以在較短的時(shí)間內(nèi)生成初始解。生成初始解的流程如圖1所示。

Figure 1 Initial solution generation of nurse rostering圖1 護(hù)士排班表初始解的生成

其步驟如下：

第1步 按照每一天醫(yī)院對(duì)各類護(hù)士的需求，隨機(jī)分布各列。

第2步 按照護(hù)士總的工作量范圍按天調(diào)整護(hù)士之間的上班班次；工作量超出的護(hù)士將某一天中大于0的變量與工作量較少的護(hù)士同天中等于0的變量進(jìn)行互換。

第3步 當(dāng)護(hù)士總的工作量滿足時(shí)停止，否則轉(zhuǎn)到第2步。

3.3 解空間的分離與搜索

生成初始解后，便開始對(duì)初始解進(jìn)行一系列的變換處理。每個(gè)護(hù)士的排班都是根據(jù)前一步處理得到的信息，來指導(dǎo)下一步的變換方式。在變換的過程中，對(duì)護(hù)士排班表進(jìn)行分段處理，從而達(dá)到對(duì)解空間進(jìn)行分離的目的。這種處理方式的優(yōu)點(diǎn)是縮短了解的求解時(shí)間，同時(shí)不同解空間可采用不同的算法；缺點(diǎn)是每個(gè)解空間得出的解都不是全局最優(yōu)解，即使最后會(huì)把所有的局部最優(yōu)解進(jìn)行組合優(yōu)化處理，依然無法保證得到的就是逼近全局最優(yōu)解的情況，甚至?xí)x全局最優(yōu)解。

在上述解空間分離的情況下，通過以下三種方式對(duì)各個(gè)分離子空間進(jìn)行搜索：

（1）采用啟發(fā)式算法：可變鄰域搜索算法（VNS）可有效提高算法的搜索效率，減少不必要的搜索和計(jì)算。

（2）算法按照護(hù)士的分類對(duì)自變量空間進(jìn)行分解，每次的交換都在兩個(gè)護(hù)士之間進(jìn)行，其他的護(hù)士不做變動(dòng)，因此其他護(hù)士的約束函數(shù)無需重復(fù)計(jì)算。

（3）變換的過程中根據(jù)3.2節(jié)中的第2步和第3步對(duì)新個(gè)體進(jìn)行修正，以保證新個(gè)體滿足每天各種類型護(hù)士的總量和每個(gè)護(hù)士總的工作量約束。

通過上述解空間的分離和搜索，可產(chǎn)生新的個(gè)體，然后根據(jù)約束的度量得出其適應(yīng)值大小，約束越大對(duì)應(yīng)的適應(yīng)值越低，并依此根據(jù)判定準(zhǔn)則擇優(yōu)錄取。選取的最優(yōu)個(gè)體如果不違反約束，則算法終止；否則，對(duì)每一個(gè)護(hù)士的違反程度進(jìn)行度量，得出每個(gè)護(hù)士的約束懲罰值。然后，按照懲罰值的大小進(jìn)行排序，懲罰值越大的優(yōu)先級(jí)越高，并優(yōu)先進(jìn)行處理。然后，采用3.3節(jié)中的三種方式進(jìn)行搜索。

3.4 GA＋VNS混合策略

通過實(shí)踐證明，GA 算法的優(yōu)勢在于求出的解具有更高的質(zhì)量，盡管其計(jì)算時(shí)間比較長，但卻是在可接受范圍之內(nèi)，沒有超出限制的時(shí)間。按照護(hù)士的分類對(duì)自變量空間進(jìn)行分解，每次的交換都在兩個(gè)護(hù)士之間進(jìn)行，而其他的護(hù)士不做變動(dòng)。因此，其他護(hù)士的約束函數(shù)無需重復(fù)計(jì)算。在交換的過程中我們可以采取多種交換策略，如VNS算法和隨機(jī)搜索算法；同時(shí)，為了避免算法陷入局部收斂，在進(jìn)化過程中采用了模擬退火的思想，進(jìn)行重升溫重退火的方式來搜索最優(yōu)解。GA＋VNS混合算法流程如圖2所示。

Figure 2 Hybrid algorithm of GA＋VNS圖2 GA＋VNS混合算法流程

其中，雜交變異與VNS混合策略的偽代碼如下（xij為第i個(gè)護(hù)士第j 天的值班類型）：

輸入：護(hù)士排班表。

輸出：新護(hù)士排班表。

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

表1是GA＋VNS方法與IP＋VNS方法經(jīng)過實(shí)驗(yàn)對(duì)比所得到的結(jié)果分析表。在第一階段的算法運(yùn)行過程中，IP 階段所進(jìn)行的迭代次數(shù)是GA階段的迭代次數(shù)的25倍，這是為了保證IP階段能夠充分得到良好的問題解，以方便進(jìn)行測試對(duì)比。在都經(jīng)過VNS 優(yōu)化后的20 組問題測試數(shù)據(jù)中，GA＋VNS方法在其中19組實(shí)驗(yàn)中的結(jié)果均優(yōu)于IP＋VNS方法，剩余的1組實(shí)驗(yàn)結(jié)果也僅僅稍微劣于IP＋VNS方法[4]，如圖3所示。

Table 1 Comparison of GA＋VNS and IP＋VNS表1 GA＋VNS方法與IP＋VNS方法對(duì)比

結(jié)果分析總結(jié)說明，在NRP 問題規(guī)模較大的情況下（此問題是求解30個(gè)護(hù)士在30天內(nèi)的排班安排），在優(yōu)良的初始解的基礎(chǔ)上，通過針對(duì)具體問題而設(shè)計(jì)的不違反約束的GA 算法通常能夠在可接受的執(zhí)行時(shí)間內(nèi)得到非常好的結(jié)果解。由于GA 算法本身帶有很大的不確定性，在進(jìn)化操作中采用VNS進(jìn)行優(yōu)化，能夠有效地調(diào)整進(jìn)化方向，進(jìn)而有目的性地產(chǎn)生較優(yōu)的子代，最終產(chǎn)生良好的問題解。經(jīng)過優(yōu)化后的GA＋VNS算法充分結(jié)合了GA 算法的自適應(yīng)性以及VNS算法對(duì)進(jìn)化方向修正的特點(diǎn)，在20組數(shù)據(jù)測試中GA＋VNS算法的表現(xiàn)優(yōu)于IP＋VNS。

根據(jù)上述實(shí)驗(yàn)結(jié)果，可得出以下結(jié)論：

Figure 3 Object function comparison of GA＋VNS and IP＋VNS圖3 GA＋VNS方法與IP＋VNS方法目標(biāo)函數(shù)值的直觀對(duì)比

GA 算法操作有賴于良好的進(jìn)化策略（3.4節(jié)的雜交變異）。GA 階段進(jìn)化策略是針對(duì)本文中的具體問題而巧妙設(shè)計(jì)的，其中的效果主要是在保證滿足硬約束條件的情況下有目標(biāo)地向更優(yōu)解接近，從而產(chǎn)生出更好的子代，有效地進(jìn)行進(jìn)化操作。較大規(guī)模的NRP 問題宜用啟發(fā)式算法以及其他輔助算法混合一起使用，如本文的GA＋VNS算法。由于解的空間比較大，同時(shí)約束條件比較多（容易產(chǎn)生許多不可行區(qū)域），單純的啟發(fā)式算法難以直接得到比較好的結(jié)果。因此，應(yīng)該針對(duì)不同的具體問題混合其他策略來優(yōu)化其效果，例如優(yōu)化初始解（3.2節(jié)子算法），通過解空間分離進(jìn)行局部搜索（3.3節(jié)子算法）等；同時(shí)，啟發(fā)式搜索規(guī)則（3.4節(jié)）也需要有目的地設(shè)置，以保證VNS啟發(fā)式搜索是有方向性地進(jìn)行，而非盲目地在大范圍的解空間內(nèi)進(jìn)行無效搜索。

5 結(jié)束語

護(hù)士排班問題是一類NP問題，本文使用帶約束的交換機(jī)制生成初始解，以達(dá)到最佳的初始解效果，為下一步處理作了準(zhǔn)備。更關(guān)鍵的是，本文提出了一種混合GA 算法，首先對(duì)解空間進(jìn)行分離，然后分別進(jìn)行搜索，得到各個(gè)解空間的局部最優(yōu)解后，再對(duì)各個(gè)解進(jìn)行綜合，逼近全局最優(yōu)解。實(shí)驗(yàn)結(jié)果說明，該方法兼顧了時(shí)間效率以及結(jié)果質(zhì)量，彈性適應(yīng)能力強(qiáng)，能從容應(yīng)對(duì)醫(yī)療護(hù)理人員的突發(fā)請求以及班次變更。

[1]Gutjahr W J，Rauner M S.An Aco algorithm for a dynamic regional nurse-scheduling problem in Austria[J].Computers＆Operations Research，2007，34（3）：642-666.

[2]Brucker P，Burke E K，Curtois T，et al.A shift sequence based approach for nurse scheduling and a new benchmark dataset[J].Journal of Heuristics，2008，16（4）：559-573.

[3]Moz M，Pato M V.A genetic algorithm approach to a nurse rerostering problem[J].Computers ＆Operations Research，2007，34（3）：667-691.

[4]Burke E K，Li Jing-peng，Qu Rong.A hybrid model of integer programming and variable neighborhood search for highly-constrained nurse rostering problems[J].European Journal of Operational Research，2010，2.3（2）：484-492.

[5]Cheang B，Li H，Lim A，et al.Nurse rostering problem—a bibliographic survey[J].European Journal of Operational Research，2003，151（3）：447-460.

[6]Burke E，Causmaecker P D，Petrovic S，et al.Variable neighborhood search for nurse rostering problems[M]∥Metaheuristics：Computer decision-making，Norwell：Kluwer Academic Publishers，2003：153-172.

[7]Burke E K，Curtois T，Post G，et al.A hybrid heuristic ordering and variable neighborhood search for the nurse rostering problem[J].European Journal of Operational Research，2008，188（2）：330-341.

[8]Tsai Chang-chun，Li S H A.A two-stage modeling with genetic algorithms for the nurse scheduling problem[J].Expert Systems with Applications，2009，36（5）：9506-9512.

[9]Zhang Yu-shan，Hao Zhi-feng，Huang Han.Convergence analysis of two-membered evolution strategy[J].Computer Science，2011，38（7）：231-234.（in Chinese）

[10]Chen Tian-shi，Tang Ke，Chen Guo-liang，et al.Analysis of computational time of simple estimation of distribution algorithms[J].IEEE Transactions on Evolutionary Computation，2010，14（1）：1-22.

附中文參考文獻(xiàn)：

[9]張宇山，郝志峰，黃翰.二元進(jìn)化策略的收斂性分析[J].計(jì)算機(jī)科學(xué)，2011，38（7）：231-234.