Efficient Refinery Scheduling Heuristic in Heterogeneous Computing Systems

With the emergence of distributed systems, the problem of task scheduling has been arousing attention in recent past. Task scheduling is a NP-complete problem and it is more complicated under the distributed heterogeneous computing environment. To harness the potential of these systems, efficient scheduling algorithms are needed. This paper proposes a new distributed scheduling algorithm for independent tasks to be assigned optimally amongst available machines. The approach works in two phases. In first phase, it assigns a task according to the Min-min heuristic and in second phase, it improves the scheduling by using efficient refinery scheduling heuristic. The refinery heuristic balances the load across all the machines and reduces the make-span time of jobs. The results obtained using the proposed heuristic improves over the existing approaches.