Abstract
Job scheduling is one of the most important research problems in distributed systems, particularly cloud environments/computing. The dynamic and heterogeneous nature of resources in such distributed systems makes optimum job scheduling a non-trivial task. Maximal resource utilization in cloud computing demands/necessitates an algorithm that allocates resources to jobs with optimal execution time and cost. The critical issue for job scheduling is assigning jobs to the most suitable resources, considering user preferences and requirements. In this paper, we present a hybrid approach called FUGE that is based on fuzzy theory and a genetic algorithm (GA) that aims to perform optimal load balancing considering execution time and cost. We modify the standard genetic algorithm (SGA) and use fuzzy theory to devise a fuzzy-based steady-state GA in order to improve SGA performance in term of makespan. In details, the FUGE algorithm assigns jobs to resources by considering virtual machine (VM) processing speed, VM memory, VM bandwidth, and the job lengths. We mathematically prove our optimization problem which is convex with well-known analytical conditions (specifically, Karush–Kuhn–Tucker conditions). We compare the performance of our approach to several other cloud scheduling models. The results of the experiments show the efficiency of the FUGE approach in terms of execution time, execution cost, and average degree of imbalance.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Mezmaz, M., et al.: A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems. J. Parallel Distrib. Comput. 71(11), 1497–1508 (2011)
Armbrust, M., et al.: A view of cloud computing. Commun ACM 53(4), 50–58 (2010)
Dikaiakos, M.D., Pallis, G., Katsaros, D., Mehra, P., Vakali, A.: Cloud computing: distributed Internet computing for IT and scientific research. IEEE Internet Comput. 13(5), 10–13 (2009)
Rimal, B. P., Eunmi, C., Lumb, I. A.: Taxonomy and Survey of Cloud Computing Systems. In: Fifth International Joint Conference on INC, IMS and IDC, Seoul, 2009, pp. 44–51.
Li, Q., Yike, G.: Optimization of resource scheduling in cloud computing. IEEE SYNASC, Timisoara (2010)
Cordeschi, N., Shojafar, M., Baccarelli, E.: Energy-saving self-configuring networked data centers. Computer Networks 57(17), 3479–3491 (2013)
Goldberg, D.E., Holland, J.H.: Genetic algorithms and machine learning. Mach. Learn. 3(2–3), 95–99 (1988)
Vas, P.: Artificial-intelligence-based electrical machines and drives: application of fuzzy, neural, fuzzy-neural, and genetic-algorithm-based techniques. Oxford University Press, Oxford (1999)
T. Takagi, M. Sugeno, Fuzzy identification of systems and its applications to modeling and control. In: IEEE Transactions on Systems, Man and Cybernetics, SMC- 15(1)1 116–132 (1985).
Javanmardi, S., Shojafar, M., Amendola, D., Cordeschi, N., Liu, H., Abraham, A.: Hybrid job scheduling algorithm for cloud computing environment. Adv. Intell. Syst. Comput. 303, 43–52 (2014)
Javanmardi, S., Shojafar, M., Shariatmadari, Sh, Abawajy, J.H., Singhal, M.: PGSW-OS: a novel approach for resource management in a semantic web operating system based on a P2P grid architecture. The Journal of Supercomputing 69(2), 955–975 (2014)
Randles, M., Lamb, D., Taleb-Bendiab, A.: A comparative study into distributed load balancing algorithms for cloud computing. In: IEEE Advanced Information Networking and Applications Workshops (WAINA), pp. 551–556. WA, Perth (2010)
X. Baowen, G. Yu, Ch. Zhenqiang, K. R. P. H. Leung, Parallel genetic algorithms with schema migration. In: Computer Software and Applications Conference (COMPSAC), pp. 879–884 (2002).
Zhongni, Z., Wang, R., Hai, Z., Xuejie, Z.: An approach for cloud resource scheduling based on Parallel Genetic Algorithm. In: ICCRD IEEE Shanghai, China, 2, 444–447 (2011)
Hu, J., Jianhua, G., Guofei, S., Tianhai, Z.: A Scheduling Strategy on Load Balancing of Virtual Machine Resources in Cloud Computing Environment. In: IEEE PAAP. pp. 89–96. Dalian, China (2010)
Singh, R.M., Sendhil Kumar, K.S., Jaisankar, N.: Comparison of probabilistic optimization algorithms for resource scheduling in cloud computing environment. Int. J. Eng. Technol. 5(2), 1419–1427 (2013)
Mamdani, E.H.: Application of fuzzy algorithms for control of simple dynamic plant. In: Proceedings of the Institution of Electrical Engineer, IET Digital Library 121(12), 1585–1588 (1974)
Vignesh, V., Sendhil, K.S., Jaisankar, N.: Resource Management and Scheduling in Cloud Environment. Int. J. Sci. Res. Publ. 3(6), 1–6 (2013)
Beloglazov, A., Buyya, R.: Energy Efficient Resource Management in Virtualized Cloud Data Centers. In: 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGRID), Melbourne, Australia, pp. 826–831 (2010).
Chen, S., Wu, J., Lu, Z.: A Cloud Computing Resource Scheduling Policy Based on Genetic Algorithm with Multiple Fitness. In: IEEE 12th International Conference on Computer and Information Technology, Chengdu, pp. 177–184 (2012)
Sh. Sawant, A Genetic Algorithm Scheduling Approach for Virtual Machine Resources in a Cloud Computing Environment, Msc Thesis, (2011)
Kaur, S., Verma, A.: An efficient approach to genetic algorithm for job scheduling in cloud computing environment. Int. J. Info. Technol. Comput. Sci. 4(10), 74–79 (2012)
Kumar, V.V., Dinesh, K.: Job scheduling using fuzzy neural network algorithm in cloud environment. Int. J. Man Mach. Interface 2(1), 1–6 (2012)
Calheiros, R.N., Ranjan, R., Beloglazov, A., De Rose, C.A.F., Buyya, R.: CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Software: Pract. Experience 41(1), 23–50 (2011)
Abirami, S.P., Ramanathan, Sh: Linear scheduling strategy for resource allocation in cloud environment. International Journal on Cloud Computing: Services and Architecture (IJCCSA) 2(1), 9–17 (2012)
Foster, I., Zhao, Y., Raicu, I., Lu, S.: Cloud Computing and Grid Computing 360-Degree Compared, Grid Computing Environments Workshop (GCE ’08), pp. 1–10. Austin, TX, (2008)
Beloglazov, A., Buyya, R.: Managing Overloaded Hosts for Dynamic Consolidation of Virtual Machines in Cloud Data Centers under Quality of Service Constraints. IEEE Trans. Parallel Distrib. Syst. 24(7), 1366–1379 (2013)
Buyya, R., Broberg, J., Goscinski, A.M.: Cloud computing: principles and paradigms. John Wiley and Sons, New York (2011)
Joyent official Site. http://www.joyent.com/. Accessed 2014
Microsoft’s Windows Azure official Site. https://azure.microsoft.com/. Accessed 2014
Rackspace official Site. www.rackspace.com/. Accessed 2014
Dadgar, M., Hosseini, M.V., Merati, A.A., Sarkheyli, A.: Comparison of Mamdani and Sugeno fuzzy inference system in prediction of residual frieze effect of frieze carpet yarns. Tekstilna Industrija 61(2), 16–25 (2013)
Javanmardi, S., Shariatmadari, Sh, Mosleh, M.: A novel decentralized fuzzy based approach for grid resource discovery. Int. J. Innov. Comput. 3(1), 23–32 (2013)
Javanmardi, S., Shojafar, M., Shariatmadari, Sh, Ahrabi, S.S.: FR TRUST: a fuzzy reputation based model for Trust management in semantic P2P grids. Int. J. Grid Utility Comput. 6(1), 57–66 (2015)
Medhat, A.T., Ashraf, E.S., Arabi, E.K., Fawzy, A.T.: Hybrid job scheduling algorithm for cloud computing environment. Adv. Intell. Syst. Comput. 303, 43-52 (2014), Atlantis Press, pp. 169–172 (2013)
Du, D.-Z., Ko, K.-I.: Theory of computational complexity. John Wiley and Sons, New York (2011)
Ephzibah, E.P.: Time complexity analysis of genetic-fuzzy system for disease diagnosis, Advanced Computing, 2(4), 23–31 (2011)
Lotfi Zadeh, A.: A computational approach to fuzzy quantifiers in natural languages. Computers Math. Appl. 9(1), 149–184 (1983)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Shojafar, M., Javanmardi, S., Abolfazli, S. et al. FUGE: A joint meta-heuristic approach to cloud job scheduling algorithm using fuzzy theory and a genetic method. Cluster Comput 18, 829–844 (2015). https://doi.org/10.1007/s10586-014-0420-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10586-014-0420-x