Title :
A modified genetic algorithm for DAG scheduling in grid systems
Author :
Zhu, Beibei ; Qiu, Hongze
Author_Institution :
Dept. of Comput. Sci. & Technol., Shandong Univ., Jinan, China
Abstract :
Distributed systems play a vital role in the improvement of high performance computing. Of primary concern when analyzing these systems is DAG scheduling. The problem of DAG scheduling can be stated as scheduling and mapping of the precedence-constrained task graph to processors so that the completion time can be minimized. It is known to be a NP-complete problem. Several studies have demonstrated that genetic algorithm based on the principles of evolution perform better than others generally. In this paper, we will propose an modified genetic algorithm by improving genetic operators and experimental studies show that the modified genetic algorithm converge quickly and can get optimal solution.
Keywords :
computational complexity; directed graphs; genetic algorithms; grid computing; scheduling; DAG scheduling; NP-complete problem; directed acyclic task graph; distributed systems; genetic operators; grid systems; modified genetic algorithm; precedence-constrained task graph; Biological cells; Program processors; DAG scheduling; genetic algorithm; grid;
Conference_Titel :
Software Engineering and Service Science (ICSESS), 2012 IEEE 3rd International Conference on
Conference_Location :
Beijing
Print_ISBN :
978-1-4673-2007-8
DOI :
10.1109/ICSESS.2012.6269505