A hybrid genetic algorithm for tasks scheduling in heterogeneous computing systems

Efficient application scheduling is critical for achieving high performance in Heterogeneous Computing Systems (HCS). Because an application can be partitioned into a group of tasks and represented as a Directed Acyclic Graph (DAG), the problem can be stated as finding a schedule for a DAG to be executed in a HCS so that the schedule length can be minimized. The tasks scheduling problem is NP-hard in general, except in a few simplified situations. In order to obtain optimal or suboptimal solutions, a large number of scheduling heuristics have been presented in the literature. In recent years, genetic algorithm (GA), as a power tool to achieve global optimal, has been successfully used in this field. This paper presents a new hybrid genetic algorithm to solve the scheduling problem in HCS. It uses a direct method to encode a solution into chromosome. Topological sort of DAG is used to repair the offspring in order to avoid yielding illegal or infeasible solutions, and it also guarantee that all feasible solutions can be reached with some probability. In order to remedy the GA's weakness in fine-tuning, this paper uses a greedy strategy to improve the fitness of the individuals in crossover operator, based on Lamarckian theory in the evolution. The simulation results comparing with a typical genetic algorithm and a typical list heuristic, both from the literature, show that this algorithm produces better results in terms of both quality of solution and convergence speed.