Similar articles

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.

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

[1]Abrishami, S., Naghibzadeh, M., Epema, D., 2010. Cost-driven scheduling of grid workflows using partial critical paths. 11th IEEE/ACM Int. Conf. on Grid Computing, p.81-88.

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

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

[4]Bittencourt, L., Madeira, E., 2011. HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds. J. Internet Serv. Appl., 2(3):207-227.

[5]Blazewicz, J., Ecker, K., Schmidt, G., et al., 1993. Scheduling in Computer and Manufacturing Systems. Springer Publishing Company.

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

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

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

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

[10]Canfora, G., Penta, M., Esposito, R., et al., 2005b. QoS-aware replanning of composite web services. Proc. IEEE Int. Conf. on Web Services, 1:121-129.

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

[12]Chin, S., Suh, T., Yu, H., 2010. Adaptive service scheduling for workflow applications in service-oriented grid. J. Supercomput., 52(3):253-283.

[13]Chirigati, F., Silva, V., Ogasawara, E., et al., 2012. Evaluating parameter sweep workflows in high performance computing. Proc. 1st ACM SIGMOD Workshop on Scalable Workflow Execution Engines and Technologies, p.1-10.

[14]Coutinho, F., Ogasawara, E., de Oliveira, D., et al., 2010. Data parallelism in bioinformatics workflows using Hydra. Proc. 19th ACM Int. Symp. on High Performance Distributed Computing, p.507-515.

[15]Czarnul, P., 2006. Integration of compute-intensive tasks into scientific workflows in BeesyCluster. Proc. 6th Int. Conf. on Computational Science, p.944-947.

[16]Czarnul, P., 2010. 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, p.629-636.

[17]Czarnul, P., 2013a. Modeling, run-time optimization and execution of distributed workflow applications in the JEE-based BeesyCluster environment. J Supercomput., 63(1):46-71.

[18]Czarnul, P., 2013b. A model, design, and implementation of an efficient multithreaded workflow execution engine with data streaming, caching, and storage constraints. J Supercomput., 63(3):919-945.

[19]Czarnul, P., Dziubich, T., Krawczyk, H., 2012. Evaluation of multimedia applications in a cluster oriented environment. Metrol. Meas. Syst., 19(2):177-190.

[20]Deelman, E., Blythe, J., Gil, Y., et al., 2004. Pegasus: mapping scientific workflows onto the grid. Grid Computing, p.11-20.

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

[22]Floudas, C., Lin, X., 2005. Mixed integer linear programming in process scheduling: modeling, algorithms, and applications. Ann. Oper. Res., 139(1):131-162.

[23]Gao, A., Yang, D., Tang, S., et al., 2005. Web service composition using integer programming-based models. IEEE Int. Conf. on e-Business Engineering, p.603-606.

[24]Garg, S., Buyya, R., Siegel, H., 2010. Time and cost trade-off management for scheduling parallel applications on utility grids. Fut. Gener. Comput. Syst., 26(8):1344-1355.

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

[26]Geppert, A., Kradolfer, M., Tombros, D., 1998. Market-based workflow management. In: Trends in Distributed Systems for Electronic Commerce. Springer Berlin Heidelberg, p.179-191.

[27]Juve, G., Chervenak, A., Deelman, E., et al., 2013. Characterizing and profiling scientific workflows. Fut. Gener. Comput. Syst., 29(3):682-692.

[28]Kyriazis, D., Tserpes, K., Menychtas, A., et al., 2008. An innovative workflow mapping mechanism for grids in the frame of quality of service. Fut. Gener. Comput. Syst., 24(6):498-511.

[29]Lin, C., Lu, S., 2011. Scheduling scientific workflows elastically for cloud computing. IEEE Int. Conf. on Cloud Computing, p.746-747.

[30]Ludäscher, B., Altintas, I., Berkley, C., et al., 2006. Scientific workflow management and the Kepler system. Concurr. Comput. Pract. Exper., 18(10):1039-1065.

[31]Majithia, S., Shields, M., Taylor, I., et al., 2004. Triana: a graphical web service composition and execution toolkit. IEEE Int. Conf. on Web Services, p.514-521.

[32]Mika, M., Waligora, G., Weglarz, J., 2011. Modelling and solving grid resource allocation problem with network resources for workflow applications. J. Schedul., 14(3):291-306.

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

[34]Rahman, M., Hassan, R., Ranjan, R., et al., 2013. Adaptive workflow scheduling for dynamic grid and cloud computing environment. Concurr. Comput. Pract. Exper., 25(13):1816-1842.

[35]Sakellariou, R., Zhao, H., Tsiakkouri, E., et al., 2007. Scheduling workflows with budget constraints. In: Integrated Research in Grid Computing. Springer, p.189-202.

[36]Stricker, C., Riboni, S., Kradolfer, M., et al., 2000. Market-based workflow management for supply chains of services. Proc. 33rd Hawaii Int. Conf. on System Sciences, p.1-10.

[37]Topcuoglu, H., Hariri, S., Wu, M., 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parall. Distr. Syst., 13(3):260-274.

[38]Varalakshmi, P., Ramaswamy, A., Balasubramanian, A., et al., 2011. An optimal workflow based scheduling and resource allocation in cloud. In: Advances in Computing and Communications. Springer Berlin Heidelberg, p.411-420.

[39]Wieczorek, M., Prodan, R., Fahringer, T., 2005. Scheduling of scientific workflows in the ASKALON grid environment. ACM SIGMOD Rec., 34(3):56-62.

[40]Wieczorek, M., Prodan, R., Fahringer, T., 2006. Comparison of workflow scheduling strategies on the Grid. Int. Conf. on Parallel Processing and Applied Mathematics, p.792-800.

[41]Wieczorek, M., Hoheisel, A., Prodan, R., 2009. Towards a general model of the multi-criteria workflow scheduling on the grid. Fut. Gener. Comput. Syst., 25(3):237-256.

[42]Yao, Y., Liu, J., Ma, L., 2010. Efficient cost optimization for workflow scheduling on grids. Int. Conf. on Management and Service Science, p.1-4.

[43]Yassa, S., Chelouah, R., Kadima, H., et al., 2013. Multi-objective approach for energy-aware workflow scheduling in cloud computing environments. Sci. World J., 2013:350934.

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

[45]Yu, J., Buyya, R., 2005. A taxonomy of workflow management systems for grid computing. J. Grid Comput., 3(3-4):171-200.

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

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

[48]Yu, J., Buyya, R., Tham, C., 2005. Cost-based scheduling of scientific workflow applications on utility grids. Proc. 1st IEEE Int. Conf. on e-Science and Grid Computing, p.1-8.

[49]Yu, J., Buyya, R., Ramamohanarao, K., 2008. Workflow scheduling algorithms for grid computing. In: Metaheuristics for Scheduling in Distributed Computing Environments. Springer Berlin Heidelberg, p.173-214.

[50]Yuan, Y., Li, X., Sun, C., 2007. Cost-effective heuristics for workflow scheduling in grid computing economy. Proc. 6th Int. Conf. on Grid and Cooperative Computing, p.322-329.

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

[52]Zeng, L., Benatallah, B., Ngu, A.H.H., et al., 2004. QoS-aware middleware for web services composition. IEEE Trans. Softw. Eng., 30(5):311-327.