QoS Based Multi-Constraints Bin Packing Job

Scheduling Heuristic for Heterogeneous

Volunteer Grid Resources

Saddaf Rubab, Mohd Fadzil Hassan, Ahmad Mahmood, and Nasir Mehmood

Department of Computer and Information Sciences, University Technology Petronas, Malaysia

Abstract: Volunteer grid is a kind of distributed networks, consisting of contributed resources which are heterogonous and distributed. The heterogeneity of resources can be in terms of the time of availability, resource characteristics among others. Usually submitted jobs to volunteer grid usually require different heterogeneous resources depending on their requirements. Efficient scheduling of submitted jobs can be done if jobs are divided into small number of tasks to fulfil multiple requirements, which requires multi-resource scheduling policy to consider different constraints of resource and job before scheduling. In traditional scheduling policies only single scheduling or optimization constraint is considered to either complete job within specific deadline or to maximize the resource usage. Therefore, a scheduling policy is required to serve multiple constraints for optimizing resource usage and completing jobs within specified deadlines. The work presented in this paper proposed Quality of Service (QoS) based multi-constraint job scheduling heuristics for volunteer grid resources. Bin packing problem is also incorporated within the proposed heuristic for reordering and jobs assignment. The performance of proposed scheduling heuristic is measured by comparing it with other scheduling algorithms used in grid environment. The results presented suggest that there is a reasonable improvement in waiting time, turnaround time, slowdown time and job failure rate.

Keywords: Volunteer grid computing, volunteer resources, QoS, SLA, multi-constraints, rescheduling, bin-packing, back-filling.