基于改進(jìn)遺傳算法解決多目標(biāo)智能排班問題研究

王夢真 陳歡良

摘要：該文將使用遺傳算法與模擬退火算法相結(jié)合從而優(yōu)化傳統(tǒng)遺傳算法，不斷的循環(huán)迭代篩選出最優(yōu)解進(jìn)而得到最高效率的排班，將算法與數(shù)學(xué)模型相結(jié)合，并采用減治思想提高算法效率。其中綜合考慮各類如公司排班制度，員工情緒、公司利益等相關(guān)因素，使其適應(yīng)度達(dá)到最高。采用真實(shí)的公司員工數(shù)據(jù)進(jìn)行仿真實(shí)例實(shí)驗(yàn)證結(jié)果表明，研究的排班優(yōu)化思想和算法是切實(shí)可行的。

關(guān)鍵詞：員工排班;組合優(yōu)化;遺傳算法;模擬退火算法

中圖分類號：TP311 ? ? ?文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2022）02-0079-03

1 引言

人員排班問題是社會生活中的一個實(shí)際問題，從政府機(jī)關(guān)、企業(yè)單位到團(tuán)體組織、班級人員的安排，都離不開這個問題，是各個行業(yè)都需要面對和解決的問題。排班是公司運(yùn)營的基礎(chǔ)，對公司有著甚至是巨大的影響。人員排班是保證企業(yè)日常運(yùn)營和應(yīng)對突發(fā)情況的重要手段，首先要解決的就是人力資源的有效使用和安排，其次要保證人員安排的合理性和規(guī)范性;再次要實(shí)現(xiàn)收益的最大化，用最少的人，完成最多的任務(wù)[1]。

排班是一個綜合復(fù)雜的過程需要考慮各種因素，才能排出最優(yōu)的排班序列而智能排班相較于人工排班來說最大的優(yōu)勢就是采用計算機(jī)實(shí)現(xiàn)高效率排班，這是人工排班無法比擬的。

為了實(shí)現(xiàn)智能排班且盡可能高效率地得出最優(yōu)解，本文提出將遺傳算法與模擬退火算法相結(jié)合，并且針對排班問題特點(diǎn)提出改進(jìn)算法等以提高傳統(tǒng)遺傳算法的效率。

2 智能排班模型建立

2.1研究問題

在公司里，人員排班工作主要就是根據(jù)公司每月工作計劃、考慮每個員工的具體情況，對每一天的每一個崗位分配合適的員工，最終的目的是使公司以最優(yōu)的排班使得員工完成工作。

1.1 智能排班問題算法模型建立

本文將以月為單位建立排班模型。

模型如下：

BaseDay為必須工作的工作天數(shù)

[BaseDay=（int）[（EveryDay-EveryRelDay）CEveryNumNum]?EveryNum]

WorkOvertime為某些員工需多工作的天數(shù)

[WorkOvertime=（int）[（EveryNum-EveryRelDay）%CEveryNumNum]]

Day為最合理的工作的天數(shù)

[Day=（int）[（EveryDay-EveryRelDay）CEveryNumNum]?EveryNum+（int）[（EveryNum-EveryRelDay）%CEveryNumNum]]

EveryDayWtij為每個員工每天的工作情況相當(dāng)于Total個01二維表

EveryDayWtij=[1，員工j在i這天工作0 ，員工j在i這天休息]

WorkDayTj[（BaseDay≤WorkDayTj≤Day）]為每個員工工作的總天數(shù)

[WorkDayTj=i=0EveryDayEveryDayWtij]

ContinueDj為每個員工連續(xù)工作的天數(shù)

ContinueDj[]

DayTotalt為總員工工作總天數(shù)

DayTotalt=[t=0Totali=0Numj=0EveryDayEveryDayWtij]

Sum為軟條件約束的總個數(shù)：

X為各種軟條件的編號

[X={1，2，3，4，…，Sum}]

S1連續(xù)工作日約束：

每個員工連續(xù)工作的天數(shù)不能超過給定的硬性條件的限制范圍，否則會造成員工身心疲倦，懲戒值加1。

S2連續(xù)休息日約束：

每個員工連續(xù)休息的天數(shù)不能超過給定的硬性條件的限制范圍，否則會影響公司業(yè)務(wù)進(jìn)度，且影響員工工作效率，懲戒值加1.

S3員工偏好約束：

根據(jù)員工請定換班工作卻仍安排其在那一天工作，如若違反懲戒值加1。

S4公司利益約束：

根據(jù)公司某日工作任務(wù)所需合理安排工作人數(shù)，如若違反懲戒值加1.

KX為權(quán)值每一個軟條件所占的比重

[φt]為軟條件的值：

[φt=XSumSX*KX]

[f]為適應(yīng)度值：

[ft=1φt]

[f]為變動的臨界值：

[f=（fmax-fmin）2+fmin2-fmin3]

BestWij為最優(yōu)排班序列：

T1為使得每一代在一定條件下盡可能地達(dá)到最優(yōu)解的退火算法的初始溫度，ET1為相應(yīng)的結(jié)束溫度，L1為相應(yīng)的子迭代次數(shù)，Rate1為退火速率。

T2為個體交叉中以概率性地保證種群多樣性與優(yōu)質(zhì)性的退火算法的初始溫度，ET2為相應(yīng)的結(jié)束溫度，L2為相應(yīng)的子迭代次數(shù)，Rate2為退火速率。

T3為個體交叉中以概率性地保證種群多樣性與優(yōu)質(zhì)性的退火算法的初始溫度，ET3為相應(yīng)的結(jié)束溫度，L3為相應(yīng)的子迭代次數(shù)，Rate3為退火速率。

[Δf]為兩個適應(yīng)度的差值：

[Δf=fnew-f]

[p]為概率：

上式中所出現(xiàn)的參數(shù)：

Num為員工的總?cè)藬?shù);

EveryNum為每天工作所需的員工人數(shù);

EveryDay為某個月的總天數(shù);

EveryRelaxDay為每個月員工放假的總天數(shù);

BanDay為公司規(guī)定員工工作不能連續(xù)超過的天數(shù);

RelaxDay為公司規(guī)定員工休息不能連續(xù)超過的天數(shù);

Total為每一代的個數(shù)總數(shù);

UO為交叉的概率;

UV為變異的概率;

GT為遺傳算法的總代數(shù);

i為具體某個月的某天：

[i={1，2，3，4，…，EveryDay}]

j為員工序號：

[j={1，2，3，4，…，Num}]

t為具體某一代的個體編號：

[t={1，2，3，4，…，Total}]

a為具體的最優(yōu)區(qū)間大?。?/p>

[a={1，2，3，4，…，All}]

2.2 智能排班算法模型設(shè)計

具體設(shè)計圖見圖1。

2.3 智能排班算法基本框架

即要滿足每天必須上班的人數(shù)也要滿足不能連續(xù)工作的天數(shù)，解決這個硬條件其實(shí)也是消除沖突。現(xiàn)將無序的排班調(diào)整符合每天需要工作的員工人數(shù)和員工所需工作的天數(shù)，所以只會出現(xiàn)連續(xù)上班天數(shù)不符合的情況，當(dāng)發(fā)現(xiàn)這種情況的時候需要縱向查找可替換的日期也需要橫向查找可替換的員工以保證每天所需的員工人數(shù)不變。且需要檢測替換后是否會出現(xiàn)新的沖突。

在此將有沖突的區(qū)間保留為[work_day1，work_day2]。為了簡單化從中間[mid=work_day1+work_day22]開始查找替換離中間位置最近的[minmid-work_dayx]替換是最合理的選擇其中。

Algorithm 2： ?Fitness（）

循環(huán)根據(jù)公式進(jìn)行計算，得出的結(jié)果取反后為適應(yīng)度值及越違反軟條件時適應(yīng)度值越低。

Algorithm 3： Screen（）

先給最優(yōu)適應(yīng)度值賦初始值越低越好，循環(huán)進(jìn)行查找當(dāng)找到比它大的值進(jìn)行替換，從而使得一次循環(huán)過后能得到當(dāng)代最優(yōu)的解。

Algorithm 4：

傳統(tǒng)的遺傳算法是隨機(jī)產(chǎn)生兩個父代進(jìn)行隨機(jī)交叉然后生成個體，按照一定比例進(jìn)行選擇，使得種群能比下一代獲得優(yōu)化，這樣不斷循環(huán)迭代會逐漸顯露弊端后面的種群會不斷趨向于一個優(yōu)解，但這個優(yōu)解不一定是全局最優(yōu)很可能是局部最優(yōu)這也稱“過早收斂”。將遺傳算法與模擬退火算法結(jié)合到一起就可以很好地解決這一個為問題使得種群很好地保持多樣性。有選擇地替換種群中適應(yīng)度值較低的個體，提高種群的質(zhì)量，且有概率的保留解可以使得種群保留多樣性。

3 實(shí)驗(yàn)結(jié)果與分析

本文以銀行員工排班為例，選取2021年3月份為所需排班的月份，一個月的天數(shù)為EveryDay=31天.某銀行有員工人數(shù)Num=3人，每天需上班人數(shù)為EveryNum=2人，每周周日休息且每個月再額外隨機(jī)選取一天休息，休息總天數(shù)為EveryRelaxDay=5天，不能連續(xù)工作的天數(shù)為BanDay=5天， 不能連續(xù)休息的天數(shù)為RelaxDay=6天.交叉概率為UO=0.88，變異的概率為UV=0.01.需連續(xù)循環(huán)迭代次數(shù)為GT=1000代.退火算法的初始溫度為T1=90，相應(yīng)的結(jié)束溫度為ET1=0，子迭代次數(shù)為L1=100，退火速率為Rate1=0.025。個體交叉中以概率性地保證種群多樣性與優(yōu)質(zhì)性的退火算法的初始溫度為T2=80，相應(yīng)的結(jié)束溫度為ET2=0，相應(yīng)的子迭代次數(shù)為L2=100，退火速率為Rate2=0.015。個體交叉中以概率性地保證種群多樣性與優(yōu)質(zhì)性的退火算法的初始溫度為T3=50，相應(yīng)的結(jié)束溫度為ET3=0，相應(yīng)的子迭代次數(shù)為L3=100，退火速率為Rate3=0.020。

本文改進(jìn)遺傳算法是在遺傳算法全局搜索能力強(qiáng)的基礎(chǔ)上加入模擬退火算法增加局部搜索能力從而使得算法不再局限于局部最優(yōu)解且更快更有效率收斂找到全局最優(yōu)解，每個算法都有利弊，若單采用遺傳算法不斷的循環(huán)迭代篩選每代最優(yōu)解，通過每代隨機(jī)進(jìn)行交換和若干個個體產(chǎn)生變異從而更新種群實(shí)現(xiàn)如生物界的優(yōu)勝劣汰，但若某些個體樣式在種群中占優(yōu)勢，就會不斷向這個樣式靠近，從而使得搜索范圍變窄，逐漸收斂可能會導(dǎo)致得出的結(jié)果并不是全局最優(yōu)而是局部最優(yōu)如文獻(xiàn)[2]。且算法本身存在收斂與全局搜索存在對立。存在范圍運(yùn)行時間長且效率較低，而且還容易過早收斂，且其全局搜索能力強(qiáng)但局部搜索能力弱等問題如文獻(xiàn)[3]。為了提高算法的效率基于標(biāo)準(zhǔn)遺傳算法上進(jìn)行改進(jìn)。而模擬退火算法正好與其對立。所以可以試想在遺傳算法里包含著模擬退火算法使得每一代能以一定速率生成足夠的較優(yōu)解從而提高種群總體的質(zhì)量然后在交叉變異中使用模擬退火算法的概率性以確保種群的多樣性，使得種群不易收斂再經(jīng)過每代的循環(huán)迭代從而得到全局最優(yōu)解。其中為滿足硬性條件時會存在沖突，消除沖突是解決整個問題中最核心也是最困難的地方為此借助文獻(xiàn)[4]中消除沖突的思想來解決這個難題。從圖一可知本文改進(jìn)的遺傳算法相較于標(biāo)準(zhǔn)的遺傳算法而言其更早地得到適應(yīng)度函數(shù)值的水平曲線且適應(yīng)度函數(shù)值也高于標(biāo)準(zhǔn)遺傳算法。證明了本文改進(jìn)的遺傳算法是切實(shí)可行的。

4 結(jié)論

本文以銀行員工排班為例進(jìn)行對員工排班問題的研究實(shí)則是一種需滿足條件的組合排列優(yōu)化問題。將遺傳算法與模擬退火算法相結(jié)合，有效地解決了傳統(tǒng)遺傳算法過早收斂的問題，保持種群的多樣性，防止出現(xiàn)局部最優(yōu)解的問題，使每代種群盡可能地達(dá)到最優(yōu)。并采用實(shí)際銀行數(shù)據(jù)進(jìn)行測試，證實(shí)了算法與模型的可行性，并能在較為理想的時間內(nèi)解決問題。為解決排班問題提供了一定的參考性。

參考文獻(xiàn)：

[1] 雷明.企業(yè)人力資源管理中，為何科學(xué)排班如此重要[J].人力資源管理，2018.

[2] 王雪梅，王義和.模擬退火算法與遺傳算法的結(jié)合[J].計算機(jī)學(xué)報，1997，20（4）：381-384.

[3] 江建.模擬退火混合遺傳算法及其實(shí)現(xiàn)[J].重慶文理學(xué)院學(xué)報（自然科學(xué)版），2009，28（5）：65-67.

[4] 劉浩.基于改進(jìn)遺傳算法的多目標(biāo)約束條件排課問題研究[D].桂林：桂林理工大學(xué)，2019：1-84.

【通聯(lián)編輯：李雅琪】

1456500511247