Cost-based workflow scheduling using algebraic structures

Document Type : Original Article

Authors

1 Department of Computer Science, Faculty of Science, Mahallat Institute of Higher Education, Mahallat, Iran.

2 Department of Computer Engineering, Faculty of Electrical and Computer Engineering, Kashan University, Kashan, Iran.

Abstract

Workflow is a common model for describing a wide range of applications in distributed systems. Due to the computing power of cloud computing, it has been widely applied to solve large workflows. Cloud workflow scheduling aims to find the most suitable resources for each task of a workflow so that optimizing certain performance metrics such as execution time and cost are met. Since scheduling is a well-known NP-complete problem, many heuristic approaches have been proposed to solve it in homogeneous and heterogeneous distributed systems. The longest path of a workflow is called the critical path on which the workflow completion time depends. In fact, delays in the execution of critical path tasks can delay the workflow completion time and violate the execution deadline of the workflow. Hence, in this paper, we present a parallel heuristic algorithm for quality-based workflow scheduling. The objective function proposed in the algorithm leads to minimizing the execution time of a workflow as well as respecting the deadline. By assigning a pseudo-lattice to each sub-workflow, the start and end time of each task and the appropriate resources for them are determined. The simulation results on the Montage and LIGO workflows show that the proposed approach reduces the cost by 5.5% compared to IC-PCP and by 11% compared to IC-PCPD2. 

Keywords

References

[1] Juve G., Chervenak A. L., Deelman E., Bharathi S., Mehta G., Vahi K., “Characterizing and profiling scientific workflows,” Future Generation Comp. Syst. vol. 29, no. 3, pp. 682-692, 2013.
[2] Arunarani A. R., Manjula D., Sugumaran V., “Task scheduling techniques in cloud computing: A literature survey,” Future Gener. Comput. Syst., vol. 91, pp. 407-415, 2019.
[3] Mershad K., Artail H., Saghir M. A. R., Hajj H., Awad M., “A study of the performance of a cloud datacenter server,” IEEE Transactions on Cloud Computing, vol. 5, no. 4, pp. 590-603, 2017.
[4] Sadooghi I., Martin J. H., Li T., Brandstatter K., Maheshwari K., de Lacerda Ruivo T. P. P., Garzoglio G., Timm S., Zhao Y., Raicu I., “Understanding the performance and potential of cloud computing for scientific applications,” IEEE Transactions on Cloud Computing, vol. 5, no. 2, pp. 358-371, 2017.
[5] Topcuoglu H., Hariri S., Wu M., “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260-274, 2002.
[6] Son J. H., Kim J., Kim M., “Extracting the workflow critical path from the extended well-formed workflow schema,” J. Comput. Syst. Sci., vol. 70, no. 1, pp. 86-106, 2005.
[7] Abrishami S., Naghibzadeh M., Epema D. H. J., “Cost-Driven Scheduling of Grid Workflows Using Partial Critical Paths,” IEEE Trans. Parallel Distributed Syst., vol. 23, no. 8, pp. 1400-1414, 2012.
[8] Abrishami S., Naghibzadeh M., Epema D. H. J., “Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds,” Future Generation Comp. Syst., vol. 29, no. 1, pp. 158-169, 2013.
[9] Wu F., Wu Q., Tan Y., Li R., Wang W., “Pcp-b2: Partial critical path budget balanced scheduling algorithms for scientific workflow applications,” Future Generation Comp. Syst., vol. 60, pp. 22-34, 2016.
[10] Yuan Y., Li X., Wang Q., Zhu X., “Deadline division-based heuristic for cost optimization in workflow scheduling,” Inf. Sci., vol. 179, no. 15, pp. 2562-2575, 2009.
[11] Jailalita, Singh S., Dutta M., “Critical path based scheduling algorithm for workflow applications in cloud computing,” in: 2016 International Conference on Advances in Computing, Communication, Automation (ICACCA) (Spring), pp. 1-6, 2016.
[12] Calheiros R.N., Buyya R., “Meeting deadlines of scientific workflows in public clouds with tasks replication,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 7, pp. 1787–1796, 2014.
[13] Cai Z., Li X., Gupta J. N. D., “Critical path-based iterative heuristic for workflow scheduling in utility and cloud computing,” in: Service-Oriented Computing - 11th International Conference, ICSOC 2013, Berlin, Germany, December 2-5, pp. 207-221, 2013.
[14] Poola D., Garg S. K., Buyya R., Yang Y., Ramamohanarao K., “Robust Scheduling of Scientific Workflows with Deadline and Budget Constraints in Clouds,” AINA, pp. 858-865, 2014.
[15] Arabnejad V., Bubendorfer K., Ng B., Chard K., “A deadline constrained critical path heuristic for cost-effectively scheduling workflows,” in: 2015 IEEE/ACM 8th International Conference on Utility and Cloud Computing (UCC), pp. 242-250, 2015.
[16] Arabnejad V., Bubendorfer K., Ng B., “Scheduling deadline constrained scientific workflows on dynamically provisioned cloud resources,” Future Generation Comp. Syst., vol. 75, pp. 348-364, 2017.
[17] Ghafouri R., Movaghar A., Mohsenzadeh M., “A budget constrained scheduling algorithm for executing workflow application in infrastructure as a service clouds,” Peer-to-Peer Netw. Appl., vol. 12, no. 1, pp. 241–268, 2019.
[18] Matani A., Darvishy A., “A Novel Critical-Path Based Scheduling Algorithm for Stochastic Workflow in Distributed Computing Systems,” in International Congress on High-Performance Computing and Big Data Analysis, pp. 476-489, 2019.
[19] Pan Y., Wang S., Wu L., Xia Y., Zheng W., Pang S., Zeng Z., Chen P., Li Y., “A Novel Approach to Scheduling Workflows Upon Cloud Resources with Fluctuating Performance,” Mob. Networks Appl., vol. 25, no. 2, pp. 690-700, 2020.
[20] Davey B. A., Priestley H. A., “Introduction to Lattices and Order,” Cambridge University Press, ISBN 978-0-521-78451-1, 2002.

Files

History

  • Receive Date: 02 September 2020
  • Revise Date: 17 June 2021
  • Accept Date: 14 September 2021

Share

How to cite

Statistics