混合灰狼优化算法求解柔性作业车间调度问题

《混合灰狼优化算法求解柔性作业车间调度问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第33卷第3期控制与决策Vol.33No.32018年3月ControlandDecisionMar.2018文章编号:1001-0920(2018)03-0503-06DOI:10.13195/j.kzyjc.2017.0124混合灰狼优化算法求解柔性作业车间调度问题姜天华y(鲁东大学交通学院，山东烟台264025)摘要:将灰狼优化算法(GWO)用于柔性作业车间调度问题(FJSP),以优化最大完工时间为目标,提出一种混合灰狼优化算法(HGWO).首先,采用两段式编码方式,建立GWO连续空间与FJSP离散空间的映射关系;其次,设计种群初始化方法,保证算法初始解的质量;然后,嵌入一种变邻域搜

2、索策略,加强算法的局部搜索能力,引入遗传算子,提升算法的全局探索能力;最后,通过实验数据验证HGWO算法在求解FJSP问题方面的有效性.关键词:柔性作业车间调度；最大完工时间；灰狼优化算法；变邻域搜索策略；遗传算法中图分类号:TH165文献标志码:AFlexiblejobshopschedulingproblemwithhybridgreywolfoptimizationalgorithmJIANGTian-huay(SchoolofTransportation，LudongUniversity，Yantai264025，China)Abstract:Greywolfoptimizatio

3、n(GWO)algorithmisappliedtotheflexiblejobshopschedulingproblem(FJSP),andahybridGWO(HGWO)isproposedwiththeobjectiveofminimizingthemakespan.Firstly,atwo-phaseencodingmethodisemployed,andamappingrelationshipissetupbetweenthecontinuousspaceandthediscretespaceofFJSP.Then,apopulationinitializationstrategy

4、isdesignedtoensurethequalityoftheinitialsolutions,andthenavariableneighborhoodsearch(VNS)strategyisembeddedtoenhancethelocalsearchability.Inaddition,geneticoperatorsareintroducedtoimprovetheglobalexplorationcapabilityofthealgorithm.Finally,experimentaldatashowthattheproposedHGWOiseffectiveforsolvin

5、gtheFJSP.Keywords:flexiblejobshopscheduling；makespan；greywolfoptimizationalgorithm；variableneighborhoodsearch；geneticalgorithm0引言传算法,以优化FJSP问题中的3个指标:最大完工时间、机器总负载和瓶颈机器负荷;Liu等[3]提出了一种柔性作业车间调度问题(FJSP)作为经典作业车间调度问题的一种延伸形式,具有更强的应用背景和改进双链量子遗传算法求解具有模糊交货期的柔性更大的求解难度,已被证明是一种具有NP难特性的作业车间调度问题,以优化系统完工时间、总成本组合优化问

6、题[1].与JSP问题相比,FJSP中工件柔性和提前/拖期惩罚;Karthikeyan等[4]提出了一种混合加工路径的特性在减小机器约束的同时,又增加了调离散萤火虫算法求解有限资源约束下的多目标柔性度的灵活性,使其更能贴近于实际生产[2],但是这也作业车间调度问题;Yuan等[5]提出了一种混合差分大大提升了其复杂程度.该问题的求解算法研究已进化算法,以优化柔性作业车间工件的最大完工时间;Li等[6]将遗传算法和禁忌搜索相结合,提出了一成为车间调度领域的热点,目前元启发式算法已成为最流行的方法,它为FJSP问题提供了更多更新的求种混合算法以优化最大完工时间.尽管各种元启发解思路和方法,引起

7、了国内外学者们的广泛关注.式算法在FJSP问题中已得到了广泛的研究,但目前Zhang等[1]针对不同性能指标下柔性作业车间仍没有任何一种算法能够获得所有问题的最优解,因调度问题进行了研究,提出了一种具有双层子代产生此学者们仍在不断积极探索,以获得更丰富且更有效模式的改进遗传算法;Zhang等[2]提出了一种改进遗的方法.收稿日期:2017-02-12；修回日期:2017-04-26.基金项目:山东省自然科学基金项目(ZR