Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Online scheduling of dependent tasks of cloud’s workflows to enhance resource utilization and reduce the makespan using multiple reinforcement learning-based agents

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

Due to different heterogeneous cloud resources and diverse and complex applications of the users, an optimal task scheduling, which can satisfy users and cloud service providers with energy-saving and cost-effective use of resources, is a major issue in cloud computing. On the one hand, network users are demanding the quality assurance of their requested services, minimizing their costs, and their own data security, and on the other hand, the service providers consider less power consumption, more efficient use of resources, and optimal utilization. In dependent tasks dealing with massive data, resource scheduling is considered as an important challenge. Due to the time limitation of online scheduling process of dependent tasks, many existing methods of the literature are not able to guarantee the best resource utilization. In this paper, a reinforcement learning approach is exploited in a multi-agent system for task scheduling and resource provisioning, in order to reduce the makespan, minimize the required power, optimize the cost of using the resources, and maximize the utilization of the resources (considering their expiration time), simultaneously. The proposed algorithm has two phases. In the first phase, the tasks are scheduled using reinforcement learning techniques, and in the second one, considering the information obtained from the scheduling phase, resources are allocated in a multi-agent environment. The results of experiments show that this method improves the efficiency of the use of resources and reduces their costs. Moreover, the expiration time of the tasks is observed and the total execution time and energy consumption will be significantly reduced.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Elastic Computer Cloud.

References

  • Abazari F, Analoui M, Takabi H, Fu S (2019) MOWS: multi-objective workflow scheduling in cloud computing based on heuristic algorithm. Simul Model Pract Theory 93:119–132

    Google Scholar 

  • Abualigah LMQ (2019) Feature selection and enhanced krill herd algorithm for text document clustering. Springer, Berlin, pp 1–165

    Google Scholar 

  • Abualigah LMQ, Hanandeh ES (2015) Applying genetic algorithms to information retrieval using vector space model. Int J Comput Sci Eng Appl 5(1):19

    Google Scholar 

  • Abualigah LM, Khader AT (2017) Unsupervised text feature selection technique based on hybrid particle swarm optimization algorithm with genetic operators for the text clustering. J Supercomput 73(11):4773–4795

    Google Scholar 

  • Abualigah LM, Khader AT, Hanandeh ES, Gandomi AH (2017) A novel hybridization strategy for krill herd algorithm applied to clustering techniques. Appl Soft Comput 60:423–435

    Google Scholar 

  • Abualigah LM, Khader AT, Hanandeh ES (2018a) Hybrid clustering analysis using improved krill herd algorithm. Appl Intell 48(11):4047–4071

    Google Scholar 

  • Abualigah LM, Khader AT, Hanandeh ES (2018b) A combination of objective functions and hybrid Krill herd algorithm for text document clustering analysis. Eng Appl Artif Intell 73:111–125

    Google Scholar 

  • Abualigah LM, Khader AT, Hanandeh ES (2018c) A new feature selection method to improve the document clustering using particle swarm optimization algorithm. J Comput Sci 25:456–466

    Google Scholar 

  • Alkhanak EN, Lee SP, Khan SUR (2015) Cost-aware challenges for workflow scheduling approaches in cloud computing environments: taxonomy and opportunities. Future Gener Comput Syst 50:3–21

    Google Scholar 

  • Altmann J, Kashef MM (2014) Cost model based service placement in federated hybrid clouds. Future Gener Comput Syst 41:79–90

    Google Scholar 

  • Bahrpeyma F, Haghighi H, Zakerolhosseini A (2015) An adaptive RL based approach for dynamic resource provisioning in cloud virtualized data centers. Computing 97(12):1209–1234

    MathSciNet  Google Scholar 

  • Bansal N, Maurya A, Kumar T, Singh M, Bansal S (2015) Cost performance of QoS Driven task scheduling in cloud computing. Procedia Comput Sci 57:126–130

    Google Scholar 

  • Barbierato E, Gribaudo M, Iacono M (2013) Modeling apache hive based applications in big data architectures. In: Proceedings of the 7th international conference on performance evaluation methodologies and tools. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), pp 30–38

  • Barrett E, Howley E, Duggan J (2011) A learning architecture for scheduling workflow applications in the cloud. In: Ninth IEEE European conference on web services (ECOWS), 2011. IEEE, pp 83–90

  • Barrett E, Howley E, Duggan J (2013) Applying reinforcement learning towards automating resource allocation and application scalability in the cloud. Concurr Comput Pract Exp 25(12):1656–1674

    Google Scholar 

  • Benifa JB, Dejey D (2019) Rlpas: reinforcement learning-based proactive auto-scaler for resource provisioning in cloud environment. Mob Netw Appl 24(4):1348–1363

    Google Scholar 

  • Berral JL, Gavalda R, Torres J (2011) Adaptive scheduling on power-aware managed data-centers using machine learning. In: 12th IEEE/ACM international conference on grid computing (GRID), 2011. IEEE, pp 66–73

  • Buyya R, Yeo CS, Venugopal S, Broberg J, Brandic I (2009) Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility. Future Gener Comput Syst 25(6):599–616

    Google Scholar 

  • Byun EK, Kee YS, Kim JS, Maeng S (2011) Cost optimized provisioning of elastic resources for application workflows. Future Gener Comput Syst 27(8):1011–1026

    Google Scholar 

  • Cai Z, Li X, Ruiz R (2017) Resource provisioning for task-batch based workflows with deadlines in public clouds. IEEE Trans Cloud Comput 7(3):814–826

    Google Scholar 

  • Calheiros RN, Ranjan R, Beloglazov A, De Rose CA, Buyya R (2011) CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw Pract Exp 41(1):23–50

    Google Scholar 

  • Cao G (2019) Topology-aware multi-objective virtual machine dynamic consolidation for cloud datacenter. Sustain Comput Inform Syst 21:179–188

    Google Scholar 

  • Castiglione A, Gribaudo M, Iacono M, Palmieri F (2014) Exploiting mean field analysis to model performances of big data architectures. Future Gener Comput Syst 37:203–211

    Google Scholar 

  • Chaisiri S, Lee BS, Niyato D (2012) Optimization of resource provisioning cost in cloud computing. IEEE Trans Serv Comput 5(2):164–177

    Google Scholar 

  • Chen W, Deelman E (2012) Workflowsim: a toolkit for simulating scientific workflows in distributed environments. In: IEEE 8th international conference on E-science (e-science), 2012. IEEE, pp 1–8

  • Dayan P, Watkins CJCH (1992) Q-learning. Mach Learn 8(3):279–292

    MATH  Google Scholar 

  • Ding Y, Qin X, Liu L, Wang T (2015) Energy efficient scheduling of virtual machines in cloud with deadline constraint. Future Gener Comput Syst. 1(50):62–74

    Google Scholar 

  • Duggan M, Flesk K, Duggan J, Howley E, Barrett E (2016) A reinforcement learning approach for dynamic selection of virtual machines in cloud data centres. In: 2016 sixth international conference on innovative computing technology (INTECH). IEEE, pp 92–97

  • Farahnakian F, Liljeberg P, Plosila J (2014) Energy-efficient virtual machines consolidation in cloud data centers using reinforcement learning. In: 22nd Euromicro international conference on parallel, distributed and network-based processing (PDP), 2014. IEEE, pp 500–507

  • Garg SK, Yeo CS, Anandasivam A, Buyya R (2011) Environment-conscious scheduling of HPC applications on distributed cloud-oriented data centers. J Parallel Distrib Comput 71(6):732–749

    MATH  Google Scholar 

  • Ghobaei-Arani M, Jabbehdari S, Pourmina MA (2018) An autonomic resource provisioning approach for service-based cloud applications: a hybrid approach. Future Gener Comput Syst 78:191–210

    Google Scholar 

  • Hosseinimotlagh S, Khunjush F, Samadzadeh R (2015) SEATS: smart energy-aware task scheduling in real-time cloud computing. J Supercomput 71(1):45–66

    Google Scholar 

  • Islam S, Keung J, Lee K, Liu A (2012) Empirical prediction models for adaptive resource provisioning in the cloud. Future Gener Comput Syst 28(1):155–162

    Google Scholar 

  • https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator

  • Janssens W (2008) The allocation of time and location information to activity-travel sequence data by means of reinforcement learning. In reinforcement learning. InTech, London

    Google Scholar 

  • Jin Y, Bouzid M, Kostadinov D, Aghasaryan A (2019) Resource management of cloud-enabled systems using model-free reinforcement learning. Ann Telecommun 74(9–10):625–636

    Google Scholar 

  • Juve G, Chervenak A, Deelman E, Bharathi S, Mehta G, Vahi K (2013) Characterizing and profiling scientific workflows. Future Gener Comput Syst 29(3):682–692

    Google Scholar 

  • Kaelbling LP, Littman ML, Moore AW (1996) Reinforcement learning: a survey. J Artif Intell Res 4:237–285

    Google Scholar 

  • Keshanchi B, Souri A, Navimipour NJ (2017) An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: formal verification, simulation, and statistical testing. J Syst Softw 124:1–21

    Google Scholar 

  • Lee YC, Han H, Zomaya AY, Yousif M (2015) Resource-efficient workflow scheduling in clouds. Knowl-Based Syst 80:153–162

    Google Scholar 

  • Li C, Wang Y, Tang H, Luo Y (2019) Dynamic multi-objective optimized replica placement and migration strategies for SaaS applications in edge cloud. Future Gener Comput Syst 100:921–937

    Google Scholar 

  • Liaqat M, Chang V, Gani A, Ab Hamid SH, Toseef M, Shoaib U, Ali RL (2017) Federated cloud resource management: review and discussion. J Netw Comput Appl 77:87–105

    Google Scholar 

  • Madni SHH, Latiff MSA, Ali J (2019) Multi-objective-oriented cuckoo search optimization-based resource scheduling algorithm for clouds. Arab J Sci Eng 44(4):3585–3602

    Google Scholar 

  • Maurer M, Breskovic I, Emeakaroha VC, Brandic I (2011) Revealing the MAPE loop for the autonomic management of cloud infrastructures. In: 2011 IEEE symposium on computers and communications (ISCC). IEEE, pp 147–152

  • McGough AS, Forshaw M, Gerrard C, Wheater S, Allen B, Robinson P (2014) Comparison of a cost-effective virtual cloud cluster with an existing campus cluster. Future Gener Comput Syst 41:65–78

    Google Scholar 

  • Milani AS, Navimipour NJ (2016) Load balancing mechanisms and techniques in the cloud environments: systematic literature review and future trends. J Netw Comput Appl 71:86–98

    Google Scholar 

  • Moghadam MH, Babamir SM (2018) Makespan reduction for dynamic workloads in cluster-based data grids using reinforcement-learning based scheduling. J Comput Sci 24:402–412

    MathSciNet  Google Scholar 

  • Muppala S, Chen G, Zhou X (2014) Multi-tier service differentiation by coordinated learning-based resource provisioning and admission control. J Parallel Distrib Comput 74(5):2351–2364

    Google Scholar 

  • Nouri SMR, Li H, Venugopal S, Guo W, He M, Tian W (2019) Autonomic decentralized elasticity based on a reinforcement learning controller for cloud applications. Future Gener Comput Syst 94:765–780

    Google Scholar 

  • Nowé A, Vrancx P, De Hauwere YM (2012) Game theory and multi-agent reinforcement learning. In: Wiering M, van Otterlo M (eds) Reinforcement learning. Adaptation, learning, and optimization, vol 12. Springer, Berlin, pp 441–470

    Google Scholar 

  • Orhean AI, Pop F, Raicu I (2018) New scheduling approach using reinforcement learning for heterogeneous distributed systems. J Parallel Distrib Comput 117:292–302

    Google Scholar 

  • Peng Z, Cui D, Zuo J, Li Q, Xu B, Lin W (2015) Random task scheduling scheme based on reinforcement learning in cloud computing. Clust Comput 18(4):1595–1607

    Google Scholar 

  • Petcu D, Macariu G, Panica S, Crăciun C (2013) Portable cloud applications—from theory to practice. Future Gener Comput Syst 29(6):1417–1430

    Google Scholar 

  • Qin Y, Wang H, Yi S, Li X, Zhai L (2020) An energy-aware scheduling algorithm for budget-constrained scientific workflows based on multi-objective reinforcement learning. J Supercomput 76(1):455–480

    Google Scholar 

  • Rehman A, Hussain SS, ur Rehman Z, Zia S, Shamshirband S (2019) Multi-objective approach of energy efficient workflow scheduling in cloud environments. Concurr Comput Pract Exp 31(8):e4949

    Google Scholar 

  • Shin S, Kim Y, Lee S (2015) Deadline-guaranteed scheduling algorithm with improved resource utilization for cloud computing. In: Consumer communications and networking conference (CCNC), 2015 12th annual IEEE. IEEE, pp 814–819

  • Simarro JLL, Moreno-Vozmediano R, Montero RS, Llorente IM (2011) Dynamic placement of virtual machines for cost optimization in multi-cloud environments. In: International conference on high performance computing and simulation (HPCS), 2011. IEEE, pp 1–7

  • Singh S, Chana I (2016) A survey on resource scheduling in cloud computing: issues and challenges. J Grid Comput 14(2):217–264

    Google Scholar 

  • Sutton RS, Barto AG (1998) Reinforcement learning: an introduction, vol 1. MIT Press, Cambridge

    MATH  Google Scholar 

  • Szepesvári C (2010) Algorithms for reinforcement learning. Synth Lect Artif Intell Mach Learn 4(1):1–103

    MATH  Google Scholar 

  • Tong Z, Deng X, Chen H, Mei J, Liu H (2019) QL-HEFT: a novel machine learning scheduling scheme base on cloud computing environment. Neural Comput Appl. https://doi.org/10.1007/s00521-019-04118-8

    Article  Google Scholar 

  • Toosi AN, Sinnott RO, Buyya R (2018) Resource provisioning for data-intensive applications with deadline constraints on hybrid clouds using Aneka. Future Gener Comput Syst 79:765–775

    Google Scholar 

  • Topcuoglu H, Hariri S, Wu MY (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260–274

    Google Scholar 

  • Vanhulsel M, Janssens D, Wets G, Vanhoof K (2009) Simulation of sequential data: an enhanced reinforcement learning approach. Expert Syst Appl 36(4):8032–8039

    Google Scholar 

  • Vasile MA, Pop F, Tutueanu RI, Cristea V, Kołodziej J (2015) Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing. Future Gener Comput Syst 51:61–71

    Google Scholar 

  • Wang Q, Tan MM, Tang X, Cai W (2017) Minimizing cost in IaaS clouds via scheduled instance reservation. In: IEEE 37th international conference on distributed computing systems (ICDCS), 2017. IEEE, pp 1565–1574

  • Wang Y, Liu H, Zheng W, Xia Y, Li Y, Chen P, Guo K, Xie H (2019) Multi-objective workflow scheduling with deep-Q-network-based multi-agent reinforcement learning. IEEE Access 7:39974–39982

    Google Scholar 

  • Wu Z, Madhyastha HV (2013) Understanding the latency benefits of multi-cloud webservice deployments. ACM SIGCOMM Comput Commun Rev 43(2):13–20

    Google Scholar 

  • Wu Y, Min G, Li K, Javadi B (2012) Modeling and analysis of communication networks in multicluster systems under spatio-temporal bursty traffic. IEEE Trans Parallel Distrib Syst 23(5):902–912

    Google Scholar 

  • Wu Y, Min G, Zhu D, Yang LT (2013) An analytical model for on-chip interconnects in multimedia embedded systems. ACM Trans EmbedComput Syst 13(1s):29

    Google Scholar 

  • Xu CZ, Rao J, Bu X (2012) URL: a unified reinforcement learning approach for autonomic cloud management. J Parallel Distrib Comput 72(2):95–105

    Google Scholar 

  • Zeng D, Gu L, Pan S, Cai J, Guo S (2019) Resource management at the network edge: a deep reinforcement learning approach. IEEE Netw 33(3):26–33

    Google Scholar 

  • Zhang M, Li H, Liu L, Buyya R (2018) An adaptive multi-objective evolutionary algorithm for constrained workflow scheduling in Clouds. Distrib Parallel Databases 36(2):339–368

    Google Scholar 

  • Zheng W, Wang C, Zhang D (2016) A randomization approach for stochastic workflow scheduling in clouds. Sci Program. https://doi.org/10.1155/2016/9136107

    Article  Google Scholar 

  • Zheng W, Qin Y, Emmanuel B, Zhang D, Chen J (2018) Cost optimization for deadline-aware scheduling of big-data processing jobs on clouds. Future Gener Comput Syst 82:244–255

    Google Scholar 

  • Zhong JH, Peng ZP, Li QR, He JG (2019) Multi workflow fair scheduling scheme research based on reinforcement learning. Procedia Comput Sci 154:117–123

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Engineering, Semnan Branch, Islamic Azad University, Semnan, Iran

    Ali Asghari, Mohammad Karim Sohrabi & Farzin Yaghmaee

  2. Department of Electrical and Computer Engineering, Semnan University, Semnan, Iran

    Farzin Yaghmaee

Authors
  1. Ali Asghari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammad Karim Sohrabi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Farzin Yaghmaee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohammad Karim Sohrabi.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Communicated by V. Loia.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Asghari, A., Sohrabi, M.K. & Yaghmaee, F. Online scheduling of dependent tasks of cloud’s workflows to enhance resource utilization and reduce the makespan using multiple reinforcement learning-based agents. Soft Comput 24, 16177–16199 (2020). https://doi.org/10.1007/s00500-020-04931-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-020-04931-7

Keywords

Search

Navigation