Exploring the Efficacy of Branch and Bound Strategy for Scheduling Workflows on Heterogeneous Computing Systems

Computationally complex applications featuring workflows comprises of modules that can be deployed on Heterogeneous Computing Systems (HCS) for accomplishing high performance. The problem of scheduling the workflows on HCS is proven to be NP-Complete. In the present work, Branch and Bound (B&B) strategy for scheduling the workflows on HCS is proposed to attain globally optimal solutions. The primary merit of the proposed strategy is due to the estimation of the rank functions which are sharper and not complex. The proposed B&B strategy expands the most promising states first. The sharper ranks aid in converging to the solution quickly by pruning the unpromising states which do not lead to an optimal solution. Therefore, the search space is drastically reduced hence higher performance can be expected. The experimental results reveal that the proposed B&B scheme is efficient in exploring high potentials of B&B strategy in finding exact solutions. The performance analysis on a set of benchmark workflows shows that the proposed B&B strategy has generated optimal schedules for 94.37% of the cases.