For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Ordered-Deme Genetic Algorithm for Multiprocessor Scheduling
Bong-Joon JUNG Kwang-Il PARK Kyu Ho PARK
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/06/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
genetic algorithm, multiprocessor scheduling, optimization technique, stochastic search algorithm, task graph,
Full Text: PDF>>
In static multiprocessor scheduling, heuristic algorithms have been widely used. Instead of gaining execution speed, most of them show non promising solutions since they search only a part of solution spaces. In this paper, we propose a scheduling algorithm using the genetic algorithm (GA) which is a well-known stochastic search algorithm. The proposed algorithm, named ordered-deme GA (OGA), is based on the multiple subpopulation GA, where a global population is divided into several subpopulations (demes) and each demes evolves independently. To find better schedules, the OGA orders demes from the highest to the lowest deme and migrates both the best and the worst individuals at the same time. In addition, the OGA adaptively assigns different mutation probabilities to each deme to improve search capability. We compare the OGA with well-known heuristic algorithms and other GAs for random task graphs and the task graphs from real numerical problems. The results indicate that the OGA finds mostly better schedules than others although being slower in terms of execution time.