求解异构并行机调度问题的混合烟花算法

发布时间：2022-01-02 19:07

　　以加工时间可控的机器调度为研究对象,考虑一类以优化能耗和延迟成本为目标的异构并行机调度问题。对该调度问题进行描述,并构建混合整数线性规划模型;提出混合烟花求解算法（HFWA）,设计特定的编解码方法以表示问题的解,并融入反向学习初始化方法以提升初始解的质量;构建基于变邻域搜索算法的局部优化流程用以强化基本算法的寻优性能。仿真实验验证了该算法的可行性和有效性。 

【文章来源】：计算机应用与软件. 2020,37(06)北大核心

【文章页数】：9 页

【部分图文】：

基于轮盘赌规则的加工速度选择

变域搜索算法通过系统地改变当前解以拓展算法的搜索范围,进而获得待优化问题的局部最优解;同时,基于此局部最优解,再次系统地进行解空间的拓展,力求获得另一局部最优解。图3为变邻域搜索算法的示意图。邻域结构设计构成了变邻域搜索算法的一项核心内容,对于当前研究的PMS-CPT问题,本文采用交换和翻转两种邻域结构实现从当前解到新解的变换,具体描述如下:

图4所示的邻域结构示意图清晰地说明了以上两种变异算子。当前编码方法中,编码第一层用于各个机器的加工任务序列,编码第二层用于确定各任务在机器上的加工速度。因此,以上邻域变换能够对改善的解产生扰动,探索其周围的解。由编解码方法可知,编码第一层用于各个机器的加工任务序列,编码第二层用于确定各任务在机器上的加工速度。因此,以上邻域变换能够对当前解产生扰动,从而探索当前解附近的其他解。


本文编号：3564722