Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm
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 reclama...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-01-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/10/2/209 |
| _version_ | 1797410213405392896 |
|---|---|
| author | Yujian Zhang Fei Tong Chuanyou Li Yuwei Xu |
| author_facet | Yujian Zhang Fei Tong Chuanyou Li Yuwei Xu |
| author_sort | Yujian Zhang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T04:26:38Z |
| format | Article |
| id | doaj.art-3cabef2bdc2248738debadb5927e9c62 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-09T04:26:38Z |
| publishDate | 2021-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-3cabef2bdc2248738debadb5927e9c622023-12-03T13:39:11ZengMDPI AGElectronics2079-92922021-01-0110220910.3390/electronics10020209Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic AlgorithmYujian Zhang0Fei Tong1Chuanyou Li2Yuwei Xu3Key Laboratory of Computer Network and Information Integration, Southeast University, Nanjing 211189, ChinaKey Laboratory of Computer Network and Information Integration, Southeast University, Nanjing 211189, ChinaKey Laboratory of Computer Network and Information Integration, Southeast University, Nanjing 211189, ChinaKey Laboratory of Computer Network and Information Integration, Southeast University, Nanjing 211189, ChinaDue 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.https://www.mdpi.com/2079-9292/10/2/209energy efficiencyheterogeneous computing systemworkflow schedulingbi-objectivememetic algorithm |
| spellingShingle | Yujian Zhang Fei Tong Chuanyou Li Yuwei Xu Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm Electronics energy efficiency heterogeneous computing system workflow scheduling bi-objective memetic algorithm |
| title | Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm |
| title_full | Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm |
| title_fullStr | Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm |
| title_full_unstemmed | Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm |
| title_short | Bi-Objective Workflow Scheduling on Heterogeneous Computing Systems Using a Memetic Algorithm |
| title_sort | bi objective workflow scheduling on heterogeneous computing systems using a memetic algorithm |
| topic | energy efficiency heterogeneous computing system workflow scheduling bi-objective memetic algorithm |
| url | https://www.mdpi.com/2079-9292/10/2/209 |
| work_keys_str_mv | AT yujianzhang biobjectiveworkflowschedulingonheterogeneouscomputingsystemsusingamemeticalgorithm AT feitong biobjectiveworkflowschedulingonheterogeneouscomputingsystemsusingamemeticalgorithm AT chuanyouli biobjectiveworkflowschedulingonheterogeneouscomputingsystemsusingamemeticalgorithm AT yuweixu biobjectiveworkflowschedulingonheterogeneouscomputingsystemsusingamemeticalgorithm |