Abstract

The effectiveness of genetic algorithms (GA) can be improved by adjusting genetic operators and integrating an efficient heuristic. These enhancements are integrated into the suggested enhanced hybrid genetic algorithm (e-HGA). The e-HGA begins with an initial population that includes a solution derived from a heuristic, which serves as a guiding point toward achieving an optimal makespan solution. The proposed e-HGA was evaluated in this work for two degrees of fitness, which qualified a chromosome and a gene to be preferred above their other counterpart in a data population. To preserve population variety and avoid premature convergence, parents were randomly picked from the population and crossed over (mated) to generate offspring that were then modified by introducing random geneLists. The conventional hybrid genetic algorithm (HGA) and e-HGA required 9.95 s and 9.148 s, respectively, for task completion. Increasing the number of cloudlets to 40, the conventional HGA and e-HGA took 10.674 s and 9.558 s, respectively. When 50 cloudlets were assigned to 10 virtual machines (VMs) the conventional HGA completed the task in 11.01 s, while the e-HGA required 12.863 s. Subsequently, with 60 cloudlets on 10 VMs, the conventional HGA and e-HGA achieved task completion in 14.74 s and 14.242 s, respectively. For 70 cloudlets on 10 VMs, the conventional HGA and e-HGA required 15.38 s and 17.25 s, respectively. The results contributed to research on task scheduling optimization by scheduling task operations to reduce cost, enable efficient resource allocation, and manage time.

Keyword

Genetic algorithm, Enhanced hybrid genetic algorithm, Hybrid genetic algorithm, Scheduling, Makespan, GeneLists.

Cite this article

Busayo AT, Mohamad Z, Mahiddin NA, Wan Nik WN.Workflow scheduler optimization using an enhanced hybrid genetic algorithm. International Journal of Advanced Technology and Engineering Exploration. 2024;11(111):119-144. DOI:10.19101/IJATEE.2023.10102108

Refference

[1]Sun Q, Chien S, Hu D, Chen X. Optimizing customized transit service considering stochastic bus arrival time. Journal of Advanced Transportation. 2021; 2021:1-9.

[2]Tumuluru JS, Mcculloch R. Application of hybrid genetic algorithm routine in optimizing food and bioengineering processes. Foods. 2016; 5(4):1-13.

[3]Sulaiman M, Halim Z, Waqas M, Aydın D. A hybrid list-based task scheduling scheme for heterogeneous computing. The Journal of Supercomputing. 2021; 77:10252-88.

[4]Kaya SH, Corneille KV, Yassa S, Romain O, Etienne NM, Laurent BI. Industry 4.0 and industrial workflow scheduling: a survey. Journal of Industrial Information Integration. 2023: 100546.

[5]Kumari M, Singh V. Breast cancer prediction system. Procedia Computer Science. 2018; 132:371-6.

[6]Liu Y, Liu J, Zhu X, Wei D, Huang X, Song L. Learning task-specific representation for video anomaly detection with spatial-temporal attention. In international conference on acoustics, speech and signal processing 2022 (pp. 2190-4). IEEE.

[7]Karami S, Azizi S, Ahmadizar F. A bi-objective workflow scheduling in virtualized fog-cloud computing using NSGA-II with semi-greedy initialization. Applied Soft Computing. 2024; 151:111142.

[8]Abdel-basset M, Mohamed R, Abd EW, Sharawi M, Sallam KM. Task scheduling approach in cloud computing environment using hybrid differential evolution. Mathematics. 2022; 10(21):1-26.

[9]Zawawi O. Resource-efficient data pre-processing for deep learning (Doctoral Dissertation). Computer, Electrical and Mathematical Science and Engineering (CEMSE) Division. 2024.

[10]Bezdan T, Zivkovic M, Bacanin N, Strumberger I, Tuba E, Tuba M. Multi-objective task scheduling in cloud computing environment by hybridized bat algorithm. Journal of Intelligent & Fuzzy Systems. 2022; 42(1):411-23.

[11]Singh S, Kumar R, Singh D. An empirical investigation of task scheduling and VM consolidation schemes in cloud environment. Computer Science Review. 2023; 50:100583.

[12]Wu Z, Liu X, Ni Z, Yuan D, Yang Y. A market-oriented hierarchical scheduling strategy in cloud workflow systems. The Journal of Supercomputing. 2013; 63:256-93.

[13]Houssein EH, Gad AG, Wazery YM, Suganthan PN. Task scheduling in cloud computing based on meta-heuristics: review, taxonomy, open challenges, and future trends. Swarm and Evolutionary Computation. 2021; 62:100841.

[14]Zhao S, Miao J, Zhao J, Naghshbandi N. A comprehensive and systematic review of the banking systems based on pay-as-you-go payment fashion and cloud computing in the pandemic era. Information Systems and e-Business Management. 2023:1-29.

[15]Concha SL, Monzon BV. Harnessing the potential of emerging technologies to break down barriers in tactical communications. Telecom. 2023; 4(4):709-31.

[16]Huang J. The workflow task scheduling algorithm based on the GA model in the cloud computing environment. Journal of Software. 2014; 9(4):873-80.

[17]Abazari F, Analoui M, Takabi H, Fu S. MOWS: multi-objective workflow scheduling in cloud computing based on heuristic algorithm. Simulation Modelling Practice and Theory. 2019; 93:119-32.

[18]Zhu Z, Zhang G, Li M, Liu X. Evolutionary multi-objective workflow scheduling in cloud. IEEE Transactions on Parallel and Distributed Systems. 2015; 27(5):1344-57.

[19]Alzain MA, Pardede E, Soh B, Thom JA. Cloud computing security: from single to multi-clouds. In 45th Hawaii international conference on system sciences 2012 (pp. 5490-9). IEEE.

[20]Jensen M, Schwenk J, Bohli JM, Gruschka N, Iacono LL. Security prospects through cloud computing by adopting multiple clouds. In 4th international conference on cloud computing 2011 (pp. 565-72). IEEE.

[21]Krishna BH, Kiran S, Murali G, Reddy RP. Security issues in service model of cloud computing environment. Procedia Computer Science. 2016; 87:246-51.

[22]Yasrab R. Platform-as-a-service (PaaS): the next hype of cloud computing. arXiv preprint arXiv:1804.10811. 2018.

[23]Sadeeq MM, Abdulkareem NM, Zeebaree SR, Ahmed DM, Sami AS, Zebari RR. IoT and cloud computing issues, challenges and opportunities: a review. Qubahan Academic Journal. 2021; 1(2):1-7.

[24]Osanaiye O, Chen S, Yan Z, Lu R, Choo KK, Dlodlo M. From cloud to fog computing: a review and a conceptual live VM migration framework. IEEE Access. 2017; 5:8284-300.

[25]Wang L, Von LG, Kunze M, Tao J. Schedule distributed virtual machines in a service oriented environment. In 24th international conference on advanced information networking and applications 2010 (pp. 230-6). IEEE.

[26]Masdari M, ValiKardan S, Shahi Z, Azar SI. Towards workflow scheduling in cloud computing: a comprehensive analysis. Journal of Network and Computer Applications. 2016; 66:64-82.

[27]Żotkiewicz M, Guzek M, Kliazovich D, Bouvry P. Minimum dependencies energy-efficient scheduling in data centers. IEEE Transactions on Parallel and Distributed Systems. 2016; 27(12):3561-74.

[28]Rahman M, Hassan R, Ranjan R, Buyya R. Adaptive workflow scheduling for dynamic grid and cloud computing environment. Concurrency and Computation: Practice and Experience. 2013; 25(13):1816-42.

[29]Bala A, Chana I. A survey of various workflow scheduling algorithms in cloud environment. In 2nd national conference on information and communication technology 2011 (pp. 26-30).

[30]Rodriguez MA, Buyya R. A taxonomy and survey on scheduling algorithms for scientific workflows in IaaS cloud computing environments. Concurrency and Computation: Practice and Experience. 2017; 29(8):e4041.

[31]Vincent FY, Redi AP, Hidayat YA, Wibowo OJ. A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing. 2017; 53:119-32.

[32]Saima GA. Workflow optimization in distributed computing environment for stream-based data processing model/Saima Gulzar Ahmad. Doctoral Dissertation, University of Malaya. 2017.

[33]Gul F, Mir I, Abualigah L, Sumari P. Multi-robot space exploration: an augmented arithmetic approach. IEEE Access. 2021; 9:107738-50.

[34]Daoud MI, Kharma N. A hybrid heuristic–genetic algorithm for task scheduling in heterogeneous processor networks. Journal of Parallel and Distributed Computing. 2011; 71(11):1518-31.

[35]Srikanth M, Kessler JA. Nanotechnology-novel therapeutics for CNS disorders. Nature Reviews Neurology. 2012; 8(6):307-18.

[36]Seemakuthi S, Siriki VA, Lydia EL. A review on various scheduling algorithms. International Journal of Scientific & Engineering Research. 2015; 6:769-79.

[37]Zheng W, Sakellariou R. Budget-deadline constrained workflow planning for admission control. Journal of Grid Computing. 2013; 11(4):633-51.

[38]Zhao L, Ren Y, Sakurai K. Reliable workflow scheduling with less resource redundancy. Parallel Computing. 2013; 39(10):567-85.

[39]Zhong Z, Chen K, Zhai X, Zhou S. Virtual machine-based task scheduling algorithm in a cloud computing environment. Tsinghua Science and Technology. 2016; 21(6):660-7.

[40]Wei XJ, Bei W, Jun L. SAMPGA task scheduling algorithm in cloud computing. In 36th Chinese control conference 2017 (pp. 5633-7). IEEE.

[41]Lin R, Li Q. Task scheduling algorithm based on pre-allocation strategy in cloud computing. In international conference on cloud computing and big data analysis 2016 (pp. 227-32). IEEE.

[42]Fan Y, Liang Q, Chen Y, Yan X, Hu C, Yao H, et al. Executing time and cost-aware task scheduling in hybrid cloud using a modified DE algorithm. In computational intelligence and intelligent systems: 7th international symposium, Guangzhou, China, 2015 (pp. 74-83). Springer Singapore.

[43]Gupta N, Patel N, Tiwari BN, Khosravy M. Genetic algorithm based on enhanced selection and log-scaled mutation technique. In proceedings of the future technologies conference 2018 (pp. 730-48). Springer International Publishing.

[44]Wei H, Li S, Jiang H, Hu J, Hu J. Hybrid genetic simulated annealing algorithm for improved flow shop scheduling with makespan criterion. Applied Sciences. 2018; 8(12):1-20.

[45]Liaw CF. A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research. 2000; 124(1):28-42.

[46]Oh IS, Lee JS, Moon BR. Hybrid genetic algorithms for feature selection. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004; 26(11):1424-37.

[47]Lin CJ, Su SC. Protein 3D HP model folding simulation using a hybrid of genetic algorithm and particle swarm optimization. International Journal of Fuzzy Systems. 2011; 13(2):140-7.

[48]Calheiros RN, Ranjan R, De RCA, Buyya R. Cloudsim: a novel framework for modeling and simulation of cloud computing infrastructures and services. arXiv preprint arXiv:0903.2525. 2009.

[49]Buyya R, Murshed M. Gridsim: a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. Concurrency and Computation: Practice and Experience. 2002; 14(13‐15):1175-220.

[50]Wu F, Wu Q, Tan Y. Workflow scheduling in cloud: a survey. The Journal of Supercomputing. 2015; 71:3373-418.

[51]Sharifi M, Shahrivari S, Salimi H. PASTA: a power-aware solution to scheduling of precedence-constrained tasks on heterogeneous computing resources. Computing. 2013; 95(1):67-88.

[52]Hosseinzadeh M, Ghafour MY, Hama HK, Vo B, Khoshnevis A. Multi-objective task and workflow scheduling approaches in cloud computing: a comprehensive review. Journal of Grid Computing. 2020; 18:327-56.

[53]Radulescu A, Van GAJ. Fast and effective task scheduling in heterogeneous systems. In proceedings 9th heterogeneous computing workshop 2000 (pp. 229-38). IEEE.

[54]Khurana S, Singh R. Workflow scheduling and reliability improvement by hybrid intelligence optimization approach with task ranking. EAI Endorsed Transactions on Scalable Information Systems. 2019; 7(24):1-10.

[55]Aziza H, Krichen S. A hybrid genetic algorithm for scientific workflow scheduling in cloud environment. Neural Computing and Applications. 2020; 32:15263-78.

[56]Schad J, Dittrich J, Quiané-ruiz JA. Runtime measurements in the cloud: observing, analyzing, and reducing variance. Proceedings of the VLDB Endowment. 2010; 3(1-2):460-71.

[57]Arif M, Kiani AK, Qadir J. Machine learning based optimized live virtual machine migration over WAN links. Telecommunication Systems. 2017; 64:245-57.

[58]Casas I, Taheri J, Ranjan R, Wang L, Zomaya AY. GA-ETI: an enhanced genetic algorithm for the scheduling of scientific workflows in cloud environments. Journal of Computational Science. 2018; 26:318-31.

[59]Mohammadzadeh A, Masdari M, Gharehchopogh FS, Jafarian A. A hybrid multi-objective metaheuristic optimization algorithm for scientific workflow scheduling. Cluster Computing. 2021; 24:1479-503.

[60]Wood T, Ramakrishnan KK, Shenoy P, Van DMJ. CloudNet: dynamic pooling of cloud resources by live WAN migration of virtual machines. ACM Sigplan Notices. 2011; 46(7):121-32.