DRSCRO: A Metaheuristic Algorithm for Task Scheduling on Heterogeneous Systems
Joint Authors
Shao, Zhiqing
Jiang, Yuyi
Guo, Yi
Zhang, Huanhuan
Niu, Kun
Source
Mathematical Problems in Engineering
Issue
Vol. 2015, Issue 2015 (31 Dec. 2015), pp.1-20, 20 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2015-12-28
Country of Publication
Egypt
No. of Pages
20
Main Subjects
Abstract EN
An efficient DAG task scheduling is crucial for leveraging the performance potential of a heterogeneous system and finding a schedule that minimizes the makespan (i.e., the total execution time) of a DAG is known to be NP-complete.
A recently proposed metaheuristic method, Chemical Reaction Optimization (CRO), demonstrates its capability for solving NP-complete optimization problems.
This paper develops an algorithm named Double-Reaction-Structured Chemical Reaction Optimization (DRSCRO) for DAG scheduling on heterogeneous systems, which modifies the conventional CRO framework and incorporates CRO with the variable neighborhood search (VNS) method.
DRSCRO has two reaction phases for super molecule selection and global optimization, respectively.
In the molecule selection phase, the CRO as a metaheuristic algorithm is adopted to obtain a super molecule for accelerating convergence.
For promoting the intensification capability, in the global optimization phase, the VNS algorithm with a new processor selection model is used as the initialization under the consideration of scheduling order and processor assignment, and the load balance neighborhood structure of VNS is also utilized in the ineffective reaction operator.
The experimental results verify the effectiveness and efficiency of DRSCRO in terms of makespan and convergence rate.
American Psychological Association (APA)
Jiang, Yuyi& Shao, Zhiqing& Guo, Yi& Zhang, Huanhuan& Niu, Kun. 2015. DRSCRO: A Metaheuristic Algorithm for Task Scheduling on Heterogeneous Systems. Mathematical Problems in Engineering،Vol. 2015, no. 2015, pp.1-20.
https://search.emarefa.net/detail/BIM-1073733
Modern Language Association (MLA)
Jiang, Yuyi…[et al.]. DRSCRO: A Metaheuristic Algorithm for Task Scheduling on Heterogeneous Systems. Mathematical Problems in Engineering No. 2015 (2015), pp.1-20.
https://search.emarefa.net/detail/BIM-1073733
American Medical Association (AMA)
Jiang, Yuyi& Shao, Zhiqing& Guo, Yi& Zhang, Huanhuan& Niu, Kun. DRSCRO: A Metaheuristic Algorithm for Task Scheduling on Heterogeneous Systems. Mathematical Problems in Engineering. 2015. Vol. 2015, no. 2015, pp.1-20.
https://search.emarefa.net/detail/BIM-1073733
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1073733