We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Enhanced genetic algorithm with some heuristic principles for task graph scheduling.
- Authors
Nematpour, Mohammad; Izadkhah, Habib; Mahan, Farnaz
- Abstract
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%.
- Subjects
GENETIC algorithms; HEURISTIC algorithms; CHROMOSOME structure; GRAPH algorithms; PARALLEL programming; NP-complete problems
- Publication
Journal of Supercomputing, 2023, Vol 79, Issue 2, p1784
- ISSN
0920-8542
- Publication type
Academic Journal
- DOI
10.1007/s11227-022-04684-0