More Web Proxy on the site http://driver.im/

research-article

A latency-aware task scheduling algorithm for allocating virtual machines in a cost-effective and time-sensitive fog-cloud architecture

Authors:

Seyedeh Samira Mohammadi,

Fariborz Jolai,

Reza Tavakkoli-MoghaddamAuthors Info & Claims

The Journal of Supercomputing, Volume 78, Issue 1

Pages 93 - 122

https://doi.org/10.1007/s11227-021-03868-4

Published: 01 January 2022 Publication History

Abstract

Recently, with the expansion of communications and generated data, the need for processing this high volume of data in minimum time and maximum speed has increased. Also, performing this volume of computing operations requires high processing and storage resources leading to hardware cost increment. In such systems, one of the most critical challenges is the task scheduling problem, which tries to find the optimal allocation for maximum resource usage and reduce the response time. Therefore, the purpose of this study is to design an infrastructure for smart home energy management with minimum hardware cost using cloud and fog computing and to propose a latency-aware scheduling algorithm based on virtual machine matching using meta-heuristics. Among heuristic methods, Tabu search makes it a common practice because of its high expansion in various optimization issues, as well as memory and high-speed features. Thereby, a novel algorithm based on the Tabu search is proposed that is improved using approximate nearest neighbor (ANN) and fruit fly optimization (FOA) algorithms. Finally, to validate the proposed method, a case study is simulated and the proposed algorithm is implemented considering target factors of execution time, latency, allocated memory, and cost function to illustrate the performance of the algorithm. The comparison results show that the proposed algorithm outperforms the Tabu search, genetic algorithm, PSO, and simulated annealing methods.

References

[1]

Varghese B and Buyya R Next generation cloud computing: new trends and research directions Future Gener Comput Syst 2018 79 849-861

[2]

Amadeo M, Giordano A, Mastroianni C, and Molinaro A On the integration of information centric networking and fog computing for smart home services 2019 Cham Springer 75-93

[3]

Rahmani AM, Gia TN, Negash B, Anzanpour A, Azimi I, Jiang M, and Liljeberg P Exploiting smart e-Health gateways at the edge of healthcare Internet-of-Things: a fog computing approach Future Gener Comput Syst 2018 78 641-658

[4]

Gilbert GM, Naiman S, Kimaro H, and Bagile B A critical review of edge and fog computing for smart grid applications 2019 Berlin Springer

[5]

Wang P, Liu S, Ye F, Chen X (2018) A fog-based architecture and programming model for IoT applications in the smart grid.

[6]

Hussain M and Beg MM Fog Computing for Internet of Things (IoT)-aided smart grid architectures Big Data Cogn Comput 2019 3 1 8

[7]

Dowsland KA, Thompson JM (2012) Simulated annealing BT—handbook of natural computing. In Rozenberg G, Bäck T, Kok JN (eds). Springer, Berlin, pp. 1623–1655

[8]

Zhang H, Shi J, Deng B, Jia G, Han G, and Shu L MCTE: Minimizes task completion time and execution cost to optimize scheduling performance for smart grid cloud IEEE Access 2019 7 134793-134803

[9]

Sun H, Yu H, Fan G, and Chen L Energy and time efficient task offloading and resource allocation on the generic IoT-fog-cloud architecture Peer-to-Peer Netw Appl 2020 13 2 548-563

[10]

Li J and Han Y A hybrid multi-objective artificial bee colony algorithm for flexible task scheduling problems in cloud computing system Cluster Comput 2020 23 4 2483-2499

[11]

Tang H, Li C, Bai J, Tang JH, and Luo Y Dynamic resource allocation strategy for latency-critical and computation-intensive applications in cloud–edge environment Comput Commun 2019 134 70-82

[12]

Eng KL, Muhammed A, Mohamed MA, and Hasan S A hybrid heuristic of variable neighbourhood descent and great deluge algorithm for efficient task scheduling in Grid computing Eur J Oper Res 2020 284 1 75-86

[13]

Sanaj MS and Joe Prathap PM Nature inspired chaotic squirrel search algorithm (CSSA) for multi objective task scheduling in an IAAS cloud computing atmosphere Eng Sci Technol Int J 2020 23 4 891-902

[14]

Pirim H, Bayraktar E, and Eksioglu B Tabu search: a comparative study Tabu Search 2008

[15]

Glover F (1995) Tabu search fundamentals and uses. Vasa

[16]

Ashtiani AF, Pierre S, Feizi A, and Pierre S Power allocation and resource assignment for secure D2D communication underlaying cellular networks: a Tabu search approach Comput Netw 2020 178 107350

[17]

Alharkan I, Saleh M, Ghaleb MA, Kaid H, Farhan A, and Almarfadi A Tabu search and particle swarm optimization algorithms for two identical parallel machines scheduling problem with a single server J King Saud Univers Sci 2020 32 5 330-338

[18]

Mathlouthi I, Gendreau M, and Potvin JY A metaheuristic based on tabu search for solving a technician routing and scheduling problem Comput Oper Res 2021 125 105

[19]

Memari P, Tavakkoli-Moghaddam R, Navazi F, and Jolai F Air and ground ambulance location-allocation-routing problem for designing a temporary emergency management system after a disaster Proc Inst Mech Eng Part H J Eng Med 2020 234 8 812-828

[20]

Arostegui MA, Kadipasaoglu SN, and Khumawala BM An empirical comparison of Tabu search, simulated annealing, and genetic algorithms for facilities location problems Int J Prod Econ 2006 103 742-754

[21]

Chu B (1999) Genetic Algorithms vs. Tabu search in timetable scheduling, pp 492–495

[22]

Rathore MM, Paul A, Hong W-H, Seo H, Awan I, and Saeed S Exploiting IoT and big data analytics: defining Smart Digital City using real-time urban data Sustain Cities Soc 2018 40 600-610

[23]

Bitam S, Zeadally S, and Mellouk A Fog computing job scheduling optimization based on bees swarm Enterp Inf Syst 2018 12 4 373-397

[24]

Li C, Liu J, Li W, and Luo Y Adaptive priority-based data placement and multi-task scheduling in geo-distributed cloud systems Knowl Based Syst 2021 224 107050

[25]

Peng L, Dhaini AR, and Ho P-H Toward integrated Cloud–Fog networks for efficient IoT provisioning: key challenges and solutions Future Gener Comput Syst 2018 88 606-613

[26]

Yassine A, Singh S, Hossain MS, and Muhammad G IoT big data analytics for smart homes with fog and cloud computing Future Gener Comput Syst 2019 91 563-573

[27]

Naqvi SAA, Javaid N, Butt H, Kamal MB, Hamza A, and Kashif M Metaheuristic optimization technique for load balancing in cloud-fog environment integrated with smart grid 2019 Cham Springer 700-711

[28]

Naranjo PGV, Pooranian Z, Shojafar M, Conti M, and Buyya R FOCAN: a Fog-supported smart city network architecture for management of applications in the Internet of Everything environments J Parallel Distrib Comput 2018

[29]

Iwanir E, Tamir T (2019) Recent advances in computational optimization, 795 207 233

[30]

Wang B, Wang C, Huang W, Song Y, and Qin X Security-aware task scheduling with deadline constraints on heterogeneous hybrid clouds J Parallel Distrib Comput 2021 15 315-28

[31]

Bittencourt L, Immich R, Sakellariou R, Fonseca N, Madeira E, Curado M, Villas L, DaSilva L, Lee C, and Rana O The Internet of Things, Fog and Cloud continuum: integration and challenges Internet Things 2018 3 4134-155

[32]

Pérez JL, Gutierrez-Torre A, Berral JL, and Carrera D A resilient and distributed near real-time traffic forecasting application for Fog computing environments Future Gener Comput Syst 2018 87 198-212

[33]

Lin K, Pankaj S, and Wang D Task offloading and resource allocation for edge-of-things computing on smart healthcare systems Comput Electr Eng 2018 72 348-360

[34]

Basu S, Karuppiah M, Selvakumar K, Li KC, Islam SH, Hassan MM, and Bhuiyan MZ An intelligent/cognitive model of task scheduling for IoT applications in cloud computing environment Future Gener Comput Syst 2018 88 254-261

[35]

Li Q, Zhao L, Gao J, Liang H, Zhao L, and Tang X SMDP-based coordinated virtual machine allocations in cloud-fog computing systems IEEE Internet Things J 2018 5 3 1977-1988

[36]

Hussain M, Wei LF, Lakhan A, Wali S, Ali S, and Hussain A Energy and performance-efficient task scheduling in heterogeneous virtualized cloud computing Sustain Comput Inform Syst 2021 30 100517

[37]

Mohammad Hasani Zade B, Mansouri N, and Javidi MM SAEA: A security-aware and energy-aware task scheduling strategy by Parallel Squirrel Search Algorithm in cloud environment Expert Syst Appl 2021 176 114915

[38]

Memari P, Mohammadi SS, Ghaderi SF (2018) Data mining model for evaluating and forecasting energy consumption by cloud computing. In: 2018 IEEE electrical power and energy conference (EPEC), pp 1–6.

[39]

Thevenin S and Zufferey N Learning variable neighborhood search for a scheduling problem with time windows and rejections Discrete Appl Math 2018

[40]

Pacheco J, Porras S, Casado S, and Baruque B Variable neighborhood search with memory for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times Knowl Based Syst 2018 145 236-249

[41]

Zeng Z, Yu X, He K, and Fu Z Adaptive Tabu search and variable neighborhood descent for packing unequal circles into a square Appl Soft Comput 2018 65 196-213

[42]

Mathlouti I, Gendreau M, and Potvin J-Y A metaheuristic based on tabu search for solving a technician routing and scheduling problem Comput Oper Res 2018

[43]

Houssein EH, Gad AG, Wazery YM, and Suganthan PN Task scheduling in cloud computing based on meta-heuristics: review, taxonomy, open challenges, and future trends Swarm Evol Comput 2021 62 100841

[44]

Sharifi AH and Maghouli P Energy management of smart homes equipped with energy storage systems considering the PAR index based on real-time pricing Sustain Cities Soc 2019 45 579-587

[45]

Iqbal A, Ullah F, Anwar H, Kwak KS, Imran M, Jamal W, and ur Rahman A Interoperable Internet-of-Things platform for smart home system using web-of-objects and cloud Sustain Cities Soc 2018 38 636-646

[46]

Alboaneen D, Tianfield H, Zhang Y, and Pranggono B A metaheuristic method for joint task scheduling and virtual machine placement in cloud data centers Future Gener Comput Syst 2021 115 201-212

[47]

Sattarpour T, Nazarpour D, and Golshannavaz S A multi-objective HEM strategy for smart home energy scheduling: a collaborative approach to support microgrid operation Sustain Cities Soc 2018

[48]

Alsaidy SA, Abbood AD, and Sahib MA Heuristic initialization of PSO task scheduling algorithm in cloud computing J King Saud Univers Comput Inf Sci 2020

[49]

Memari P, Mohammadi SS, Ghaderi SF (2018) Cloud platform real-time measurement and verification procedure for energy efficiency of washing machines.

[50]

Raidl GR, Puchinger J, Blum C. Metaheuristic hybrids

[51]

Puchinger J, Raidl R (2005) Artificial intelligence and knowledge engineering applications: a bioinspired approach. 3562:41–53

[52]

Ling KQ Photochemical synthesis of l, 2-dihydro-3H-indol-3-ones Chem Res Chin Univers 1996 17 6 268-308

[53]

Glover F Tabu search—Part I ORSA J Comput 1989 1 3 190-206

[54]

Yadwadkar NJ, Hariharan B, Gonzalez JE, Katz R (2016) Multi-task learning for straggler avoiding predictive job scheduling. J Mach Learn Res, pp 171–37

[55]

Indyk P, Motwani R (1998) Approximate nearest neighbors, pp 604–613.

[56]

Pan W-T A new fruit fly optimization algorithm: taking the financial distress model as an example Knowl Based Syst 2012

Cited By

Satouf AHamidoğlu AGül ÖKuusik ADurak Ata LKadry S(2025)Metaheuristic-based task scheduling for latency-sensitive IoT applications in edge computingCluster Computing10.1007/s10586-024-04878-628:2Online publication date: 1-Apr-2025
https://dl.acm.org/doi/10.1007/s10586-024-04878-6
Maashi MAlabdulkreem EMaray MShankar KDarem AAlzahrani AYaseen I(2024)Elevating Survivability in Next-Gen IoT-Fog-Cloud Networks: Scheduling Optimization With the Metaheuristic Mountain Gazelle AlgorithmIEEE Transactions on Consumer Electronics10.1109/TCE.2024.337177470:1(3802-3809)Online publication date: 8-Mar-2024
https://dl.acm.org/doi/10.1109/TCE.2024.3371774
Daghayeghi ANickray M(2024)Delay-Aware and Energy-Efficient Task Scheduling Using Strength Pareto Evolutionary Algorithm II in Fog-Cloud Computing ParadigmWireless Personal Communications: An International Journal10.1007/s11277-024-11510-8138:1(409-457)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11277-024-11510-8
Show More Cited By

Index Terms

A latency-aware task scheduling algorithm for allocating virtual machines in a cost-effective and time-sensitive fog-cloud architecture

Index terms have been assigned to the content through auto-classification.

Recommendations

An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with non-identical capacities and unequal ready times

We consider the problem of scheduling jobs on unrelated batch machines so as to minimize the makespan.We present a MIP formulation of the problem and present a lower bound on the optimal makespan.We propose an iterated greedy algorithm to solve the ...
A tabu search algorithm for the quadratic assignment problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). ...
An implementation of the iterated tabu search algorithm for the quadratic assignment problem

In this paper, we describe an implementation of the iterated tabu search (ITS) algorithm for the quadratic assignment problem (QAP), which is one of the well-known problems in combinatorial optimization. The medium- and large-scale QAPs are not, to this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Supercomputing

The Journal of Supercomputing Volume 78, Issue 1

Jan 2022

1563 pages

ISSN:0920-8542

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 2022

Accepted: 05 May 2021

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Satouf AHamidoğlu AGül ÖKuusik ADurak Ata LKadry S(2025)Metaheuristic-based task scheduling for latency-sensitive IoT applications in edge computingCluster Computing10.1007/s10586-024-04878-628:2Online publication date: 1-Apr-2025
https://dl.acm.org/doi/10.1007/s10586-024-04878-6
Maashi MAlabdulkreem EMaray MShankar KDarem AAlzahrani AYaseen I(2024)Elevating Survivability in Next-Gen IoT-Fog-Cloud Networks: Scheduling Optimization With the Metaheuristic Mountain Gazelle AlgorithmIEEE Transactions on Consumer Electronics10.1109/TCE.2024.337177470:1(3802-3809)Online publication date: 8-Mar-2024
https://dl.acm.org/doi/10.1109/TCE.2024.3371774
Daghayeghi ANickray M(2024)Delay-Aware and Energy-Efficient Task Scheduling Using Strength Pareto Evolutionary Algorithm II in Fog-Cloud Computing ParadigmWireless Personal Communications: An International Journal10.1007/s11277-024-11510-8138:1(409-457)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s11277-024-11510-8
Chowdhary SRao A(2024)QoS and reliability aware matched bald eagle task scheduling framework based on IoT-cloud in educational applicationsCluster Computing10.1007/s10586-024-04415-527:6(8141-8158)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10586-024-04415-5
Entrialgo JMoreno-Vozmediano RDíaz J(2024)Cost and response time optimization of edge architecturesCluster Computing10.1007/s10586-024-04359-w27:6(7757-7773)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10586-024-04359-w
Zuo H(2023)Towards optimal virtual machine placement methods in cloud environmentsJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-22289644:5(8663-8696)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/JIFS-222896
Vispute SVashisht P(2023)Energy-Efficient Task Scheduling in Fog Computing Based on Particle Swarm OptimizationSN Computer Science10.1007/s42979-022-01639-34:4Online publication date: 11-May-2023
https://dl.acm.org/doi/10.1007/s42979-022-01639-3
Mukherjee AGhosh SGhosh SBuyya R(2023)Mobi-Sense: mobility-aware sensor-fog paradigm for mission-critical applications using network coding and steganographyThe Journal of Supercomputing10.1007/s11227-023-05300-579:15(17495-17518)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1007/s11227-023-05300-5
Mukhopadhyay NTewari B(2022)Dynamic cost effective solution for efficient cloud infrastructureThe Journal of Supercomputing10.1007/s11227-022-04913-679:6(6471-6506)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1007/s11227-022-04913-6
Wu CLakhan AGronali T(2022)Microservices architectural based secure and failure aware task assignment schemes in fog‐cloud assisted Internet of thingsInternational Journal of Intelligent Systems10.1002/int.2296437:11(8696-8729)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1002/int.22964
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents