A Double-Helix Structure Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems

The task scheduling problem is known to be an NP-complete problem and the heuristic-based optimization approaches have been proposed to obtain suboptimal solutions. But they are not likely to produce consistent results on a wide range of problems. In this paper, by the DNA double-helix structure inspired, a double-helix structure genetic algorithm (DHSGA) for task scheduling on heterogeneous computing systems is proposed. Its basic idea is to exploit the advantages of heuristic-based algorithms while avoiding their drawbacks. According to the data dependencies of a DAG task graph, the heuristic approach is used to control the crossover and mutation operations of GA algorithm in order to change the main chain structure of a chromosome reasonably, thus the DHSGA generates a better task scheduling priority queue. Then imitating the complementary based on a pairing principle, the heuristic HEFT algorithm improves the effectiveness and convergent speed by mapping from the chromosomal chain (task set) to another chromosome chain (processor set). The software simulation results show that the proposed DHSGA significantly improves the makespan on distributed heterogeneous computing systems, over a large set of randomly generated graphs as well as graphs for real-world problems with various characteristics, compared with the list scheduling algorithms. The average makespan reduction is about 10.1%.