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