Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/90425
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem |
Author: | Ebrahimi Moghaddam, M. Bonyadi, M. |
Citation: | International Journal of Parallel Programming, 2012; 40(2):225-257 |
Publisher: | Springer US |
Issue Date: | 2012 |
ISSN: | 0885-7458 1573-7640 |
Statement of Responsibility: | Mohsen Ebrahimi Moghaddam, Mohammad Reza Bonyadi |
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 |
Keywords: | Multiprocessor task scheduling problem (MTSP) Makespan Genetic algorithm (GA) Meta-heuristic |
Rights: | © Springer Science+Business Media, LLC 2011 |
DOI: | 10.1007/s10766-011-0179-0 |
Published version: | http://dx.doi.org/10.1007/s10766-011-0179-0 |
Appears in Collections: | Aurora harvest 2 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.