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

doi:10.12005/orms.2017.##

运筹与管理 ›› 2017, Vol. 26 ›› Issue (8): 193-199.DOI: 10.12005/orms.2017.##

• 管理科学 • 上一篇

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

姚丽莎¹, 王占凤², 程家兴¹

1.安徽新华学院信息工程学院,安徽合肥 230088;
2.巢湖学院计算机与信息工程学院,安徽合肥 238000

收稿日期:2016-05-08 出版日期:2017-08-25
作者简介:姚丽莎(1986-),女,安徽合肥人,讲师,研究方向:智能计算与模式识别;王占凤(1985-),女,安徽合肥人,讲师,研究方向:模糊数学与数据处理;程家兴(1946-),男,安徽合肥人,博士,博士生导师,研究方向:模糊数学、智能计算。
基金资助:
安徽省高校自然科学重点研究项目,指纹IRLRD特征加密技术在手机支付中的研究与应用(KJ2015A309);国家级大学生创新训练计划项目(基于二维码的图书管理系统的设计与实现(201512216007);国家级大学生创新训练计划项目(指纹IRLRD特征加密的移动支付系统(201512216008)

Scheduling in Heterogeneous Multi-coreSystem for Hierarchical Hybrid Local Search Strategy

YAO Li-sha¹, WANG Zhan-feng², CHENG Jia-xing¹

1.Faculty of Information Engineering, Anhui Xinhua University, Hefei 230088, China;
2.Computer and Information Engineering Institute, Chaohu University, Hefei, 238000, China

Received:2016-05-08 Online:2017-08-25

摘要/Abstract

摘要： 针对遗传算法解决异构多核系统的任务调度问题容易产生早熟现象及其局部寻优能力较差的缺点,将局部搜索算法与遗传算法相结合,创新性地提出一种求解异构多核系统的任务调度问题的分层混合局部搜索遗传算法。该算法提出一种新的分层优化策略以产生初始种群,在变异操作中,对部分个体设计3-opt优化变异,对种群中的优秀个体用改进的Lin-Kernighan算法进行优化。仿真实验结果表明,分层混合局部搜索遗传算法求解异构多核系统的任务调度问题时可以高效获得高质量的解。

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

Abstract: 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 genetic algorithm combined,this paper proposesa genetic algorithm for hierarchical hybrid local searchcreatively 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 hierarchical hybrid local search can get high-quality solution efficiently when applied to solve the problem oftasks scheduling for heterogeneous multi-core system.

Key words: genetic algorithm, hierarchical optimization strategy, lin-kernighan algorithm, 3-opt algorithm, heterogeneous multi-core, tasks scheduling

中图分类号:

TP316.4

姚丽莎, 王占凤, 程家兴. 分层混合局部搜索策略异构多核系统调度[J]. 运筹与管理, 2017, 26(8): 193-199.

YAO Li-sha, WANG Zhan-feng, CHENG Jia-xing. Scheduling in Heterogeneous Multi-coreSystem for Hierarchical Hybrid Local Search Strategy[J]. Operations Research and Management Science, 2017, 26(8): 193-199.

参考文献

[1] 姚丽落,王占凤,程家兴.基于人工鱼群遗传算法的异构多核系统任务调度研究[J]. 计算机工程与科学,2014,36(10):1866-1871.
[2] Ibarra O H, Kim C E. Heuristic algorithms for scheduling inde-pendent tasks onnonidentical processor[J]. Journal of the ACM, 1977, 24(2): 280-289.
[3] Olivier Beaumont.Vinent Boudet,Yves Robert. A realistic model and efficientheuristic for scheduling with heterogeneous process-801"8[C]. Proceedings of the16th International Parallel and DistributedProcessing Symposium, 2002. 37.
[4] 王旭涛.基于异构多核处理器系统的任务调度算法研究[D].南京:南京邮电大学,2011.
[5] 袁雪莉,钟明洋.改进遗传算法的并行任务调度[J].计算机工程与应用,2011,47(10):56-59.
[6] 蒋建春.异构多核嵌入式软件关键问题研究[D].重庆:重庆大学,2011.
[7] 钟旭.基于混合遗传算法的异构网格任务调度[D].济南:山东大学,2010.
[8] 姚丽莎,王占凤,程家兴.基于人工鱼群遗传算法的异构多核系统任务调度研究[J].计算机工程与科学,2014,36(10):1866-1871.
[9] Zhang J, Zhan Z, Lin Y, et al. Evolutionary computation meets machine learning: a survey[J]. Computational Intelligence Magazine, IEEE, 2011, 6(4): 68-75.
[10] 徐远超,谭旭,范灵俊等.性能不对称多核处理器负载均衡调度研究[J].计算机工程与科学,2013,35(11):80-86.
[11] Dutot P. Complexity of master-slave tasking on heterogeneoustrees[J]. EuropeanJournal on Operational Research, 2005, 164(3): 690-695.
[12] Fonseca C M, Fleming P J. Genetic algorithms for multi-objective optimization: formulation, discussion and generalization[C]. Genetic algorithms: proceedings of 5thinternational conference,2010. 416-423.
[13] Lin S. Computer solutions to the traveling salesman problem[J]. Bell System Technical Journal(S0005-8580), 1965, 44(10): 2245-2269.
[14] Lin S, Kernighan B W. An effective heuristic algorithm for the traveling salesman problem[J]. Operations Research(S0030-364X), 1973, 21(2): 498-516.
[15] 曾华,崔文,付连宁,吴耀华.Lin-Kernighan算法初始解的启发式构造策略[J].山东大学学报(工学版),2012,42(2):30-35.

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

Scheduling in Heterogeneous Multi-coreSystem for Hierarchical Hybrid Local Search Strategy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘琴, 申海, 黎建强. 基于部件指派的多状态系统可靠度优化研究[J]. 运筹与管理, 2021, 30(9): 25-30.
[2]	郑红星, 段爽, 孙丛. 考虑翻箱的场桥调度和提箱集卡数量的集成优化[J]. 运筹与管理, 2021, 30(9): 48-55.
[3]	闫妍, 张锦, 唐秋宇, 张洪基. 航线联盟下航空货运网络枢纽点选址问题研究[J]. 运筹与管理, 2021, 30(9): 64-72.
[4]	初良勇, 左世萍, 阮志毅. 考虑退货不确定性的多层次多站点逆向物流网络选址优化研究[J]. 运筹与管理, 2021, 30(9): 73-79.
[5]	丁肇炜, 杨建华, 王艾, 王欣. 面向突发事件的安保巡逻选址-路径优化研究[J]. 运筹与管理, 2021, 30(8): 1-6.
[6]	王愚勤, 胡卉, 刘富鑫, 王艳慧, 赵姣, 韩毅. 智能网联下无人车配送路径优化[J]. 运筹与管理, 2021, 30(8): 52-58.
[7]	刘畅, 姚建明. 高铁场景下的无人零售终端补货供应链调度优化研究[J]. 运筹与管理, 2021, 30(7): 9-15.
[8]	李建斌, 梅启煌, 张蕊, 戴宾. 运单体积不确定对货运共享平台定价决策的影响研究[J]. 运筹与管理, 2021, 30(4): 69-75.
[9]	周丽, 杨江龙. 基于遗传算法的多通道密集式移动货架订单拣选研究[J]. 运筹与管理, 2021, 30(2): 84-90.
[10]	刘国山, 王敏, 张转霞. 基于时间窗延迟的资源约束项目调度双层优化研究[J]. 运筹与管理, 2021, 30(12): 6-12.
[11]	吕海利, 孙佳祺, 吴姝. 考虑机器能耗的绿色作业车间调度问题[J]. 运筹与管理, 2021, 30(12): 220-225.
[12]	徐小峰, 孙玉萍, 林姿汝. 缺货情形下轴辐式库存的纵横向协作调拨[J]. 运筹与管理, 2021, 30(10): 113-119.
[13]	黄学文, 孙榕, 艾亚晴. 招标采购中的采购物品打包模型及其优化算法[J]. 运筹与管理, 2020, 29(9): 18-26.
[14]	张庆, 余淼. 基于两阶段混合整数规划模型的洪涝灾害应急管理研究[J]. 运筹与管理, 2020, 29(9): 62-69.
[15]	周愉峰, 陈娜, 李志, 龚英. 考虑设施中断情景的震后救援初期应急物流网络优化设计[J]. 运筹与管理, 2020, 29(6): 107-112.