摘要
针对作业车间调度问题(job-shop scheduling problem, JSP)中存在的求解复杂程度高、动态性强等难题,提出基于差分特性的量子粒子群优化算法。量子粒子群算法引入量子机制克服了粒子群算法在全局收敛性上的不足,并采用差分进化思想对粒子状态进行更新,借助变异操作增大种群多样性,对早熟粒子进行交叉选择操作,防止个体收敛到局部极值,进一步采用多邻域搜索方法以提高算法的寻优速度。对FT、LA两类JSP算例进行求解,将所提算法与离散粒子群算法、遗传算法以及细菌觅食算法进行实验对比。结果表明,4种算法收敛到FL10算例理论最优解的时间分别为127、134.8、143.5以及141.3 s;而LA36算例的理论最优解为1 268,4种算法所得结果分别为1 294.6、1 457.4、1 374.3以及1 398,且所提算法收敛时间最短。仿真结果表明所提算法能以较快的收敛速度得到最优解,相比于其他算法,寻优速度和精度都有了明显提升。
Aiming at the problems of high complexity and strong dynamics in job-shop scheduling problem(JSP),a quantum particle swarm optimization algorithm based on differential characteristics was proposed.Quantum mechanism was introduced into quantum particle swarm optimization algorithm to overcome the shortcomings of particle swarm optimization algorithm in global convergence,and differential evolution was used to update the particle state,mutation operation was used to increase the population diversity,cross selection operation was carried out on premature particles to prevent individuals from converging to local extreme values,and multi neighborhood search method was further used to improve the optimization speed of the algorithm.Two JSP examples of FT and LA were solved,and the proposed algorithm was compared with discrete particle swarm optimization,genetic algorithm and bacterial foraging algorithm.The results show that the time for the four algorithms to converge to the theoretical optimal solution of the FL10 example is 127,134.8,143.5 and 141.3 s respectively.While the theoretical optimal solution of the LA36 example is 1268,the results obtained by the four algorithms are 1294.6,1457.4,1374.3 and 1398,and the proposed algorithm has the shortest convergence time.The simulation results show that the proposed algorithm can obtain the optimal solution with a faster convergence speed.Compared with other algorithms,the optimization speed and accuracy are significantly improved.
作者
黄宇
顾智勇
张中印
王东风
HUANG Yu;GU Zhi-yong;ZHANG Zhong-yin;WANG Dong-feng(Department of Automation,North China Electric Power University,Baoding 071003,China)
出处
《科学技术与工程》
北大核心
2022年第29期12848-12854,共7页
Science Technology and Engineering
基金
中央高校基本科研业务费专项资金项目(2021MS089)。
关键词
量子粒子群优化算法
差分进化
多邻域搜索
作业车间调度
quantum particle swarm optimization algorithm
differential evolution
multi neighborhood search
job-shop scheduling
