A novel hybrid PSO–GA meta-heuristic for scheduling of DAG with communication on multiprocessor systems. (January 2016)

• Record Type: Journal Article
• Authors: Kumar, Neetesh; Vidyarthi, Deo
• Is Part Of: Engineering with computers. Volume 32:Number 1(2016)
• Page Start: 35
• Page End: 47
• Publication Date: 2016-01
• Subjects: Multiprocessor DAG scheduling -- Genetic algorithm -- Particle swarm optimization -- NP-hard -- Critical path; Engineering design -- Data processing -- Periodicals; Computer-aided design -- Periodicals; Conception technique -- Informatique -- Périodiques; Conception assistée par ordinateur -- Périodiques; Electronic journals; 620.00285
• DOI: 10.1007/s00366-015-0396-z
• Languages: English
• ISSNs: 0177-0667

Abstract

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.