基于細(xì)菌覓食算法的排班智能優(yōu)化

張永棠

摘 要：智能排班問題是極為復(fù)雜的組合優(yōu)化問題。它包含了勞動(dòng)法約束、員工層級(jí)、不同層級(jí)的工資策略、不同班次的工資策略、資源需求等復(fù)雜因素。我們以南昌某醫(yī)院護(hù)士排班智能優(yōu)化為例，選取了基于細(xì)菌覓食優(yōu)化的算法來為此類問題進(jìn)行優(yōu)化求解。為了提高算法的搜索能力，將信息交流機(jī)制加入到細(xì)菌在趨化過程中的翻轉(zhuǎn)方向選擇上，研究了基于四種靜態(tài)拓?fù)浣Y(jié)構(gòu)和一種動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)的鄰域結(jié)構(gòu)下的細(xì)菌覓食優(yōu)化算法。

關(guān)鍵詞：智能優(yōu)化 群體智能 調(diào)度 細(xì)菌覓食算法

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2018）01（b）-0031-02

隨著人們對(duì)于健康保健意識(shí)的日益增強(qiáng)，患者及家屬對(duì)護(hù)理服務(wù)的需求不斷提高。如何有效分配護(hù)理資源管理、為病人提供高品質(zhì)的服務(wù)并有效控制預(yù)算是當(dāng)今當(dāng)前醫(yī)院護(hù)理管理所面臨的重大課題。但是在實(shí)際中，勞動(dòng)法規(guī)約束、個(gè)人能力的差別、應(yīng)急性、工作時(shí)間不穩(wěn)定等因素導(dǎo)致實(shí)現(xiàn)較好的護(hù)理管理困難重重。

智能排班問題（Intelligent Rostering Problem，簡(jiǎn)稱IRP）是指在給定的排班時(shí)間段內(nèi)為特定的一組員工安排班次，并使該排班方案滿足各種硬性約束條件，同時(shí)盡量滿足各種軟性約束條件，并在此基礎(chǔ)上優(yōu)化相關(guān)性能指標(biāo)。因此，智能排班問題是一個(gè)極為復(fù)雜的組合優(yōu)化問題，也是現(xiàn)代人力資源管理亟待解決的一大難題。

1 排班問題

本文研究以南昌某醫(yī)院的護(hù)士排班問題為例。在給定的一個(gè)排班周期內(nèi)對(duì)于一定數(shù)量的包括不同等級(jí)的護(hù)士進(jìn)行排班安排。需要考慮的條件有：滿足國家勞動(dòng)法規(guī)定、醫(yī)院一系列約束條件，滿足醫(yī)院工作需求，護(hù)士合理要求。本文研究的護(hù)士排班問題主要有以下特點(diǎn)：

（1）護(hù)士每天的工作分為三種班次，分別為早班（0點(diǎn)～8點(diǎn)）、白班（8點(diǎn)～16點(diǎn)）、晚班（16點(diǎn)～24點(diǎn)）。

（2）護(hù)士工資按照技術(shù)資格（初級(jí)、中級(jí)、高級(jí)）分配。其中如果低級(jí)護(hù)士工資為1，則中級(jí)護(hù)士工資為1.2，高級(jí)護(hù)士工資為1.5。

（3）同時(shí)由于夜班比較辛苦，因此對(duì)于夜班工資具有一定的補(bǔ)償。如果早班、白班工資為1，則夜班工資為1.5。

除了上述特點(diǎn)，護(hù)士排班問題還必須滿足一定的約束條件，其中必須滿足的硬約束條件為：

HC1：排班周期內(nèi)，每天每個(gè)班次必須安排護(hù)士；

HC2：每個(gè)護(hù)士每天只能上一種類型的班；

HC3：每個(gè)護(hù)士在相鄰2天的班次不能出現(xiàn)連續(xù)排班；

HC4：在一個(gè)排班周期內(nèi)，最長(zhǎng)工作時(shí)間不能超過規(guī)定的上限；

HC5：在一個(gè)排班周期內(nèi)，最短工作時(shí)間不能少于規(guī)定的下限；

HC6：高級(jí)護(hù)士可以替代中級(jí)、低級(jí)護(hù)士，中級(jí)護(hù)士可以替代低級(jí)護(hù)士，反之不行。

盡可能滿足的軟約束為：

SC1：任何一個(gè)班次（早班、白班和夜班）的各級(jí)護(hù)士數(shù)不低于實(shí)際需求量。

2 基于細(xì)菌覓食優(yōu)化的算法

細(xì)菌覓食優(yōu)化算法是受大腸桿菌覓食的啟發(fā)提出來的。它包含趨化行為、游動(dòng)行為、繁殖行為、死亡-驅(qū)散行為四種基本的行為。通過這四種行為，細(xì)菌進(jìn)行位置迭代，尋找到最優(yōu)的適應(yīng)度值。

結(jié)構(gòu)重組的細(xì)菌覓食優(yōu)化算法（Structure-redesign-based Bacterial Foraging Optimization，SRBFO）是基于BFO算法的一種改進(jìn)算法。原始BFO算法中，4個(gè)操作算子組成了三層嵌套循環(huán)結(jié)構(gòu)，每一次計(jì)算都需要遍歷三層循環(huán)，導(dǎo)致算法計(jì)算復(fù)雜，收斂速度緩慢，計(jì)算耗時(shí)長(zhǎng)。因此，Niu等人針對(duì)這一缺點(diǎn)，從GA、PSO以及其他智能算法中獲取靈感，將單循環(huán)結(jié)構(gòu)引入到原始BFO算法中，代替原來的三層嵌套循環(huán)結(jié)構(gòu)，提出了SRBFO算法。在SRBFO算法中，復(fù)制操作、死亡-驅(qū)散操作均與趨化操作并行進(jìn)行，從根本上簡(jiǎn)化了算法的計(jì)算復(fù)雜性。目前已有相關(guān)的研究成果已經(jīng)證明的該算法在函數(shù)優(yōu)化和現(xiàn)實(shí)問題優(yōu)化求解上的有效性，詳細(xì)情況見文獻(xiàn)。

細(xì)菌信息交流機(jī)制最重要的就是細(xì)菌與其他細(xì)菌之間的相連，從而實(shí)現(xiàn)信息的傳達(dá)。不同鄰域結(jié)構(gòu)的SRBFO算法的效果會(huì)有很大的差別。因此，借鑒Kennedy等在文獻(xiàn)中首次提到的粒子群算法中的拓?fù)浣Y(jié)構(gòu)，本文擬將選取5種拓?fù)浣Y(jié)構(gòu)加入到SRBFO算法中，其中4種分別為：環(huán)型（SRBFO-R）、星型（SRBFO-ST）、全連接型（SRBFO-FC）、von Neumann（SRBFO-VN）型；另外一種為動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)（SRBFO-DN），其拓?fù)浣Y(jié)構(gòu)是通過一定的概率條件在星型和環(huán)型之間轉(zhuǎn)化。這五種拓?fù)浣Y(jié)構(gòu)主要加入在趨化過程中細(xì)菌在翻轉(zhuǎn)時(shí)的方向選擇上，通過與鄰域的細(xì)菌進(jìn)行交流學(xué)習(xí)來選擇自身的翻轉(zhuǎn)方向。

3 優(yōu)化求解

為了求解本文所研究的護(hù)士排班調(diào)度問題，采用考慮了不同信息交流機(jī)制的結(jié)構(gòu)重組的細(xì)菌覓食優(yōu)化的算法對(duì)此進(jìn)行求解，主要包括三大步驟：粒子編碼、方案可行化、目標(biāo)函數(shù)構(gòu)建等。

3.1 粒子編碼

對(duì)于算法而言，每一個(gè)粒子應(yīng)該是一個(gè)潛在的可行解，即每個(gè)粒子所攜帶的信息必須包括所有待調(diào)度的護(hù)士的排班安排，因此在Matlab中編碼時(shí)，將每個(gè)粒子設(shè)為一個(gè)元胞，即每個(gè)粒子是1*nn（nn為總護(hù)士數(shù)）的矩陣，在該矩陣中的每個(gè)元素為ss*sd矩陣（ss為班次數(shù)，一般加上休班，ss=4；sd為調(diào)度周期），如下所示：

該編碼所代表的信息為：

3.2 方案可行化

細(xì)菌覓食優(yōu)化算法是求解連續(xù)的優(yōu)化問題，對(duì)于排班調(diào)度這種離散問題，必須通過一定的機(jī)制將迭代后的位置值轉(zhuǎn)化為離散的，才可以成功應(yīng)用于求解護(hù)士排班問題。因此在粒子編碼時(shí)，每個(gè)粒子的編碼是ss*sd的矩陣，通過最小位置值的解碼方式，將矩陣中的每一列的元素都轉(zhuǎn)換為0-1，同時(shí)滿足每一列中有一個(gè)1、3個(gè)0（此轉(zhuǎn)換后的方案直接滿足約束條件HC1、HC2），該元素1所在的行則代表該護(hù)士在調(diào)度周期的某一天的班次，如果為第1行，則表示該天的班次為早班，如此類推。

3.3 目標(biāo)函數(shù)構(gòu)建

護(hù)士排班調(diào)度問題的原始目標(biāo)函數(shù)為使得總護(hù)士工資成本最小，同時(shí)為了盡可能滿足軟約束SC1，通過罰函數(shù)的方法將未滿足的需求加權(quán)到目標(biāo)函數(shù)中，本文中懲罰系數(shù)設(shè)為1000。但是HC6規(guī)定高級(jí)護(hù)士可以替代中級(jí)、低級(jí)護(hù)士，中級(jí)護(hù)士可以替代低級(jí)護(hù)士，反之不行。因此在計(jì)算未滿足的需求成本時(shí)，必須分層計(jì)算，從低級(jí)護(hù)士開始計(jì)算，如果低級(jí)護(hù)士排班方案中的某個(gè)班次數(shù)量低于需求，則計(jì)算中級(jí)護(hù)士，如果中級(jí)護(hù)士在該班次的排班數(shù)量大于需求，則剩下的班次可以用來填補(bǔ)低級(jí)護(hù)士排班方案中所未滿足的需求，如此類推，最后計(jì)算總的未滿足的需求，并計(jì)算總的未滿足的需求成本。

4 結(jié)語

本文針對(duì)我國目前的情況，考慮了勞動(dòng)法約束、護(hù)士層級(jí)、不同層級(jí)的工資策略、不同班次的工資策略等因素，對(duì)護(hù)士排班問題進(jìn)行了研究。為了優(yōu)化求解這類NP-Hard問題，本文提出了基于交流機(jī)制的結(jié)構(gòu)重組的細(xì)菌覓食優(yōu)化算法來對(duì)這一問題進(jìn)行優(yōu)化求解。將四種靜態(tài)拓?fù)浣Y(jié)構(gòu)：環(huán)型、星型、全連接型、von Neumann型以及一種動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)分別加入到細(xì)菌在趨化過程中的翻轉(zhuǎn)方向選擇上，以提高算法的搜索能力。從整體上來看，本文不僅擴(kuò)展了細(xì)菌覓食優(yōu)化算法的應(yīng)用范圍，同時(shí)為護(hù)士排班這類NP-Hard問題的優(yōu)化求解提供了更多借鑒。

參考文獻(xiàn)

[1] 童向紅，徐蘭玲，張娃蓮.內(nèi)科護(hù)士排班模式改進(jìn)與效果分析[J].浙江醫(yī)學(xué)教育，2008（4）：24-25.

[2] 范淑玉，楊向紅.我國護(hù)士排班狀況研究進(jìn)展[J].護(hù)理管理雜志，2008，8（12）：27-29.

[3] 劉梅，廖少玲，文若蘭.護(hù)士排班的研究現(xiàn)狀[J].廣東醫(yī)學(xué)院學(xué)報(bào)，2011，29（2）：210-211.