双档案粒子群算法求解柔性作业车间调度问题  

Double Archive Particle Swarm Optimization Solving Flexible Job-Shop Scheduling Problem

作　　者：张宇嘉 宋威 ZHANG Yujia;SONG Wei(School of Artificial Intelligence and Computer Science,Jiangnan University,Wuxi,Jiangsu 214122,China)

机构地区：[1]江南大学人工智能与计算机学院,江苏无锡214122

出　　处：《计算机工程与应用》2023年第11期294-301,共8页Computer Engineering and Applications

基　　金：国家自然科学基金(61673193,62076110);中国博士后科学基金(2017M621625);江苏省自然科学基金(BK20181341)。

摘　　要：针对最小化完工时间的柔性作业车间调度问题(FJSP),提出了双档案粒子群算法(DAPSO)。构建精英档案和进步档案分别存储具有较好适应值的精英粒子的个体历史最优位置(Pbest)和进步较快粒子的位置。利用精英档案中的粒子计算解可信度,并根据解可信度来判断当前群体所处的进化状态,粒子根据进化状态调整向两个档案中学习的力度以达到收敛性与多样性的平衡。在Kacem的5个测试问题和MK系列10个测试问题开展了广泛实验,通过与其他算法按照最小完工时间、平均完工时间进行了比较,证明了DAPSO在求解FJSP问题时的有效性。This paper proposes a particle swarm optimization based on credibility of solution and double archive to minimize makespan of flexible job-shop scheduling problem(FJSP).Firstly,the elite archive and the optimization archive are constructed to store the individual historical optimal position(Pbest)of the elite particle with better fitness value and the position of the particles that have made rapid progress,respectively.Secondly,it uses the particles in the elite archives to calculate the credibility of solution,and judge the evolutionary state of the current population according to the credibility of solution.The particles adjust the strength of learning from the two archives according to the evolutionary state to achieve a balance between convergence and diversity.Further,extensive experiments are carried out on 5 test problems of Kacem and 10 test problems of MK series,and the comparison with other algorithms according to the minimum completion time and average completion time proves the effectiveness of DAPSO in solving the FJSP problem.

关 键 词：粒子群优化算法 柔性作业车间调度 双档案机制 解可信度 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]