An Ordered-Deme Genetic Algorithm for Multiprocessor Scheduling

Bong-Joon JUNG  Kwang-Il PARK  Kyu Ho PARK  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D   No.6   pp.1207-1215
Publication Date: 2000/06/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
genetic algorithm,  multiprocessor scheduling,  optimization technique,  stochastic search algorithm,  task graph,  

Full Text: PDF>>
Buy this Article

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.