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.
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
.
DOI: 10.3969/j.issn.0255-8297.2022.02.016
[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.
