混合差分进化算法求解柔性作业车间调度问题.pdf

第38卷第6期佳木斯大学学报(自然科学版)Vol.38No.62020年11月JournalofJiamusiUniversity(NaturalScienceEdition)Nov.2020文章编号：1008-1402(2020)06-0101-06混合差分进化算法求解柔性作业车间调度问题1宁桂英S曹敦虔2(1.柳州工学院数理教学部，广西柳州545616;2.广西民族大学理学院，广西南宁530006)摘要：针对柔性作业车间调度问题(FlexibleJobShopSchedulingProblem，町SP)的求解特点，提出了一种混合差分进化算法，该方法以最小化最大完工时间为目标，采用双向变异策略，以一定的概率采用差分变异和遗传变异，同时在变异过程中采用特殊的解码方式;在交叉的过程中采用改进的随机变位交叉的方式，提高了算法的性能。最后用该算法对经典算例进行了测试并与已有算法进行了比较，结果表明，提出的方法具有很好的稳定性和鲁棒性，是求解町SP的一种有效方法。关键词：差分进化；遗传算法；柔性作业车间调度；NP-难；最大完工时间中图分类号：TH165：TP18文献标识码：A0引言干双粒子群算法求解柔性作业车间调度问题［4］;吕聪等提出柔性车间调度问题的协作混合帝国算柔性作业车间调度问题(FlexibleJob-shop法［5］;李帆等提出改进蝙蝠算法柔性作业车间调SchedulingProblem,FJSP)是由Brucker［1］在1990度问题研究［6］;王芳等提出求解柔性流水车间调年首次提出的，该问题是传统作业车间调度问题度问题的高效分布估算算法［7］o在以上的研究中(Job-shopSchedulingProblem,FSP)的延伸和拓可以发现，学者们开始将用于研究连续性问题的智展。与传统作业车间调度问题不同的是，在柔性作能算法设计为研究离散型的调度问题，主要考虑对业车间调度问题中，每个工件有多道工序,每道工算法的改进和与其他算法的混合以提高算法的局序可以选择加工的机床有多台，不同机床加工工序部搜索能力，防止算法限于局部极优。所需要的时间不同，所以柔性作业车间调度问题可针对柔性车间调度问题的特点,提出了混合差以看成是多工件多工序排列在多机器上加工的高分进化算法(HybridDifferentialEvolutionAlgo­维规划问题,是一种复杂的NP-hard问题［2］。该rithm,简称HDEA)求解柔性作业车间调度问题。问题更符合企业生产中的实际问题调度的需要，因首先对差分进化算法进行特殊的编码和解码，以适此，对该问题的研究具有重要的理论意义和应用价合求解离散型问题;然后在变异的过程中，采用双值。FJSP问题自提出以来,一直是国内外学者们向变异策略，利用概率值，将遗传算法的变异和差所关注的热点问题，迄今为止,对该问题已有大量分进化算法的变异有机结合，增强了种群的多样的研究，在众多的研究中，经典的具有代表性的算性，防止限于局部极值，利用差分进化算法的变异法有分支界定算法，但该方法的复杂度会随着问题策略，将全局搜索能力和局部搜索能力进行有效平规模的增大而成指数级增长，因此不能满足实际问衡，提高了收敛速度和精度，同时根据问题的特点,题的需要。近年来，随着智能算法的兴起,越来越采用遗传算法的改进交叉方式,即采用随机变位交多的学者开始关注用智能算法解决此类问题,并取叉的方式，在保证生成的新个体是有效解的同时也得了一定的成果,如张超勇等提出了柔性作业车间增加了种群的多样性。对14个经典测试算例和2调度问题的两级遗传算法［3］;戴月明等提出了骨个实际案例进行了仿真,仿真结果表明,提出的算①收稿日期：2020-09-29基金项目：国家自然科学基金(61165015)；广西高校科学技术研究项目(KY2015YB521)；广西高校中青年教师科研基础能力提升项目(2019KY1098)；广西科技大学鹿山学院教学改革重点项目(2018JGZ004)。作者简介：宁桂英(1979-),女，湖北武汉人，副教授，硕士，研究方向：进化计算及应用。1022020X1(5)k=11SMCrlk(6)1);(2)1.1;(3);(4)MN;(5)PiiOvi,;(6)jTi]kijCMkSl]kijkkCij2kC,1,ijkXyk0,1.2FJSPNMpt,(makespan)2.1DE/rand/1/binDE/best/1/bin(1),t+1)t)+(1)X,(t)+(2)(()())best(7)FXp1,jt-Xp2jtAe[0,1]A=T-t,t(3),TF=1(4)(5)A10,A=1DE/rand/1/binf=min{max(CJ}(1)A=0DE/best/1/bin,1WiWNXM1,2;:(1,2,=,...pjCS+iN:[0,1