Slack based Scheduling for dependent tasks in Heterogeneous Computing environments

Computationally intensive applications may be efficiently solved by decomposing the problem into several tasks that can be executed in parallel. High Performance can be achieved by scheduling such applications on Heterogeneous Distributed Computing Systems. The problem of task scheduling in HDCS has been proved to be NP-complete and heuristics are generally used to obtain near optimal solution. In this paper a novel heuristic approach based on slack namely, Slack based Task Scheduling (STS) is proposed. The proposed heuristic first generates the schedule by ordering the execution of the tasks. Then the algorithm shortens the schedule length by inserting the tasks into the slack that is created by delaying some tasks. By efficiently utilizing the slack of a task, shorter span schedules can be generated and performance can also be enhanced. The STS algorithm´s performance analysed and compared with the well known HEFT and PETS algorithms. The experimental results reveal that STS algorithm´s performance is better PETS and HEFT algorithms in terms of schedule length ratio, speedup and efficiency.