A novel hybrid PSO–GA meta-heuristic for scheduling of DAG with communication on multiprocessor systems |
| |
Authors: | Neetesh?Kumar Email author" target="_blank">Deo?Prakash?VidyarthiEmail author |
| |
Affiliation: | 1.School of Computer and Systems Sciences,Jawaharlal Nehru University,New Delhi,India |
| |
Abstract: | This work presents a novel hybrid meta-heuristic that combines particle swarm optimization and genetic algorithm (PSO–GA) for the job/tasks in the form of directed acyclic graph (DAG) exhibiting inter-task communication. The proposed meta-heuristic starts with PSO and enters into GA when local best result from PSO is obtained. Thus, the proposed PSO–GA meta-heuristic is different than other such hybrid meta-heuristics as it aims at improving the solution obtained by PSO using GA. In the proposed meta-heuristic, PSO is used to provide diversification while GA is used to provide intensification. The PSO–GA is tested for task scheduling on two standard well-known linear algebra problems: LU decomposition and Gauss–Jordan elimination. It is also compared with other states-of-the-art heuristics for known solutions. Furthermore, its effectiveness is evaluated on few large sizes of random task graphs. Comparative study of the proposed PSO-GA with other heuristics depicts that the PSO–GA performs quite effectively for multiprocessor DAG scheduling problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|