Skip to main content
Top
Published in: The Journal of Supercomputing 2/2023

04-08-2022

A novel technique to optimize quality of service for directed acyclic graph (DAG) scheduling in cloud computing environment using heuristic approach

Authors: Ranjit Rajak, Shrawan Kumar, Shiv Prakash, Nidhi Rajak, Pratibha Dixit

Published in: The Journal of Supercomputing | Issue 2/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

At present, the cloud computing environment (CCE) has emerged as one of the significant technologies in communication, computing, and the Internet. It facilitates on-demand services of different types based on pay-per-use access such as platforms, applications and infrastructure. Because of its growing reputation, the massive requests need to be served in an efficient way which gives the researcher a challenging problem known as task scheduling. These requests are handled by method of efficient allocation of resources. In the process of resource allocation, task scheduling is accomplished where there is a dependency between tasks, which is a Directed Acyclic Graph (DAG) scheduling. DAG is one of the most important scheduling due to wide range of its applicable in different areas such as environmental technology, resources, and energy optimization. NP-complete is a renowned concern, so various models deals with NP-complete that have been suggested in the literature. However, as the Quality of Service (QoS)-aware services in the CCEplatform have turned into an attractive and prevalent way to provide computing resources emerges as a novel critical issue. Therefore, the key aim of this manuscript is to develop a novel DAG scheduling model for optimizing the QoS parameters in the CCEplatform and validation of this can be done with the help of extensive simulation technique. Each simulated result is compared with the existing results, and it is found that newly developed algorithm performs better in comparison to the state-of-the-art algorithms.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literature
5.
go back to reference Sharma S, Sajid M (2021) Integrated fog and cloud computing: issues and challenges. Int J Cloud Appl Comput (IGI) 11(4), Article 10 Sharma S, Sajid M (2021) Integrated fog and cloud computing: issues and challenges. Int J Cloud Appl Comput (IGI) 11(4), Article 10
6.
go back to reference Buyya R, Pandey S, Vecchiola C (2009) Cloudbus toolkit for market-oriented cloud computing. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). pp 24–44 Buyya R, Pandey S, Vecchiola C (2009) Cloudbus toolkit for market-oriented cloud computing. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). pp 24–44
10.
go back to reference Sahitya A (2021) Importance of Fog Computing in. Integr Cloud Comput with Internet Things Found Anal Appl, p 211 Sahitya A (2021) Importance of Fog Computing in. Integr Cloud Comput with Internet Things Found Anal Appl, p 211
11.
go back to reference Song A, Chen W-N, Luo X-N, et al (2020) Scheduling Workflows with Composite Tasks: A Nested Particle Swarm Optimization Approach. IEEE Trans Serv Comput Song A, Chen W-N, Luo X-N, et al (2020) Scheduling Workflows with Composite Tasks: A Nested Particle Swarm Optimization Approach. IEEE Trans Serv Comput
12.
go back to reference Jain R, Sharma N (2021) A QoS Aware Binary Salp Swarm Algorithm for Effective Task Scheduling in Cloud Computing. In: Progress in Advanced Computing and Intelligent Engineering. Springer, pp 462–473 Jain R, Sharma N (2021) A QoS Aware Binary Salp Swarm Algorithm for Effective Task Scheduling in Cloud Computing. In: Progress in Advanced Computing and Intelligent Engineering. Springer, pp 462–473
13.
go back to reference Farid M, Latip R, Hussin M, Abdul Hamid NAW (2020) A survey on QoS requirements based on particle swarm optimization scheduling techniques for workflow scheduling in cloud computing. Symmetry (Basel) 12:551CrossRef Farid M, Latip R, Hussin M, Abdul Hamid NAW (2020) A survey on QoS requirements based on particle swarm optimization scheduling techniques for workflow scheduling in cloud computing. Symmetry (Basel) 12:551CrossRef
14.
go back to reference da Silva EC, Gabriel PHR (2020) A Comprehensive Review of Evolutionary Algorithms for Multiprocessor DAG Scheduling. Computation 8:26CrossRef da Silva EC, Gabriel PHR (2020) A Comprehensive Review of Evolutionary Algorithms for Multiprocessor DAG Scheduling. Computation 8:26CrossRef
15.
go back to reference Hosseinzadeh M, Ghafour MY, Hama HK, et al (2020) Multi-objective task and workflow scheduling approaches in cloud computing: a comprehensive review. J Grid Comput, pp 1–30 Hosseinzadeh M, Ghafour MY, Hama HK, et al (2020) Multi-objective task and workflow scheduling approaches in cloud computing: a comprehensive review. J Grid Comput, pp 1–30
16.
go back to reference .Li J, Zhang X, Han L et al. (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983 .Li J, Zhang X, Han L et al. (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983
17.
go back to reference Woeginger GJ (2003) Exact algorithms for NP-hard problems: A survey. In: Combinatorial optimization—eureka, you shrink! Springer, pp 185–207 Woeginger GJ (2003) Exact algorithms for NP-hard problems: A survey. In: Combinatorial optimization—eureka, you shrink! Springer, pp 185–207
18.
go back to reference Hanen C (1994) Study of a NP-hard cyclic scheduling problem: The recurrent job-shop. Eur J Oper Res 72:82–101CrossRefMATH Hanen C (1994) Study of a NP-hard cyclic scheduling problem: The recurrent job-shop. Eur J Oper Res 72:82–101CrossRefMATH
19.
go back to reference Tong Z, Chen H, Deng X et al (2020) A scheduling scheme in the cloud computing environment using deep Q-learning. Inf Sci (Ny) 512:1170–1191CrossRef Tong Z, Chen H, Deng X et al (2020) A scheduling scheme in the cloud computing environment using deep Q-learning. Inf Sci (Ny) 512:1170–1191CrossRef
21.
go back to reference Pop F, Dobre C, Cristea V (2008) Performance analysis of grid DAG scheduling algorithms using MONARC simulation tool. In: 2008 International Symposium on Parallel and Distributed Computing, pp 131–138 Pop F, Dobre C, Cristea V (2008) Performance analysis of grid DAG scheduling algorithms using MONARC simulation tool. In: 2008 International Symposium on Parallel and Distributed Computing, pp 131–138
22.
go back to reference Bozdag D, Ozguner F, Catalyurek UV (2008) Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans Parallel Distrib Syst 20:857–871CrossRef Bozdag D, Ozguner F, Catalyurek UV (2008) Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans Parallel Distrib Syst 20:857–871CrossRef
23.
go back to reference Kannan R, Karpinski M (2005) Approximation algorithms for NP-hard problems. Oberwolfach Reports 1:1461–1540MathSciNetMATH Kannan R, Karpinski M (2005) Approximation algorithms for NP-hard problems. Oberwolfach Reports 1:1461–1540MathSciNetMATH
24.
go back to reference Hochba DS (1997) Approximation algorithms for NP-hard problems. ACM SIGACT News 28:40–52CrossRef Hochba DS (1997) Approximation algorithms for NP-hard problems. ACM SIGACT News 28:40–52CrossRef
25.
go back to reference Demirci G, Marincic I, Hoffmann H (2018) A divide and conquer algorithm for dag scheduling under power constraints. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pp 466–477 Demirci G, Marincic I, Hoffmann H (2018) A divide and conquer algorithm for dag scheduling under power constraints. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pp 466–477
27.
go back to reference Sulaiman M, Halim Z, Waqas M et al (2021) A hybrid list-based task scheduling scheme for heterogeneous computing. J Supercomput 77:10252–10288CrossRef Sulaiman M, Halim Z, Waqas M et al (2021) A hybrid list-based task scheduling scheme for heterogeneous computing. J Supercomput 77:10252–10288CrossRef
28.
go back to reference Topcuoglu H, Hariri S, Wu M-Y (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans parallel Distrib Syst 13:260–274CrossRef Topcuoglu H, Hariri S, Wu M-Y (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans parallel Distrib Syst 13:260–274CrossRef
29.
go back to reference Li J, Zhang X, Han L et al (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983CrossRef Li J, Zhang X, Han L et al (2021) OKCM: improving parallel task scheduling in high-performance computing systems using online learning. J Supercomput 77:5960–5983CrossRef
30.
go back to reference Ramezani R (2021) Dynamic scheduling of task graphs in multi-FPGA systems using the critical path. J Supercomput 77:597–618CrossRef Ramezani R (2021) Dynamic scheduling of task graphs in multi-FPGA systems using the critical path. J Supercomput 77:597–618CrossRef
31.
go back to reference Chowdhary SK, Rao ALN (2021) QoS Enhancement in Cloud-IoT Framework for Educational Institution with Task Allocation and Scheduling with Task-VM Matching Approach. Wireless PersCommun 121:267–286CrossRef Chowdhary SK, Rao ALN (2021) QoS Enhancement in Cloud-IoT Framework for Educational Institution with Task Allocation and Scheduling with Task-VM Matching Approach. Wireless PersCommun 121:267–286CrossRef
33.
go back to reference Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci (Ny) 270:255–287MathSciNetCrossRefMATH Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci (Ny) 270:255–287MathSciNetCrossRefMATH
34.
go back to reference Xu X-J, Xiao C-B, Tian G-Z, Sun T (2016) Hybrid scheduling deadline-constrained multi-DAGs based on reverse HEFT. In: 2016 International Conference on Information System and Artificial Intelligence (ISAI), pp 196–202 Xu X-J, Xiao C-B, Tian G-Z, Sun T (2016) Hybrid scheduling deadline-constrained multi-DAGs based on reverse HEFT. In: 2016 International Conference on Information System and Artificial Intelligence (ISAI), pp 196–202
35.
go back to reference Samimi P, Teimouri Y, Mukhtar M (2016) A combinatorial double auction resource allocation model in cloud computing. Inf Sci (Ny) 357:201–216CrossRefMATH Samimi P, Teimouri Y, Mukhtar M (2016) A combinatorial double auction resource allocation model in cloud computing. Inf Sci (Ny) 357:201–216CrossRefMATH
36.
go back to reference Rajak R, Shukla D, Alim A (2018) Modified critical path and top-level attributes (MCPTL)-based task scheduling algorithm in parallel computing. In: Soft Computing: Theories and Applications. Springer, pp 1–13 Rajak R, Shukla D, Alim A (2018) Modified critical path and top-level attributes (MCPTL)-based task scheduling algorithm in parallel computing. In: Soft Computing: Theories and Applications. Springer, pp 1–13
37.
go back to reference Rajak R (2018) Deterministic task scheduling method in multiprocessor environment. In: International Conference on Advances in Computing and Data Sciences, pp 331–341 Rajak R (2018) Deterministic task scheduling method in multiprocessor environment. In: International Conference on Advances in Computing and Data Sciences, pp 331–341
38.
go back to reference Rajak N, Shukla D, (2019) Performance analysis of workflow scheduling algorithm in cloud computing environment using priority attribute. Int J Adv Sci Technol Australia 28(16):1810 – 1831 Rajak N, Shukla D, (2019) Performance analysis of workflow scheduling algorithm in cloud computing environment using priority attribute. Int J Adv Sci Technol Australia 28(16):1810 – 1831
39.
go back to reference Braun TD, Siegel HJ, Beck N et al (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61:810–837CrossRef Braun TD, Siegel HJ, Beck N et al (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61:810–837CrossRef
40.
go back to reference Pop F, Dobre C, Cristea V (2009) Genetic algorithm for DAG scheduling in grid environments. In: 2009 IEEE 5th International Conference on Intelligent Computer Communication and Processing, pp 299–305 Pop F, Dobre C, Cristea V (2009) Genetic algorithm for DAG scheduling in grid environments. In: 2009 IEEE 5th International Conference on Intelligent Computer Communication and Processing, pp 299–305
41.
go back to reference Canon L-C, Jeannot E (2009) Evaluation and optimization of the robustness of dag schedules in heterogeneous environments. IEEE Trans Parallel Distrib Syst 21:532–546CrossRef Canon L-C, Jeannot E (2009) Evaluation and optimization of the robustness of dag schedules in heterogeneous environments. IEEE Trans Parallel Distrib Syst 21:532–546CrossRef
42.
go back to reference Raza Abbas Haidri (2020) ChittaranjanPadmanabhKatti, Prem Chandra Saxena, Cost effective deadline aware scheduling strategy for workflow applications on virtual machines in cloud computing. J King Saud Univ Comput Inf Sci 32(6):666–683 Raza Abbas Haidri (2020) ChittaranjanPadmanabhKatti, Prem Chandra Saxena, Cost effective deadline aware scheduling strategy for workflow applications on virtual machines in cloud computing. J King Saud Univ Comput Inf Sci 32(6):666–683
43.
go back to reference Darbha S, Aggarwal DP (1994) SDBS: A task duplication based optimal scheduling algorithm. In Proceedings of IEEE scalable high performance computing conference, Knoxville, TN, pp 756_61. Darbha S, Aggarwal DP (1994) SDBS: A task duplication based optimal scheduling algorithm. In Proceedings of IEEE scalable high performance computing conference, Knoxville, TN, pp 756_61.
44.
go back to reference Sinnen O Task scheduling for parallel systems. Wiley-Interscience Publication (2007) Sinnen O Task scheduling for parallel systems. Wiley-Interscience Publication (2007)
45.
go back to reference Kumar MS, Gupta I (2017) Jana PK Delay-based workflow scheduling for cost optimization in heterogeneous cloud system. In: 2017 Tenth International Conference on Contemporary Computing (IC3), Noida, pp. 1–6 Kumar MS, Gupta I (2017) Jana PK Delay-based workflow scheduling for cost optimization in heterogeneous cloud system. In: 2017 Tenth International Conference on Contemporary Computing (IC3), Noida, pp. 1–6
46.
go back to reference Gupta I, Kumar MS, Jana PK (2018) Efficient workflow scheduling algorithm for cloud computing system: a dynamic priority-based approach. Arab J Sci Eng 43(12):7945–7960CrossRef Gupta I, Kumar MS, Jana PK (2018) Efficient workflow scheduling algorithm for cloud computing system: a dynamic priority-based approach. Arab J Sci Eng 43(12):7945–7960CrossRef
47.
go back to reference Hwang K (2005) Advanced computer architecture: parallelism,scalability, programmability, 5th reprint. New Delhi:TMH Publishing Company, pp 51_104 Hwang K (2005) Advanced computer architecture: parallelism,scalability, programmability, 5th reprint. New Delhi:TMH Publishing Company, pp 51_104
48.
go back to reference Akbar MF, Munir EU, Rafique M M, Malik, Khan SU, Yang LT (2016)zs List-Based Task Scheduling for Cloud Computing. In: 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), Chengdu, pp 652–659 Akbar MF, Munir EU, Rafique M M, Malik, Khan SU, Yang LT (2016)zs List-Based Task Scheduling for Cloud Computing. In: 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), Chengdu, pp 652–659
49.
go back to reference Kalra M, Singh S (2015) A review of metaheuristic scheduling techniques in cloud computing. Egypt informatics J 16:275–295CrossRef Kalra M, Singh S (2015) A review of metaheuristic scheduling techniques in cloud computing. Egypt informatics J 16:275–295CrossRef
50.
go back to reference Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT press Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT press
Metadata
Title
A novel technique to optimize quality of service for directed acyclic graph (DAG) scheduling in cloud computing environment using heuristic approach
Authors
Ranjit Rajak
Shrawan Kumar
Shiv Prakash
Nidhi Rajak
Pratibha Dixit
Publication date
04-08-2022
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 2/2023
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-022-04729-4

Other articles of this Issue 2/2023

The Journal of Supercomputing 2/2023 Go to the issue

Premium Partner