A transformation-based approach to static multiprocessor scheduling

This paper describes a novel Genetic Algorithm (GA) approach to scheduling. Although the particular problems examined are all multi-processor scheduling types it can, because the algorithm takes a DAG (Directed Acyclic Graph) as input, be applied to any scheduling problem represented by a DAG. The algorithm works by calculating the mobility of each node in the graph and using this to constrain the search space in a useful way, that is, nodes can be scheduled using a larger range of levels in the final schedule than those obtained by a simple levelling of the DAG. The GA itself operates by evolving sequences of transformations which build up ever increasing lists of task associations, using two simple transformations. We show that our algorithm can outperform standard methods, both traditional and GA based, at considerably lower costs.