交换突变策略改进萤火虫算法的异构并行机调度  

Improved Firefly Algorithm Based on Mutation Strategy for Unrelated Parallel Machine Scheduling Problem

作　　者：罗冬梅[1] 陈玲清 张瑀鑫 黄兴旺 LUO Dongmei;CHEN Lingqing;ZHANG Yuxin;HUANG Xingwang(School of Computer Engineering,Jimei University,Xiamen 361021,China)

机构地区：[1]集美大学计算机工程学院

出　　处：《集美大学学报（自然科学版）》2023年第2期177-184,共8页Journal of Jimei University：Natural Science

基　　金：国家自然科学基金项目(62006096);福建省自然科学基金项目(2020J01699,2020J05146);福建省中青年教师教育科研项目(JAT190320)。

摘　　要：序列相关设置时间的异构并行机调度问题是个NP(non-deterministic polynomial)问题,在高纬度情况下难以求解。选取任务完工时间为优化目标建立数学模型,提出一种基于交换突变策略改进的萤火虫算法,并应用该算法进行求解,以期在可接受的时间内提供近似最优解的可行方案。实验结果表明,所提出的算法在处理异构并行机调度问题时具有较突出的全局搜索优势,收敛速度较快,搜索精度高,测算了36个算例,其中的28个取得最优平均解,并且较萤火虫算法、模拟退火算法和遗传算法分别减少了11.12%、7.36%和1.43%的平均任务完工时间。The unrelated parallel machines scheduling problem with sequence dependent setup times has been applied in many fields.The schediling problem of unrelated parallel machines considering the sequence-dependent setup time is an NP(non-deterministic polynomial)problem,which is difficult to solve in high-dimensional cases.In this paper,the maximum completion time is selected as the optimization objective to establish a mathematical model,and an improved firefly algorithm based on swap mutation strategy is proposed,and the algorithm is applied to solve the problem,in order to provide a feasible solution of approximate optimal solution in an acceptable time.The experimental results show that the proposed algorithm has outstanding global search advantages in dealing with unrelated parallel machine scheduling problem with sequence-dependent setup times,with fast convergence speed and high search accuracy.The optimal average solution is obtained in 28 of the 36 cases,and the average makespan is reduced by 11.12%,7.36%and 1.43%respectively compared with firely algorithm(FA),simulated annealing(SA)and genetic algorithm(GA).

关 键 词：异构并行机调度 萤火虫算法 交换突变 任务完工时间 序相关设置时间 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]