MULTIPROCESSOR SCHEDULING IN A GENETIC PARADIGM

In this paper, we present a technique based on the problem-space genet ic algorithm (PSGA) for the static scheduling of directed acyclic grap hs onto homogeneous multiprocessor systems to reduce the response-time . The PSGA based approach combines genetic algorithms with a list sche duling heuristic to search a large solution space efficiently and effe ctively 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 exam ples shows a significant improvement in the response-time. We also dem onstrate the effectiveness of our algorithm by comparing it with the C ritical Path/Maximum Immediate Successor First (CP/MISF) list scheduli ng 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.