Multiple-Objective Particle Swarm Optimization Algorithm for Independent Task Scheduling in Distributed Heterogeneous Computing Systems
 |
International Journal of Computer Trends and Technology (IJCTT) |  |
| © 2017 by IJCTT Journal | ||
| Volume-45 Number-1 |
||
| Year of Publication : 2017 | ||
| Authors : Amit Prakash, Karamjit Bhatia, Raj Kumar | ||
| DOI : 10.14445/22312803/IJCTT-V45P103 |
Amit Prakash, Karamjit Bhatia, Raj Kumar; "Multiple-Objective Particle Swarm Optimization Algorithm for Independent Task Scheduling in Distributed Heterogeneous Computing Systems". International Journal of Computer Trends and Technology (IJCTT) V45(1):10-20, March 2017. ISSN:2231-2803. www.ijcttjournal.org. Published by Seventh Sense Research Group.
Abstract -
Task scheduling is a crucial issue in distributed (disbursed) heterogeneous processing environment and significantly influence the performance of the system. The task scheduling problem has been identified to be NP-complete in its universal frame. In this paper the task scheduling problem is investigated using multiple-objective particle (molecule) swarm optimization algorithm with crowded displacement operator (MOPSO-CD). Particle swarm optimization is a populace based meta-heuristic which mimics the convivial conduct of feathered creatures running. In this algorithm particles move in the problem`s search space to achieve near optimal solutions. The performance of this algorithm is compared with non-domination sorting genetic algorithm II (NSGA-II). The proposed scheduling algorithm intends to find the near optimal solution with aim to minimize the make-span and flow time. The exploratory results demonstrate that the proposed multi-objective PSO algorithm is more productive and gives better outcomes when contrasted with those of NSGA-II.
References
[1] Munir E U, Li J-Z, Shi S-F and Rasool Q Performance Analysis of Task Scheduling Heuristics in Grid, In: ICMLC’07: Proceedings of the International Conference on Machine Learning and Cybernetics,6: 3093–3098, 2007.
[2] Maheswaran M, Ali S, Siegel H J, Hensgen D and Freund R F, Dynamic mapping of a class of independent tasks onto heterogeneous computing systems, J. Parallel and Distributed Computing 59: 107–131, 1999.
[3] Freund R F, Gherrity M, Ambrosius S, Campbell M, Halderman M, Hensgen D, Keith D E, Kidd T, Kussow M, Lima J D, Mirabile F, Moore L, Rust B and Siegel H J, Scheduling resources in multiuser, heterogeneous, computing environments with SmartNet, In: 7th IEEE Heterogeneous Computing Workshop, 184–199, 1998.
[4] Abraham A, Buyya R and Nath B, Nature’s heuristics for scheduling jobs on computational grids, The 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), India, 2000.
[5] Page A and Naughton J, Framework for task scheduling in heterogeneous distributed computing using genetic algorithms, Artificial Intelligence Rev. 24: 415–429, 2005.
[6] Yarkhan A and Dongarra J, Experiments with scheduling using simulated annealing in a grid environment, In: Proceedings of the 3rd International Workshop on Grid Computing (GRID2002), 232–242, 2002.
[7] Ritchie G and Levine L , A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments, In: 23rd Workshop of the UK Planning and Scheduling Special Interest Group, PLANSIG, 2004.
[8] Salman A, Ahmad I and Al-Madani S, Particle swarm optimization for task assignment problem, Microprocessors and Microsystems 26(8): 363–371, 2002.
[9] Braun T D, Siegel H J, Beck N, Boloni L L, Maheswaran M, Reuther A I, Robertson J P, Theys M D and Yao B, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, J. Parallel and Distributed Computing 61: 810–837, 2001.
[10] Liu H, Abraham A and Hassanien A, Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm, Future Generation Computer Systems 26 (8) : 1336–1343, 2010.
[11] Izakian H, Abraham A and Snasel V, Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments, IEEE Control Systems Magazine 1: 8–12, 2009.
[12] Abraham A, Liu H, Grosan C and Xhafa F, Nature inspired meta-heuristics for grid scheduling: single and multi-objective optimization approaches. Studies in computational intelligence, Berlin Heidelberg: Springer Verlag, 247–272, 2008.
[13] Izakian H, Tork Ladani B, Zamanifar K and Abraham A, A novel particle swarm optimization approach for grid job scheduling, In: Proceedings of the Third International Conference on Information Systems, Technology and Management, 100–110, 2009.
[14] Xhafa F, Carretero J and Abraham A, Genetic algorithm based schedulers for grid computing systems, Int. J. Innovative Computing, Information and Control 3: 1053–1071, 2007.
[15] V. Di Martino and M. Mililotti. Sub optimal scheduling in a grid using genetic algorithms. Parallel Computing, 30:553–565, 2004.
[16] A.Y. Zomaya and Y.H. Teh. Observations on using genetic algorithms for dynamic load-balancing. IEEE Transactions On Parallel and Distributed Systems, 12(9):899–911, 2001.
[17] Deb K, Pratap A, Agarwal S. and Meyarivan T, A Fast Elitist Multiobjective Genetic Algorithm: NSGA-II, Kanpur Genetic Algorithms Laboratory Report No-200001 , Indian Institute of Technology, Kanpur, 2000.
[18] Christos Gogos, Christos Valouxis, Panayiotis Alefragis, George Goulas, Nikolaos Voros, Efthymios Housos, Scheduling independent tasks on heterogeneous processors using heuristics and Column Pricing, Future Generation Computer Systems 60, 48–66, 2016.
[19] A.K. Chaturvedi, R. Sahu, New heuristic for scheduling of independent tasks in computational grid, Int. J. Grid Distributed Computing. 4 (3), 25–36, 2011.
[20] G Subashini and M C Bhuvaneswari, Comparison of multi-objective evolutionary approaches for task scheduling in distributed computing systems, Sadhana, Vol. 37, Part 6, pp. 675–694. Indian Academy of Sciences, December 2012.
[21] Carlo R. Raquel, Prospero C. Naval, Jr., An Effective Use of Crowding Distance in Multiobjective Particle Swarm Optimization, ACM, GECCO’ 05, June 25-29, 2005.
[22] Angeline, P.J. Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. In Proceedings of the Seventh Annual Conference on Evolutionary Programming, San Diego, pp. 601–610, 1998.
[23] Salerno, J. Using the particle swarm optimization technique to train a recurrent neural model. In Proceedings of the IEEE International Conference on Tools with Artificial Intelligence, Newport Beach, CA, USA, pp. 45–49, November 3-8, 1997.
[24] Eberhart, R.C.; Shi, Y. Evolving artificial neural networks. In Proceedings of the International Conference on Neural Networks and Brain, Beijing, P.R. China, pp. 5–13, October 27-30, 1998.
[25] Coello Coello, C. A. and Salazar Lechuga, M., MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization. In Proceedings of the Congress on Evolutionay Computation (CEC’02), volume 1, pages 1051–1056, Honolulu, HI. IEEE Press, 2002.
[26] Coello Coello, C. A., Toscano Pulido, G., and Salazar Lechuga, M. Handling Multiple Objectives With Particle Swarm Optimization. IEEE Transactions on Evolutionary Computation, 8(3):256–279, 2004.
[27] Kennedy, J. and Eberhart, R. C. Particle Swarm Optimization. In Proceedings of the IEEE International Conference on Neural Networks, pages 1942–1948, Piscataway, New Jersey. IEEE Service Center, 1995.
[28] Kennedy, J. and Eberhart, R. C. Swarm Intelligence. Morgan Kaufmann, San Francisco, California, 2001.
[29] C. Tsou, S. Chang, and P. Lai., Using Crowding Distance to Improve Multi-Objective PSO with Local Search, Swarm Intelligence , Focus on Ant and Particle Swarm Optimization, Edited by Felix T.S. Chan and Manoj Kumar Tiwari, 2007.
[30] K. Deb and N. Srinivas, Multi-objective optimization using non-dominated sorting in genetic algorithms. Evolutionary Computation, pages 221–248, 1994.
[31] Shreeram Kushwaha, Multiobjective optimization of cluster measures in Microarray Cancer data using Genetic Algorithm Based Fuzzy Clustering, Bachelor of Technology in Computer Science & Engineering Thesis, National Institute of Technology Rourkela, 2012-13.
[32] Y. Shi and R. Eberhart, Empirical study of particle swarm optimization. In Proceedings of the 1999 Congress on Evolutionary Computation (CEC 1999), pages 1945–1950, 1999.
[33] Seshadri, A., A Fast Elitist Multiobjective Genetic Algorithm: NSGA-II (1st ed.). New Jersey: New Jersey Institute of Technology. Retrieved from https://web.njit.edu/~horacio/Math451H/download/Seshadri_NSGA-II.pdf, 2006.
[34] M. T. Jensen., Reducing the run-time complexity of multiobjective eas: The nsga-ii and other algorithms. Trans. Evol. Comp, 7(5) : 503 -515. ISSN 1089 - 778X. doi: 10.1109/ TEVC. 2003. 817234. URL http://dx/doi.org/10.1109/ TEVC.2003.817234, October 2003.
[35] Hossein Ghiasi, Damiano Pasini and Larry Lessard, A non-dominated sorting hybrid algorithm for multi-objective optimization of engineering problems, Vol. 43, No. 1, 39–59, Engineering Optimization, January 2011.
[36] Zengqiang Jiang, Le Zuo, Mingcheng E, Study on Multi-objective Flexible Job-shop Scheduling Problem considering Energy Consumption, 7(3), 589-604, Journal of Industrial Engineering and Management, 2014.
[37] Kalyanmoy Deb, Udaya Bhaskara Rao N., and S. Karthik, Dynamic Multi-Objective Optimization and Decision-Making Using Modified NSGA-II: A Case Study on Hydro-Thermal Power Scheduling, Kanpur Genetic Algorithms Laboratory (KanGAL) Report Number 2006008, Indian Institute of Technology Kanpur, 2005.
[38] Adriana Cortes God?nez, Luis Ernesto Mancilla Espinosa, EfrenMezura Montes, An Experimental Comparison of Multi-Objective Algorithms: NSGA-II and OMOPSO, Electronics, Robotics and Automotive Mechanics Conference (CERMA), 2010, Oct. 2010,.
[39] Hagerup T., Allocating Independent Tasks to Parallel Processors: An Experimental Study. Journal of Parallel and Distributed Computing, 47, pp. 185-197, 1997.
[40] Satyobroto Talukder, Mathematical Modeling and Applications of Particle Swarm Optimization, Master of Science Thesis, School of Engineering, Blekinge Institute of Technology, Sweden, February 2011.
[41] Mahmood Rahmani, Particle swarm optimization of artificial neural networks for autonomous robots, Master of Science in Complex Adaptive Systems Thesis, Department of Applied Physics, Chalmers University of Technology, Sweden, 2008.
[42] Peng-Yeng Yin, Shiuh-Sheng Yu, Pei-Pei Wang, Yi-Te Wang, A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems, Computer Standards & Interfaces , Vol.28, pp. 441-450, 2006.
Keywords
Task scheduling, Independent tasks, Meta heuristic, Particle swarm intelligence, Non-domination sorting genetic algorithm, Make-span, Flow-time.