基于細菌覓食算法的排班智能優化

張永棠

摘 要：智能排班問題是極為復雜的組合優化問題。它包含了勞動法約束、員工層級、不同層級的工資策略、不同班次的工資策略、資源需求等復雜因素。我們以南昌某醫院護士排班智能優化為例，選取了基于細菌覓食優化的算法來為此類問題進行優化求解。為了提高算法的搜索能力，將信息交流機制加入到細菌在趨化過程中的翻轉方向選擇上，研究了基于四種靜態拓撲結構和一種動態拓撲結構的鄰域結構下的細菌覓食優化算法。

關鍵詞：智能優化 群體智能 調度 細菌覓食算法

中圖分類號：TP18 文獻標識碼：A 文章編號：1672-3791（2018）01（b）-0031-02

隨著人們對于健康保健意識的日益增強，患者及家屬對護理服務的需求不斷提高。如何有效分配護理資源管理、為病人提供高品質的服務并有效控制預算是當今當前醫院護理管理所面臨的重大課題。但是在實際中，勞動法規約束、個人能力的差別、應急性、工作時間不穩定等因素導致實現較好的護理管理困難重重。

智能排班問題（Intelligent Rostering Problem，簡稱IRP）是指在給定的排班時間段內為特定的一組員工安排班次，并使該排班方案滿足各種硬性約束條件，同時盡量滿足各種軟性約束條件，并在此基礎上優化相關性能指標。因此，智能排班問題是一個極為復雜的組合優化問題，也是現代人力資源管理亟待解決的一大難題。

1 排班問題

本文研究以南昌某醫院的護士排班問題為例。在給定的一個排班周期內對于一定數量的包括不同等級的護士進行排班安排。需要考慮的條件有：滿足國家勞動法規定、醫院一系列約束條件，滿足醫院工作需求，護士合理要求。本文研究的護士排班問題主要有以下特點：

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

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

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

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

HC1：排班周期內，每天每個班次必須安排護士；

HC2：每個護士每天只能上一種類型的班；

HC3：每個護士在相鄰2天的班次不能出現連續排班；

HC4：在一個排班周期內，最長工作時間不能超過規定的上限；

HC5：在一個排班周期內，最短工作時間不能少于規定的下限；

HC6：高級護士可以替代中級、低級護士，中級護士可以替代低級護士，反之不行。

盡可能滿足的軟約束為：

SC1：任何一個班次（早班、白班和夜班）的各級護士數不低于實際需求量。

2 基于細菌覓食優化的算法

細菌覓食優化算法是受大腸桿菌覓食的啟發提出來的。它包含趨化行為、游動行為、繁殖行為、死亡-驅散行為四種基本的行為。通過這四種行為，細菌進行位置迭代，尋找到最優的適應度值。

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

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

3 優化求解

為了求解本文所研究的護士排班調度問題，采用考慮了不同信息交流機制的結構重組的細菌覓食優化的算法對此進行求解，主要包括三大步驟：粒子編碼、方案可行化、目標函數構建等。

3.1 粒子編碼

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

該編碼所代表的信息為：

3.2 方案可行化

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

3.3 目標函數構建

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

4 結語

本文針對我國目前的情況，考慮了勞動法約束、護士層級、不同層級的工資策略、不同班次的工資策略等因素，對護士排班問題進行了研究。為了優化求解這類NP-Hard問題，本文提出了基于交流機制的結構重組的細菌覓食優化算法來對這一問題進行優化求解。將四種靜態拓撲結構：環型、星型、全連接型、von Neumann型以及一種動態拓撲結構分別加入到細菌在趨化過程中的翻轉方向選擇上，以提高算法的搜索能力。從整體上來看，本文不僅擴展了細菌覓食優化算法的應用范圍，同時為護士排班這類NP-Hard問題的優化求解提供了更多借鑒。

參考文獻

[1] 童向紅，徐蘭玲，張娃蓮.內科護士排班模式改進與效果分析[J].浙江醫學教育，2008（4）：24-25.

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

[3] 劉梅，廖少玲，文若蘭.護士排班的研究現狀[J].廣東醫學院學報，2011，29（2）：210-211.