General Information
    • ISSN: 1793-8201 (Print), 2972-4511 (Online)
    • Abbreviated Title: Int. J. Comput. Theory Eng.
    • Frequency: Quarterly
    • DOI: 10.7763/IJCTE
    • Editor-in-Chief: Prof. Mehmet Sahinoglu
    • Associate Editor-in-Chief: Assoc. Prof. Alberto Arteta, Assoc. Prof. Engin Maşazade
    • Managing Editor: Ms. Mia Hu
    • Abstracting/Indexing: Scopus (Since 2022), INSPEC (IET), CNKI,  Google Scholar, EBSCO, etc.
    • Average Days from Submission to Acceptance: 192 days
    • APC: 800 USD
    • E-mail: ijcte@iacsitp.com
    • Journal Metrics:
    • SCImago Journal & Country Rank
Editor-in-chief
Prof. Mehmet Sahinoglu
Computer Science Department, Troy University, USA
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-2024. International Association of Computer Science and Information Technology. All rights reserved.