Abstract—The general problem of multiprocessor scheduling can be stated as scheduling a task graph onto a multiprocessor system so that schedule length can be optimized. Task scheduling in multiprocessor system is a NP-complete problem. In literature, several heuristic methods have been developed that obtain suboptimal solutions in less than the polynomial time. Recently, Genetic algorithms have received much awareness as they are robust and guarantee for a good solution. In this paper, we have developed a genetic algorithm based on the principles of evolution found in nature for finding an optimal solution. Genetic algorithm is based on three operators: Natural Selection, Crossover and Mutation. To compare the performance of our algorithm, we have also implemented another scheduling algorithm HEFT which is a heuristic algorithm. Simulation results comprises of three parts: Quality of solutions, robustness of genetic algorithm, and effect of mutation probability on performance of genetic algorithm.
Index Terms—Genetic algorithm, fitness function, multi-processor system, NP-complete etc.
S. Gupta and G. Agarwal are with the Computer Science and Information Technology Deptt. Krishna Institute of Management and Technology, Moradabad, India (e-mail: sachiagarwal@rediffmail.com, meetgaurav1@rediffmail.com)
V. Kumar is with the Computer Science Deptt, Moradabad Institute of Technology Moradabad, India (e-mail: Vikas_in_mittal@rediffmail.com).
[PDF]
Cite: Sachi Gupta, Gaurav Agarwal, and Vikas Kumar, "An Efficient and Robust Genetic Algorithm for Multiprocessor Task Scheduling,"
International Journal of Computer Theory and Engineering vol. 5, no. 2, pp. 377-382, 2013.
