An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems

摘要

One of the important problems in heterogeneous computing systems is task scheduling. The task scheduling problem intends to assigns tasks to a number of processors in a manner that will optimize the overall performance of the system, i.e. minimizing execution time or maximizing parallelization in assigning the tasks to the processors. The task scheduling problem is an NP-complete and this is why the algorithms applied to this problem are heuristic or meta-heuristic by which we could reach a relatively optimal solution. This paper presents a genetic-based algorithm as a meta-heuristic method to address static task scheduling for processors in heterogeneous computing systems. The algorithm improves the performance of genetic algorithm through significant changes in its genetic functions and introduction of new operators that guarantee sample variety and consistent coverage of the whole space. Moreover, the random initial population has been replaced with some initial populations with relatively optimized solutions to lower repetitions in the genetic algorithm. The results of running this algorithm on the graphs of real-world applications and random graphs in heterogeneous computing systems with a wide range of characteristics, indicated significant improvements of efficiency of the proposed algorithm compared with other task scheduling algorithms.