自适应混合粒子群算法求解置换流水车间调度问题  

Self-adaptive hybrid particle swarm optimization forpermutation flow shop scheduling problem

作　　者：谢美华 李艳武 葛棚丹 Xie Meihua;Li Yanwu;Ge Pengdan(College of Electronic&Information Engineering,Chongqing Three Gorges University,Chongqing 404020,China)

机构地区：[1]重庆三峡学院电子与信息工程学院,重庆404020

出　　处：《计算机应用研究》2023年第11期3241-3246,3253,共7页Application Research of Computers

基　　金：重庆市教育委员会科学技术研究项目(KJQN202001224)。

摘　　要：为更有效地解决以最大完工时间最小化为目标的置换流水车间调度问题,提出了一种自适应混合粒子群算法(SHPSO)。该算法结合Q学习设计了参数自适应更新策略,以平衡算法的探索和开发;同时引入粒子停滞判断方法,使用平局决胜机制和Taillard加速算法改进基于迭代贪婪的局部搜索策略,对全局极值进行局部搜索,帮助粒子跳出局部最优。实验结果表明,对比其他四种改进PSO算法,SHPSO算法取得的平均相对百分偏差(RPDavg)至少下降了83.2%,在求解质量上具有明显优势。To solve the permutation flow shop scheduling problem with the objective to minimize makespan more effectively,this paper proposed a self-adaptive hybrid particle swarm optimization(SHPSO)algorithm.The algorithm combined Q-learning to design a parameter adaptive update strategy to balance the exploration and development of the algorithm.It also introduced a particle stagnation judgment method,used the tie-breaking mechanism and Taillard acceleration algorithm to improve the local search strategy based on iterated greedy to perform local search on global extremes and help particles jump out of the local optimum.The experimental results show that the average relative percentage deviation(RPDavg)achieved by the SHPSO algorithm is at least 83.2%lower than that of the other four improved PSO algorithms,providing a significant advantage in solution quality.

关 键 词：置换流水车间调度 粒子群算法 Q学习 局部搜索策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]