启发式狼群算法求解不相关并行机调度问题

Heuristic Wolf Pack Algorithm Solving Unrelated Parallel Machine Scheduling Problems

针对以最小化最大完工时间为目标的不相关并行机调度问题,提出一种启发式狼群算法(HWPA)进行求解。首先,考虑到经典狼群算法的搜索效率以及计算资源占用率等问题,在生成初始种群时,建立一种启发式算法,选择工件分配方案的同时通过最大完工时间设置相应邻域搜索机制,与随机生成的初始种群同时进行优化,以提高算法效率;其次,根据问题特点设计算法中智能行为机制,将探狼游走时的固定步长替换为随机步长,在召唤与围攻机制中采用差异化的局部保优策略,跳出局部最优解,提高算法搜索效率;最后,运用该算法进行仿真优化实验,结果表明,在较少的迭代次数内,该算法相较于GA、FOA平均改进107.35%、113.62%,证明了该算法的有效性和优越性。

A Heuristic Wolf Pack Algorithm(HWPA)is proposed to solve the unrelated parallel machine scheduling problem aiming at minimizing the maximum completion time.Firstly,considering the search efficiency of the WPA and the computational resource usage,a new heuristic algorithm is established to generate the initial population.In order to improve the efficiency of the algorithm,the makespan was used to set the corresponding local search mechanism,which was optimized at the same time with the randomly generated initial population;Secondly,the intelligent rules are designed according to the characteristics of the problem and the walking around mechanism in the algorithm is adjusted to replace the fixed step size with random step size.Differentiated local optimal strategies are adopted in the summoning and besieging mechanism to jump out of the local optimal solution and improve the search efficiency of the algorithm;Finally,the new algorithm is used in simulation and optimization experiments.Experimental results show that the algorithm is 107.35%better than GA and 113.62%better than FOA in less iterations.The effectiveness and superiority of the algorithm are proved.