A novel cost-efficient approach for deadline-constrained workflow scheduling by dynamic provisioning of resources

摘要

AbstractWorkflow scheduling is a crucial aspect of cloud computing that should be performed in an efficient manner for optimal utilization of resources. The development of a cost-efficient algorithm has always been an important topic of research in this regard. In this paper, we propose a novel workflow scheduling algorithm, which is cost-efficient and deadline-constrained. The proposed algorithm is consolidated by dynamic provisioning of the resources, usingk-means clustering technique and a variant of the Subset-Sum problem. In the algorithm, we consider level based scheduling using the concept of Bag of Tasks (bots) and develop a new technique for associating deadlines with eachbot. Through extensive simulation runs, we show that the proposed algorithm outperforms the existing algorithms like Dynamic Provisioning Dynamic Scheduling (DPDS) and Infrastructure as a Service (IaaS) Cloud-Partial Critical Path (IC-PCP). The effectiveness of our algorithm over these two algorithms is also illustrated through the popular statistical test ANOVA and its subsequent post-hoc analysis.Highlights•Proposed a cost-efficient deadline-constrained algorithm, called PPDPS for workflow scheduling.•Introduced a new method for deadline determination.•Use ofk-means clustering and partition problem for dynamic provisioning of resources.•Demonstration of better performance through simulation results, the statistical test ANOVA and its post-hoc analysis.