{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T16:50:18Z","timestamp":1774889418275,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cloud Comp"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A workflow is an effective way for modeling complex applications and serves as a means for scientists and researchers to better understand the details of applications. Cloud computing enables the running of workflow applications on many types of computational resources which become available on-demand. As one of the most important aspects of cloud computing, workflow scheduling needs to be performed efficiently to optimize resources. Due to the existence of various resource types at different prices, workflow scheduling has evolved into an even more challenging problem on cloud computing. The present paper proposes a workflow scheduling algorithm in the cloud to minimize the execution cost of the deadline-constrained workflow. The proposed method, EDQWS, extends the current authors\u2019 previous study (DQWS) and is a two-step scheduler based on divide and conquer. In the first step, the workflow is divided into sub-workflows by defining, scheduling, and removing a critical path from the workflow, similar to DQWS. The process continues until only chain-structured sub-workflows, called linear graphs, remain. In the second step which is linear graph scheduling, a new merging algorithm is proposed that combines the resulting linear graphs so as to reduce the number of used instances and minimize the overall execution cost. In addition, the current work introduces a scoring function to select the most efficient instances for scheduling the linear graphs. Experiments show that EDQWS outperforms its competitors, both in terms of minimizing the monetary costs of executing scheduled workflows and meeting user-defined deadlines. Furthermore, in more than 50% of the examined workflow samples, EDQWS succeeds in reducing the number of resource instances compared to the previously introduced DQWS method.<\/jats:p>","DOI":"10.1186\/s13677-022-00284-8","type":"journal-article","created":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T13:03:15Z","timestamp":1653570195000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":37,"title":["EDQWS: an enhanced divide and conquer algorithm for workflow scheduling in cloud"],"prefix":"10.1186","volume":"11","author":[{"given":"Ghazaleh","family":"Khojasteh Toussi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5550-5565","authenticated-orcid":false,"given":"Mahmoud","family":"Naghibzadeh","sequence":"additional","affiliation":[]},{"given":"Saeid","family":"Abrishami","sequence":"additional","affiliation":[]},{"given":"Hoda","family":"Taheri","sequence":"additional","affiliation":[]},{"given":"Hamid","family":"Abrishami","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,26]]},"reference":[{"issue":"4","key":"284_CR1","doi-asserted-by":"publisher","first-page":"1571","DOI":"10.1109\/TNSM.2018.2872066","volume":"15","author":"W Guo","year":"2018","unstructured":"Guo W, Lin B, Chen G, Chen Y, Liang F (2018) Cost-driven scheduling for deadline-based workflow across multiple clouds. IEEE Trans Netw Serv Manag 15(4):1571\u20131585. https:\/\/doi.org\/10.1109\/TNSM.2018.2872066","journal-title":"IEEE Trans Netw Serv Manag"},{"issue":"12","key":"284_CR2","doi-asserted-by":"publisher","first-page":"3401","DOI":"10.1109\/TPDS.2017.2735400","volume":"28","author":"Q Wu","year":"2017","unstructured":"Wu Q, Ishikawa F, Zhu Q, Xia Y, Wen J (2017) Deadline-constrained cost optimization approaches for workflow scheduling in clouds. IEEE Trans Parallel Distributed Syst 28(12):3401\u20133412. https:\/\/doi.org\/10.1109\/TPDS.2017.2735400","journal-title":"IEEE Trans Parallel Distributed Syst"},{"key":"284_CR3","doi-asserted-by":"publisher","unstructured":"Rodriguez MA, Buyya R (2017) A taxonomy and survey on scheduling algorithms for scientific workflows in IaaS cloud computing environments. Concurrency Comput 29(8). https:\/\/doi.org\/10.1002\/cpe.4041","DOI":"10.1002\/cpe.4041"},{"issue":"6","key":"284_CR4","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.1109\/TPDS.2019.2961098","volume":"31","author":"HR Faragardi","year":"2020","unstructured":"Faragardi HR, Saleh Sedghpour MR, Fazliahmadi S, Fahringer T, Rasouli N (2020) GRP-HEFT: a budget-constrained resource provisioning scheme for workflow scheduling in IaaS clouds. IEEE Trans Parallel Distributed Syst 31(6):1239\u20131254. https:\/\/doi.org\/10.1109\/TPDS.2019.2961098","journal-title":"IEEE Trans Parallel Distributed Syst"},{"key":"284_CR5","doi-asserted-by":"publisher","unstructured":"Khojasteh Toussi G, Naghibzadeh M (2021) A divide and conquer approach to deadline constrained cost-optimization workflow scheduling for the cloud. Clust Comput. https:\/\/doi.org\/10.1007\/s10586-020-03223-x","DOI":"10.1007\/s10586-020-03223-x"},{"issue":"3","key":"284_CR6","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s10723-019-09490-2","volume":"18","author":"V Singh","year":"2020","unstructured":"Singh V, Gupta I, Jana PK (2020) An energy efficient algorithm for workflow scheduling in IaaS cloud. J Grid Comput 18(3):357\u2013376. https:\/\/doi.org\/10.1007\/s10723-019-09490-2","journal-title":"J Grid Comput"},{"issue":"2","key":"284_CR7","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1007\/s10586-020-03149-4","volume":"24","author":"N Garg","year":"2021","unstructured":"Garg N, Singh D, Goraya MS (2021) Energy and resource efficient workflow scheduling in a virtualized cloud environment. Clust Comput 24(2):767\u2013797. https:\/\/doi.org\/10.1007\/s10586-020-03149-4","journal-title":"Clust Comput"},{"issue":"4","key":"284_CR8","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10723-017-9391-5","volume":"15","author":"J Jiang","year":"2017","unstructured":"Jiang J, Lin Y, Xie G, Fu L, Yang J (2017) Time and energy optimization algorithms for the static scheduling of multiple workflows in heterogeneous computing system. J Grid Comput 15(4):435\u2013456. https:\/\/doi.org\/10.1007\/s10723-017-9391-5","journal-title":"J Grid Comput"},{"key":"284_CR9","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1007\/s10586-017-1055-5","volume":"22","author":"K Sreenu","year":"2019","unstructured":"Sreenu K, Sreelatha M (2019) W-scheduler: whale optimization for task scheduling in cloud computing. Clust Comput 22:1087\u20131098. https:\/\/doi.org\/10.1007\/s10586-017-1055-5","journal-title":"Clust Comput"},{"issue":"1","key":"284_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s10723-016-9386-7","volume":"15","author":"S Wang","year":"2017","unstructured":"Wang S, Li K, Mei J, Xiao G, Li K (2017) A reliability-aware task scheduling algorithm based on replication on heterogeneous computing systems. J Grid Comput 15(1):23\u201339. https:\/\/doi.org\/10.1007\/s10723-016-9386-7","journal-title":"J Grid Comput"},{"issue":"4","key":"284_CR11","doi-asserted-by":"publisher","first-page":"3405","DOI":"10.1007\/s10586-020-03095-1","volume":"23","author":"K Kalyan Chakravarthi","year":"2020","unstructured":"Kalyan Chakravarthi K, Shyamala L, Vaidehi V (2020) Budget aware scheduling algorithm for workflow applications in IaaS clouds. Clust Comput 23(4):3405\u20133419. https:\/\/doi.org\/10.1007\/s10586-020-03095-1","journal-title":"Clust Comput"},{"key":"284_CR12","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.future.2017.01.002","volume":"75","author":"V Arabnejad","year":"2017","unstructured":"Arabnejad V, Bubendorfer K, Ng B (2017) Scheduling deadline constrained scientific workflows on dynamically provisioned cloud resources. Futur Gener Comput Syst 75:348\u2013364. https:\/\/doi.org\/10.1016\/j.future.2017.01.002","journal-title":"Futur Gener Comput Syst"},{"issue":"4","key":"284_CR13","doi-asserted-by":"publisher","first-page":"3185","DOI":"10.1007\/s10586-020-03079-1","volume":"23","author":"N Rizvi","year":"2020","unstructured":"Rizvi N, Ramesh D (2020) Fair budget constrained workflow scheduling approach for heterogeneous clouds. Clust Comput 23(4):3185\u20133201. https:\/\/doi.org\/10.1007\/s10586-020-03079-1","journal-title":"Clust Comput"},{"key":"284_CR14","doi-asserted-by":"crossref","unstructured":"Cao, S., Deng, K., Ren, K., Li, X., Nie, T., and Song, J.: \u2018A deadline-constrained scheduling algorithm for scientific workflows in clouds\u2019, in Editor (Ed.)^(Eds.): \u2018Book A deadline-constrained scheduling algorithm for scientific workflows in clouds\u2019 (Institute of Electrical and Electronics Engineers Inc., 2019, edn.), pp. 98\u2013105","DOI":"10.1109\/HPCC\/SmartCity\/DSS.2019.00029"},{"issue":"4","key":"284_CR15","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s10723-015-9344-9","volume":"13","author":"A Verma","year":"2015","unstructured":"Verma A, Kaushal S (2015) Cost-time efficient scheduling plan for executing workflows in the cloud. J Grid Comput 13(4):495\u2013506. https:\/\/doi.org\/10.1007\/s10723-015-9344-9","journal-title":"J Grid Comput"},{"issue":"3","key":"284_CR16","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"JD Ullman","year":"1975","unstructured":"Ullman JD (1975) NP-complete scheduling problems. J Comput Syst Sci 10(3):384\u2013393. https:\/\/doi.org\/10.1016\/S0022-0000(75)80008-0","journal-title":"J Comput Syst Sci"},{"key":"284_CR17","doi-asserted-by":"publisher","unstructured":"Malawski M, Figiela K, Bubak M, Deelman E, Nabrzyski J (2015) Scheduling multilevel deadline-constrained scientific workflows on clouds based on cost optimization. Sci Program 2015. https:\/\/doi.org\/10.1155\/2015\/680271","DOI":"10.1155\/2015\/680271"},{"issue":"1","key":"284_CR18","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.future.2012.05.004","volume":"29","author":"S Abrishami","year":"2013","unstructured":"Abrishami S, Naghibzadeh M, Epema DHJ (2013) Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Futur Gener Comput Syst 29(1):158\u2013169. https:\/\/doi.org\/10.1016\/j.future.2012.05.004","journal-title":"Futur Gener Comput Syst"},{"issue":"7","key":"284_CR19","doi-asserted-by":"publisher","first-page":"1787","DOI":"10.1109\/TPDS.2013.238","volume":"25","author":"RN Calheiros","year":"2014","unstructured":"Calheiros RN, Buyya R (2014) Meeting deadlines of scientific workflows in public clouds with tasks replication. IEEE Trans Parallel Distributed Syst 25(7):1787\u20131796. https:\/\/doi.org\/10.1109\/TPDS.2013.238","journal-title":"IEEE Trans Parallel Distributed Syst"},{"key":"284_CR20","doi-asserted-by":"crossref","unstructured":"Arabnejad, V., Bubendorfer, K., Ng, B., and Chard, K.: \u2018A Deadline Constrained Critical Path Heuristic for Cost-Effectively Scheduling Workflows C3 - Proceedings - 2015 IEEE\/ACM 8th International Conference on Utility and Cloud Computing, UCC 2015\u2019, in Editor (Ed.)^(Eds.): \u2018Book A Deadline Constrained Critical Path Heuristic for Cost-Effectively Scheduling Workflows C3 - Proceedings - 2015 IEEE\/ACM 8th International Conference on Utility and Cloud Computing, UCC 2015\u2019 (Institute of Electrical and Electronics Engineers Inc., 2015, edn.), pp. 242\u2013250","DOI":"10.1109\/UCC.2015.41"},{"issue":"2","key":"284_CR21","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1109\/TCC.2014.2314655","volume":"2","author":"MA Rodriguez","year":"2014","unstructured":"Rodriguez MA, Buyya R (2014) Deadline based resource provisioningand scheduling algorithm for scientific workflows on clouds. IEEE Trans Cloud Comput 2(2):222\u2013235","journal-title":"IEEE Trans Cloud Comput"},{"issue":"4","key":"284_CR22","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/s10723-014-9294-7","volume":"12","author":"H Arabnejad","year":"2014","unstructured":"Arabnejad H, Barbosa JG (2014) A budget constrained scheduling algorithm for workflow applications. J Grid Comput 12(4):665\u2013679. https:\/\/doi.org\/10.1007\/s10723-014-9294-7","journal-title":"J Grid Comput"},{"issue":"3","key":"284_CR23","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/71.993206","volume":"13","author":"H Topcuoglu","year":"2002","unstructured":"Topcuoglu H, Hariri S, Wu MY (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distributed Syst 13(3):260\u2013274. https:\/\/doi.org\/10.1109\/71.993206","journal-title":"IEEE Trans Parallel Distributed Syst"},{"key":"284_CR24","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.future.2016.01.004","volume":"60","author":"F Wu","year":"2016","unstructured":"Wu F, Wu Q, Tan Y, Li R, Wang W (2016) PCP-B2: partial critical path budget balanced scheduling algorithms for scientific workflow applications. Futur Gener Comput Syst 60:22\u201334. https:\/\/doi.org\/10.1016\/j.future.2016.01.004","journal-title":"Futur Gener Comput Syst"},{"issue":"2","key":"284_CR25","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s10586-013-0325-0","volume":"17","author":"JJ Durillo","year":"2014","unstructured":"Durillo JJ, Prodan R (2014) Multi-objective workflow scheduling in amazon EC2. Clust Comput 17(2):169\u2013189. https:\/\/doi.org\/10.1007\/s10586-013-0325-0","journal-title":"Clust Comput"},{"key":"284_CR26","doi-asserted-by":"crossref","unstructured":"Wu, Z., Ni, Z., Gu, L., and Liu, X. (2010). \u2018A revised discrete particle swarm optimization for cloud workflow scheduling C3 - Proceedings - 2010 International Conference on Computational Intelligence and Security, CIS 2010\u2019, in Editor (Ed.)^(Eds.): \u2018Book A revised discrete particle swarm optimization for cloud workflow scheduling C3 - Proceedings - 2010 International Conference on Computational Intelligence and Security, CIS 2010\u2019, pp. 184\u2013188","DOI":"10.1109\/CIS.2010.46"},{"issue":"1","key":"284_CR27","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1109\/TPDS.2018.2849396","volume":"30","author":"V Arabnejad","year":"2019","unstructured":"Arabnejad V, Bubendorfer K, Ng B (2019) Budget and deadline aware e-science workflow scheduling in clouds. IEEE Trans Parallel Distributed Syst 30(1):29\u201344. https:\/\/doi.org\/10.1109\/TPDS.2018.2849396","journal-title":"IEEE Trans Parallel Distributed Syst"},{"key":"284_CR28","doi-asserted-by":"crossref","unstructured":"Palankar, M.R., Iamnitchi, A., Ripeanu, M., and Garfinkel, S. (2008). \u2018Amazon S3 for science grids: a viable solution?\u2019, in Editor (Ed)^(Eds): \u2018Book Amazon S3 for science grids: a viable solution?\u2019, pp. 55\u201364","DOI":"10.1145\/1383519.1383526"},{"issue":"3","key":"284_CR29","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1016\/j.future.2012.08.015","volume":"29","author":"G Juve","year":"2013","unstructured":"Juve G, Chervenak A, Deelman E, Bharathi S, Mehta G, Vahi K (2013) Characterizing and profiling scientific workflows. Futur Gener Comput Syst 29(3):682\u2013692. https:\/\/doi.org\/10.1016\/j.future.2012.08.015","journal-title":"Futur Gener Comput Syst"},{"key":"284_CR30","doi-asserted-by":"crossref","unstructured":"Bharathi, S., Chervenak, A., Deelman, E., Mehta, G., Su, M.H., and Vahi, K. (2008). \u2018Characterization of scientific workflows C3\u20132008 3rd Workshop on Workflows in Support of Large-Scale Science, WORKS 2008\u2019, in Editor (Ed.)^(Eds.): \u2018Book Characterization of scientific workflows C3\u20132008 3rd Workshop on Workflows in Support of Large-Scale Science, WORKS 2008\u2019, pp","DOI":"10.1109\/WORKS.2008.4723958"}],"container-title":["Journal of Cloud Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-022-00284-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13677-022-00284-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13677-022-00284-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T13:09:58Z","timestamp":1653570598000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofcloudcomputing.springeropen.com\/articles\/10.1186\/s13677-022-00284-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["284"],"URL":"https:\/\/doi.org\/10.1186\/s13677-022-00284-8","relation":{},"ISSN":["2192-113X"],"issn-type":[{"value":"2192-113X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"6 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13"}}