Treffer: Enhanced genetic algorithm with some heuristic principles for task graph scheduling.

Multiprocessor systems with parallel computing play an important role in data processing. Considering the optimal use of existing computing systems, scheduling on parallel systems has gained great significance. Usually, a sequential program to run on parallel systems is modeled by a task graph. Because scheduling of task graphs onto processors is considered the most crucial NP-complete problem, many attempts have been made to find the most approximate optimal scheduling using genetic algorithms. Its chromosomal representation largely influences the performance of the genetic algorithm. The chromosomal structure used in the existing genetic algorithms does not entirely scan the solution space. As a result, these algorithms fail to produce an appropriate schedule frequently. To overcome this constraint, the present study proposed a new method for constructing chromosomal representation. The proposed approach was divided into three phases: ranking, clustering, and cluster scheduling, where a genetic algorithm schedules clusters. To optimize the proposed genetic algorithm's performance, it was equipped with four heuristic principles: load balancing, reuse of idle time, task duplication, and critical path. Finally, by comparing the obtained results for 6 task graphs in 3 types, the amount of optimization was equal to the results of previous best algorithm, but in the other 3 types, the amount of optimization was a value between 4.25 and 6.88%. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Supercomputing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)