• May 27, 2016 News!The submission for Special Issue is officially open now!   [Click]
  • May 03, 2016 News!Vol.6, No.6 has been indexed by EI (Inspec).   [Click]
  • Mar 17, 2017 News!Vol.9, No.2 has been published with online version. 13 peer reviewed articles from 4 specific areas are published in this issue.   [Click]
General Information
Editor-in-chief
Prof. Wael Badawy
Department of Computing and Information Systems Umm Al Qura University, Canada
I'm happy to take on the position of editor in chief of IJCTE. We encourage authors to submit papers concerning any branch of computer theory and engineering.
IJCTE 2012 Vol.5(2): 377-382 ISSN: 1793-8201
DOI: 10.7763/IJCTE.2013.V5.713

An Efficient and Robust Genetic Algorithm for Multiprocessor Task Scheduling

Sachi Gupta, Gaurav Agarwal, and Vikas Kumar
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.
Copyright © 2008-2015. International Journal of Computer Theory and Engineering. All rights reserved.
E-mail: ijcte@vip.163.com