基于剪枝优化的多变邻域节能调度算法

doi:10.3969/j.issn.0255-8297.2022.02.016

应用科学学报 ›› 2022, Vol. 40 ›› Issue (2): 349-360.doi: 10.3969/j.issn.0255-8297.2022.02.016

• 计算机科学与应用 • 上一篇

基于剪枝优化的多变邻域节能调度算法

仇宾, 孙曼曼, 崔素丽

河北师范大学民族学院, 河北石家庄 050091

收稿日期:2021-06-10 发布日期:2022-04-01
通信作者: 仇宾，讲师，研究方向为高性能网络计算、云计算任务调度及大数据挖掘。E-mail：daikw84@126.com E-mail:daikw84@126.com
基金资助:
河北省科学发展研究课题（No.20200602007）资助

Energy-Saving Scheduling Algorithm for Multi-Variable Neighborhood Based on Pruning Optimization

QIU Bin, SUN Manman, CUI Suli

Nationalities school, HeBei Normal University, Shijiazhuang 050091, Hebei, China

Received:2021-06-10 Published:2022-04-01

摘要/Abstract

摘要： 为了提高异构计算机系统中任务调度的节能水平，提出了融合剪枝优化的多变邻域节能调度算法。算法构建处理机约束和时间约束两个邻域结构，借助处理机约束邻域减少冗余处理机量，从而降低整体能耗；利用时间约束邻域有效缩减关键路径长度，实现了任务调度对时间的要求。提出了基于时间和能耗的剪枝优化策略，以提高局部寻优效率。通过仿真实验和实际问题求解对比可知，所提算法在不同问题规模、处理机量和通信比下，都取得了较好的节能效果。

关键词: 节能任务调度, 变邻域结构, 处理机约束, 时间约束, 剪枝优化

Abstract: In order to improve the energy-saving level of task scheduling in heterogeneous computer systems, a multi-variable neighborhood energy-saving scheduling algorithm fused with pruning optimization is proposed. Processor constraint and time constraint neighborhood structures are constructed in the algorithm. The number of redundant processors is reduced by constraining the neighborhood of processors, thus lowering the overall energy consumption. Pruning optimization is introduced into the time and energy consumption neighborhood to improve the efficiency of local optimization. Simulation results show that the proposed algorithm achieves good energy-saving effect under different problem scales, processor capacity and communication ratio.

Key words: energy saving task scheduling, variable neighborhood structure, processor constraints, time constraint, pruning optimization

中图分类号:

TP393

仇宾, 孙曼曼, 崔素丽. 基于剪枝优化的多变邻域节能调度算法[J]. 应用科学学报, 2022, 40(2): 349-360.

QIU Bin, SUN Manman, CUI Suli. Energy-Saving Scheduling Algorithm for Multi-Variable Neighborhood Based on Pruning Optimization[J]. Journal of Applied Sciences, 2022, 40(2): 349-360.

参考文献

[1] Fu H H, Liao J F, Yang J Z, et al. The Sunway TaihuLight supercomputer:system and applications[J]. Science China Information Sciences, 2016, 59(7):1-16.
[2] Rizvandi N B, Taheri J, Zomaya A Y. Some observations on optimal frequency selection in DVFS-based energy consumption minimization[J]. Journal of Parallel and Distributed Computing, 2011, 71(8):1154-1164.
[3] Zheng W, Huang S H. Deadline constrained energy-efficient scheduling for workflows in clouds[C]//2014 International Conference on Advanced Cloud and Big Data, 2014:69-76.
[4] Huang Q J, Su S, Li J, et al. Enhanced energy-efficient scheduling for parallel applications in cloud[C]//2012 IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 2012:781-786.
[5] Pineda A A S, Peroce J, Huacuja H, et al. An iterative local search algorithm for scheduling precedence-constrained applications on heterogeneous machines[C]//6th Multidisciplinary International Conference on Scheduling:Theory and Applications (MISTA 2013), 2013:27-29.
[6] Xu Y M, Li K L, He L G, et al. A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(12):3208-3222.
[7] Keshanchi B, Navimipour N J. Priority-based task scheduling in the cloud systems using a memetic algorithm[J]. Journal of Circuits, Systems and Computers, 2016, 25(10):1650119.
[8] 李智勇,陈少淼,杨波,等.异构云环境多目标Memetic优化任务调度方法[J].计算机学报, 2016, 39(2):377-390. Li Z Y, Chen S M, Yang B, et al. Multi-objective memetic algorithm for task scheduling on heterogeneous cloud[J]. Chinese Journal of Computers, 2016, 39(2):377-390.(in Chinese)
[9] Gerards M E T, Hurink J L, Kuper J. On the interplay between global DVFS and scheduling tasks with precedence constraints[J]. IEEE Transactions on Computers, 2015, 64(6):1742-1754.
[10] 肖鹏,胡志刚,屈喜龙.面向数据密集型工作流的能耗感知调度策略[J].通信学报, 2015(1):149-158. Xiao P, Hu Z G, Qu X L. Energy-aware scheduling policy for data-intensive workflow[J]. Journal on Communications, 2015(1):149-158.(in Chinese)
[11] Zhou P J, Zheng W. An efficient biobjective heuristic for scheduling workflows on heterogeneous DVS-enabled processors[J]. Journal of Applied Mathematics, 2014, 2014:370917.
[12] Li K Q. Scheduling precedence constrained tasks with reduced processor energy on multiprocessor computers[J]. IEEE Transactions on Computers, 2012, 61(12):1668-1681.
[13] Mladenovi N, Hansen P. Variable neighborhood search[J]. Computers&Operations Research, 1997, 24(11):1097-1100.
[14] Zhao F Q, Qin S, Zhang Y, et al. A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2019, 126:321-339.
[15] Zhao F Q, Liu Y, Zhang Y, et al. A hybrid harmony search algorithm with efficient job sequence scheme and variable neighborhood search for the permutation flow shop scheduling problems[J]. Engineering Applications of Artificial Intelligence, 2017, 65:178-199.
[16] Kalayci C B, Can K Y. An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery[J]. Expert Systems with Applications, 2016, 66:163-175.
[17] Marinakis Y, Migdalas A, Sifaleras A. A hybrid particle swarm optimization-variable neighborhood search algorithm for constrained shortest path problems[J]. European Journal of Operational Research, 2017, 261(3):819-834.
[18] Arabnejad H, Barbosa J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3):682-694.
[19] Topcuoglu H, Hariri S, Wu M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3):260-274.
[20] Zhang Y J, Wang Y, Tang X Y, et al. Energy-efficient task scheduling on heterogeneous computing systems by linear programming[J]. Concurrency and Computation:Practice and Experience, 2018, 30(19):e4731.
[21] Khorsand R, Ramezanpour M. An energy-efficient task-scheduling algorithm based on a multi-criteria decision-making method in cloud computing[J].International Journal of Communication Systems, 2020, 33(9):4379-4396.
[22] Su S, Huang Q J, Li J, et al. Enhanced energy-efficient scheduling for parallel tasks using partial optimal slacking[J]. The Computer Journal, 2014, 58(2):246-257.

基于剪枝优化的多变邻域节能调度算法

Energy-Saving Scheduling Algorithm for Multi-Variable Neighborhood Based on Pruning Optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价