ISSN:
1614-7456
Keywords:
Hybrid genetic algorithms
;
Multiprocessor roblem
;
Priority list
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract The multiprocessor scheduling problem is one of the classic examples of NP-hard combinatorial optimization problems. Several polynomial time optimization algorithms have been proposed for approximating the multiprocessor scheduling problem. In this paper, we suggest a geneticizedknowledge genetic algorithm (gkGA) as an efficient heuristic approach for solving the multiprocessor scheduling and other combinatorial optimization problems. The basic idea behind the gkGA approach is that knowledge of the heuristics to be used in the GA is also geneticized alongiside the genetic chromosomes. We start by providing four conversion schemes based on heuristics for converting chromosomes into priority lists. Through experimental evaluation, we observe that the performance of our GA based on each of these schemes is instance-dependent. However, if we simultaneously incorporate these schemes into our GA through the gkGA approach, simulation results show that the approach is not problem-dependent, and that the approach outperforms that of the previous GA. We also show the effectiveness of the gkGA approach compared with other conventional schemes through experimental evaluation.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02471158
Permalink
