Cost effective hybrid genetic algorithm for workflow scheduling in cloud
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2022.3.08Keywords:
cloud computing, cost effective, genetic algorithm, metaheuristic algorithm, predict earliest finish time, Workflow schedulingAbstract
Cloud computing plays a significant role in everyone’s lifestyle by snugly linking communities, information, and trades across the globe. Due to its NP-hard nature, recognizing the optimal solution for workflow scheduling in the cloud is a challenging area. We proposed a hybrid meta-heuristic cost-effective load-balanced approach to schedule workflow in a heterogeneous environment. Our model is based on a genetic algorithm integrated with predict earliest finish time (PEFT) to minimize makespan. Instead of assigning the task randomly to a virtual machine, we apply a greedy strategy that assigns the task to the lowest-loaded virtual machine. After completing the mutation operation, we verify the dependency constraint instead of each crossover operation, which yields a better outcome. The proposed model incorporates the virtual machine’s performance variance as well as acquisition delay, which concedes the minimum makespan and computing cost. One of the most astounding aspects of our cost-effective hybrid genetic algorithm (CHGA) is its capacity to anticipate by creating an optimistic cost table (OCT) while maintaining quadratic time complexity. Based on the results of our meticulous experiments on some real-world workflow benchmarks and comprehensive analysis of some recently successful scheduling algorithms, we concluded that the performance of our CHGA is melodious. CHGA is 14.58188%, 11.40224%, 11.75306%, and 9.78841% cheaper than standard Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), Cost Effective Genetic Algorithm(CEGA), and Cost-Effective Load-balanced Genetic Algorithm (CLGA), respectively.
References
S. Ibrahim, B. He, and H. Jin, “Towards pay-as-you-consume cloud computing,” Proc. 2011 IEEE Int. Conf. Serv. Comput. SCC 2011, pp. 370–377. doi: 10.1109/SCC.2011.38.
R. Buyya, C.S. Yeo, S. Venugopal, J. Broberg, and I. Brandic, “Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility,” Futur. Gener. Comput. Syst., 25(6), pp. 599–616, 2009. doi: 10.1016/j.future.2008.12.001.
A.S. Kulik, A.G. Chukhray, and O.V. Havrylenko, “Information technology for creating intelligent computer programs for training in algorithmic tasks. Part 1: mathematical foundations,” System Research & Information Technologies, no. 4, 2021. doi: 10.20535/SRIT.2308-8893.2021.4.02
S. Singhal and J. Grover, “Hybrid biogeography algorithm for reducing power consumption in cloud computing,” 2017 Int. Conf. Adv. Comput. Commun. Informatics, ICACCI 2017, pp. 121–124. doi: 10.1109/ICACCI.2017.8125827.
S. Singhal and J. Patel, “Load balancing scheduling algorithm for concurrent workflow,” Comput. Informatics, 37(2), pp. 311–326, 2018. doi: 10.4149/cai_2018_2_311.
G. Dalin and V. Radhamani, “IRIAL-an improved approach for VM migrations in cloud computing,” International Journal of Advanced Technology and Engineering Exploration, 2018 July 1, 5(44), pp. 165–171.
J. Yu and R. Buyya, “A taxonomy of workflow management systems for Grid computing,” J. Grid Comput., 3(3–4), pp. 171–200, 2005. doi: 10.1007/s10723-005-9010-8.
D. Malhotra, “An adaptive threshold policy for host overload detection in cloud data centre,” International Journal of Advanced Technology and Engineering Exploration, 2021 Oct 1, 8(83), pp. 1315–1335.
S.K. Bothra and S. Singhal, “Nature-inspired metaheuristic scheduling algorithms in cloud: A systematic review,” Sci. Tech. J. Inf. Technol. Mech. Opt., 21(4), pp. 463–472, 2021. doi: 10.17586/2226-1494-2021-21-4-463-472.
S.K. Bothra, S. Singhal, and H. Goyal, “Deadline-constrained cost-effective load-balanced improved genetic algorithm for workflow scheduling,” Int. J. Inf. Technol. Web Eng., 16(4), pp. 1–34, 2021. doi: 10.4018/IJITWE.2021100101.
L.F. Bittencourt, R. Sakellariou, and E.R.M. Madeira, “DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm,” Proc. 18th Euromicro Conf. Parallel, Distrib. Network-Based Process, PDP 2010, pp. 27–34. doi: 10.1109/PDP.2010.56.
V.M. Sineglazov, K.D. Riazanovskiy, and O.I. Chumachenko, “Multicriteria conditional optimization based on genetic algorithms,” System Research & Information Technologies, no. 3, pp. 89–104, 2020. doi: 10.20535/SRIT.2308-8893.2020.3.07
Dorigo and C. Blum, “Ant colony optimization theory: A survey,” Theoretical Computer Science, 344, pp. 243–278, 2005. doi: 10.1016/j.tcs.2005.05.020.
S.K. Patel and A.K. Sharma, “Improved PSO based job scheduling algorithm for resource management in grid computing,” International Journal of Advanced Technology and Engineering Exploration, 2019 May 1, 6(54), pp. 152–161.
D. Karaboga and B. Akay, “A modified Artificial Bee Colony (ABC) algorithm for constrained optimization problems,” Appl. Soft Comput. J., 11(3), pp. 3021–3031, 2011. doi: 10.1016/j.asoc.2010.12.001.
Z. Wu, Z. Ni, and L. Gu, “A Revised Discrete Particle Swarm Optimization for Cloud Workflow Scheduling,” Proceedings of the 2010 International Conference on Computational Intelligence and Security, pp. 184–188. doi: 10.1109/CIS.2010.46.
S. Pandey, L. Wu, S.M. Guru, and R. Buyya, “A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments,” Proc. Int. Conf. Adv. Inf. Netw. Appl. AINA, 2010, pp. 400–407. doi: 10.1109/AINA.2010.31.
F. Engineering, “Scheduling Workflow in Cloud Computing Based on Ant Colony Optimization Algorithm,” 2013 Sixth International Conference on Business Intelligence and Financial Engineering (BIFE), pp. 57–61. doi: 10.1109/BIFE.2013.14.
Z. Chen and K. Du, “Deadline Constrained Cloud Computing Resources Scheduling for Cost Optimization based on Dynamic Objective Genetic Algorithm,” Evolutionary Computation (CEC), 2015 IEEE Congress on, IEEE, 2015, pp. 708–714.
J. Meena, M. Kumar, and M. Vardhan, “Cost Effective Genetic Algorithm for Workflow Scheduling in Cloud Under Deadline Constraint,” IEEE Access, 4, pp. 5065–5082, 2016. doi: 10.1109/ACCESS.2016.2593903.
M. Mollajafari and H.S. Shahhoseini, “A cost-optimized GA-based heuristic for scheduling time-constrained workflow applications in infrastructure clouds using an innovative feasibility-assured decoding mechanism,” J. Inf. Sci. Eng., 32(6), pp. 1541–1560, 2016. doi: 10.1688/JISE.2016.32.6.8.
Gupta, V. Gajera, P.K. Jana, and I.S. Member, “An Effective Multi-Objective Work-flowScheduling in Cloud Computing: A PSO based Approach, “Ninth International Conference on Contemporary Computing”, 2016.
Y. Moon, H. Yu, J.M. Gil, and J. Lim, “A slave ants based ant colony optimization algorithm for task scheduling in cloud computing environments,” Human-centric Comput. Inf. Sci., 2017. doi: 10.1186/s13673-017-0109-2.
A. You, M.A.Y. Be, and I. In, “Task scheduling based on ant colony optimization in cloud environment,” AIP Conference Proceedings, vol. 1834, iss. 1, 040039, 2017. doi: 10.1063/1.4981635.
B. Xiang, B. Zhang, and L. Zhang, “Greedy Ant: Ant Colony System-Inspired Workflow Scheduling for Heterogeneous Computing,” IEEE Access, 2017. doi: 10.1109/ACCESS.2017.2715279.
S.K. Sonkar and M.U. Kharat, “Load prediction analysis based on virtual machine execution time using optimal sequencing algorithm in cloud federated environment,” Int. J. Inf. Technol., 11(2), pp. 265–275, 2019. doi: 10.1007/s41870-019-00282-1.
C. Yan, M.X. Li, and W. Liu, “Application of improved genetic algorithm in function optimization,” J. Inf. Sci. Eng., 35(6), pp. 1299–1309, 2019. doi: 10.6688/JISE.201911_35(6).0008.
Al-Azzawi, “Evaluation of Genetic Algorithm Optimization in Machine Learning,” J. Inf. Sci. Eng., 36(2), 2020.
A. Belgacem and K. Beghdad-Bey, “Multi-objective workflow scheduling in cloud computing: trade-off between makespan and cost,” Cluster Computing, 25(1), pp. 579–595, 2022.
H. Arabnejad and J.G. Barbosa, “List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table,” IEEE Transactions on Parallel and Distributed Systems, 25(3), pp. 682–694, 2014.
Z. Hill and M. Humphrey, “A quantitative analysis of high performance computing with Amazon’s EC2 infrastructure: The death of the local cluster?” Proc. IEEE/ACM Int. Work. Grid Comput., pp. 26–33, 2009. doi: 10.1109/GRID.2009.5353067.
Amazon Elastic Block Store. Available: https://aws.amazon.com/ebs/. Accessed 22 July, 2020.
M. Naderan, “Review methods for breast cancer detection using artificial intelligence and deep learning methods,” System Research & Information Technologies, no. 1, 2021. doi: 10.20535/SRIT.2308-8893.2021.1.08
I.V. Beyko, J.V. Spivak, and O.V. Furtel, “Generalized solutions of optimal control problems,” System Research & Information Technologies, no. 4, 2020, pp. 104–114. doi: 10.20535/SRIT.2308-8893.2020.4.08.
