An ordered-deme genetic algorithm for multiprocessor scheduling

Abstract

In static multiprocessor scheduling, heuristic algorithms have been widely used. Instead of gaining execution speed, must of them show lion 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 sub-population CA, 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 tu the lowest deme and migrates both tilt Lest 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 tho OGA with well-known heuristic algorithms and other Chu for random task graphs and the task graphs from real numerical problems. The results indicate that the OGA finds mostly Letter schedules than others although being slower in terms of execution time.