具有动态变化服务可用性的工作流应用程序调度算法比较

Paweł CZARNUL

doi:10.1631/jzus.C1300270

Your Location：

Home >

Browse articles >

具有动态变化服务可用性的工作流应用程序调度算法比较

计算机与自动化 | Updated：2022-05-19

- 具有动态变化服务可用性的工作流应用程序调度算法比较
- Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability
- 信息与电子工程前沿（英文） 2014年15卷第6期页码：401-422
- Affiliations：
  
  Department of Computer Architecture, Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Gdansk 80-233, Poland
- Author bio：
  
  [ "Paweł CZARNUL, E-mail: pczarnul@eti.pg.gda.pl; pczarnul@gmail.com" ]
- Funds：
  
  Project partially supported by the Polish National Science Center(No. DEC-2012/07/B/ST6/01516)
- DOI：10.1631/jzus.C1300270
  中图分类号： TP302
- 收稿：2013-09-29，
  
  修回：2014-;5-;4，
  
  纸质出版：2014-06
- Accepted：
Scan QR Code
具有动态变化服务可用性的工作流应用程序调度算法比较[J]. 信息与电子工程前沿（英文）, 2014,15(6):401-422.

Paweł CZARNUL. Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(6): 401-422.
具有动态变化服务可用性的工作流应用程序调度算法比较[J]. 信息与电子工程前沿（英文）, 2014,15(6):401-422. DOI： 10.1631/jzus.C1300270.

Paweł CZARNUL. Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability[J]. Frontiers of Information Technology & Electronic Engineering, 2014, 15(6): 401-422. DOI： 10.1631/jzus.C1300270.

摘要

研究目的

在服务可用性和相关参数可变的环境中，选取合适的工作流应用程序调度算法，在预算范围内，尽可能降低工作流的执行时间。根据不同算法的比较，提出一个在具有动态变化服务可用性的环境中获取最优调度方案的模型。

研究方法

在服务可用性和其他服务质量参数动态变化的环境中，比较不同调度算法--包括整数线性规划算法（ILP）、启发式整数线性规划算法（ILPHEU）、分治算法（DaC）、遗传算法（GA）以及收益算法（GAIN）--在不同条件下的性能和成本（图6-图23），得出相应条件下各算法的性能排序（图24），并在实际环境（BeesyCluster）中测试。

重要结论

得出不同算法的执行时间（表5）和优缺点（表6）以及处理不同尺度问题时的性能排序--（1）对于小工作流（如6个节点），性能排序（由高至低）：ILP>DaC>GAIN>GA；（2）对于中等工作流（如40个节点），性能排序：ILPHEU>GAIN>DaC>GA；（3）对于大工作流（如100多个节点、几百项服务），性能排序：ILPHEU>DaC>GAIN>GA。

Abstract

This paper compares the quality and execution times of several algorithms for scheduling service based workflow applications with changeable service availability and parameters. A workflow is defined as an acyclic directed graph with nodes corresponding to tasks and edges to dependencies between tasks. For each task

one out of several available services needs to be chosen and scheduled to minimize the workflow execution time and keep the cost of service within the budget. During the execution of a workflow

some services may become unavailable

new ones may appear

and costs and execution times may change with a certain probability. Rescheduling is needed to obtain a better schedule. A solution is proposed on how integer linear programming can be used to solve this problem to obtain optimal solutions for smaller problems or suboptimal solutions for larger ones. It is compared side-by-side with GAIN

divide-and-conquer

and genetic algorithms for various probabilities of service unavailability or change in service parameters. The algorithms are implemented and subsequently tested in a real BeesyCluster environment.

关键词

Keywords

references

S. Abrishami , , , M. Naghibzadeh , , , D. Epema . . Cost-driven scheduling of grid workflows using partial critical paths . . 11th IEEE/ACM Int. Conf. on Grid Computing , , 2010 . . p.81 - - 88 . . DOI: 10.1109/GRID.2010.5697955 http://doi.org/10.1109/GRID.2010.5697955 . .

R. Aggarwal , , , K. Verma , , , J. Miller , , , 等 . . Constraint driven web service composition in METEOR-S . . Proc. IEEE Int. Conf. on Services Computing , , 2004a . . p.23 - - 30 . . . .

R. Aggarwal , , , K. Verma , , , J. Miller , , , 等 . . Dynamic Web Service Composition in METEOR-S . . Technical Report, LSDIS Lab, Univeristy of Georgia, Georgia, USA , , 2004b . . .

L. Bittencourt , , , E. Madeira . . HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds . . J. Internet Serv. Appl. , , 2011 . . 2 ( ( 3 ): ): 207 - - 227 . . DOI: 10.1007/s13174-011-0032-0 http://doi.org/10.1007/s13174-011-0032-0 . .

J. Blazewicz , , , K. Ecker , , , G. Schmidt , , , 等 . . Scheduling in Computer and Manufacturing Systems . . Springer Publishing Company , , 1993 . . DOI: 10.1007/978-3-662-00074-8 http://doi.org/10.1007/978-3-662-00074-8 . .

J. Blythe , , , S. Jain , , , E. Deelman , , , 等 . . Task scheduling strategies for workflow-based applications in grids . . IEEE Int. Symp. on Cluster Computing and the Grid , , 2005 . . p.759 - - 767 . . . .

T. Braun , , , H. Siegel , , , N. Beck , , , 等 . . A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems . . Proc. Heterogeneous Computing Workshop , , 1999 . . p.15 - - 29 . . . .

G. Canfora , , , M. Penta . . A lightweight approach for QoS-aware service composition . . Proc. 2nd Int. Conf. on Service Oriented Computing , , 2004 . . p.1 - - 10 . . . .

G. Canfora , , , M. Penta , , , R. Esposito , , , 等 . . An approach for QoS-aware service composition based on genetic algorithms . . Proc. Conf. on Genetic and Evolutionary Computation , , 2005a . . p.1069 - - 1075 . . . .

G. Canfora , , , M. Penta , , , R. Esposito , , , 等 . . QoS-aware replanning of composite web services . . Proc. IEEE Int. Conf. on Web Services , , 2005b . . 1 121 - - 129 . . DOI: 10.1109/ICWS.2005.96 http://doi.org/10.1109/ICWS.2005.96 . .

J. Cardoso , , , A. Sheth , , , J. Miller . . Workflow Quality of Service . . Technical Report, LSDIS Lab, Computer Science, Univiersity of Georgia, Georgia, USA , , 2002 . . .

S. Chin , , , T. Suh , , , H. Yu . . Adaptive service scheduling for workflow applications in service-oriented grid . . J. Supercomput. , , 2010 . . 52 ( ( 3 ): ): 253 - - 283 . . DOI: 10.1007/s11227-009-0290-9 http://doi.org/10.1007/s11227-009-0290-9 . .

F. Chirigati , , , V. Silva , , , E. Ogasawara , , , 等 . . Evaluating parameter sweep workflows in high performance computing . . Proc. 1st ACM SIGMOD Workshop on Scalable Workflow Execution Engines and Technologies , , 2012 . . p.1 - - 10 . . DOI: 10.1145/2443416.2443418 http://doi.org/10.1145/2443416.2443418 . .

F. Coutinho , , , E. Ogasawara , , , D. de Oliveira , , , 等 . . Data parallelism in bioinformatics workflows using Hydra . . Proc. 19th ACM Int. Symp. on High Performance Distributed Computing , , 2010 . . p.507 - - 515 . . DOI: 10.1145/1851476.1851550 http://doi.org/10.1145/1851476.1851550 . .

P. Czarnul . . Integration of compute-intensive tasks into scientific workflows in BeesyCluster . . Proc. 6th Int. Conf. on Computational Science , , 2006 . . p.944 - - 947 . . DOI: 10.1007/11758532_127 http://doi.org/10.1007/11758532_127 . .

P. Czarnul . . Modelling, optimization and execution of workflow applications with data distribution, service selection and budget constraints in BeesyCluster . . Proc. Int. Multiconf. on Computer Science and Information Technology , , 2010 . . p.629 - - 636 . . . .

P. Czarnul . . Modeling, run-time optimization and execution of distributed workflow applications in the JEE-based BeesyCluster environment . . J Supercomput. , , 2013a . . 63 ( ( 1 ): ): 46 - - 71 . . DOI: 10.1007/s11227-010-0499-7 http://doi.org/10.1007/s11227-010-0499-7 . .

P. Czarnul . . A model, design, and implementation of an efficient multithreaded workflow execution engine with data streaming, caching, and storage constraints . . J Supercomput. , , 2013b . . 63 ( ( 3 ): ): 919 - - 945 . . DOI: 10.1007/s11227-012-0837-z http://doi.org/10.1007/s11227-012-0837-z . .

P. Czarnul , , , T. Dziubich , , , H. Krawczyk . . Evaluation of multimedia applications in a cluster oriented environment . . Metrol. Meas. Syst. , , 2012 . . 19 ( ( 2 ): ): 177 - - 190 . . DOI: 10.2478/v10178-012-0016-9 http://doi.org/10.2478/v10178-012-0016-9 . .

E. Deelman , , , J. Blythe , , , Y. Gil , , , 等 . . Pegasus: mapping scientific workflows onto the grid . . Grid Computing , , 2004 . . p.11 - - 20 . . DOI: 10.1007/978-3-540-28642-4_2 http://doi.org/10.1007/978-3-540-28642-4_2 . .

E. Deelman , , , G. Singha , , , M. Sua , , , 等 . . Pegasus: a framework for mapping complex scientific workflows onto distributed systems . . Sci. Program. , , 2005 . . 13 ( ( 3 ): ): 219 - - 237 . . . .

C. Floudas , , , X. Lin . . Mixed integer linear programming in process scheduling: modeling, algorithms, and applications . . Ann. Oper. Res. , , 2005 . . 139 ( ( 1 ): ): 131 - - 162 . . DOI: 10.1007/s10479-005-3446-x http://doi.org/10.1007/s10479-005-3446-x . .

A. Gao , , , D. Yang , , , S. Tang , , , 等 . . Web service composition using integer programming-based models . . IEEE Int. Conf. on e-Business Engineering , , 2005 . . p.603 - - 606 . . DOI: 10.1109/ICEBE.2005.127 http://doi.org/10.1109/ICEBE.2005.127 . .

S. Garg , , , R. Buyya , , , H. Siegel . . Time and cost trade-off management for scheduling parallel applications on utility grids . . Fut. Gener. Comput. Syst. , , 2010 . . 26 ( ( 8 ): ): 1344 - - 1355 . . DOI: 10.1016/j.future.2009.07.003 http://doi.org/10.1016/j.future.2009.07.003 . .

T. Genez , , , L. Bittencourt , , , E. Madeira . . Workflow scheduling for SaaS/PaaS cloud providers considering two SLA levels . . IEEE Network Operations and Management Symp. , , 2012 . . p.906 - - 912 . . . .

A. Geppert , , , M. Kradolfer , , , D. Tombros . . Market-based workflow management . . In : Trends in Distributed Systems for Electronic Commerce. Springer Berlin Heidelberg , , 1998 . . p.179 - - 191 . . DOI: 10.1007/BFb0053410 http://doi.org/10.1007/BFb0053410 . .

G. Juve , , , A. Chervenak , , , E. Deelman , , , 等 . . Characterizing and profiling scientific workflows . . Fut. Gener. Comput. Syst. , , 2013 . . 29 ( ( 3 ): ): 682 - - 692 . . DOI: 10.1016/j.future.2012.08.015 http://doi.org/10.1016/j.future.2012.08.015 . .

D. Kyriazis , , , K. Tserpes , , , A. Menychtas , , , 等 . . An innovative workflow mapping mechanism for grids in the frame of quality of service . . Fut. Gener. Comput. Syst. , , 2008 . . 24 ( ( 6 ): ): 498 - - 511 . . DOI: 10.1016/j.future.2007.07.009 http://doi.org/10.1016/j.future.2007.07.009 . .

C. Lin , , , S. Lu . . Scheduling scientific workflows elastically for cloud computing . . IEEE Int. Conf. on Cloud Computing , , 2011 . . p.746 - - 747 . . DOI: 10.1109/CLOUD.2011.110 http://doi.org/10.1109/CLOUD.2011.110 . .

B. Ludscher , , , I. Altintas , , , C. Berkley , , , 等 . . Scientific workflow management and the Kepler system . . Concurr. Comput. Pract. Exper. , , 2006 . . 18 ( ( 10 ): ): 1039 - - 1065 . . DOI: 10.1002/cpe.994 http://doi.org/10.1002/cpe.994 . .

S. Majithia , , , M. Shields , , , I. Taylor , , , 等 . . Triana: a graphical web service composition and execution toolkit . . IEEE Int. Conf. on Web Services , , 2004 . . p.514 - - 521 . . DOI: 10.1109/ICWS.2004.1314777 http://doi.org/10.1109/ICWS.2004.1314777 . .

M. Mika , , , G. Waligora , , , J. Weglarz . . Modelling and solving grid resource allocation problem with network resources for workflow applications . . J. Schedul. , , 2011 . . 14 ( ( 3 ): ): 291 - - 306 . . DOI: 10.1007/s10951-009-0158-0 http://doi.org/10.1007/s10951-009-0158-0 . .

C. Patel , , , K. Supekar , , , Y. Lee . . A QoS oriented framework for adaptive management of web service based workflows . . Proc. 14th Int. Database and Expert Systems Applications Conf. , , 2003 . . p.826 - - 835 . . . .

M. Rahman , , , R. Hassan , , , R. Ranjan , , , 等 . . Adaptive workflow scheduling for dynamic grid and cloud computing environment . . Concurr. Comput. Pract. Exper. , , 2013 . . 25 ( ( 13 ): ): 1816 - - 1842 . . DOI: 10.1002/cpe.3003 http://doi.org/10.1002/cpe.3003 . .

R. Sakellariou , , , H. Zhao , , , E. Tsiakkouri , , , 等 . . Scheduling workflows with budget constraints . . In : Integrated Research in Grid Computing. Springer , , 2007 . . p.189 - - 202 . . DOI: 10.1007/978-0-387-47658-2_14 http://doi.org/10.1007/978-0-387-47658-2_14 . .

C. Stricker , , , S. Riboni , , , M. Kradolfer , , , 等 . . Market- based workflow management for supply chains of services . . Proc. 33rd Hawaii Int. Conf. on System Sciences , , 2000 . . p.1 - - 10 . . DOI: 10.1109/HICSS.2000.926843 http://doi.org/10.1109/HICSS.2000.926843 . .

H. Topcuoglu , , , S. Hariri , , , M. Wu . . Performance- effective and low-complexity task scheduling for heterogeneous computing . . IEEE Trans. Parall. Distr. Syst. , , 2002 . . 13 ( ( 3 ): ): 260 - - 274 . . DOI: 10.1109/71.993206 http://doi.org/10.1109/71.993206 . .

P. Varalakshmi , , , A. Ramaswamy , , , A. Balasubramanian , , , 等 . . An optimal workflow based scheduling and resource allocation in cloud . . In : Advances in Computing and Communications. Springer Berlin Heidelberg , , 2011 . . p.411 - - 420 . . DOI: 10.1007/978-3-642-22709-7_41 http://doi.org/10.1007/978-3-642-22709-7_41 . .

M. Wieczorek , , , R. Prodan , , , T. Fahringer . . Scheduling of scientific workflows in the ASKALON grid environment . . ACM SIGMOD Rec. , , 2005 . . 34 ( ( 3 ): ): 56 - - 62 . . DOI: 10.1145/1084805.1084816 http://doi.org/10.1145/1084805.1084816 . .

M. Wieczorek , , , R. Prodan , , , T. Fahringer . . Comparison of workflow scheduling strategies on the Grid . . Int. Conf. on Parallel Processing and Applied Mathematics , , 2006 . . p.792 - - 800 . . DOI: 10.1007/11752578_95 http://doi.org/10.1007/11752578_95 . .

M. Wieczorek , , , A. Hoheisel , , , R. Prodan . . Towards a general model of the multi-criteria workflow scheduling on the grid . . Fut. Gener. Comput. Syst. , , 2009 . . 25 ( ( 3 ): ): 237 - - 256 . . DOI: 10.1016/j.future.2008.09.002 http://doi.org/10.1016/j.future.2008.09.002 . .

Y. Yao , , , J. Liu , , , L. Ma . . Efficient cost optimization for workflow scheduling on grids . . Int. Conf. on Management and Service Science , , 2010 . . p.1 - - 4 . . DOI: 10.1109/ICMSS.2010.5577645 http://doi.org/10.1109/ICMSS.2010.5577645 . .

S. Yassa , , , R. Chelouah , , , H. Kadima , , , 等 . . Multi- objective approach for energy-aware workflow scheduling in cloud computing environments . . Sci. World J. , , 2013 . . 2013 350934 DOI: 10.1155/2013/350934 http://doi.org/10.1155/2013/350934 . .

L. Young , , , S. McGough , , , S. Newhouse , , , 等 . . Scheduling architecture and algorithms within the ICENI grid middleware . . UK e-Science All Hands Meeting , , 2003 . . p.5 - - 12 . . . .

J. Yu , , , R. Buyya . . A taxonomy of workflow management systems for grid computing . . J. Grid Comput. , , 2005 . . 3 ( ( 3-4 ): ): 171 - - 200 . . DOI: 10.1007/s10723-005-9010-8 http://doi.org/10.1007/s10723-005-9010-8 . .

J. Yu , , , R. Buyya . . A budget constrained scheduling of workflow applications on utility grids using genetic algorithms . . Workshop on Workflows in Support of Large-Scale Science , , 2006a . . p.1 - - 10 . . . .

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

J. Yu , , , R. Buyya , , , C. Tham . . Cost-based scheduling of scientific workflow applications on utility grids . . Proc. 1st IEEE Int. Conf. on e-Science and Grid Computing , , 2005 . . p.1 - - 8 . . DOI: 10.1109/E-SCIENCE.2005.26 http://doi.org/10.1109/E-SCIENCE.2005.26 . .

J. Yu , , , R. Buyya , , , K. Ramamohanarao . . Workflow scheduling algorithms for grid computing . . In : Metaheuristics for Scheduling in Distributed Computing Environments. Springer Berlin Heidelberg , , 2008 . . p.173 - - 214 . . DOI: 10.1007/978-3-540-69277-5_7 http://doi.org/10.1007/978-3-540-69277-5_7 . .

Y. Yuan , , , X. Li , , , C. Sun . . Cost-effective heuristics for workflow scheduling in grid computing economy . . Proc. 6th Int. Conf. on Grid and Cooperative Computing , , 2007 . . p.322 - - 329 . . DOI: 10.1109/GCC.2007.57 http://doi.org/10.1109/GCC.2007.57 . .

L. Zeng , , , B. Benatallah , , , M. Dumas , , , 等 . . Quality driven web services composition . . Proc. 12th Int. Conf. on World Wide Web , , 2003 . . p.411 - - 421 . . . .

L. Zeng , , , B. Benatallah , , , A.H.H. Ngu , , , 等 . . QoS-aware middleware for web services composition . . IEEE Trans. Softw. Eng. , , 2004 . . 30 ( ( 5 ): ): 311 - - 327 . . DOI: 10.1109/TSE.2004.11 http://doi.org/10.1109/TSE.2004.11 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据