Scheduling dynamically evolving parallel programs using the genetic approach

Presents a study of scheduling dynamically evolving parallel programs in distributed multiprocessor systems. Four centralized schedulers based on a genetic algorithm are proposed. These schedulers consider both load balancing and communication minimization. They do not assume a-priori knowledge of the execution time or communication overhead. The newly-arrived parallel programs are scheduled to run immediately on arrival, and the processors are not reserved exclusively for the execution of a single parallel program. Simulation experiments were designed and conducted to evaluate the proposed schedulers. The results show that these schedulers can achieve up to 60% improvement in the average response time and up to 80% improvement in communication minimization as compared to the least-loaded scheduler.