nach oben

Soft Computing

Erschienen in:

09.06.2018 | Focus

Concurrent workflow budget- and deadline-constrained scheduling in heterogeneous distributed environments

verfasst von: Naqin Zhou, FuFang Li, Kefu Xu, Deyu Qi

Erschienen in: Soft Computing | Ausgabe 23/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In heterogeneous distributed environment, it is a great challenge to schedule multiple workflows submitted at different times. Particularly, scheduling of concurrent workflows with deadline and budget constraints makes the problem become more complex. Recent studies have proposed dynamic scheduling strategies for concurrent workflows which have limitations in inconsistent environments. Therefore, this paper presents a new dynamic scheduling algorithm for concurrent workflows. This algorithm proposes a uniform ranking that considers the time and costs for both workflows and workgroups to assign priorities for tasks. In the resource selection phase, it controls the resource selection range for each task based on an optimistic budget for the current task and selects resources for the current task according to a defined bi-factor. The experimental results show that our algorithm outperforms the existing algorithms in both consistent and inconsistent environments.

Vorheriger Artikel Dimension reduction in radio maps based on the supervised kernel principal component analysis

Nächster Artikel Verifiable privacy-preserving single-layer perceptron training scheme in cloud computing

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Abrishami S, Naghibzadeh M, Epema DHJ (2012) Cost-driven scheduling of grid workflows using partial critical paths. IEEE Trans Parallel Distrib Syst 23(8):1400–1414CrossRef

Abrishami S, Naghibzadeh M, Epema DHJ (2013) Deadline-constrained workflow scheduling algorithms for Infrastructure as a service clouds. Future Gen Comput Syst 29(1):158–169CrossRef

Arabnejad H, Barbosa JG (2014a) A budget constrained scheduling algorithm for workflow applications. J Grid Comput 12(4):665–679CrossRef

Arabnejad H, Barbosa JG (2014c) List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Trans Parallel Distrib Syst 25(3):682–694CrossRef

Arabnejad H, Barbosa JG (2016) Maximizing the completion rate of concurrent scientific applications under time and budget constraints. J Comput Sci 23(2017):120–129MathSciNet

Arabnejad H, Barbosa JG, Suter F (2014) Fair resource sharing for dynamic scheduling of workflows on heterogeneous systems. Series on parallel and distributed computing. Wiley, New York, pp 145–167

Arabnejad H, Barbosa JG, Prodan R (2015) Low-time complexity budget-deadline constrained workflow scheduling on heterogeneous resources. Future Gen Comput Syst 55:29–40CrossRef

Arabnejad H, Barbosa J (2012) Fairness resource sharing for dynamic workflow scheduling on heterogeneous systems. In: IEEE international symposium on parallel and distributed processing with applications. IEEE, pp 633–639

Arabnejad H, Barbosa JG (2014b) Budget constrained scheduling strategies for on-line workflow applications. In: International conference on computational science and its applications. Springer, pp 532–545

Arabnejad H, Barbosa JG (2015) Multi-workflow QoS-constrained scheduling for utility computing. In: Computational science and engineering (CSE), 2015 IEEE 18th international conference on IEEE, pp 137–144

Azad P, Navimipour NJ, Azad P, Navimipour NJ (2017) An energy-aware task scheduling in the cloud computing using a hybrid cultural and ant colony optimization algorithm. Int J Cloud Appl Comput 7(4):20–40

Bittencourt LF, Madeira ERM (2010) Towards the scheduling of multiple workflows on computational grids. J Grid Comput 8(3):419–441CrossRef

Broberg J, Venugopal S, Buyya R (2008) Market-oriented grids and utility computing: the state-of-the-art and future directions. J Grid Comput 6(3):255–276CrossRef

Casanova H, Legrand A, Quinson M (2008) SimGrid: a generic framework for large-scale distributed experiments. In: Proceedings of the tenth international conference on computer modeling and simulation. IEEE, pp 126–131

Chen W, Xie G, Li R, Bai Y, Fan C, Li K (2017) Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems. Future Gen Comput Syst 74(2017):1–11CrossRef

Daoud MI, Kharma N (2008) A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. J Parallel Distrib Comput 68(4):399–409CrossRef

Fahringer T et al (2005) ASKALON: a grid application development and computing environment. In: Proceedings of the 6th IEEE/ACM international workshop on grid computing. IEEE Computer Society, pp 122–131

Guo-Zhong T, Chuang-Bai X, Zhu-Sheng X, Xia X (2012) Hybrid scheduling strategy for multiple DAGs workflow in heterogeneous system. J Softw 23(10):2720–2734CrossRef

Gupta BB, Agrawal DP, Yamaguchi S (2016) Handbook of research on modern cryptographic solutions for computer and cyber security. IGI Global, New York, pp 96–125CrossRef

Hossain MS, Muhammad G, Abdul W, Song B, Gupta BB (2017) Cloud-assisted secure video transmission and sharing framework for smart cities. Future Gen Comput Syst 83(2018):596–606

Hsu CC, Huang KC, Wang FJ (2011) Online scheduling of workflow applications in grid environment. Future Gen Comput Syst 27(6):860–870CrossRef

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

Li Y, Wang G, Nie L, Wang Q, Tan W (2017) Distance metric optimization driven convolutional neural network for age invariant face recognition. Pattern Recogn 75:51–62CrossRef

Lin W, Xu S, He L, Li J (2017) Multi-resource scheduling and power simulation for cloud computing. Inf Sci 397(A):168–186CrossRef

Maheswaran M, Ali S, Siegel HJ, Hensgen D, Freund RF (1999) Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems. In: Heterogeneous computing workshop. IEEE, pp 30–44

Patra SS (2018) Energy-efficient task consolidation for cloud data center. Int J Cloud Appl Comput 8(1):117–142MathSciNet

Prodan R, Wieczorek M (2010) Bi-criteria scheduling of scientific grid workflows. IEEE Trans Autom Sci Eng 7(2):364–376CrossRef

Sakellariou R, Zhao H, Tsiakkouri E, Dikaiakos MD (2007) Scheduling workflows with budget constraints. In:Integrated research in GRID computing. Springer, pp 189–202

Stergiou C, Psannis KE, Kim BG, Gupta B (2016) Secure integration of IoT and cloud computing. Future Gen Comput Syst 78(2018):964–975

Suter F (2017) A synthethic task graph generator. https://github.com/frs69wq/daggen. Accessed 10 May 2017

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

Wang H, Wang W, Cui Z, Zhou X, Zhao J, Li Y (2018) A new dynamic firefly algorithm for demand estimation of water resources. Inf Sci 438:95–106MathSciNetCrossRef

Weiwei Lin SX, Li J, Lingling X, Peng Z (2017a) Design and theoretical analysis of virtual machine placement algorithm based on peak workload characteristics. Soft Comput 21(5):1301–1314CrossRef

Weiwei Lin ZW, Lin L, Wen A, Li J (2017) An ensemble random forest algorithm for insurance big data analysis. IEEE Access 5(2017):16568–16575CrossRef

Wu F, Wu Q, Tan Y, Li R, Wang W (2016) PCP-B 2: partial critical path budget balanced scheduling algorithms for scientific workflow applications. Future Gen Comput Syst 60(2016):22–34CrossRef

Xiao-Le W, Hong-Bin H, Su D (2012) List scheduling algorithm for static task with precedence constraints for cyber-physical systems. Acta Autom Sin 38(11):1870–1879CrossRef

Xu X, Xiao C, Tian G, Sun T (2017) Expansion slot backfill scheduling for concurrent workflows with deadline on heterogeneous resources. Clust Comput 20(1):471–483CrossRef

Ying Huang WL, Zhengping Liang Y, Xue XW (2018) Efficient business process consolidation: combining topic features with structure matching. Soft Comput 22(2):645–657CrossRef

Yu J, Buyya R (2006) Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms. Sci Program 14(3–4):217–230

Yu J, Buyya R, Ramamohanarao K (2008) Workflow scheduling algorithms for grid computing. Springer, Berlin, pp 173–214MATH

Yu Z, Shi W (2008) A planner-guided scheduling strategy for multiple workflow applications. In: International conference on parallel processing-workshops. Icpp-W. IEEE, pp 1–8

Zhao H, Sakellariou R (2006) Scheduling multiple DAGs onto heterogeneous systems. In: Parallel and distributed processing symposium, IPDPS 2006, 20th international. IEEE, pp 159–159

Zheng W, Sakellariou R (2013) Budget-deadline constrained workflow planning for admission control. J Grid Comput 11(4):633–651CrossRef

Zheng W, Sakellariou R (2011) Budget-deadline constrained workflow planning for admission control in market-oriented environments. In: International workshop on grid economics and business models. Springer, pp 105–119

Zhou N, Qi D, Wang X, Zheng Z, Lin W (2017) A list scheduling algorithm for heterogeneous systems based on a critical node cost table and pessimistic cost table. Concurr Comput Pract Exp 29(5):e3944. https://doi.org/10.1002/cpe.3944 CrossRef

Titel: Concurrent workflow budget- and deadline-constrained scheduling in heterogeneous distributed environments
verfasst von: Naqin Zhou
FuFang Li
Kefu Xu
Deyu Qi
Publikationsdatum: 09.06.2018
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 23/2018
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-018-3229-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 23/2018

A class of belief structures based on possibility measures

Innovative Savonius rotors evolved by genetic algorithm based on 2D-DCT encoding

Checking virtual machine kernel control-flow integrity using a page-level dynamic tracing approach

Verifiable privacy-preserving single-layer perceptron training scheme in cloud computing

Face pose estimation based on kernelized maximum separability

A bibliometric analysis of text mining in medical research

Premium Partner