改进粒子群算法的不相关并行批处理调度优化  

Improved Particle Swarm Algorithm of Unrelated Parallel Batch Scheduling Optimization

作　　者：杜利珍[1] 叶涛 王宇豪 张亚军 宣自风 Du Lizhen;Ye Tao;Wang Yuhao;Zhang Yajun;Xuan Zifeng(School of Mechanical Engineering and Automation,Wuhan Textile University,Wuhan 430200,China)

机构地区：[1]武汉纺织大学机械工程及自动化学院,湖北武汉430200

出　　处：《系统仿真学报》2023年第7期1549-1561,共13页Journal of System Simulation

基　　金：国家重点研发计划(2019YFB1706300)。

摘　　要：针对粒子群优化(particle swarm optimization,PSO)算法在处理不相关并行批处理调度问题中存在的种群多样性丢失、易陷入局部最优等问题,提出了一种改进PSO的调度优化算法,用于最小化最大完工时间求解。采用基于工件序列的实数编码方式进行编码操作;基于该问题的混合整数规划模型,设计了一种J_B局部搜索的新策略;将模拟退火算法的Metropolis准则引入种群粒子的个体极值搜索。通过随机生成的小型、中型和大型实例对该算法的性能进行了测试,并与针对该调度问题提出的元启发式算法和其他3种元启发式算法进行了比较。实验结果和统计测试表明,该算法的性能明显优于对比算法。To address the problems of population diversity loss and the tendency to fall into local optimality in the PSO(particle swarm optimization)algorithm in dealing with unrelated parallel batch scheduling problems,an improved scheduling optimization algorithm for PSO is proposed for minimizing the maximum completion time solution.A real number encoding based on the sequence of artifacts is used for the encoding operation.A new strategy based on J_B local search is designed based on the mixed integer programming model of the problem.The Metropolis criterion of the simulated annealing algorithm isintroduced into the individual extreme value search of the population particles.The performance of the algorithm is tested with randomly generated small,medium and large instances and compared with proposed metaheuristic for this scheduling problem and three other metaheuristics.The experimental results and statistical tests shows that the algorithm performs significantly better than the comparison algorithm.

关 键 词：不相关并行 批调度 局部搜索策略 粒子群算法 模拟退火 

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