A Multi-Objective Deadline-Constrained Task Scheduling Algorithm with Guaranteed Performance in Load Balancing on Heterogeneous Networks

Scheduling of complex workflows in heterogeneous distributed computing systems is a challenging task for their management and optimization of a direct or derived set of parametric values. With a heterogeneous environment, processors may have different processing power and associated memory to execute the tasks corresponding to given workflows. The tasks could have requirements of different execution time, dependence among themselves as well as resource constraints. Moreover, workflows are dynamic in nature and they need to be scheduled along with the existing and previously scheduled execution environment. In this paper, workflow scheduling is considered as a multi-objective optimization problem with various constraints and we aim to find a solution for optimizing the load, total cost, and total execution time. We propose a new algorithm CEFT-LB to achieve optimized workflow scheduling while achieving load balancing among the processors. In the task selection phase of our proposed algorithm, we have incorporated necessary modifications to the ranking function of the HEFT algorithm in deciding an Order of Execution (OE) of the tasks. We propose a new algorithm in the processor selection phase for selecting the optimal solutions by considering several factors like: load of the node, total cost, total execution time, utilization of nodes, average response time, minimum queue length, etc. Comparisons with TOPSIS and other state-of-the-art algorithms prove that our proposed algorithm performs better with reference to optimizing the deadline satisfaction rate, the total cost, the total network execution time, and the mean load.