Novel Approaches for Scheduling Task Graphs in Heterogeneous Distributed Computing Environment

Ehsan Munir¹, Saima Ijaz¹, Sheraz Anjum¹, Ali Khan³, Waqas Anwar² and Wasif Nisar¹

¹Department of Computer Science, COMSATS Institute of Information Technology, Wah Cantt, Pakistan

²Department of Computer Science, COMSATS Institute of Information Technology, Abbottabad,   Pakistan

³Department of Electrical Engineering, COMSATS Institute of Information Technology, Lahore, Pakistan

Abstract: Distributed heterogeneous computing environment comprises of diverse set of interconnected resources that are capable of performing computationally complex tasks efficiently. In order to exploit the high performance of such a system, the task scheduling problem demands for the efficient mapping of the tasks. Because of its fundamental importance, the problem has been studied extensively and several algorithms have been proposed. In this paper, we propose two novel approaches for the task scheduling problem and compare the proposed work on the basis of randomly generated task graphs with the well-known existing algorithms. The simulation results elucidate on the basis of different cost and performance metrics that for most of the scenarios, the proposed approaches outperform the existing ones considerably.