一种基于和声搜索和模拟退火的多处理机任务调度的方法

摘要

本发明是一种基于和声搜索和模拟退火的多处理机任务调度的算法。算法核心将和声搜索和模拟退火算法进行了融合，首先初始化和声算法相关参数、及和声库，然后在和声库中直接对最好的和声解所对应的任务序列执行退火过程，增强了算法的搜索速度。算法中通过保存最优解，充分发挥SA算法的概率突跳特性，摆脱局部极小点，有效的提高了算法性能。并把该改进算法成功的运用到多处理机的任务调度问题中，经过验证，该算法比传统算法具有更好运行效率的调度策略。

主权项

1.一种基于和声搜索和模拟退火的多处理机任务调度的方法，该方法包括以下步骤： (1) 初始化HS相关参数、初始温度T、降温系数t；(2) 初始化和声库（HM），利用微调概率PAR，使HS算法产生新解Xnew更新HM，找出最优解Xopt；（3）以最优解对应的任务序列Sopt作为SA算法的初始解x, 并计算相应的评价函数f(x)的值,评价函数为；；（4）利用模拟退火算法产生新解x’，计算评价函数f（x’）；根据Metropolis准则进行判断△E＝f（x’）－f（x）；如果△E<0 则接受x’作为新解，否则以概率min（1，exp(-△E/ T_k )）接受，如果x’优于和声库中最优解，则更新和声库HM；T_k 为当前的温度；（5）以作为退温函数进行退温，t为迭代次数，为退温系数；（6）重复执行第4步，直到到达最大迭代次数，算法终止。