Multiprocessor scheduling in a genetic paradigm

In this paper, we present a technique based on the problem-space genetic algorithm (PSGA) for the static scheduling of directed acyclic graphs onto homogeneous multiprocessor systems to reduce the response-time. The PSGA based approach combines genetic algorithms with a list scheduling heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable cpu time. Comparison of results with the genetic algorithm (GA) based scheduling technique for the Stanford manipulator and the Elbow manipulator examples shows a significant improvement in the response-time. We also demonstrate the effectiveness of our algorithm by comparing it with the Critical Path/Maximum Immediate Successor First (CP/MISF) list scheduling technique for randomly generated graphs. The proposed scheme offers on the average a 3.6% improvement in the response-time as compared to the CP/MISF technique for all the random graphs.