Improved Multiprocessor Task Scheduling Using Genetic Algorithms

May 1999

Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference (FLAIRS 1999)

Volume

Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference (FLAIRS 1999)

All Papers

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.