Open Access   Article

Parallel Job Scheduling Using Grey Wolf Optimization Algorithm for Heterogeneous Multi-Cluster Environment

Sapinderjit Kaur1 , Kirandeep Kaur2 , Amit.Chhabra 3

1 Dept. of Computer Engineering and Technology, Guru Nanak Dev University, Amritsar, India.
2 Dept. of Computer Engineering and Technology, Guru Nanak Dev University, Amritsar, India.
3 Dept. of Computer Engineering and Technology, Guru Nanak Dev University, Amritsar, India.

Correspondence should be addressed to:

Section:Research Paper, Product Type: Journal Paper
Volume-5 , Issue-10 , Page no. 44-53, Oct-2017


Online published on Oct 30, 2017

Copyright © Sapinderjit Kaur, Kirandeep Kaur, Amit.Chhabra . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library


IEEE Style Citation: Sapinderjit Kaur, Kirandeep Kaur, Amit.Chhabra, “Parallel Job Scheduling Using Grey Wolf Optimization Algorithm for Heterogeneous Multi-Cluster Environment”, International Journal of Computer Sciences and Engineering, Vol.5, Issue.10, pp.44-53, 2017.

MLA Style Citation: Sapinderjit Kaur, Kirandeep Kaur, Amit.Chhabra "Parallel Job Scheduling Using Grey Wolf Optimization Algorithm for Heterogeneous Multi-Cluster Environment." International Journal of Computer Sciences and Engineering 5.10 (2017): 44-53.

APA Style Citation: Sapinderjit Kaur, Kirandeep Kaur, Amit.Chhabra, (2017). Parallel Job Scheduling Using Grey Wolf Optimization Algorithm for Heterogeneous Multi-Cluster Environment. International Journal of Computer Sciences and Engineering, 5(10), 44-53.

289 166 downloads 53 downloads


Multi-cluster environment consists of computational nodes that allow computational problems with resource requirement more than those available resources in a cluster to be treated. Scheduling jobs in heterogeneous multi-cluster environments where each cluster has varied number of processors and each computational node has a varying speed is NP hard. Thus, we always search for sub-optimal solution for scheduling jobs. Various meta-heuristics have been proposed for scheduling jobs. The literature shows that the Genetic algorithm has been employed for parallel jobs scheduling in heterogeneous multi cluster environment. But it suffers from certain limitations like slow convergence speed, local optima problem. In this research work, a Grey Wolf Optimization algorithm (GWO) has been introduced in order to minimize makespan, flowtime and mean waiting time. The proposed methodology has shown quite significant improvement over available ones.

Key-Words / Index Term

Heterogeneous multi-cluster environment, Scheduling, Co-allocation, Grey wolf Optimization Algorithm(GWOA))


[1] Abawajy, Jemal H., and Sivarama P. Dandamudi. "Parallel Job Scheduling on Multicluster Computing Systems." CLUSTER. Vol. 3. 2003
[2] Abawajy, Jemal H. "Fault-tolerant scheduling policy for grid computing systems." Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International. IEEE, 2004
[3] Alkhanak, Ehab Nabiel, Sai Peck Lee, and Saif Ur Rehman Khan. "Cost-aware challenges for workflow scheduling approaches in cloud computing environments: Taxonomy and opportunities." Future Generation Computer Systems 50 (2015): 3-21.
[4] Arsuaga-Ríos, María, and Miguel A. Vega-Rodríguez. "Energy optimization for task scheduling in distributed systems by an Artificial Bee Colony approach." Nature and Biologically Inspired Computing (NaBIC), 2014 Sixth World Congress on. IEEE, 2014.
[5] .Barbosa, Jorge, and António P. Monteiro. "A list scheduling algorithm for scheduling multi-user jobs on clusters." International Conference on High Performance Computing for Computational Science. Springer Berlin Heidelberg, 2008.
[6] Bilgaiyan, Saurabh, Santwana Sagnika, and Madhabananda Das. "An analysis of task scheduling in cloud computing using evolutionary and swarm-based algorithms." International Journal of Computer Applications 89.2 (2014).
[7] Blanco, Héctor, et al. "Multiple job co-allocation strategy for heterogeneous multi-cluster systems based on linear programming." The Journal of Supercomputing 58.3 (2011): 394-402.
[8] Bokhari, M. U., Mahfooz Alam, and Faraz Hasan. "Performance analysis of dynamic load balancing algorithm for multiprocessor interconnection network." Perspectives in Science 8 (2016): 564-566.
[9] Civicioglu, Pinar, and Erkan Besdok. "A conceptual comparison of the Cuckoo-search, particle swarm optimization, differential evolution and artificial bee colony algorithms." Artificial intelligence review 39.4 (2013): 315-346.
[10] Dorronsoro, B., Nesmachnow, S., Taheri, J., Zomaya, A. Y., Talbi, E. G., & Bouvry, P. (2014). A hierarchical approach for energy-efficient scheduling of large workloads in multicore distributed systems. Sustainable Computing: Informatics and Systems, 4(4), 252-261.
[11] Farahnakian, F., Ashraf, A., Pahikkala, T., Liljeberg, P., Plosila, J., Porres, I., & Tenhunen, H. (2015). Using ant colony system to consolidate vms for green cloud computing. IEEE Transactions on Services Computing, 8(2), 187-198.
[12] Fang, Yiqiu, Fei Wang, and Junwei Ge. "A task scheduling algorithm based on load balancing in cloud computing." International Conference on Web Information Systems and Mining. Springer Berlin Heidelberg, 2010.
[13] Feng, Yu Jianjun Sun Shudong Zheng. "Job-shop scheduling study by dynamic evaluation based immune algorithm [J]." Chinese Journal of Mechanical Engineering 3 (2005): 004.
[14] Ferrandi, F., Lanzi, P. L., Pilato, C., Sciuto, D., & Tumeo, A. (2010). Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 29(6), 911-924.
[15] Gabaldon, Eloi, et al. "Blacklist muti-objective genetic algorithm for energy saving in heterogeneous environments." The Journal of Supercomputing 73.1 (2017): 354-369.
[16] Guzek, M., Pecero, J. E., Dorronsoro, B., Bouvry, P., & Khan, S. U. (2010, June). A cellular genetic algorithm for scheduling applications and energy-aware communication optimization. In High Performance Computing and Simulation (HPCS), 2010 International Conference on (pp. 241-248). IEEE.
[17] HOU, You-hua, et al. "Analysis on active power fluctuation characteristics of large-scale grid-connected wind farm and generation scheduling simulation under different capacity power injected from wind farms into power grid [J]." Power System Technology 5 (2010): 013.
[18] .Javadi, Bahman, Mohammad K. Akbari, and Jemal H. Abawajy. "Performance analysis of heterogeneous multi-cluster systems." Parallel Processing, 2005. ICPP 2005 Workshops. International Conference Workshops on. IEEE, 2005.
[19] Jia, H. Z., Nee, A. Y., Fuh, J. Y., & Zhang, Y. F. (2003). A modified genetic algorithm for distributed scheduling problems. Journal of Intelligent Manufacturing, 14(3-4), 351-362.
[20] Javanmardi, Saeed, et al. "Hybrid job scheduling algorithm for cloud computing environment." Proceedings of the Fifth International Conference on Innovations in Bio-Inspired Computing and Applications IBICA 2014. Springer International Publishing, 2014.
[21] Javanmardi, S., Shojafar, M., Amendola, D., Cordeschi, N., Liu, H., & Abraham, A. (2014). Hybrid job scheduling algorithm for cloud computing environment. In Proceedings of the Fifth International Conference on Innovations in Bio-Inspired Computing and Applications IBICA 2014 (pp. 43-52). Springer International Publishing.
[22] Liu, J., Luo, X. G., Zhang, X. M., Zhang, F., & Li, B. N. (2013). Job scheduling model for cloud computing based on multi-objective genetic algorithm. IJCSI International Journal of Computer Science Issues, 10(1), 134-139.
[23] Liu, S. L., Liu, Y. X., Zhang, F., Tang, G. F., & Jing, N. (2007). Dynamic web services selection algorithm with QoS global optimal in web services composition. Ruan Jian Xue Bao(Journal of Software), 18(3), 646-656.
[24] Li, Jun-Qing, Quan-Ke Pan, and Kai-Zhou Gao. "Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems." The International Journal of Advanced Manufacturing Technology 55.9-12 (2011): 1159-1169.
[25] Li, S., Li, G., Wang, X., & Liu, Q. (2005). Minimizing makespan on a single batching machine with release times and non-identical job sizes. Operations Research Letters, 33(2), 157-164.
[26] Lorpunmanee, S., Sap, M. N., Abdullah, A. H., & Chompoo-inwai, C. (2007). An ant colony optimization for dynamic job scheduling in grid environment. International Journal of Computer and Information Science and Engineering, 1(4), 207-214.
[27] Masdari, M., ValiKardan, S., Shahi, Z., & Azar, S. I. (2016). Towards workflow scheduling in cloud computing: A comprehensive analysis. Journal of Network and Computer Applications, 66, 64-82.
[28] Makhlouf, Sid Ahmed, and Belabbas Yagoubi. "Resources Co-allocation Strategies in Grid Computing." CIIA. 2011.
[29] Mirjalili, Seyedali, Seyed Mohammad Mirjalili, and Andrew Lewis. "Grey wolf optimizer." Advances in Engineering Software 69 (2014): 46-61.
[30] Moganarangan, N., Babukarthik, R. G., Bhuvaneswari, S., Basha, M. S., & Dhavachelvan, P. (2016). A novel algorithm for reducing energy-consumption in cloud computing environment: Web service computing approach. Journal of King Saud University-Computer and Information Sciences, 28(1), 55-67.
[31] Pinel, F., Dorronsoro, B., Pecero, J. E., Bouvry, P., & Khan, S. U. (2013). A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids. Cluster Computing, 16(3), 421-433.
[32] Priya, S. Baghavathi, M. Prakash, and K. K. Dhawan. "Fault tolerance-genetic algorithm for grid task scheduling using check point." Grid and Cooperative Computing, 2007. GCC 2007. Sixth International Conference on. IEEE, 2007.
[33] Qu, H., Mashayekhi, O., Terei, D., & Levis, P. (2016). Canary: A Scheduling Architecture for High Performance Cloud Computing. arXiv preprint arXiv:1602.01412.
[34] Sajedi, Hedieh, and Maryam Rabiee. "A metaheuristic algorithm for job scheduling in grid computing." International Journal of Modern Education and Computer Science 6.5 (2014): 52.
[35] Sheikhalishahi, M., Ebrahimipour, V., Shiri, H., Zaman, H., & Jeihoonian, M. (2013). A hybrid GA–PSO approach for reliability optimization in redundancy allocation problem. The International Journal of Advanced Manufacturing Technology, 68(1-4), 317-338.
[36] Singh, S., & Chana, I. (2015). QRSF: QoS-aware resource scheduling framework in cloud computing. The Journal of Supercomputing, 71(1), 241-292.
[37] Singh, Sukhpal, and Inderveer Chana. "Energy based efficient resource scheduling: a step towards green computing." Int J Energy Inf Commun 5.2 (2014): 35-52.
[38] Tao, F., Zhang, L., Venkatesh, V.C., Luo, Y. and Cheng, Y., 2011. Cloud manufacturing: a computing and service-oriented manufacturing model. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 225(10), pp.1969-1976.
[39] Vigneswari, T., and Ma Maluk Mohamed. "Optimal GridScheduling Using Improved Artificial Bee Colony Algorithm." International Journal of Computer, Electrical, Automation, Control and Information Engineering 8 (2014).
[40] Wang, Lizhe, et al. "Energy-aware parallel task scheduling in a cluster." Future Generation Computer Systems 29.7 (2013): 1661-1670.
[41] Xu, Yuming, Kenli Li, Jingtong Hu, and Keqin Li. "A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues." Information Sciences 270 (2014): 255-287
[42] Yang, Chao-Tung, et al. "Well-balanced allocation strategy for multi-cluster computing environments." Future Trends of Distributed Computing Systems, 2008. FTDCS`08. 12th IEEE International Workshop on. IEEE, 2008.
[43] YING, Chang-tian, Jiong YU, and Xing-yao YANG. "Energy-aware task scheduling algorithms in cloud computing [J]." Microelectronics & Computer 5 (2012): 044.
[44] Zhao, Jianfeng, and Hongze Qiu. "Genetic algorithm and ant colony algorithm based Energy-Efficient Task Scheduling." Information Science and Technology (ICIST), 2013 International Conference on. IEEE, 2013.