Nasim Soltani Soulegan; Behrang Barekatain; Behzad Soleimani Neysiani

MTC: Minimizing Time and Cost of Cloud Task Scheduling based on Customers and Providers Needs using Genetic Algorithm

Full Text (PDF, 565KB), PP.38-51

Views: 0 Downloads: 0

Author(s)

Nasim Soltani Soulegan ^1,* Behrang Barekatain ^2,3 Behzad Soleimani Neysiani ^4,5

1. Department of Software Engineering, Allame Naeini Higher Education Institute, Naein, Isfahan, Iran

2. Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

3. Big Data Research Center, Najafabad Branch, Islamic Azad University, Najafabad, Iran

4. Department of Software Engineering, Isfahan (Khorasgan) Branch, Islamic Azad University, Isfahan, Isfahan, Iran

5. Department of Research & Development, Iranian Training Saba Institute, Isfahan, Isfahan, Iran

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2021.02.03

Received: 10 Dec. 2020 / Revised: 11 Jan. 2021 / Accepted: 19 Feb. 2021 / Published: 8 Apr. 2021

Index Terms

Cloud Computing, Task Scheduling, Genetic Algorithm, Multi-objective Optimization of Weight, Resource Utility

Abstract

Cloud computing is considered a pattern for distributed and heterogeneous computing derived from many resources, and requests aim to share resources. Recently, cloud computing is graded among the top best technologies globally, which must be scheduled favorably to maximize providers’ profit and improve service quality for their customers. Scheduling specifies how users’ requests are assigned to virtual machines, and it plays a vital role in the efficiency and capability of the system. Its objective is to have a throughput or complete jobs in minimum time and the highest standard. Scheduling jobs in heterogeneous distributed systems is an NP-hard polynomial indecisive problem that is not solvable in polynomial time for real-time scheduling. The time complexity of jobs is growing exponentially, and this problem has a considerable effect on the quality of cloud services and providers’ efficiencies. The optimization of scheduling-related parameters using heuristic and meta-heuristic algorithms can reduce the search space complexity and execution time. This study intends to represent a fitness function to minimize time and cost parameters. The proposed method uses a multi-purposed weighted genetic algorithm that provides six basic parameters: utility, task execution cost, response time, wait time, Makespan, and throughput to provide comprehensive optimization. The proposed approach improved response and wait times, throughput, Makespan, and utility 16, 9, 7, 8 percentages, respectively, by only a one cost unit reduction, which is dispensable. As a result, both providers and users will experience better services. The statistical tests show that the achieved improvement is valid for 94% of experiments.

Cite This Paper

Nasim Soltani Soulegan, Behrang Barekatain, Behzad Soleimani Neysiani, "MTC: Minimizing Time and Cost of Cloud Task Scheduling based on Customers and Providers Needs using Genetic Algorithm", International Journal of Intelligent Systems and Applications(IJISA), Vol.13, No.2, pp.38-51, 2021. DOI:10.5815/ijisa.2021.02.03

Reference

[1]M. Armbrust et al., "A view of cloud computing," Communications of the ACM, vol. 53, no. 4, pp. 50-58, 2010.
[2]N. Soltani, H. Moie Emamqeysi, M. Robati, and M. Davarpanah, "A Review of Methods for Resource Allocation and Operational Framework in Cloud Computing," Journal of Advances in Computer Engineering and Technology, 2017.
[3]A. Marinos and G. Briscoe, "Community cloud computing," in Cloud Computing: Springer, 2009, pp. 472-484.
[4]M. Haynie, "Enterprise cloud services: Deriving business value from Cloud Computing," Micro Focus, Tech. Rep, 2009.
[5]V. Kumar, A. A. Laghari, S. Karim, M. Shakir, and A. A. Brohi, "Comparison of fog computing & cloud computing," Int. J. Math. Sci. Comput, vol. 1, pp. 31-41, 2019.
[6]M. Agarwal and G. M. S. Srivastava, "Cloud computing: A paradigm shift in the way of computing," International Journal of Modern Education and Computer Science, vol. 9, no. 12, pp. 38-48, 2017.
[7]Z.-H. Zhan, X.-F. Liu, Y.-J. Gong, J. Zhang, H. S.-H. Chung, and Y. Li, "Cloud computing resource scheduling and a survey of its evolutionary approaches," ACM Computing Surveys (CSUR), vol. 47, no. 4, p. 63, 2015.
[8]A. K. Jayswal, "Efficient Task Allocation for Cloud Using Bat Algorithm," in 2020 Sixth International Conference on Parallel, Distributed and Grid Computing (PDGC), 2020: IEEE, pp. 186-190.
[9]A. Radulescu and A. J. Van Gemund, "Fast and effective task scheduling in heterogeneous systems," in Heterogeneous Computing Workshop, 2000.(HCW 2000) Proceedings. 9th, 2000: IEEE, pp. 229-238.
[10]K. Naik, G. M. Gandhi, and S. Patil, "Multiobjective virtual machine selection for task scheduling in cloud computing," in Computational Intelligence: Theories, Applications and Future Directions-Volume I: Springer, 2019, pp. 319-331.
[11]M. A. Elaziz, S. Xiong, K. Jayasena, and L. Li, "Task scheduling in cloud computing based on hybrid moth search algorithm and differential evolution," Knowledge-Based Systems, vol. 169, pp. 39-52, 2019.
[12]N. Bansal and A. K. Singh, "Grey Wolf Optimized Task Scheduling Algorithm in Cloud Computing," in Frontiers in Intelligent Computing: Theory and Applications: Springer, 2020, pp. 137-145.
[13]Rashid G. Alakbarov, "Method for Effective Use of Cloudlet Network Resources", International Journal of Computer Network and Information Security, Vol.12, No.5, pp.46-55, 2020.
[14]N. Soltani, B. Barekatain, and B. Soleimani Neysiani, "Job Scheduling based on Single and Multi Objective Meta- Heuristic Algorithms in Cloud Computing: A Survey," Conference: International Conference on Information Technology, Communications and Telecommunications (IRICT), , vol. 2, no. At Iran, Tehran, March 2016.
[15]Nasim Soltani, Behzad Soleimani, Behrang Barekatain,"Heuristic Algorithms for Task Scheduling in Cloud Computing: A Survey", International Journal of Computer Network and Information Security, Vol.9, No.8, pp.16-22, 2017.
[16]P. Singh, M. Dutta, and N. Aggarwal, "A review of task scheduling based on meta-heuristics approach in cloud computing," Knowledge and Information Systems, pp. 1-51, 2017.
[17]B. L. Muhammad-Bello and M. Aritsugi, "Robust deadline-constrained resource provisioning and workflow scheduling algorithm for handling performance uncertainty in iaas clouds," in Companion Proceedings of the10th International Conference on Utility and Cloud Computing, 2017, pp. 29-34.
[18]S. Mohanty, S. C. Moharana, H. Das, and S. C. Satpathy, "QoS Aware Group-Based Workload Scheduling in Cloud Environment," in Data Engineering and Communication Technology: Springer, 2020, pp. 953-960.
[19]M. I. Alam, M. Pandey, and S. S. Rautaray, "A comprehensive survey on cloud computing," International Journal of Information Technology and Computer Science, vol. 7, no. 2, pp. 68-79, 2015.
[20]B. L. Muhammad-Bello and M. Aritsugi, "A Robust Algorithm for Deadline Constrained Scheduling in IaaS Cloud Environment," Ieice Transactions on Information and Systems, vol. 101, no. 12, pp. 2942-2957, 2018.
[21]Z.-H. Liang, D. Wang, F. Dai, and Y.-X. Huang, "Research of SLA-Based Multitask-User-Requests Admission Control and Related Algorithm for the Cloud Service Provider," Current Journal of Applied Science and Technology, pp. 1-11, 2017.
[22]K. R. Babu and P. Samuel, "Enhanced Bee Colony Algorithm for Efficient Load Balancing and Scheduling in Cloud," in Innovations in Bio-Inspired Computing and Applications: Springer, 2016, pp. 67-78.
[23]J. Ma, W. Li, T. Fu, L. Yan, and G. Hu, "A novel dynamic task scheduling algorithm based on improved genetic algorithm in cloud computing," in Wireless Communications, Networking and Applications: Springer, 2016, pp. 829-835.
[24]S. Bilgaiyan, S. Sagnika, and M. Das, "A Multi-objective Cat Swarm Optimization Algorithm for Workflow Scheduling in Cloud Computing Environment," in Intelligent Computing, Communication and Devices: Springer, 2015, pp. 73-84.
[25]F. Ramezani, J. Lu, J. Taheri, and F. K. Hussain, "Evolutionary algorithm-based multi-objective task scheduling optimization model in cloud environments," World Wide Web, vol. no. 6, pp. 1-21, 2015.
[26]A. A. Beegom and M. Rajasree, "Genetic Algorithm Framework for Bi-objective Task Scheduling in Cloud Computing Systems," in Distributed Computing and Internet Technology: Springer, 2015, pp. 356-359.
[27]F. A. I. C. COMPUTING, "A Load Balancing Model Using Firefly Algorithm in Cloud Computing," Journal of Computer Science, vol. 10, no. 7, pp. 1156-1165, 2014.
[28]L. Singh and S. Singh, "A Genetic Algorithm for Scheduling Workflow Applications in Unreliable Cloud Environment," in Recent Trends in Computer Networks and Distributed Systems Security: Springer, 2014, pp. 139-150.
[29]H. Zhao and W. Chenyu, "A Dynamic Dispatching Method of Resource Based on Particle Swarm Optimization for Cloud Computing Environment," in Web Information System and Application Conference (WISA), 2013 10th, 2013: IEEE, pp. 351-354.
[30]D. B. L.D and P. Venkata Krishna, "Honey bee behavior inspired load balancing of tasks in cloud computing environments," Applied Soft Computing, vol. 13, no. 5, pp. 2292-2303, 2013/05/01 2013, doi: 10.1016/j.asoc.2013.01.025.
[31]N. Netjinda, B. Sirinaovakul, and T. Achalakul, "Cost optimization in cloud provisioning using particle swarm optimization," in 9th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), , 2012, vol. 9: IEEE, pp. 1-4, doi: 10.1109/ECTICon.2012.6254298.
[32]A. A. Beegom and M. Rajasree, "A Particle Swarm Optimization Based Pareto Optimal Task Scheduling in Cloud Computing," in Advances in Swarm Intelligence: Springer, 2014, pp. 79-86.
[33]S. H. Jang, T. Y. Kim, J. K. Kim, and J. S. Lee, "The study of genetic algorithm-based task scheduling for cloud computing," International Journal of Control and Automation, vol. 5, no. 4, pp. 157-162, 2012.
[34]M. Srinivas and L. M. Patnaik, "Genetic algorithms: A survey," Computer, vol. 27, no. 6, pp. 17-26, 06 August 2002 1994, doi: 10.1109/2.294849.
[35]F. Yiqiu, X. Xia, and G. Junwei, "Cloud Computing Task Scheduling Algorithm Based on Improved Genetic Algorithm," in IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), 2019, vol. 3: IEEE, pp. 852-856, doi: 10.1109/ITNEC.2019.8728996.
[36]R. Toemeh and S. Arumugam, "Breaking Transposition Cipher with Genetic Algorithm," Elektronika ir Elektrotechnika, vol. 79, no. 7, pp. 75-78, 2015.
[37]T. İnkaya and M. Akansel, "Coordinated scheduling of the transfer lots in an assembly-type supply chain: A genetic algorithm approach," Journal of Intelligent Manufacturing, vol. 28, no. 4, pp. 1005-1015, 2017.
[38]A. Ganjehkaviri, M. M. Jaafar, S. Hosseini, and H. Barzegaravval, "Genetic algorithm for optimization of energy systems: Solution uniqueness, accuracy, Pareto convergence and dimension reduction," Energy, vol. 119, pp. 167-177, 2017.
[39]B. Soleimani Neysiani, N. Soltani, R. Mofidi, and M. H. Nadimi-Shahraki, "Improve performance of association rule-based collaborative filtering recommendation systems using genetic algorithm," International Journal of Information Technology and Computer Science, vol. 11, no. 2, pp. 48-55, 2019/2/6 2019.
[40]H. Hatami Varzaneh, B. Soleimani Neysiani, H. Ziafat, and N. Soltani, "Recommendation systems based on association rule mining for a target object by evolutionary algorithms," Emerging Science Journal, vol. 2, no. 2, pp. 100-107, 2018, doi: 10.28991/esj-2018-01133.
[41]S. Doostali, S. M. Babamir, M. Shiralizadeh Dezfoli, and B. Soleimani Neysiani, "IoT-Based Model in Smart Urban Traffic Control: Graph theory and Genetic Algorithm," in 2020 11th International Conference on Information and Knowledge Technology (IKT), 2020: IEEE, pp. 119-121.
[42]B. Soleimani Neysiani, N. Soltani, and S. Ghezelbash, "A framework for improving find best marketing targets using a hybrid genetic algorithm and neural networks," in IEEE 2nd International Conference on Knowledge-Based Engineering and Innovation (KBEI), Tehran, Iran, 2015, vol. 2: IEEE, pp. 733-738, doi: 10.1109/KBEI.2015.7436136. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/7436136/
[43]X. Evers, W. H. CSG, R. B. CSG, I. Herschberg, D. Epema, and J. de Jongh, "A literature study on scheduling in distributed systems," Delft University of Technology, 1992.
[44]Amazon. "Amazon EC2 Pricing." https://aws.amazon.com/ec2/pricing/ (accessed 1/15/2021.
[45]S. K. Garg, S. Versteeg, and R. Buyya, "A framework for ranking of cloud computing services," Future Generation Computer Systems- The International Journal of eScience, vol. 29, no. 4, pp. 1012-1023, 2013.
[46]A. Jain and V. Kanhangad, "Exploring orientation and accelerometer sensor data for personal authentication in smartphones using touchscreen gestures," Pattern recognition letters, vol. 68, no. 2 pp. 351-360, 2015.
[47]K. J. Preacher and A. F. Hayes, "SPSS and SAS procedures for estimating indirect effects in simple mediation models," Behavior research methods, instruments, & computers, vol. 36, no. 4, pp. 717-731, 2004.
[48]H. S. Al-Olimat, R. C. Green II, and M. Alam, "Cloudlet Scheduling with Population Based Metaheuristics," in IEEE 2015 Fifth International Conference on Communication Systems and Network Technologies, 2015 2015.
[49]D. Feitelson. "Parallel Workloads Archive Dataset." http://www.cs.huji.ac.il/labs/parallel/workload/ (accessed 1/15/2021.
[50]D. G. Feitelson, D. Tsafrir, and D. Krakov, "Experience with using the Parallel Workloads Archive," Journal of Parallel and Distributed Computing, vol. 74, no. 10, pp. 2967-2982, 2014/10/01 2014, doi: 10.1016/j.jpdc.2014.06.013.
[51]Z. Wu, Z. Ni, L. Gu, and X. Liu, "A revised discrete particle swarm optimization for cloud workflow scheduling," in Computational Intelligence and Security (CIS), 2010 International Conference on, 2010: IEEE, pp. 184-188.
[52]S. Kaur and A. Verma, "An efficient approach to genetic algorithm for task scheduling in cloud computing environment," International Journal of Information Technology and Computer Science, vol. 4, no. 10, pp. 74-79, 2012.

International Journal of Intelligent Systems and Applications (IJISA)