Title:
Enhanced Genetic Algorithm with Some Heuristic Principles for Task Graph Scheduling
Mohammad Nematpour Shamlou Habib Izadkhah
Department of Computer Science, University of Tabriz, Tabriz, Iran Department of Computer Science, University of Tabriz, Tabriz, Iran
Abstract:
Nowadays, multiprocessor systems are widely used in parallel computing. Considering the optimal use of existing computing systems, scheduling on parallel systems has great importance. The scheduling of task graph onto processors is considered to be the most crucial NP-complete problem, hence in the literature, many attempts were made to find a nearly optimal scheduling using genetic algorithm. The performance of genetic algorithm is largely influenced by its chromosomal representation. The chromosomal structural used in the existing genetic algorithms does not allow them to scan the solution space entirely. Therefore, often, these algorithms cannot produce the appropriate scheduling. For overcome this constraint, this paper presents a new method for constructing chromosomal representation. Our approach, called GAHP, concerning the scheduling problem includes three stages: ranking, clustering and clusters scheduling; where the clusters are scheduled by genetic algorithm. To improve the performance of the proposed GA, it is equipped with three heuristic principles namely reuse idle time, critical path and their combination, aiming to reduce the communication overhead. On standard benchmarks, the developed GA always outperforms the existing algorithms.
Keyword:
Task Graph Scheduling, Homogeneous systems, Genetic Algorithm, Critical Path.