Improved Multiprocessor Task Scheduling Using Genetic Algorithms

Michael Bohler, Air Force Research Laboratory; Frank Moore, Miami University; Yi Pan, University of Dayton

Efficient multiprocessor task scheduling is a long-studied and difficult problem that continues to be a topic of considerable research. This NP-complete problem is typically solved using a combination of search techniques and heuristics. Traditional solutions require a deterministic search of the solution space, which is computationally and temporally exhaustive. Genetic algorithms are known to provide robust, stochastic solutions for numerous optimization problems. This paper describes the design and implementation of a genetic algorithm for minimizing the schedule length for a general task graph to be executed on a multiprocessor system. The implementation is scalable and adaptable to a variety of task graphs and parallel processing systems. Several improvements over state-of-the-art approaches lead to a vigorous solution.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.