文献类型：期刊文献

英文题名：DRSCRO: A Metaheuristic Algorithm for Task Scheduling on Heterogeneous Systems

作者：Jiang, Yuyi[1];Shao, Zhiqing[1];Guo, Yi[1,2];Zhang, Huanhuan[1];Niu, Kun[1]

机构：[1]E China Univ Sci & Technol, Coll Informat Sci & Engn, Shanghai 200237, Peoples R China;[2]Shihezi Univ, Sch Informat Sci & Engn, Shihezi 832003, Peoples R China

年份：2015

卷号：2015

外文期刊名：MATHEMATICAL PROBLEMS IN ENGINEERING

收录：;EI(收录号：20160601902381);WOS:【SCI-EXPANDED(收录号:WOS:000367942500001)】；

基金：This work is financially supported by the National Natural Science Foundation of China (Grant no. 61462073) and the National High Technology Research and Development Program of China (863 Program) (Grant no. 2015AA020107).

语种：英文

外文关键词：Scheduling - Scheduling algorithms - Chemical reactions - Multitasking - Molecules

摘要：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.