Task Scheduling in Parallel Systems using Genetic Algorithm

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

• J Weinberg, "Job Scheduling on Parallel Systems", Job Scheduling Strategies for Parallel Processing, 2002.
• CH Xia, G Michailidis, N Bambos, "Dynamic on-line task scheduling on parallel processors", Performance Evaluation, Elseiver 2001.
• 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.
• Rachhpal Singh, "Genetic Algorithm for Parallel Process Scheduling", International Journal of Computer Applications & Information Technology Vol. 1, 2012.
• 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.
• 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.
• 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.
• 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.
• J. E. Orosz and S. H. Jacobson, Analysis of static simulated annealing algorithm, Journal of Optimization theory and Applications, pp. 165-182, 2002.
• 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.
• A. Moraglio, H. M. M. Teneikelder, R. Tadei, "Genetic Local Search for Job Shop Scheduling Problem", Technical Report CSM, 2005.
• Ratan Mishra1 and Anant Jaiswal, "Ant colony Optimization: A Solution of Load balancing in Cloud", International Journal of Web & Semantic Technology, Vol. 3, 2012.
• 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.
• Dervis Karaboga and Bahriye Basturk, "Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems", IFSA, pp. 789–798, 2007.
• 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.
• Rizos Sakellariou and Viktor Yarmolenko, "Job Scheduling on the Grid: Towards SLA-Based Scheduling".
• 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.
• U. Karthick Kumar, "A Dynamic Load Balancing Algorithm in Computational Grid Using Fair Scheduling", International Journal of Computer Science Issues, Vol. 8, 2011.
• 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.
• Jim Blythe, Sonal Jain, Ewa Deelman, Anirban Mandal, and Ken Kennedy "Task Scheduling Strategies for Workflow-based Applications in Grids".
• Angelos Michalas, and Malamati Louta, "Adaptive Task Scheduling in Grid Computing Environments".

Index Terms

Keywords