Cellular Automata Approach to Scheduling Problem in Case of Modifications of a Program Graph
A. Święcicka, Franciszek Seredyński, Mariusz Jażdżyk · Advances in intelligent and soft computing · 2001
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 elementary 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 show efficiency of discovered rules in case of modifications of a program graph. These modifications include changing the values of the weights of some randomly chosen tasks or (and) edges of a program graph. We also show that discovered rules may be used to find optimal or suboptimal solutions of other program graphs constructed on the base of a given program graph.