An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem

Moghaddam, Mohsen Ebrahimi and Bonyadi, Mohammad Reza (2012) An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem. International Journal of Parallel Programming, 40 2: 225-257. doi:10.1007/s10766-011-0179-0


Author Moghaddam, Mohsen Ebrahimi
Bonyadi, Mohammad Reza
Title An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem
Journal name International Journal of Parallel Programming   Check publisher's open access policy
ISSN 0885-7458
1573-7640
Publication date 2012-04
Year available 2011
Sub-type Article (original research)
DOI 10.1007/s10766-011-0179-0
Open Access Status Not yet assessed
Volume 40
Issue 2
Start page 225
End page 257
Total pages 33
Place of publication New York, NY, United States
Publisher Springer New York LLC
Language eng
Formatted abstract
Multiprocessor task scheduling is an important problem in parallel applications and distributed systems. In this way, solving the multiprocessor task scheduling problem (MTSP) by heuristic, meta-heuristic, and hybrid algorithms have been proposed in literature. Although the problem has been addressed by many researchers, challenges to improve the convergence speed and the reliability of methods for solving the problem are still continued especially in the case that the communication cost is added to the problem frame work. In this paper, an Immune-based Genetic algorithm (IGA), a meta-heuristic approach, with a new coding scheme is proposed to solve MTSP. It is shown that the proposed coding reduces the search space of MTSP in many practical problems, which effectively influences the convergence speed of the optimization process. In addition to the reduced search space offered by the proposed coding that eventuate in exploring better solutions at a shorter time frame, it guarantees the validity of solutions by using any crossover and mutation operators. Furthermore, to overcome the regeneration phenomena in the proposed GA (generating similar chromosomes) which leads to premature convergence, an affinity based approach inspired from Artificial Immune system is employed which results in better exploration in the searching process. Experimental results showed that the proposed IGA surpasses related works in terms of found makespan (20% improvement in average) while it needs less iterations to find the solutions (90% improvement in average) when it is applied to standard test benches.
Keyword Genetic algorithm (GA)
Makespan
Meta-heuristic
Multiprocessor task scheduling problem (MTSP)
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Information Technology and Electrical Engineering Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 5 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 12 Jul 2016, 14:45:46 EST by System User on behalf of Learning and Research Services (UQ Library)