Weitere Artikel dieser Ausgabe durch Wischen aufrufen
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Cloud Computing enables delivery of IT resources over the Internet and follows the pay-as-you-go billing model. The cloud infrastructures can be used as an appropriate environment for executing of workflow applications. To execute workflow applications in this environment, it is necessary to develop the workflow scheduling algorithms that consider different QoS parameters such as execution time and cost. Therefore, in this paper we focus on two criteria: total completion time (makespan) and execution cost of workflow, and propose two heuristic algorithms: MTDC (Minimum Time and Decreased Cost) which aims to create a schedule that minimizes the makespan and decreases execution cost, and CTDC (Constrained Time and Decreased Cost) which is based on the first algorithm (MTDC) and aims to create a schedule that decreases the execution cost while satisfying the deadline constraint of the workflow application. The proposed algorithms are evaluated by a simulation process using WorkflowSim. To evaluate the proposed algorithms, the results of MTDC are compared with the results of HEFT (Heterogeneous Earliest Finish Time), and the results of CTDC are compared with the results of heuristic based algorithms [such as IC-PCP (IaaS Cloud Partial Critical Paths), IC-PCPD2 (Deadline Distribution) and BDHEFT (Budget and Deadline HEFT)] and meta-heuristic based algorithms [such as PSO (Particle Swarm Optimization) and CGA2 (Coevolutionary Genetic Algorithm with Adaptive penalty function)]. The results show that the proposed algorithms perform better than the mentioned algorithms in most cases.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Juve, G., Deelman, E., Vahi, K., Mehta, G., Berriman, B., Berman, B. P., & Maechling, P. (2010). Scientific workflow applications on Amazon EC2. In 5th IEEE international conference on e-Science.
Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., & Vahi, K. (2012). Characterizing and profiling scientific workflows. Future Generation Computer Systems, 29(3), 682–692. CrossRef
Mao, M., & Humphrey, M. (2011). Auto-scaling to minimize cost and meet application deadlines in cloud workflows. In Proceedings of 2011 international conference for high performance computing, networking, storage and analysis, Seattle, Washington (pp. 1–49).
Wu, F, Wu, Q., & Tan, Y. (2015). Workflow scheduling in cloud: A survey. The Journal of Supercomputing, 71(9), 3373–3418. CrossRef
Mell, P., & Grance, T. (2011). The NIST definition of cloud computing. Gaithersburg: Computer Security Division, Information Technology Laboratory, National Institute of Standards and Technology. CrossRef
Hoffa, C., Mehta, G., Freeman, T., Deelman, E., et al. (2008). On the use of cloud computing for scientific workflows. In Proceedings of the 2008 Fourth IEEE international conference on eScience (pp. 640–645).
Juve, G., & Deelman, E. (2011). Scientific workflows in the cloud. In M. Cafaro & G. Aloisio (Eds.), Grids, clouds and virtualization (pp. 71–91). New York: Springer. CrossRef
Abrishami, S., Naghibzadeh, M., & Epema, D. (2013). Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Generation Computer Systems, 29(1), 158–169. CrossRef
Garey, M., Johnson, D., & Computers and Intractability. (1990). A guide to the theory of NP-completeness. New York, NY: W. H. Freeman & Co.
Arabnejad, H., Barbosa, J., & Prodan, R. (2016). Low-time complexity budget-deadline constrained workflow scheduling on heterogeneous resources. Future Generation Computer Systems, 55(c), 29–40. CrossRef
Topcuouglu, H., Hariri, S., & Wu, M. (2002). Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transaction Parallel Distributed Systems, 13(3), 260–274. CrossRef
Kwok, Y. K., & Ahmad, I. (1996). Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors. IEEE Transaction Parallel Distributed Systems, 7(5), 506–521. CrossRef
Hagras, T., & Janecek, J. (2003). A Simple scheduling heuristic for heterogeneous computing environments. In Proceedings of the second international conference on parallel and distributed computing (pp. 104–110).
Ilavarasan, E., Thambidurai, P., & Mahilmannan, R. (2005). High performance task scheduling algorithm for heterogeneous computing system. In International conference on algorithms and architectures for parallel processing (pp. 193-203). CrossRef
Ilavarasan, E., & Thambidurai, P. (2007). Low complexity performance effective task scheduling algorithm for heterogeneous computing environments. Journal of Computer Sciences, 3(2), 94–103.
Bittencourt, L., Sakellariou, R., & Madeira, E. (2010). DAG scheduling using a look ahead variant of the heterogeneous earliest finish time algorithm. In 18th Euromicro conference on parallel, distributed and network-based processing (pp. 27–34).
Arabnejad, H., & Barbosa, J. G. (2014). List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Transactions on Parallel and Distributed Systems, 25(3), 682–694. CrossRef
Canon, L., Jeannot, E., Sakellariou, R., & Zheng, W. (2008). Comparative evaluation of the robustness of DAG scheduling heuristics. In Grid computing achievements and prospects (pp. 73–84). New York: Springer. CrossRef
Calheiros, R., & Buyya, R. (2014). Meeting deadlines of scientific workflows in public clouds with tasks replication. IEEE Transactions on Parallel and Distributed Systems, 25(7), 1787–1796. CrossRef
Sahni, J., & Vidyarthi, D. (2015). A cost-effective deadline-constrained dynamic scheduling algorithm for scientific workflows in a cloud environment. IEEE Transactions on Cloud Computing, 1(1), 99.
Chopra, N., & Singh, S. (2013). HEFT based workflow scheduling algorithm for cost optimization within deadline in hybrid clouds. In Proceeding of fourth international conference on computing (pp. 1–6). Bengaluru, India: Communications and Networking Technologies (ICCCNT).
Yu, J., Ramamohanarao, K., & Buyya, R. (2009). Deadline/budget-based scheduling of workflows on utility grids. Market-Oriented Grid and Utility Computing, 200(9), 427–450. CrossRef
Yuan, Y., Li, X., Wang, Q., & Zhang, Y. (2008). Bottom level based heuristic for workflow scheduling in grids. Chinese Journal of Computers, 31(2), 282. CrossRef
Yuan, Y., Li, X., Wang, Q., & Zhu, X. (2009). Deadline division-based heuristic for cost optimization in workflow scheduling. Information Sciences, 179(15), 2562–2575. CrossRef
Chen, W., Xie, G., Li, R., Bai, R., Fan, C., & Li, K. (2017). Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud. Future Generation Computer Systems, 74(C), 1–11. CrossRef
Wu, C. Q., Lin, X., Yu, D., Xu, W., & Li, L. (2015). End-to-end delay minimization for scientific workflows in clouds under budget constraint. IEEE Transactions on Cloud Computing, 3(2), 169–181. CrossRef
Lin, X., & Wu, C. (2013). On scientific workflow scheduling in clouds under budget constraint. In 42nd IEEE International Conference on Parallel Processing (ICPP) (pp. 90–99).
Yu, J., Ramamohanarao, K., & Buyya, R. (2009). Deadline/budget-based scheduling of workflows on utility grids. Market-oriented grid and utility computing. New York: Wiley.
Arabnejad, H., & Barbosa, J. (2014). A budget constrained scheduling algorithm for workflow applications. The Journal of Grid Computing, 12(4), 665–679. CrossRef
Sakellariou, R., & Zhao, H., et al. (2007). Scheduling workflows with budget constraints Integrated Research in GRID Computing. New York: Springer. ISBN 978-0-387-47658-2.
Zeng, L., & Veeravalli, B., Li, X. (2012). Budget conscious scheduling precedence-constrained many-task workflow applications in cloud. In Proceedings of IEEE 26th international conference on advanced information networking and applications, Fukuoka, Japan.
Poola, D., Garg, S. K., Buyya, R., Yang, Y., & Ramamohanarao, K. (2014). Robust scheduling of scientific workflows with deadline and budget constraints in clouds. In 2014 IEEE 28th international conference on advanced information networking and applications (pp. 858-865).
Zheng, W., & Sakellariou, R. (2013). Budget-deadline constrained workflow planning for admission control. The Journal of Grid Computing, 11(4), 633–651. CrossRef
Malawski, M., Juve, G., Deelman, E., & Nabrzyski, J. (2015). Algorithms for cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds. Future Generation Computer Systems, 48(1), 1–18. CrossRef
Yu, J., & Rajkumar, B. (2006). Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms. Scientific Programming, 14(3), 217–230. CrossRef
Pandey, S., Wu, L., Guru, S. M., & Buyya, R. (2010). A particle swarm optimization based heuristic for scheduling workflow applications in cloud computing environments. In 24th IEEE international conference on advanced information networking and applications (AINA) (pp. 400-407).
Liu, L., Zhang, M., Buyya, R., & Fan, Q. (2017). Deadline-constrained coevolutionary genetic algorithm for scientific workflow scheduling in cloud computing. Concurrency and Computation: Practice and Experience, 29(5), e3942. CrossRef
Bryk, P., Malawski, M., Juve, G., & Deelman, E. (2016). Storage-aware algorithms for scheduling of workflow ensembles in clouds. Journal of Grid Computing, 14(2), 359–378. CrossRef
Zhang, S., Chen, X., & Huo, X. (2010). Cloud computing research and development trend. In Second international conference on future networks, 2010, ICFN’10 (pp. 93–97).
Chen, W., & Deelman, E. (2012). WorkflowSim: A toolkit for simulating scientific workflows in distributed environments. In 2012 IEEE 8th international conference on E-Science (e-Science) (pp. 1–8).
Calheiros, R., Ranjan, R., Beloglazov, A., De, R., & Buyya, R. (2011). CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Software: Practice and Experience, 14(1), 23–50.
Bharathi, S., Chervenak, A., Deelman, E., Mehta, G., Su, M. H., & Vahi, K. (2008). Characterization of scientific workflows. In 2008 third workshop on workflows in support of large-scale science (pp. 1–10).
- Time-Cost Efficient Scheduling Algorithms for Executing Workflow in Infrastructure as a Service Clouds
- Springer US