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

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

为更有效地解决以最大完工时间最小化为目标的置换流水车间调度问题,提出了一种自适应混合粒子群算法(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.