交换突变策略改进萤火虫算法的异构并行机调度-《集美大学学报（自然科学版）》

文章信息/Info

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

Author(s):: LUO Dongmei; CHEN Lingqing; ZHANG Yuxin; HUANG Xingwang; (School of Computer Engineering，Jimei University，Xiamen 361021，China)

Keywords:: unrelated parallel machines scheduling; firefly algorithm; swap mutation; makespan; sequence-dependent setup times

摘要:: 具有序相关设置时间的异构并行机调度问题在云计算、边缘计算等领域中都有应用。序列相关设置时间的异构并行机调度问题是个NP（non-deterministic polynomial）问题，在高纬度情况下难以求解。选取任务完工时间为优化目标建立数学模型，提出一种基于交换突变策略改进的萤火虫算法，并应用该算法进行求解，以期在可接受的时间内提供近似最优解的可行方案。实验结果表明，所提出的算法在处理异构并行机调度问题时具有较突出的全局搜索优势，收敛速度较快，搜索精度高，测算了36个算例，其中的 28个取得最优平均解，并且较萤火虫算法、模拟退火算法和遗传算法分别减少了11.12%、7.36%和1.43%的平均任务完工时间。

Abstract:: 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).