基于改进遗传算法解决多目标智能排班问题研究

王梦真 陈欢良

摘要：该文将使用遗传算法与模拟退火算法相结合从而优化传统遗传算法，不断的循环迭代筛选出最优解进而得到最高效率的排班，将算法与数学模型相结合，并采用减治思想提高算法效率。其中综合考虑各类如公司排班制度，员工情绪、公司利益等相关因素，使其适应度达到最高。采用真实的公司员工数据进行仿真实例实验证结果表明，研究的排班优化思想和算法是切实可行的。

關键词：员工排班;组合优化;遗传算法;模拟退火算法

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2022）02-0079-03

1 引言

人员排班问题是社会生活中的一个实际问题，从政府机关、企业单位到团体组织、班级人员的安排，都离不开这个问题，是各个行业都需要面对和解决的问题。排班是公司运营的基础，对公司有着甚至是巨大的影响。人员排班是保证企业日常运营和应对突发情况的重要手段，首先要解决的就是人力资源的有效使用和安排，其次要保证人员安排的合理性和规范性;再次要实现收益的最大化，用最少的人，完成最多的任务[1]。

排班是一个综合复杂的过程需要考虑各种因素，才能排出最优的排班序列而智能排班相较于人工排班来说最大的优势就是采用计算机实现高效率排班，这是人工排班无法比拟的。

为了实现智能排班且尽可能高效率地得出最优解，本文提出将遗传算法与模拟退火算法相结合，并且针对排班问题特点提出改进算法等以提高传统遗传算法的效率。

2 智能排班模型建立

2.1研究问题

在公司里，人员排班工作主要就是根据公司每月工作计划、考虑每个员工的具体情况，对每一天的每一个岗位分配合适的员工，最终的目的是使公司以最优的排班使得员工完成工作。

1.1 智能排班问题算法模型建立

本文将以月为单位建立排班模型。

模型如下：

BaseDay为必须工作的工作天数

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

WorkOvertime为某些员工需多工作的天数

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

Day为最合理的工作的天数

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

EveryDayWtij为每个员工每天的工作情况相当于Total个01二维表

EveryDayWtij=[1，员工j在i这天工作0 ，员工j在i这天休息]

WorkDayTj[（BaseDay≤WorkDayTj≤Day）]为每个员工工作的总天数

[WorkDayTj=i=0EveryDayEveryDayWtij]

ContinueDj为每个员工连续工作的天数

ContinueDj[]

DayTotalt为总员工工作总天数

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

Sum为软条件约束的总个数：

X为各种软条件的编号

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

S1连续工作日约束：

每个员工连续工作的天数不能超过给定的硬性条件的限制范围，否则会造成员工身心疲倦，惩戒值加1。

S2连续休息日约束：

每个员工连续休息的天数不能超过给定的硬性条件的限制范围，否则会影响公司业务进度，且影响员工工作效率，惩戒值加1.

S3员工偏好约束：

根据员工请定换班工作却仍安排其在那一天工作，如若违反惩戒值加1。

S4公司利益约束：

根据公司某日工作任务所需合理安排工作人数，如若违反惩戒值加1.

KX为权值每一个软条件所占的比重

[φt]为软条件的值：

[φt=XSumSX*KX]

[f]为适应度值：

[ft=1φt]

[f]为变动的临界值：

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

BestWij为最优排班序列：

T1为使得每一代在一定条件下尽可能地达到最优解的退火算法的初始温度，ET1为相应的结束温度，L1为相应的子迭代次数，Rate1为退火速率。

T2为个体交叉中以概率性地保证种群多样性与优质性的退火算法的初始温度，ET2为相应的结束温度，L2为相应的子迭代次数，Rate2为退火速率。

T3为个体交叉中以概率性地保证种群多样性与优质性的退火算法的初始温度，ET3为相应的结束温度，L3为相应的子迭代次数，Rate3为退火速率。

[Δf]为两个适应度的差值：

[Δf=fnew-f]

[p]为概率：

上式中所出现的参数：

Num为员工的总人数;

EveryNum为每天工作所需的员工人数;

EveryDay为某个月的总天数;

EveryRelaxDay为每个月员工放假的总天数;

BanDay为公司规定员工工作不能连续超过的天数;

RelaxDay为公司规定员工休息不能连续超过的天数;

Total为每一代的个数总数;

UO为交叉的概率;

UV为变异的概率;

GT为遗传算法的总代数;

i为具体某个月的某天：

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

j为员工序号：

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

t为具体某一代的个体编号：

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

a为具体的最优区间大小：

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

2.2 智能排班算法模型设计

具体设计图见图1。

2.3 智能排班算法基本框架

即要满足每天必须上班的人数也要满足不能连续工作的天数，解决这个硬条件其实也是消除冲突。现将无序的排班调整符合每天需要工作的员工人数和员工所需工作的天数，所以只会出现连续上班天数不符合的情况，当发现这种情况的时候需要纵向查找可替换的日期也需要横向查找可替换的员工以保证每天所需的员工人数不变。且需要检测替换后是否会出现新的冲突。

在此将有冲突的区间保留为[work_day1，work_day2]。为了简单化从中间[mid=work_day1+work_day22]开始查找替换离中间位置最近的[minmid-work_dayx]替换是最合理的选择其中。

Algorithm 2：  Fitness（）

循环根据公式进行计算，得出的结果取反后为适应度值及越违反软条件时适应度值越低。

Algorithm 3： Screen（）

先给最优适应度值赋初始值越低越好，循环进行查找当找到比它大的值进行替换，从而使得一次循环过后能得到当代最优的解。

Algorithm 4：

传统的遗传算法是随机产生两个父代进行随机交叉然后生成个体，按照一定比例进行选择，使得种群能比下一代获得优化，这样不断循环迭代会逐渐显露弊端后面的种群会不断趋向于一个优解，但这个优解不一定是全局最优很可能是局部最优这也称“过早收敛”。将遗传算法与模拟退火算法结合到一起就可以很好地解决这一个为问题使得种群很好地保持多样性。有选择地替换种群中适应度值较低的个体，提高种群的质量，且有概率的保留解可以使得种群保留多样性。

3 实验结果与分析

本文以银行员工排班为例，选取2021年3月份为所需排班的月份，一个月的天数为EveryDay=31天.某银行有员工人数Num=3人，每天需上班人数为EveryNum=2人，每周周日休息且每个月再额外随机选取一天休息，休息总天数为EveryRelaxDay=5天，不能连续工作的天数为BanDay=5天， 不能连续休息的天数为RelaxDay=6天.交叉概率为UO=0.88，变异的概率为UV=0.01.需连续循环迭代次数为GT=1000代.退火算法的初始温度为T1=90，相应的结束温度为ET1=0，子迭代次数为L1=100，退火速率为Rate1=0.025。个体交叉中以概率性地保证种群多样性与优质性的退火算法的初始温度为T2=80，相应的结束温度为ET2=0，相应的子迭代次数为L2=100，退火速率为Rate2=0.015。个体交叉中以概率性地保证种群多样性与优质性的退火算法的初始温度为T3=50，相应的结束温度为ET3=0，相应的子迭代次数为L3=100，退火速率为Rate3=0.020。

本文改进遗传算法是在遗传算法全局搜索能力强的基础上加入模拟退火算法增加局部搜索能力从而使得算法不再局限于局部最优解且更快更有效率收敛找到全局最优解，每个算法都有利弊，若单采用遗传算法不断的循环迭代筛选每代最优解，通过每代随机进行交换和若干个个体产生变异从而更新种群实现如生物界的优胜劣汰，但若某些个体样式在种群中占优势，就会不断向这个样式靠近，从而使得搜索范围变窄，逐渐收敛可能会导致得出的结果并不是全局最优而是局部最优如文献[2]。且算法本身存在收敛与全局搜索存在对立。存在范围运行时间长且效率较低，而且还容易过早收敛，且其全局搜索能力强但局部搜索能力弱等问题如文献[3]。为了提高算法的效率基于標准遗传算法上进行改进。而模拟退火算法正好与其对立。所以可以试想在遗传算法里包含着模拟退火算法使得每一代能以一定速率生成足够的较优解从而提高种群总体的质量然后在交叉变异中使用模拟退火算法的概率性以确保种群的多样性，使得种群不易收敛再经过每代的循环迭代从而得到全局最优解。其中为满足硬性条件时会存在冲突，消除冲突是解决整个问题中最核心也是最困难的地方为此借助文献[4]中消除冲突的思想来解决这个难题。从图一可知本文改进的遗传算法相较于标准的遗传算法而言其更早地得到适应度函数值的水平曲线且适应度函数值也高于标准遗传算法。证明了本文改进的遗传算法是切实可行的。

4 结论

本文以银行员工排班为例进行对员工排班问题的研究实则是一种需满足条件的组合排列优化问题。将遗传算法与模拟退火算法相结合，有效地解决了传统遗传算法过早收敛的问题，保持种群的多样性，防止出现局部最优解的问题，使每代种群尽可能地达到最优。并采用实际银行数据进行测试，证实了算法与模型的可行性，并能在较为理想的时间内解决问题。为解决排班问题提供了一定的参考性。

参考文献：

[1] 雷明.企业人力资源管理中，为何科学排班如此重要[J].人力资源管理，2018.

[2] 王雪梅，王义和.模拟退火算法与遗传算法的结合[J].计算机学报，1997，20（4）：381-384.

[3] 江建.模拟退火混合遗传算法及其实现[J].重庆文理学院学报（自然科学版），2009，28（5）：65-67.

[4] 刘浩.基于改进遗传算法的多目标约束条件排课问题研究[D].桂林：桂林理工大学，2019：1-84.

【通联编辑：李雅琪】

1456500511247