DYNAMIC TASK SCHEDULING USING PARALLEL GENETIC ALGORITHMS FOR HETEROGENEOUS DISTRIBUTED COMPUTING

Abstract- A parallel genetic algorithm has been developed to dynamically schedule heterogeneous tasks to heterogeneous processors in a distributed environment. The scheduling problem is known to be NP complete. Genetic algorithms, a meta-heuristic search technique, have been used successfully in this field. The proposed algorithm uses multiple processors with centralized control for scheduling. Tasks are taken as batches and are scheduled to minimize the execution time and balance the loads of the processors. According to our experimental results, the proposed parallel genetic algorithm (PPGA) considerably decreases the scheduling time without adversely affecting the maxspan of the resulting schedules