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


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. 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.

[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, 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/ 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.

Task scheduling, Independent tasks, Meta heuristic, Particle swarm intelligence, Non-domination sorting genetic algorithm, Make-span, Flow-time.