An Enhanced Genetic Algorithm for Task Scheduling in Heterogeneous Systems

Generally, jobs are divided into smaller portions, in parallel and according to distributed processing, and each portion is called a task. Each task can execute dependently or independently. When introducing heterogeneous systems, it is desirable that tasks can run on these systems. Since it is advantageous that tasks running on heterogeneous systems are completed faster, the optimization of task scheduling is of great importance. Actually, task scheduling problems in heterogeneous systems are NP-hard and it is a crucial issue. In such problems, Directed Acyclic Graphs (DAGs) can be used as task graphs to be scheduled on heterogeneous systems. The proposed method presents a genetic algorithm with new operators and final scheduler to be scheduled on heterogeneous systems. The practicality and convergence of the algorithm are proved by Markov’s chain theory. The findings reveal that the currently proposed algorithm is more efficient in comparison to previously presented ones and also has a better make span. Moreover, it is concluded that the Enhanced Genetic Algorithm (EGA) achieves the solution faster in early generations.

Keywords:

Genetic Algorithm , Distributed Processing , Task Scheduling