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.