Skip to main content
Erschienen in: The Journal of Supercomputing 6/2017

02.12.2016

ATSDS: adaptive two-stage deadline-constrained workflow scheduling considering run-time circumstances in cloud computing environments

verfasst von: Reihaneh Khorsand, Faramarz Safi-Esfahani, Naser Nematbakhsh, Mehran Mohsenzade

Erschienen in: The Journal of Supercomputing | Ausgabe 6/2017

Einloggen

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

search-config
loading …

Abstract

A significant aspect of cloud computing is scheduling of a large number of real-time concurrent workflow instances. Most of the existing scheduling algorithms are designed for a single complex workflow instance. This study examined instance-intensive workflows bounded by SLA constraints, including user-defined deadlines.The scheduling method for these workflows with dynamic workloads should be able to handle changing conditions and maximize the utilization rate of the cloud resources. The study proposes an adaptive two-stage deadline-constrained scheduling (ATSDS) strategy that considers run-time circumstances of workflows in the cloud environment. The stages are workflow fragmentation and resource allocation.In the first stage, the workflows according to cloud run-time circumstances (number of Virtual Machines (VMs) and average available bandwidth) are dynamically fragmented. In the second stage, using the workflow deadline and the capacity of the VMs, the workflow fragments created are allocated to the VMs to be executed. The simulation results show improvements in terms of workflow completion time, number of messages exchanged, percentage of workflows that meet the deadline and VM usage cost compared to other approaches.

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

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!

Literatur
2.
Zurück zum Zitat Xu R, Liu X, Xie Y, Wang F, Zhang Ch (2014) Logistics scheduling based on cloud business workflows. In: IEEE 18th Int. Conf. Comput. Support. Coop. Work Des Xu R, Liu X, Xie Y, Wang F, Zhang Ch (2014) Logistics scheduling based on cloud business workflows. In: IEEE 18th Int. Conf. Comput. Support. Coop. Work Des
3.
Zurück zum Zitat Liu X, Ni Z, Yuan D, Jiang Y, Wu Z, Chen J (2011) A novel statistical time-series pattern based interval forecasting strategy for activity durations in workflow systems. J. Syst. Softw. 84:354–376CrossRef Liu X, Ni Z, Yuan D, Jiang Y, Wu Z, Chen J (2011) A novel statistical time-series pattern based interval forecasting strategy for activity durations in workflow systems. J. Syst. Softw. 84:354–376CrossRef
4.
Zurück zum Zitat Safi-Esfahani F, Azmi Murad M, Nasir Sulaiman M (2011) Run-time adaptable business process decentralization. Third Int. Conf. Information, Process. Knowl. Manag., no. c, pp 76–82 Safi-Esfahani F, Azmi Murad M, Nasir Sulaiman M (2011) Run-time adaptable business process decentralization. Third Int. Conf. Information, Process. Knowl. Manag., no. c, pp 76–82
5.
Zurück zum Zitat Li G, Muthusamy V (2010) A distributed service oriented architecture for business process execution. ACM Trans. Web, vol. V Li G, Muthusamy V (2010) A distributed service oriented architecture for business process execution. ACM Trans. Web, vol. V
6.
Zurück zum Zitat Sudha M, Monica M (2012) Dynamic adaptive workflow scheduling for instance intensive cloud applications. J Expert Syst (JES), vol. 1, No. 1, Copyr. World Sci. Publ., vol. 1, no. 1, pp. 31–36 Sudha M, Monica M (2012) Dynamic adaptive workflow scheduling for instance intensive cloud applications. J Expert Syst (JES), vol. 1, No. 1, Copyr. World Sci. Publ., vol. 1, no. 1, pp. 31–36
7.
Zurück zum Zitat Tan W (2007) Dynamic workflow model fragmentation for distributed execution. Comput Ind 58(5):381–391CrossRef Tan W (2007) Dynamic workflow model fragmentation for distributed execution. Comput Ind 58(5):381–391CrossRef
8.
Zurück zum Zitat Atluri V, Chun S, Mukkamala R (2007) A decentralized execution model for inter-organizational workflows. Distrib Parallel Databases, pp. 55–83 Atluri V, Chun S, Mukkamala R (2007) A decentralized execution model for inter-organizational workflows. Distrib Parallel Databases, pp. 55–83
9.
Zurück zum Zitat Wu Z, Liu X, Z Ni (2013) A market-oriented hierarchical scheduling strategy in cloud workflow systems. J Supercomput, Springer Sci. Media, LLC 63(1):256–293 Wu Z, Liu X, Z Ni (2013) A market-oriented hierarchical scheduling strategy in cloud workflow systems. J Supercomput, Springer Sci. Media, LLC 63(1):256–293
10.
Zurück zum Zitat Zhang F, Cao J, Hwang K, Li K, U. Khan S (2015) Adaptive workflow scheduling on cloud computing platforms with iterative ordinal optimization. IEEE Trans Cloud Comput, vol 7161 Zhang F, Cao J, Hwang K, Li K, U. Khan S (2015) Adaptive workflow scheduling on cloud computing platforms with iterative ordinal optimization. IEEE Trans Cloud Comput, vol 7161
11.
Zurück zum Zitat Hoenisch P, Schulte S, Dustdar Sh (2013) Workflow scheduling and resource allocation for cloud-based execution of elastic processes. IEEE 6th Int. Conf. Serv. Comput, Appl, 2013 Hoenisch P, Schulte S, Dustdar Sh (2013) Workflow scheduling and resource allocation for cloud-based execution of elastic processes. IEEE 6th Int. Conf. Serv. Comput, Appl, 2013
12.
Zurück zum Zitat Banerjee S, Adhikari M, Kar S, Biswas U (2015) Development and analysis of a new cloudlet allocation strategy for QoS improvement in cloud. Arab J Sci Eng 40:409–1425MathSciNetCrossRef Banerjee S, Adhikari M, Kar S, Biswas U (2015) Development and analysis of a new cloudlet allocation strategy for QoS improvement in cloud. Arab J Sci Eng 40:409–1425MathSciNetCrossRef
13.
Zurück zum Zitat Mohialdeen IA (2013) Comparative study of scheduling al-grotihms in cloud computing. J Comput Sci 9(2):252–263CrossRef Mohialdeen IA (2013) Comparative study of scheduling al-grotihms in cloud computing. J Comput Sci 9(2):252–263CrossRef
14.
Zurück zum Zitat Mendling J, Lassen KB (2006) On the transformation of control flow between block-oriented and graph-oriented process modeling languages. Inderscience Enterp. Ltd Mendling J, Lassen KB (2006) On the transformation of control flow between block-oriented and graph-oriented process modeling languages. Inderscience Enterp. Ltd
15.
Zurück zum Zitat Kopp O, Martin D, Wutke D, Leymann F (2008) On the choice between graph-based and block-structured business process modeling languages. Model. betrieblicher Informations Syst. (MobIS 2008), Saarbrücken Kopp O, Martin D, Wutke D, Leymann F (2008) On the choice between graph-based and block-structured business process modeling languages. Model. betrieblicher Informations Syst. (MobIS 2008), Saarbrücken
16.
Zurück zum Zitat Nguyen BT, Nguyen DH, Nguyen TT (2014) Translation from BPMN to BPEL, current techniques and limitations. Copyr. 2014 ACM 978-1-4503-2930-9/14/12, pp 21–30 Nguyen BT, Nguyen DH, Nguyen TT (2014) Translation from BPMN to BPEL, current techniques and limitations. Copyr. 2014 ACM 978-1-4503-2930-9/14/12, pp 21–30
17.
Zurück zum Zitat Mancioppi M, Danylevych O, Karastoyanova D (2011) Toward classification criteria for Process fragmentation techniques. 7th Int. Work. Bus. Process Des., pp 1–12 Mancioppi M, Danylevych O, Karastoyanova D (2011) Toward classification criteria for Process fragmentation techniques. 7th Int. Work. Bus. Process Des., pp 1–12
18.
Zurück zum Zitat Guo L, Robertson D, Burger Y (2005) A novel approach for enacting the distributed business workflows using BPEL4WS on the multi-agent platform. In: Proc. IEEE Int. Conf. Ebus. Eng. Washington, DC, pp 657–664 Guo L, Robertson D, Burger Y (2005) A novel approach for enacting the distributed business workflows using BPEL4WS on the multi-agent platform. In: Proc. IEEE Int. Conf. Ebus. Eng. Washington, DC, pp 657–664
19.
Zurück zum Zitat Viroli M, Denti E, Ricci A (2007) Engineering a BPEL orchestration engine as a multi-agent system. Sci Comput Program 66(3):226–245MathSciNetCrossRefMATH Viroli M, Denti E, Ricci A (2007) Engineering a BPEL orchestration engine as a multi-agent system. Sci Comput Program 66(3):226–245MathSciNetCrossRefMATH
20.
Zurück zum Zitat Baresi L, Maurino A (2006) Towards Distributed BPEL Orchestrations. Electron. Commun. EASST, vol. 3 Baresi L, Maurino A (2006) Towards Distributed BPEL Orchestrations. Electron. Commun. EASST, vol. 3
21.
Zurück zum Zitat Baeyens T (2013) BPM in the cloud. Springer, Berlin, LNCS 8094, pp 10–16 Baeyens T (2013) BPM in the cloud. Springer, Berlin, LNCS 8094, pp 10–16
22.
Zurück zum Zitat Khalaf R, Kopp O (2008) Maintaining data dependencies across BPEL process fragments. Int J Coop Inf Syst 17:259–282CrossRef Khalaf R, Kopp O (2008) Maintaining data dependencies across BPEL process fragments. Int J Coop Inf Syst 17:259–282CrossRef
23.
Zurück zum Zitat Khalaf R (2006) E Role-based decomposition of business processes using BPEL. IEEE Int. Conf, Web Serv Khalaf R (2006) E Role-based decomposition of business processes using BPEL. IEEE Int. Conf, Web Serv
24.
Zurück zum Zitat Fdhila W, Yildiz U (2009) A flexible approach for automatic process decentralization using dependency tables University of California. IEEE 7th Int. Conf. Web Serv., ICWS Fdhila W, Yildiz U (2009) A flexible approach for automatic process decentralization using dependency tables University of California. IEEE 7th Int. Conf. Web Serv., ICWS
25.
Zurück zum Zitat Sadiq W, Sadiq S (2006) Model driven distribution of collaborative business processes. IEEE Int. Conf. Serv. Comput., pp 1–4 Sadiq W, Sadiq S (2006) Model driven distribution of collaborative business processes. IEEE Int. Conf. Serv. Comput., pp 1–4
26.
Zurück zum Zitat Zhai Y, Su H (2007) A data flow optimization based approach for BPEL processes partition. IEEE Int. Conf. E-bus. Eng., pp 410–413 Zhai Y, Su H (2007) A data flow optimization based approach for BPEL processes partition. IEEE Int. Conf. E-bus. Eng., pp 410–413
27.
Zurück zum Zitat Cheng J (2012) An agent-oriented approach to process partition and planning in migrating workflow systems. Eng Appl Artif Intell 25(4):837–845CrossRef Cheng J (2012) An agent-oriented approach to process partition and planning in migrating workflow systems. Eng Appl Artif Intell 25(4):837–845CrossRef
28.
Zurück zum Zitat Safi-Esfahani F, Azmi Murad M, Nasir Sulaiman M (2011) Adaptable decentralized service oriented architecture. J Syst Softw 84(10):1591–1617CrossRef Safi-Esfahani F, Azmi Murad M, Nasir Sulaiman M (2011) Adaptable decentralized service oriented architecture. J Syst Softw 84(10):1591–1617CrossRef
29.
Zurück zum Zitat Teng F, Yang H, Li T, Yang Y (2013) Scheduling real-time workflow on mapreduce-based Cloud. 978-1-4799-0048-0/13/$31.00 2013 IEEE, pp 117–122 Teng F, Yang H, Li T, Yang Y (2013) Scheduling real-time workflow on mapreduce-based Cloud. 978-1-4799-0048-0/13/$31.00 2013 IEEE, pp 117–122
30.
Zurück zum Zitat Arabnia HR (1990) A parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput, pp 188–192 Arabnia HR (1990) A parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput, pp 188–192
31.
Zurück zum Zitat Arabnia HR (1993) Downloaded from Iran library: (http://www.libdl.ir) | Sponsored by Tehran Business School (http://www.tbs.ir). In: Proc. 7th Annu. Int. High Perform. Comput. Conf. (1993) High Perform. Comput. New Horizons Supercomput. Symp. Calgary, Alberta, Canada, June, pp 349–357 Arabnia HR (1993) Downloaded from Iran library: (http://​www.​libdl.​ir) | Sponsored by Tehran Business School (http://​www.​tbs.​ir). In: Proc. 7th Annu. Int. High Perform. Comput. Conf. (1993) High Perform. Comput. New Horizons Supercomput. Symp. Calgary, Alberta, Canada, June, pp 349–357
32.
Zurück zum Zitat Arabnia HR (1989) A transputer network for fast operations on digitised images. Int J Eurograph. Assoc. (Comput. Graph. Forum) 8(1):3–12CrossRef Arabnia HR (1989) A transputer network for fast operations on digitised images. Int J Eurograph. Assoc. (Comput. Graph. Forum) 8(1):3–12CrossRef
33.
Zurück zum Zitat Arabnia HR, Oliver MA (1987) Arbitrary rotation of raster images with SIMD machine architectures. Int. J. Eurographics Assoc. (Computer Graph. Forum), 6(1):3–12CrossRef Arabnia HR, Oliver MA (1987) Arbitrary rotation of raster images with SIMD machine architectures. Int. J. Eurographics Assoc. (Computer Graph. Forum), 6(1):3–12CrossRef
34.
Zurück zum Zitat Arabnia H. R (1995) A distributed stereocorrelation algorithm. In: Proc. Comput. Commun. Networks (ICCCN’95), IEEE, pp 479-482 Arabnia H. R (1995) A distributed stereocorrelation algorithm. In: Proc. Comput. Commun. Networks (ICCCN’95), IEEE, pp 479-482
35.
Zurück zum Zitat Arabnia HR (1986) Operations on raster images with SIMD machine architectures. Int. J. Eurograph. Assoc. (Comput. Graph. Forum) 5(3):179–188CrossRef Arabnia HR (1986) Operations on raster images with SIMD machine architectures. Int. J. Eurograph. Assoc. (Comput. Graph. Forum) 5(3):179–188CrossRef
36.
Zurück zum Zitat Arabnia HR (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. J Supercomput, Springer Publ. vol. 10, No. 3, pp 243–270, vol 269, pp 243–269 Arabnia HR (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. J Supercomput, Springer Publ. vol. 10, No. 3, pp 243–270, vol 269, pp 243–269
37.
Zurück zum Zitat Bhandarkar S, Arabnia HR (1995) The Hough transform on a reconfigurable multi-ring network. Parallel Distrib Comput 24(1):107–114CrossRef Bhandarkar S, Arabnia HR (1995) The Hough transform on a reconfigurable multi-ring network. Parallel Distrib Comput 24(1):107–114CrossRef
38.
Zurück zum Zitat Wani MA, Arabnia HR (2003) Parallel polygon approximation algorithm targeted at reconfigurable multi-ring hardware. J Supercomput 25(1):43–63CrossRefMATH Wani MA, Arabnia HR (2003) Parallel polygon approximation algorithm targeted at reconfigurable multi-ring hardware. J Supercomput 25(1):43–63CrossRefMATH
39.
Zurück zum Zitat Zhu M, Cao F (2014) High-throughput scientific workflow scheduling under deadline constraint in clouds. J Commun 9(4):312–321CrossRef Zhu M, Cao F (2014) High-throughput scientific workflow scheduling under deadline constraint in clouds. J Commun 9(4):312–321CrossRef
40.
Zurück zum Zitat Liu K, Jin H, Chen J, Liu X, Yuan D (2010) A compromised-time-cost scheduling algorithm in SwinDeW-C for instance-intensive cost-constrained workflows on cloud computing platform. Int J High Perform Comput Appl 24(2010):1–16 Liu K, Jin H, Chen J, Liu X, Yuan D (2010) A compromised-time-cost scheduling algorithm in SwinDeW-C for instance-intensive cost-constrained workflows on cloud computing platform. Int J High Perform Comput Appl 24(2010):1–16
41.
Zurück zum Zitat Li H, Ge S, Zhang L (2014) A QoS-based scheduling algorithm for instance-intensive workflows in cloud environment. Control Decis. Conf. (2014 CCDC), 26th Chinese, pp 4094–4099 Li H, Ge S, Zhang L (2014) A QoS-based scheduling algorithm for instance-intensive workflows in cloud environment. Control Decis. Conf. (2014 CCDC), 26th Chinese, pp 4094–4099
42.
Zurück zum Zitat Topcuoglu H, Hariri S, Wu M (2002) Performance-effective and low-complexity. IEEE Trans Parallel Distrib Syst 13(3):260–274CrossRef Topcuoglu H, Hariri S, Wu M (2002) Performance-effective and low-complexity. IEEE Trans Parallel Distrib Syst 13(3):260–274CrossRef
43.
Zurück zum Zitat Vega D (2010) Towards fuzzy granularity control in parallel/ distributed computing. Int J Child Comput Interact, pp 43–55 Vega D (2010) Towards fuzzy granularity control in parallel/ distributed computing. Int J Child Comput Interact, pp 43–55
44.
Zurück zum Zitat Moens H, Handekyn K (2013) Cost-aware scheduling of deadline-constrained task workflows in public cloud environments. 978-3-901882-50-0c 2013 IFIP, pp 68–75 Moens H, Handekyn K (2013) Cost-aware scheduling of deadline-constrained task workflows in public cloud environments. 978-3-901882-50-0c 2013 IFIP, pp 68–75
45.
Zurück zum Zitat Ghafarian T (2013) Deadline-constrained workflow scheduling in volunteer computing systems. Springer Int. Publ. Switz Ghafarian T (2013) Deadline-constrained workflow scheduling in volunteer computing systems. Springer Int. Publ. Switz
46.
Zurück zum Zitat Mao M, Humphrey M (2011) Auto-scaling to minimize cost and meet application deadlines in cloud workflows. SC11, Novemb. 12–18, 2011, Seattle, Washington, USA Copyr. 2011 ACM 978-1-4503-0771 Mao M, Humphrey M (2011) Auto-scaling to minimize cost and meet application deadlines in cloud workflows. SC11, Novemb. 12–18, 2011, Seattle, Washington, USA Copyr. 2011 ACM 978-1-4503-0771
47.
Zurück zum Zitat Ramakrishnan L, Chase JS, Gannon D, Nurmi D, Wolski R (2011) Deadline-sensitive workflow orchestration without explicit resource control. J Parallel Distrib Comput 71(3):343–353CrossRef Ramakrishnan L, Chase JS, Gannon D, Nurmi D, Wolski R (2011) Deadline-sensitive workflow orchestration without explicit resource control. J Parallel Distrib Comput 71(3):343–353CrossRef
48.
Zurück zum Zitat Harper jS, Wilcox DV (2000) A toolset for the performance prediction of parallel and distributed systems. Int J High Perform Comput Appl 14(3):228–251CrossRef Harper jS, Wilcox DV (2000) A toolset for the performance prediction of parallel and distributed systems. Int J High Perform Comput Appl 14(3):228–251CrossRef
49.
Zurück zum Zitat Cooper K, Dasgupta A, Kennedy K, Koelbel C, Mandal A, Marin G, Mazina M, Berman F, Casanova H, Chien A, Dail H, Liu X, Olugbile A, Sievert O, Xia H, Johnsson L, Liu B, Patel M, Reed D, Deng W, Mendes C (2004) New grid scheduling and rescheduling methods in the GrADS project. NSF Next Gener. Softw. Work. Int. Parallel Distrib. Process. Symp. St. Fe, IEEE CS Press. Los Alamitos, CA, USA Cooper K, Dasgupta A, Kennedy K, Koelbel C, Mandal A, Marin G, Mazina M, Berman F, Casanova H, Chien A, Dail H, Liu X, Olugbile A, Sievert O, Xia H, Johnsson L, Liu B, Patel M, Reed D, Deng W, Mendes C (2004) New grid scheduling and rescheduling methods in the GrADS project. NSF Next Gener. Softw. Work. Int. Parallel Distrib. Process. Symp. St. Fe, IEEE CS Press. Los Alamitos, CA, USA
50.
Zurück zum Zitat Jang S, Wu X, Taylor V, Texas A, Station C, Mehta G, Vahi K, Deelman E, Way A, Del Rey M, (2004) Using performance prediction to allocate grid resources. Tech. Rep. 2004-25, GriPhyN Proj. USA, pp 1–11 Jang S, Wu X, Taylor V, Texas A, Station C, Mehta G, Vahi K, Deelman E, Way A, Del Rey M, (2004) Using performance prediction to allocate grid resources. Tech. Rep. 2004-25, GriPhyN Proj. USA, pp 1–11
51.
Zurück zum Zitat Mostinckx S, Van Cutsem T, Timbermont S, Boix E.G, Tanter E, De Meuter W (2011) CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw. Pract. Exp. Publ. Wiley Online Libr., vol 39, no. 7, pp 661–699 Mostinckx S, Van Cutsem T, Timbermont S, Boix E.G, Tanter E, De Meuter W (2011) CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw. Pract. Exp. Publ. Wiley Online Libr., vol 39, no. 7, pp 661–699
52.
Zurück zum Zitat Li G, Muthusamy V, Jacobsen H (2010) A distributed service-oriented architecture for business process execution. ACM Trans. Web, 4(1) Li G, Muthusamy V, Jacobsen H (2010) A distributed service-oriented architecture for business process execution. ACM Trans. Web, 4(1)
Metadaten
Titel
ATSDS: adaptive two-stage deadline-constrained workflow scheduling considering run-time circumstances in cloud computing environments
verfasst von
Reihaneh Khorsand
Faramarz Safi-Esfahani
Naser Nematbakhsh
Mehran Mohsenzade
Publikationsdatum
02.12.2016
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 6/2017
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-016-1928-z

Weitere Artikel der Ausgabe 6/2017

The Journal of Supercomputing 6/2017 Zur Ausgabe