求解柔性资源受限项目调度问题的多种群遗传算法

发布时间：2021-01-24 20:40

　　柔性资源普遍存在于制造业生产制造的各个环节中,提高了资源利用率和生产效益。以柔性资源为研究对象,建立了以最小化项目完成工期为目标的柔性资源受限项目调度问题的数学模型。针对现有标准遗传算法过早地收敛从而使整个遗传搜索无法求解出全局最优值的缺陷,提出了一种改进的多种群遗传算法来求解该问题模型。算法对作业优先级列表编码,引入交叉移民算子实现多种群间的协同进化,在解码过程中运用一种启发式柔性资源技能分配算法为作业分配资源,同时通过改进的串行调度生成方案对作业调度。最后通过标准算例库PSPLIB进行数值试验,验证了所提算法求解该问题的有效性。 

【文章来源】：计算机科学. 2020,47(S1)北大核心

【文章页数】：6 页

【部分图文】：

汽车移动装配生产线简图

针对MSRCPSP问题,本文设计了一种以作业优先级列表为编码方式的改进多种群遗传算法来求解该问题模型。传统多种群遗传算法中的移民操作可能会因为外来优秀个体成为种群主导个体从而使得种群多样性迅速降低,导致无法跳出局部最优。因此,本文对传统的移民操作进行改进,对移民算子进行交叉处理,得到交叉移民算子,再通过精英策略选择较优的个体替换目标种群中的最差个体,从而达到每次交流都使得目标种群引入外来优秀个体的部分基因,又保留自身种群个体的部分基因,避免外来优秀个体迅速成为主导个体的情况发生,保证了种群的多样性。在解码过程中,针对柔性资源技能分配问题,为避免资源分配时选择的随机性,本文提出一种启发式柔性资源技能分配算法,并通过作业—技能—资源映射关系模型为作业分配相应的资源。同时调用改进的串行调度生成机制对作业进行调度,通过判断局部两作业位置关系,根据不同的情况对作业进行调度,最终得到各个作业的执行时间,使得项目完成工期最短。算法流程图如图2所示。3.1 改进多种群遗传算法

本文采用实数编码方式对作业优先级列表编码,则编码的长度等于作业的个数n+1,编码的位置代表了作业的优先级pj,j∈V,pj越小,优先级越高;该位置上的数字代表了作业编号。如图3所示,作业2的优先级p2=1,优先级最高;作业7的优先级最低,p7=7;作业3的优先级p3=5等。3.1.2 选择

【参考文献】：
期刊论文
[1]多技能资源时间窗约束下可中断项目调度的分支定界算法[J]. 刘振元,袁慧涛,周成,毕阳,胡淑芳.  系统工程理论与实践. 2019(01)
[2]基于多种群遗传算法的自动化立体库货位优化[J]. 焦玉玲,张鹏,田广东,邢小翠,邹连慧.  吉林大学学报(工学版). 2018(05)
[3]考虑技能水平的多技能资源约束项目调度[J]. 任逸飞,陆志强,刘欣仪,张猛.  浙江大学学报(工学版). 2017(05)
[4]柔性资源约束下的项目调度问题双目标优化[J]. 谢芳,徐哲,于静.  系统工程理论与实践. 2016(03)
[5]基于交叉亲和度评价的多种群遗传算法[J]. 王东,归伟夏.  广西大学学报(自然科学版). 2015(06)
[6]柔性资源约束项目调度问题的启发式求解方法[J]. 贾艳,王致民,张跃刚.  计算机集成制造系统. 2015(07)
[7]多技能资源约束项目调度问题的改进算法[J]. 张猛,陆志强.  计算机集成制造系统. 2016(03)
[8]多目标模糊柔性车间调度中的多种群遗传算法[J]. 刘爱军,杨育,邢青松,陆惠,张煜东.  计算机集成制造系统. 2011(09)



本文编号：2997895