Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm

Electronics

卷:10

Yujian Zhang¹  Fei Tong¹  Chuanyou Li¹  Yuwei Xu¹ 

[1] Key Laboratory of Computer Network and Information Integration, Southeast University, Nanjing 211189, China;

关键词: energy efficiency;    heterogeneous computing system;    workflow scheduling;    bi-objective;    memetic algorithm;   

DOI  :  10.3390/electronics10020209

来源: DOAJ

【 摘 要 】

Due to the high power bills and the negative environmental impacts, workflow scheduling with energy consciousness has been an emerging need for modern heterogeneous computing systems. A number of approaches have been developed to find suboptimal schedules through heuristics by means of slack reclamation or trade-off functions. In this article, a memetic algorithm for energy-efficient workflow scheduling is proposed for a quality-guaranteed solution with high runtime efficiency. The basic idea is to retain the advantages of population-based, heuristic-based, and local search methods while avoiding their drawbacks. Specifically, the proposed algorithm incorporates an improved non-dominated sorting genetic algorithm (NSGA-II) to explore potential task priorities and allocates tasks to processors by an earliest finish time (EFT)-based heuristic to provide a time-efficient candidate. Then, a local search method integrated with a pruning technique is launched with a low possibility, to exploit the feasible region indicated by the candidate schedule. Experimental results on workflows from both randomly-generated and real-world applications suggest that the proposed algorithm achieves bi-objective optimization, improving makespan, and energy saving by 4.9% and 24.3%, respectively. Meanwhile, it has a low time complexity compared to the similar work HECS.

【 授权许可】

Unknown