CPTF-a new heuristic based branch and bound algorithm for workflow scheduling in heterogeneous distributed computing systems

作     者：Sirisha, D. Prasad, S. Sambhu 

作者机构：Nadimpalli Satyanarayana Raju Inst Technol Visakhapatnam Andhra Pradesh India 

出 版 物：《CCF TRANSACTIONS ON HIGH PERFORMANCE COMPUTING》 (CCF Trans. HPC)

年 卷 期：2024年第6卷第5期

页      面：472-487页

核心收录：

主　　题：Workflow scheduling Task scheduling Heuristics Heterogeneous distributed computing systems Branch and bound technique Makespan 

摘      要：Computationally intensive applications embodied as workflows entail interdependent tasks that involve multifarious computation requirements and necessitate Heterogeneous Distributed Computing Systems (HDCS) to attain high performance. The scheduling of workflows on HDCS was demonstrated as an NP-Complete problem. In the current work, a new heuristic based Branch and Bound (BnB) technique namely Critical Path_finish Time First (CPTF) algorithm is proposed for workflow scheduling on HDCS to achieve the best solutions. The primary merits of CPTF algorithm are due to the bounding functions that are tight and of less complexity. The sharp bounding functions could precisely estimate the promise of each state and aid in pruning infeasible states. Thus, the search space size is reduced. The CPTF algorithm explores the most promising states in the search space and converges to the solution quickly. Therefore, high performance is achieved. The experimental results on random and scientific workflows reveal that CPTF algorithm could effectively exploit high potency of BnB technique in realizing better quality solutions against the widely referred heuristic scheduling algorithms. The results on the benchmark workflows show that CPTF algorithm has improved schedules for 89.36% of the cases.