We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Reseach Article

Task Scheduling in Parallel Systems using Genetic Algorithm

by Rachhpal Singh
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 108 - Number 16
Year of Publication: 2014
Authors: Rachhpal Singh
10.5120/18999-0470

Rachhpal Singh . Task Scheduling in Parallel Systems using Genetic Algorithm. International Journal of Computer Applications. 108, 16 ( December 2014), 34-40. DOI=10.5120/18999-0470

@article{ 10.5120/18999-0470,
author = { Rachhpal Singh },
title = { Task Scheduling in Parallel Systems using Genetic Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { December 2014 },
volume = { 108 },
number = { 16 },
month = { December },
year = { 2014 },
issn = { 0975-8887 },
pages = { 34-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume108/number16/18999-0470/ },
doi = { 10.5120/18999-0470 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:43:11.400342+05:30
%A Rachhpal Singh
%T Task Scheduling in Parallel Systems using Genetic Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 108
%N 16
%P 34-40
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The common problem of multiprocessor scheduling can be defined as allocating a task graph in a multiprocessor system so that schedule length can be improved. Task scheduling in multiprocessor system is a NP-complete problem. A number of heuristic methods have been cultivated that achieve partial solutions in less than the minimum computing time. Genetic algorithms have obtained much awareness as they are robust and provide a good solution. In this paper, genetic algorithm based on the principles of evolution to obtain an optimal solution for task scheduling is developed. Genetic algorithm is based on three operators: Natural Selection, Crossover and Mutation. The simulation results prove that the method proposed generates better results.

References
  1. J Weinberg, "Job Scheduling on Parallel Systems", Job Scheduling Strategies for Parallel Processing, 2002.
  2. CH Xia, G Michailidis, N Bambos, "Dynamic on-line task scheduling on parallel processors", Performance Evaluation, Elseiver 2001.
  3. Esquivel S. C. , Gatica C. R. , Gallard R. H, "Solving the parallel task scheduling problem by means of genetic algorithm", National Agency to Promote Science and Technology.
  4. Rachhpal Singh, "Genetic Algorithm for Parallel Process Scheduling", International Journal of Computer Applications & Information Technology Vol. 1, 2012.
  5. U. Karthick Kumar, "A Dynamic Load Balancing Algorithm in Computational Grid Using Fair Scheduling", IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 5, No 1, 2011.
  6. Lei Zhang, Yuehui Chen, Runyuan Sun, Shan Jing and Bo Yang, "A Task Scheduling Algorithm Based on PSO for Grid Computing", IEEE, vol 2, 2006.
  7. Abraham, R. Buyya and B. Nath, Nature's Heuristics for Scheduling Jobs on Computational Grids, The 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), pp. 45-52, 2000.
  8. S. Song, Y. Kwok, and K. Hwang, "Security-Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling", IEEE International Parallel and Distributed Processing, pp. 65-74, 2005.
  9. J. E. Orosz and S. H. Jacobson, Analysis of static simulated annealing algorithm, Journal of Optimization theory and Applications, pp. 165-182, 2002.
  10. R. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B. Yao, D. Hensgen and R. Freund, "A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems", pp. 810-837, J. of Parallel and Distributed Computing, vol. 61, 2001.
  11. A. Moraglio, H. M. M. Teneikelder, R. Tadei, "Genetic Local Search for Job Shop Scheduling Problem", Technical Report CSM, 2005.
  12. Ratan Mishra1 and Anant Jaiswal, "Ant colony Optimization: A Solution of Load balancing in Cloud", International Journal of Web & Semantic Technology, Vol. 3, 2012.
  13. Z. Pooranian, A. Harounabadi, M. Shojafar and N. Hedayat"New Hybrid Algorithm for Task Scheduling in Grid Computing to Decrease missed Task", World Academy of Science, Engineering and Technology, Vol-5, 2011.
  14. Dervis Karaboga and Bahriye Basturk, "Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems", IFSA, pp. 789–798, 2007.
  15. Zahra Pooranian, Mohammad Shojafar, Reza Tavoli, Mukesh Singhal, Ajith Abraham, "A Hybrid Metaheuristic Algorithm for Job Scheduling on Computational Grids", Informatica, pp 157–164, 2013.
  16. Rizos Sakellariou and Viktor Yarmolenko, "Job Scheduling on the Grid: Towards SLA-Based Scheduling".
  17. Vishnu Kant Soni, Raksha Sharma, Manoj Kumar Mishra, "Grouping-Based Job Scheduling Model In Grid Computing", World Academy of Science, Engineering and Technology, Vol: 4, 2010.
  18. U. Karthick Kumar, "A Dynamic Load Balancing Algorithm in Computational Grid Using Fair Scheduling", International Journal of Computer Science Issues, Vol. 8, 2011.
  19. S. Selvi, Dr. D. Manimegalai and Dr. A. Suruliandi, "Efficient Job Scheduling on Computational Grid with Differential Evolution Algorithm", International Journal of Computer Theory and Engineering, Vol. 3, 2011.
  20. Jim Blythe, Sonal Jain, Ewa Deelman, Anirban Mandal, and Ken Kennedy "Task Scheduling Strategies for Workflow-based Applications in Grids".
  21. Angelos Michalas, and Malamati Louta, "Adaptive Task Scheduling in Grid Computing Environments".
Index Terms

Computer Science
Information Sciences

Keywords

Parallel computing Heterogeneous system Task scheduling Task duplication Schedule length and Load balance.