带学习策略的遗传算法求解柔性作业调度问题

《带学习策略的遗传算法求解柔性作业调度问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、带学习策略的遗传算法求解柔性作业调度问题王公堂许化强（山东师范大学物理与电子科学学院，山东济南250014）摘要：多个不同最优染色体之间存在许多共有特征，如果进化过程中能识别这些优秀特征并尽可能遗传到后代个体中，则可以改善后代种群质量，加快遗传算法的收敛速度。在分析柔性作业调度问题的基础上，采用共生遗传算法并加入学习策略进行改进，在进化过程中学习父代优秀特征并指导后代的进化。通过实验测试，并与其它文献中的结果进行比较，表明改进算法在解的质量上有较好的效果。关键词：作业调度；共生遗传算法；学习策略；柔性中图分类号：TP301Improvedevolutionary

2、algorithmwithlearningstrategyfortheflexiblejob-shopschedulingproblemWANGGong-tangXUXua-qiang(CollegeofPhysicsandElectronics,ShandongNormalUniversity,Jinan250014,China)Abstract:Therearesomecommontraitsbetweendifferentbestchromosomes.Ifthesetraitscanbeidentifiedduringevolutionandbecopi

3、edtotheoffspring,thelaterpopulationwillhaveahighqualityandtheefficiencyofalgorithmwillbeenhanced.Basedontheanalysisofthecharacteristicsoftheflexiblejob-shopproblem,thesymbioticevolutionaryalgorithmwasimprovedandwasaddedwithlearningstrategy.Sooffspringcaninheritbesttraitsofparentgener

4、ationwithhighefficiency.Theimprovedalgorithmistestedoninstancestakenfromtheliteratureandcomparedwiththeirresults.Theresultsshowthattheproposedalgorithmoutperformedinsolutionquality.Keywords:job-shopschedulingproblem;symbioticevolutionaryalgorithm;learningstrategy;flexibility50引言表1一个F

5、JSP的实例2×3Tab.1AnexampleoftheFJSP2×3作业操作加工机器和加工时间M1M2M3J1O1,145-O1,2923O1,3-63J2O2,162-O2,2335传统的作业调度问题中，作业的每一道工序都是预先知道的，而且工序的加工机器和时间也是预先确定好的。而在柔性作业调度问题中，工序的加工机器是不确定的。作业的每一道工序都可以在多个加工机器上加工，而且不同的加工机器所需要的加工时间也不相同。在处理此类问题上，不仅要处理作业之间的调度问题，而且要考虑每一道工序面临可选择机器的问题，使问题更难以解决。针对柔性车间调度问题的特点，本文在Yas

6、uhiroTsujimura[1]等人提出的主从共生遗传算法的基础上进行改进，加入学习策略，在进化过程中发掘并保留种群中的优秀特征，并指导后代的进化，加快收敛速度，提高搜索效率。1带操作柔性的作业调度问题描述具有操作柔性（OF）的柔性车间调度问题（FlexibleJob-ShopSchedulingProblem,FJSP)是指同一个操作（或工序）可以在不同的机器上运行。FJSP假定加工系统中有M台机器和N个作业，每个作业包括一道或多道操作，操作顺序是预先确定的，每道操作可以选择在多台不同的设备上加工，操作的加工时间随加工设备的不同而变化。例如，表1是FJSP的

7、一个例子,共有两个作业，三个加工机器，每道工序可以选择在不同机器上以不同的加工时间加工。调度目标是为每道工序选择最合适的加工设备，以及每台设备上各工序5的最佳加工顺序，使所有作业的流通时间最短。该问题所需满足的约束条件[2]是:1)所有作业在初始时刻都可加工;2)工序在可供选择的若干机器上加工的时间已确定;3)每台加工机器在固定的时间段内只能加工一个作业;4)每个作业在固定时刻只能在一台机器上加工。2共生遗传算法设计柔性车间调度可分成两个子问题，一是为操作选择加工机器，二是类似经典车间调度问题，给作业一个合适的排序，得到最优调度。可将这两个子问题看作是共生机制中

8、的两个不同的物种，进而用