Learning Based Genetic Algorithm for Task Graph Scheduling
Nowadays, parallel and distributed based environments are used extensively; hence, for using these environments effectively, scheduling techniques are employed. The scheduling algorithm aims to minimize the makespan (i.e., completion time) of a parallel program. Due to the NP-hardness of the schedul...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Applied Computational Intelligence and Soft Computing |
| Online Access: | http://dx.doi.org/10.1155/2019/6543957 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832549443721756672 |
|---|---|
| author | Habib Izadkhah |
| author_facet | Habib Izadkhah |
| author_sort | Habib Izadkhah |
| collection | DOAJ |
| description | Nowadays, parallel and distributed based environments are used extensively; hence, for using these environments effectively, scheduling techniques are employed. The scheduling algorithm aims to minimize the makespan (i.e., completion time) of a parallel program. Due to the NP-hardness of the scheduling problem, in the literature, several genetic algorithms have been proposed to solve this problem, which are effective but are not efficient enough. An effective scheduling algorithm attempts to minimize the makespan and an efficient algorithm, in addition to that, tries to reduce the complexity of the optimization process. The majority of the existing scheduling algorithms utilize the effective scheduling algorithm, to search the solution space without considering how to reduce the complexity of the optimization process. This paper presents a learner genetic algorithm (denoted by LAGA) to address static scheduling for processors in homogenous computing systems. For this purpose, we proposed two learning criteria named Steepest Ascent Learning Criterion and Next Ascent Learning Criterion where we use the concepts of penalty and reward for learning. Hence, we can reach an efficient search method for solving scheduling problem, so that the speed of finding a scheduling improves sensibly and is prevented from trapping in local optimal. It also takes into consideration the reuse idle time criterion during the scheduling process to reduce the makespan. The results on some benchmarks demonstrate that the LAGA provides always better scheduling against existing well-known scheduling approaches. |
| format | Article |
| id | doaj-art-64f0a2933e534400af126082ec66d19c |
| institution | Kabale University |
| issn | 1687-9724 1687-9732 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Applied Computational Intelligence and Soft Computing |
| spelling | doaj-art-64f0a2933e534400af126082ec66d19c2025-02-03T06:11:21ZengWileyApplied Computational Intelligence and Soft Computing1687-97241687-97322019-01-01201910.1155/2019/65439576543957Learning Based Genetic Algorithm for Task Graph SchedulingHabib Izadkhah0Department of Computer Science, Faculty of Mathematical Sciences, University of Tabriz, Tabriz, IranNowadays, parallel and distributed based environments are used extensively; hence, for using these environments effectively, scheduling techniques are employed. The scheduling algorithm aims to minimize the makespan (i.e., completion time) of a parallel program. Due to the NP-hardness of the scheduling problem, in the literature, several genetic algorithms have been proposed to solve this problem, which are effective but are not efficient enough. An effective scheduling algorithm attempts to minimize the makespan and an efficient algorithm, in addition to that, tries to reduce the complexity of the optimization process. The majority of the existing scheduling algorithms utilize the effective scheduling algorithm, to search the solution space without considering how to reduce the complexity of the optimization process. This paper presents a learner genetic algorithm (denoted by LAGA) to address static scheduling for processors in homogenous computing systems. For this purpose, we proposed two learning criteria named Steepest Ascent Learning Criterion and Next Ascent Learning Criterion where we use the concepts of penalty and reward for learning. Hence, we can reach an efficient search method for solving scheduling problem, so that the speed of finding a scheduling improves sensibly and is prevented from trapping in local optimal. It also takes into consideration the reuse idle time criterion during the scheduling process to reduce the makespan. The results on some benchmarks demonstrate that the LAGA provides always better scheduling against existing well-known scheduling approaches.http://dx.doi.org/10.1155/2019/6543957 |
| spellingShingle | Habib Izadkhah Learning Based Genetic Algorithm for Task Graph Scheduling Applied Computational Intelligence and Soft Computing |
| title | Learning Based Genetic Algorithm for Task Graph Scheduling |
| title_full | Learning Based Genetic Algorithm for Task Graph Scheduling |
| title_fullStr | Learning Based Genetic Algorithm for Task Graph Scheduling |
| title_full_unstemmed | Learning Based Genetic Algorithm for Task Graph Scheduling |
| title_short | Learning Based Genetic Algorithm for Task Graph Scheduling |
| title_sort | learning based genetic algorithm for task graph scheduling |
| url | http://dx.doi.org/10.1155/2019/6543957 |
| work_keys_str_mv | AT habibizadkhah learningbasedgeneticalgorithmfortaskgraphscheduling |