分层混合局部搜索策略异构多核系统调度  

Scheduling in Heterogeneous Multi-core System for Hierarchical Hybrid Local Search Strategy

作　　者：姚丽莎[1] 王占凤[2] 程家兴[1] 

机构地区：[1]安徽新华学院信息工程学院,安徽合肥230088 [2]巢湖学院计算机与信息工程学院,安徽合肥238000

出　　处：《运筹与管理》2017年第8期193-199,共7页Operations Research and Management Science

基　　金：安徽省高校自然科学重点研究项目;指纹IRLRD特征加密技术在手机支付中的研究与应用(KJ2015A309);国家级大学生创新训练计划项目(基于二维码的图书管理系统的设计与实现(201512216007);国家级大学生创新训练计划项目(指纹IRLRD特征加密的移动支付系统(201512216008)

摘　　要：针对遗传算法解决异构多核系统的任务调度问题容易产生早熟现象及其局部寻优能力较差的缺点,将局部搜索算法与遗传算法相结合,创新性地提出一种求解异构多核系统的任务调度问题的分层混合局部搜索遗传算法。该算法提出一种新的分层优化策略以产生初始种群,在变异操作中,对部分个体设计3-opt优化变异,对种群中的优秀个体用改进的Lin-Kernighan算法进行优化。仿真实验结果表明,分层混合局部搜索遗传算法求解异构多核系统的任务调度问题时可以高效获得高质量的解。Genetic algorithm is prone to premature and weak in local optimisation capabilityto solve the problem oftasks scheduling for heterogeneous multi-core system. In light of this, with the local search algorithm and genet- ic algorithm combined, this paper proposesa genetic algorithm for hierarchical hybrid local searchereatively to solve the problemof tasks scheduling forheterogeneous multi-core system. In this algorithm, the initial population is generated by the new hierarchical optimization strategy, 3-opt algorithm will be applied to some individuals for optimisation and variation, the improved Lin-Kernighan algorithm will be employed for optimization for those excellent individuals in the population. The simulation results show that the proposed genetic algorithm for hierar- chical hybrid local search can get high-quality solution efficiently when applied to solve the problem oftasks scheduling for heterogeneous multi-core system.

关 键 词：遗传算法 分层优化策略 Lin-Kernighan算法 3-opt算法 异构多核 任务调度 

分 类 号：TP316.4[自动化与计算机技术—计算机软件与理论]