Document Open Access Logo

Deadline-Budget constrained Scheduling Algorithm for Scientific Workflows in a Cloud Environment

Authors Mozhgan Ghasemzadeh, Hamid Arabnejad, Jorge G. Barbosa

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.19.pdf
  • Filesize: 0.67 MB
  • 16 pages

Document Identifiers

Author Details

Mozhgan Ghasemzadeh
Hamid Arabnejad
Jorge G. Barbosa

Cite AsGet BibTex

Mozhgan Ghasemzadeh, Hamid Arabnejad, and Jorge G. Barbosa. Deadline-Budget constrained Scheduling Algorithm for Scientific Workflows in a Cloud Environment. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.OPODIS.2016.19

Abstract

Recently cloud computing has gained popularity among e-Science environments as a high performance computing platform. From the viewpoint of the system, applications can be submitted by users at any moment in time and with distinct QoS requirements. To achieve higher rates of successful applications attending to their QoS demands, an effective resource allocation (scheduling) strategy between workflow's tasks and available resources is required. Several algorithms have been proposed for QoS workflow scheduling, but most of them use search-based strategies that generally have a higher time complexity, making them less useful in realistic scenarios. In this paper, we present a heuristic scheduling algorithm with quadratic time complexity that considers two important constraints for QoS-based workflow scheduling, time and cost, named Deadline-Budget Workflow Scheduling (DBWS) for cloud environments. Performance evaluation of some well-known scientific workflows shows that the DBWS algorithm accomplishes both constraints with higher success rate in comparison to the current state-of-the-art heuristic-based approaches.
Keywords
  • Resource management
  • QoS scheduling
  • scientific workflow applications
  • deadline-constrained
  • budget-constrained

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Saeid Abrishami, Mahmoud Naghibzadeh, and Dick H. J. Epema. Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Generation Computer Systems, 29(1):158-169, 2013. Google Scholar
  2. Ehab Nabiel Alkhanak, Sai Peck Lee, and Saif Ur Rehman Khan. Cost-aware challenges for workflow scheduling approaches in cloud computing environments: Taxonomy and opportunities. Future Generation Computer Systems, 50(0):3-21, 2015. Google Scholar
  3. Hamid Arabnejad and Jorge G. Barbosa. List scheduling algorithm for heterogeneous systems by an optimistic cost table. Parallel and Distributed Systems, IEEE Transactions on, 25(3):682-694, 2014. Google Scholar
  4. Kahina Bessai, Samir Youcef, Ammar Oulamara, Claude Godart, and Selmin Nurcan. Bi-criteria workflow tasks allocation and scheduling in cloud computing environments. In 5th Int. Conf. on Cloud Computing, pages 638-645. IEEE, 2012. Google Scholar
  5. Rodrigo N. Calheiros and Rajkumar Buyya. Meeting deadlines of scientific workflows in public clouds with tasks replication. Parallel and Distributed Systems, IEEE Transactions on, 25(7):1787-1796, 2014. Google Scholar
  6. Wei-Neng Chen and Jun Zhang. A set-based discrete PSO for cloud workflow scheduling with user-defined QoS constraints. In Int. Conf. on Systems, Man, and Cybernetics (SMC), pages 773-778. IEEE, 2012. Google Scholar
  7. Juan J. Durillo and Radu Prodan. Multi-objective workflow scheduling in amazon ec2. Cluster Computing, 17(2):169-189, 2014. Google Scholar
  8. Alexandru Iosup, Simon Ostermann, M. Nezih Yigitbasi, Radu Prodan, Thomas Fahringer, and Dick H. J. Epema. Performance analysis of cloud computing services for many-tasks scientific computing. Parallel and Distributed Systems, IEEE Transactions on, 22(6):931-945, 2011. Google Scholar
  9. S. Jang, Xingfu Wu, Valerie Taylor, Gaurang Mehta, Karan Vahi, and Ewa Deelman. Using performance prediction to allocate grid resources. Technical report, Technical Report 2004-25, GriPhyN Project, USA, 2004. Google Scholar
  10. Gideon Juve, Ann Chervenak, Ewa Deelman, Shishir Bharathi, Gaurang Mehta, and Karan Vahi. Characterizing and profiling scientific workflows. Future Generation Computer Systems, 29(3):682-692, 2013. Google Scholar
  11. Young Choon Lee and Albert Y. Zomaya. Stretch out and compact: Workflow scheduling with resource abundance. In 13th IEEE/ACM Int. Symp. on Cluster, Cloud and Grid Computing (CCGrid), pages 219-226. IEEE, 2013. Google Scholar
  12. Wenjuan Li, Qifei Zhang, Jiyi Wu, Jing Li, and Haili Zhao. Trust-based and qos demand clustering analysis customizable cloud workflow scheduling strategies. In Cluster Computing Workshops, pages 111-119. IEEE, 2012. Google Scholar
  13. Xiangyu Lin and Chase Qishi Wu. On scientific workflow scheduling in clouds under budget constraint. In 42nd International Conference on Parallel Processing (ICPP), pages 90-99. IEEE, 2013. Google Scholar
  14. Nguyen Doan Man and Eui-Nam Huh. Cost and efficiency-based scheduling on a general framework combining between cloud computing and local thick clients. In Int. Conf. on Computing, Management and Telecommunications, pages 258-263. IEEE, 2013. Google Scholar
  15. Ming Mao and Marty Humphrey. A performance study on the vm startup time in the cloud. In 5th International Conference on Cloud Computing, pages 423-430. IEEE, 2012. Google Scholar
  16. Sahar Mirzayi and Vahid Rafe. A hybrid heuristic workflow scheduling algorithm for cloud computing environments. Journal of Experimental &Theoretical Artificial Intelligence, 27(6):721-735, 2015. URL: http://dx.doi.org/10.1080/0952813X.2015.1020524.
  17. Graham R. Nudd, Darren J. Kerbyson, Efstathios Papaefstathiou, Stewart C. Perry, John S. Harper, and Daniel V. Wilcox. Pace - a toolset for the performance prediction of parallel and distributed systems. International Journal of High Performance Computing Applications, 14(3):228-251, 2000. Google Scholar
  18. D. Poola, S. K. Garg, R. Buyya, Yun Yang, and K. Ramamohanarao. Robust scheduling of scientific workflows with deadline and budget constraints in clouds. In 28th Int. Conf. on Advanced Information Networking and Applications, pages 858-865. IEEE, 2014. Google Scholar
  19. Mustafizur Rahman, Xiaorong Li, and Henry Palit. Hybrid heuristic for scheduling data analytics workflow applications in hybrid cloud environment. In Int. Symp. on Parallel and Distributed Processing (IPDPSW), pages 966-974. IEEE, 2011. Google Scholar
  20. Jyoti Sahni and Deo Vidyarthi. A cost-effective deadline-constrained dynamic scheduling algorithm for scientific workflows in a cloud environment. IEEE Transactions on Cloud Computing, PP(99):1-1, 2015. Google Scholar
  21. Rizos Sakellariou, Henan Zhao, Eleni Tsiakkouri, and Marios D. Dikaiakos. Scheduling workflows with budget constraints. In Integrated research in GRID computing, pages 189-202. Springer, 2007. Google Scholar
  22. S. Selvarani and G. Sudha Sadhasivam. Improved cost-based algorithm for task scheduling in cloud computing. In Int. Conf. on Computational intelligence and computing research, pages 1-5. IEEE, 2010. Google Scholar
  23. Shaghayegh Sharif, Javid Taheri, Albert Y. Zomaya, and Surya Nepal. Online multiple workflow scheduling under privacy and deadline in hybrid cloud environment. In Cloud Computing Technology and Science (CloudCom), 2014 IEEE 6th International Conference on, pages 455-462. IEEE, 2014. Google Scholar
  24. Sucha Smanchat and Kanchana Viriyapant. Taxonomies of workflow scheduling problem and techniques in the cloud. Future Generation Computer Systems, 52:1-12, 2015. Google Scholar
  25. Sen Su, Jian Li, Qingjia Huang, Xiao Huang, Kai Shuang, and Jie Wang. Cost-efficient task scheduling for executing large programs in the cloud. Parallel Computing, 39(4):177-188, 2013. Google Scholar
  26. Haluk Topcuoglu, Salim Hariri, and Min-you Wu. Performance-effective and low-complexity task scheduling for heterogeneous computing. Parallel and Distributed Systems, IEEE Transactions on, 13(3):260-274, 2002. Google Scholar
  27. Wei Wang, Qingbo Wu, Yusong Tan, and Fuhui Wu. Maximize throughput scheduling and cost-fairness optimization for multiple dags with deadline constraint. In Algorithms and Architectures for Parallel Processing, pages 621-634. Springer, 2015. Google Scholar
  28. Chase Qishi Wu, Xiangyu Lin, Dantong Yu, Wei Xu, and Li Li. End-to-end delay minimization for scientific workflows in clouds under budget constraint. Cloud Computing, IEEE Transactions on, 3(2):169-181, 2015. Google Scholar
  29. Heyang Xu, Bo Yang, Weiwei Qi, and Emmanuel Ahene. A multi-objective optimization approach to workflow scheduling in clouds considering fault recovery. KSII Transactions on Internet and Information Systems, 10(3):976-995, 2016. Google Scholar
  30. Lingfang Zeng, Bharadwaj Veeravalli, and Xiaorong Li. Saba: A security-aware and budget-aware workflow scheduling strategy in clouds. Journal of Parallel and Distributed Computing, 75:141-151, 2015. Google Scholar
  31. Lingfang Zeng, Bharadwaj Veeravalli, and Albert Y. Zomaya. An integrated task computation and data management scheduling strategy for workflow applications in cloud environments. Journal of Network and Computer Applications, 50:39-48, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact