Cellular automata approach to task scheduling

Abstract

In this paper we propose using cellular automata (CAs) to perform distributed scheduling tasks of a parallel program in the two processor system. We consider a program graph as a CA with elementaty cells interacting locally according to a certain rule which must be found. Effective rules for a CA are discovered by a genetic algorithm (GA). With these rules, CA-based scheduler is able to find allocations which minimize the total execution time of the program in the two processor system. We also show a possibility of reusing knowledge gained during solving instances of the scheduling problem. Keywords: cellular automata, genetic algorithms, scheduling problem.