Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 23/2018

09-06-2018 | Focus

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

Authors: Naqin Zhou, FuFang Li, Kefu Xu, Deyu Qi

Published in: Soft Computing | Issue 23/2018

Log in

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

search-config
loading …

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.
previous article Dimension reduction in radio maps based on the supervised kernel principal component analysis
next article Verifiable privacy-preserving single-layer perceptron training scheme in cloud computing

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

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!

inform 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!

inform now

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!

inform now
Literature
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
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
Metadata
Title
Concurrent workflow budget- and deadline-constrained scheduling in heterogeneous distributed environments
Authors
Naqin Zhou
FuFang Li
Kefu Xu
Deyu Qi
Publication date
09-06-2018
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 23/2018
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-018-3229-3

Other articles of this Issue 23/2018

Soft Computing 23/2018 Go to the issue

Focus

Research on QoS service composition based on coevolutionary genetic algorithm

Focus

A self-feedback strategy differential evolution with fitness landscape analysis

Focus

A new container scheduling algorithm based on multi-objective optimization

Focus

An efficient and secure searchable public key encryption scheme with privacy protection for cloud storage

Focus

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

Focus

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

Premium Partner

    Image Credits