An Ordered-Deme Genetic Algorithm for Multiprocessor Scheduling

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2000-06-25

著者

• Park Kwang-il

  The Authors Are With The Computer Engineering Research Laboratory Department Of Electrical Engineeri

• Park Kyu

  The Authors Are With The Department Of Electrical Engineering And Computer Science

• Jung Bong-joon

  The Authors Are With The Computer Engineering Research Laboratory Department Of Electrical Engineeri

関連論文

• Selective Clock Suppression of Protocol Modules for a Low Power Protocol Converter
• An Ordered-Deme Genetic Algorithm for Multiprocessor Scheduling

スポンサーリンク