An Efficient Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems Based on TRIZ

An efficient assignment and scheduling of tasks is one of the key elements in effective utilization of heterogeneous multiprocessor systems. The task scheduling problem has been proven to be NP-hard is the reason why we used meta-heuristic methods for finding a suboptimal schedule. In this paper we proposed a new approach using TRIZ (specially 40 inventive principles). The basic idea of this approach is to exploit the advantages of heuristic-based algorithms to reduce space search and the time needed to find good solutions. The proposed 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. The achieved 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. Although the proposed algorithm needs lower repetitions than their genetic counterparts, it needs high frequency of repetition to produce the desired answer. This is a drawback for this algorithm compared to heuristic algorithms such as CPOP and HEFT.

Keywords:

Genetic Algorithms , Task Scheduling , TRIZ , Meta Heuristic