Record Details

GENETIC ALGORITHM-BASED HEURISTICS FOR THE MAPPING PROBLEM

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title GENETIC ALGORITHM-BASED HEURISTICS FOR THE MAPPING PROBLEM
 
Creator CHOCKALINGAM, T
ARUNKUMAR, S
 
Description The combinatorial optimization problem of assigning parallel tasks onto a multiprocessor so as to minimize the execution time is termed as the mapping problem. This problem even in its simplest form is known to be NP-hard. Several heuristic solutions that have been proposed seek to obtain a sub-optimal mapping that can be considered as a ''good'' mapping within a reasonable time. The class of genetic algorithms for this problem is found to produce better mappings than other existing algorithms. However, the execution times of this class of algorithms are far from being competitive when compared to some of the local search heuristics. In this paper, we show that the primary advantage of genetic algorithms, viz. the generalized search operators, enables easy combinations of these global search algorithms with local search heuristics to provide an efficient hybrid algorithm for the mapping problem without compromising the solution quality. The hybrid genetic mapping heuristic performs well both in terms of the quality of the mappings produced and the time taken to obtain them.
 
Publisher PERGAMON-ELSEVIER SCIENCE LTD
 
Date 2011-08-24T12:22:51Z
2011-12-26T12:56:53Z
2011-12-27T05:46:24Z
2011-08-24T12:22:51Z
2011-12-26T12:56:53Z
2011-12-27T05:46:24Z
1995
 
Type Article
 
Identifier COMPUTERS & OPERATIONS RESEARCH, 22(1), 55-64
0305-0548
http://dx.doi.org/10.1016/0305-0548(94)P2435-7
http://dspace.library.iitb.ac.in/xmlui/handle/10054/10884
http://hdl.handle.net/10054/10884
 
Language en