SGWO: A Modified Grey Wolf Optimizer for Fog–Cloud Workflow Scheduling with Emphasis on Makespan and Cost Efficiency
Abstract
The rapid deployment of IoT applications creates several challenges. To address these challenges, a new paradigm called Fog Computing extends Cloud Computing services to the network edge, which reduces latency, conserves energy, and saves bandwidth. One of the major issues in enhancing the IoT application's performance is the tasks' scheduling, specifically, how to allocate them to different resources distributed across Fog-Cloud Computing layers. In this paper, a scheduling algorithm named SGWO is proposed, which adapts the standard Grey Wolf Optimizer (GWO) algorithm by including an improvement aimed at optimizing the balance between the exploration and exploitation phases. This adaptation enables the efficient scheduling of dependent tasks, modeled as general workflows, by allocating them efficiently across a hybrid topology composed of fog and cloud nodes with the dual objectives of minimizing makespan and reducing resource utilization costs. A series of experiments were conducted in a static simulation environment using diverse workflow datasets under various topology configurations. The results demonstrate that SGWO converges quickly and delivers better performance in terms of both makespan and cost, achieving a fitness value higher than those obtained by PSO, SQGA, GA, MHEFT, and FCFS algorithms by 43.3\%, 50.8\%, 55.4\%, 54.5\%, and 57.7\%, respectively, thereby confirming its effectiveness in scheduling for this type of infrastructure.References
Maher Abdelshkour. IoT, from Cloud to Fog
Computing. https://blogs.cisco.com/perspectives/iot-from-cloud-to-fog-computing Accessed Nov. 05, 2024. 2015.
Deafallah Alsadie. “A Comprehensive Review of AI Techniques for Resource Management in Fog Computing: Trends, Challenges, and Future Directions”. In: IEEE Access 12 (2024), pp. 118007–118059. doi: https://doi.org/10.1109/ACCESS.2024.3447097.
Muhammad Rizwan Anawar et al. “Fog Computing: An Overview of Big IoT Data Analytics”. In: Wireless Communications and Mobile Computing 2018 (2018), pp. 1–22. issn: 1530-8669. doi: https://doi.org/10.1155/2018/7157192.
Lokesh Kumar Arya and Amandeep Verma. “Workflow scheduling algorithms in cloud environment - A survey”. In: 2014 Recent Advances in Engineering and Computational Sciences (RAECS) (Mar. 2014), pp. 1–4. doi: https://doi.org/10.1109/RAECS.2014.6799514.
Hany Atlam, Robert Walters, and Gary Wills.“Fog Computing and the Internet of Things: A Review”. In: Big Data and Cognitive Computing 2 (Apr. 2018). doi: https://doi.org/10.3390/bdcc2020010.
Hany F. Atlam et al. “Integration of Cloud Computing with Internet of Things: Challenges and Open Issues”. In: 2017 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). 2017, pp. 670–675. doi: https://doi.org/10.1109/iThings-GreenCom-CPSCom-SmartData.2017.105.
Raouf Belmahdi, Djamila Mechta, and Saad Harous. “A Survey on Various Methods and Algorithms of Scheduling in Fog Computing.” In: Ing´enierie des syst`emes d’information 26.2 (2021). doi: https://doi.org/10.18280/isi.260208.
Raouf Belmahdi et al. “SQGA: Quantum Genetic Algorithm-based Workflow Scheduling in Fog-Cloud Computing”. In: 2022 International Wireless Communications and Mobile Computing (IWCMC). 2022, pp. 131–136. doi: https://doi.org/10.1109/IWCMC55113.2022.9825324.
Alessio Botta et al. “Integration of Cloud computing and Internet of Things: A survey”. In: Future Generation Computer Systems 56 (2016), pp. 684–700. issn: 0167-739X. doi: https://doi.org/10.1016/j.future.2015.09.021.
Gustavo Caiza et al. “Fog computing at industrial level, architecture, latency, energy, and security: A review”. In: Heliyon 6 (4 Apr. 2020), e03706. issn: 24058440. doi: https://doi.org/10.1016/j.heliyon.2020.e03706.
Chii Chang, Satish Narayana Srirama, and Rajkumar Buyya. “Indie Fog: An Efficient FogComputing Infrastructure for the Internet of Things”. In: Computer 50.9 (2017), pp. 92–98. doi: https://doi.org/10.1109/MC.2017.3571049.
OpenFog Consortium. OpenFog Reference Architecture for Fog Computing. https : / / www . iiconsortium.org/pdf/OpenFog_Reference_Architecture_2_09_17.pdf Accessed Nov. 05, 2024. 2017.
Statista Research Department. IoT devices installed base worldwide 2015-2025. https://www.statista.com/statistics/471264/iotnumber-of-connected-devices-worldwide Accessed Nov. 05, 2024. 2016.
Jos´e Fernando Gon¸calves, Jorge Jos´e de Magalh˜aes Mendes, and Maur´ıcio G.C. Resende. “A hybrid genetic algorithm for the job shop scheduling problem”. In: European Journal of Operational Research 167 (1 Nov. 2005), pp. 77–95. issn: 03772217. doi: https://doi.org/10.1016/j.ejor.2004.03.012.
Ali Salah Hashim, Wid Akeel Awadh, and Mohammed S Hashim. “Non-dominated sorting genetic optimization-based fog cloudlet computing for wireless metropolitan area networks”. In: Informatica 47.10 (2023). doi: https://doi.org/10.31449/inf.v47i10.5118.
Doan Hoang and Thanh Dat Dang. “FBRC: Optimization of task Scheduling in Fog-Based Region and Cloud”. In: 2017 IEEE Trustcom/BigDataSE/ICESS. 2017, pp. 1109–1114. doi: https://doi.org/10.1109/Trustcom/BigDataSE/ICESS.2017.360.
Farooq Hoseiny et al. “PGA: A Priority-aware Genetic Algorithm for Task Scheduling in Heterogeneous Fog-Cloud Computing”. In: IEEE INFOCOM 2021 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). 2021, pp. 1–6. doi: https://doi.org/10.1109/INFOCOMWKSHPS51825.2021.9484436.
Pejman Hosseinioun et al. “aTask scheduling approaches in fog computing: A survey”. In: Transactions on Emerging Telecommunications Technologies 33 (3 Mar. 2022). issn: 2161-3915. doi: https://doi.org/10.1002/ett.3792.
Mehdi Hosseinzadeh et al. “Task Scheduling Mechanisms for Fog Computing: A Systematic Survey”. In: IEEE Access 11 (2023), pp. 50994–51017. doi: https://doi.org/10.1109/ACCESS.2023.3277826.
Lu Hou et al. “Internet of Things Cloud: Architecture and Implementation”. In: IEEE Communications Magazine 54.12 (2016), pp. 32–39. doi: https://doi.org/10.1109/MCOM.2016.1600398CM.
Pengfei Hu et al. “Survey on fog computing: architecture, key technologies, applications and open issues”. In: Journal of Network and Computer Applications 98 (Nov. 2017), pp. 27–42. issn: 10848045. doi: https://doi.org/10.1016/j.jnca.2017.09.002.
Omer K. Jasim Mohammad and Bassim M. Salih. “Improving Task Scheduling in Cloud Datacenters by Implementation of an Intelligent Scheduling Algorithm”. In: Informatica (Slovenia) 48.10 (2024), pp. 77–88. doi: https://doi.org/10.31449/inf.v48i10.5843.
Amir Karamoozian, Abdelhakim Hafid, and El Mostapha Aboulhamid. “On the Fog-Cloud Cooperation: How Fog Computing can address latency concerns of IoT applications”. In: 2019 Fourth International Conference on Fog and Mobile Edge Computing (FMEC). 2019, pp. 166– 172. doi: https://doi.org/10.1109/FMEC.2019.8795320.
J. Kennedy and R. Eberhart. “Particle swarm optimization”. In: Proceedings of ICNN’95 - International Conference on Neural Networks. Vol. 4. 1995, 1942–1948 vol.4. doi: https://doi.org/10.1109/ICNN.1995.488968
Zulfiqar Ali Khan et al. “A Review on Task Scheduling Techniques in Cloud and Fog Computing: Taxonomy, Tools, Open Issues, Challenges, and Future Directions”. In: IEEE Access 11 (2023), pp. 143417–143445. doi: https://doi.org/10.1109/ACCESS.2023.3343877.
P. Kuppusamy et al. “Job scheduling problem in fog-cloud-based environment using reinforced social spider optimization”. In: Journal of Cloud Computing 11.1 (2022). issn: 2192-113X. doi: https://doi.org/10.1186/s13677-022-00380-9.
Jian Ma et al. “Reliable Task Scheduling in Cloud Computing Using Optimization Techniques for Fault Tolerance”. In: Informatica 48.23 (2024), pp. 159–170. doi: https://doi.org/10.31449/inf.v48i23.6901.
Khaled Matrouk and Kholoud Alatoun. “Scheduling Algorithms in Fog Computing: A Survey”. In: International Journal of Networked and Distributed Computing 9 (1 Jan. 2021), p. 59. issn: 2211-7946. doi: https://doi.org/10.2991/ijndc.k.210111.001.
Yamina Mehor, Mohammed Rebbah, and Omar Smail. “Energy-aware Scheduling of Tasks in Cloud Computing.” In: Informatica 48.16 (2024). doi: https://doi.org/10.31449/inf.v48i16.5741.
Eva Mindasari, Sawaluddin Sawaluddin, and Parapat Gultom. “Comparison of Genetic Algorithm and Particle Swarm Optimization in Determining the Solution of Nonlinear System of Equations”. In: sinkron 8 (3 July 2024), pp. 1600–1607. issn: 2541-2019. doi: https://doi.org/10.33395/sinkron.v8i3.13785.
Seyedali Mirjalili, Seyed Mohammad Mirjalili, and Andrew Lewis. “Grey Wolf Optimizer”. In: Advances in Engineering Software 69 (2014) pp. 46–61. issn: 0965-9978. doi: https://doi.org/10.1016/j.advengsoft.2013.12.007.
Nitin Mittal, Urvinder Singh, and Balwinder Singh Sohi. “Modified grey wolf optimizer for global engineering optimization”. In: Applied Computational Intelligence and Soft Computing 2016 (2016). doi:https://doi.org/10.1155/2016/7950348.
C. Muro et al. “Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations”. In: Behavioural Processes 88.3 (2011), pp. 192–197. issn: 0376-6357. doi:https://doi.org/10.1016/j.beproc.2011.09.006.
Tina Samizadeh Nikoui et al. “Cost-Aware Task Scheduling in Fog-Cloud Environment”. In: 2020 CSI/CPSSI International Symposium on RealTime and Embedded Systems and Technologies (RTEST). 2020, pp. 1–8. doi: https://doi.org/10.1109/RTEST49666.2020.9140118.
Xuan-Qui Pham et al. “A cost- and performance-effective approach for task scheduling based on collaboration between cloud and fog computing”. In: International Journal of Distributed Sensor Networks 13.11
(2017). doi: https://doi.org/10.1177/1550147717742073.
Narayana Potu, Chandrashekar Jatoth, and Premchand Parvataneni. “Optimizing resource scheduling based on extended particle swarm optimization in fog computing environments”. In: Concurrency and Computation: Practice and Experience 33 (23 Dec. 2021). issn: 1532-0626. doi: https://doi.org/10.1002/cpe.6163.
Esmat Rashedi, Hossein Nezamabadi-Pour, and Saeid Saryazdi. “GSA: a gravitational search algorithm”. In: Information sciences 179.13 (2009), pp. 2232–2248. doi: https://doi.org/10.1016/j.ins.2009.03.004.
Yichen Ruan et al. “Pricing Tradeoffs for Data Analytics in Fog–Cloud Scenarios”. In: Fog
and Fogonomics (Mar. 2020), pp. 83–106. doi:https://doi.org/10.1002/9781119501121.ch4.
Muhammad Saad, Rabia Noor Enam, and Rehan Qureshi. “Optimizing multi-objective task scheduling in fog computing with GA-PSO algorithm for big data application”. In: Frontiers in Big Data 7 (Feb. 2024). issn: 2624-909X. doi: https://doi.org/10.3389/fdata.2024.1358486.
Ling Shen et al. “A hybrid GA-PSO algorithm for seru scheduling problem with dynamic resource allocation”. In: International Journal of Manufacturing Research 18.1 (2023), pp. 100–124. doi: https://doi.org/10.1504/IJMR.2023.129301.
Lovejit Singh and Sarbjeet Singh. “A Genetic Algorithm for Scheduling Workflow Applications in Unreliable Cloud Environment”. In: Recent Trends in Computer Networks and Distributed Systems Security: Second International Conference, SNDS 2014, Trivandrum, India, March 13-14, 2014, Proceedings 2. Vol. 420. 2014, pp. 139–150. doi:https://doi.org/10.1007/978-3-642-54525-2_12.
Rainer Storn and Kenneth Price. “Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces”. In: Journal of Global Optimization 11 (1997), pp. 341–359. doi: https://doi.org/10.1023/A:1008202821328.
Jin Xie et al. “Review on flexible job shop scheduling”. In: IET Collaborative Intelligent Manufacturing 1 (3 Sept. 2019), pp. 67–77. issn: 2516-8398. doi: https://doi.org/10.1049/iet-cim.2018.0009.
Vinita Yadav, B V Natesha, and Ram Mohana Reddy Guddeti. “GA-PSO: Service Allocation in Fog Computing Environment Using Hybrid BioInspired Algorithm”. In: TENCON 2019 - 2019 IEEE Region 10 Conference (TENCON). 2019,
pp. 1280–1285. doi: https://doi.org/10.1109/TENCON.2019.8929234.
Hyunsik Yang and Younghan Kim. “Design and Implementation of High-Availability Architecture for IoT-Cloud Services”. In: Sensors 19.15 (2019). issn: 1424-8220. doi: https://doi.org/10.3390/s19153276.
Mingyang Yu et al. “Improved multi-strategy adaptive Grey Wolf Optimization for practical engineering applications and high-dimensional problem solving”. In: Artificial Intelligence Review 57 (10 Sept. 2024). The time complexity of
theoriginal GWO algorithm is O(T × N × D) .page 15, p. 277. issn: 1573-7462. doi: 10.1007/ s10462- 024- 10821- 3. url: https://link. springer.com/10.1007/s10462-024-10821-3. [47] Arkady Zaslavsky, Charith Perera, and Dimitrios Georgakopoulos. “Sensing as a Service and Big Data”. In: ArXiv (Jan. 2013). doi: https://doi.org/10.48550/arXiv.1301.0159.
Honglin Zhang, Yaohua Wu, and Zaixing Sun. “EHEFT-R: multi-objective task scheduling scheme in cloud computing”. In: Complex & Intelligent Systems 8 (6 Dec. 2022). ajouter EHEFT-R, pp. 4475–4482. issn: 2199-4536. doi: 10.1007/s40747-021-00479-7. url: https: //link.springer.com/10.1007/s40747-021-00479-7.
Junlong Zhou et al. “Cost and makespanaware workflow scheduling in hybrid clouds”. In: Journal of Systems Architecture 100 (2019), p. 101631. issn: 1383-7621. doi: https://doi.org/10.1016/j.sysarc.2019.08.004.
DOI:
https://doi.org/10.31449/inf.v50i10.7797Downloads
Published
How to Cite
Issue
Section
License
Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.
All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.
Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.
