混合变邻域和声搜索的独立任务调度问题研究

Hybrid algorithm of harmony search and variable neighborhood search for independent task scheduling

结合和声搜索和变邻域搜索算法的特点,提出混合的和声变邻域搜索算法,并将混合算法用于解决多处理机独立任务调度问题。混合算法采用列表调度方法对和声解进行编码,把和声分量转换为基于优先级的独立任务调度模型,利用变邻域搜索算法对和声解进行局部搜索以提高和声算法的搜索效率和解质量,利用模拟退火算法中的Metropolis准则作为新解接受准则,防止算法陷入局部极值。仿真实验对比结果表明,混合算法在解决独立任务的多处理机调度中具有更强的全局搜索能力和更快的收敛速度,并且能够跳出局部极小获得更高质量的解。

Combining with characteristics of harmony search and variable neighborhood search,a new hybrid algorithm is proposed in this paper.An independent task scheduling of multiprocessors algorithm is designed based on the hybrid algorithm.The hybrid algorithm adopt list scheduling method to code harmony solution and convert harmony vector to priority-based independent task scheduling model,and perform variable neighborhood search on harmony solutions to improve harmony search efficiency and solution quality.In addition,the hybrid algorithm uses the metropolis criterion of simulated annealing algorithm as the new acceptance criteria to escape local minima.The simulation results demonstrate that the proposed algorithm can improve the global search abilities and convergence speed and can escape local minimizer to look for better solutions.