Modified Genetic Algorithm Approach to Optimize Task Scheduling on Heterogeneous Multiprocessor Parallel System using Node Duplication

Task graph scheduling is the important factor which occurs in the multiprocessor system. There is problem solving technique called NP complete which is the optimal scheduling of parallel tasks with some precedence relationship onto parallel machines and can be solved only by using heuristic approach. The execution time requirements of the applications tasks are assumed to be stochastic. Genetic algorithms are the widely used technique for constrained optimization. Performance of genetic algorithm can be improved by using the modified genetic algorithm (MGA) having top level and bottom level approach. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processor is the network may not be identical and take different amounts of time to execute the same task. In this paper the concept of Modified Genetic Algorithm with Node duplication (NMGA) based on bottom level and top level approaches is used. It also exhibits the efficiency of Node duplication modified genetic based techniques by comparing against some deterministic scheduling technique like genetic algorithm, modified genetic algorithm, first come first serve (FCFS) approach, priority algorithm for minimizing inter processor traffic communication.