SUMMARY Managing usage service level agreements (uSLAs) within environments that integrate participants and resources spanning multiple physical institutions is a challenging problem. Running workloads in such environments is often a similarly challenging problem owing to the scale of the environment, and to the resource partitioning based on various sharing strategies. Also, a resource may be taken down during a job execution, be improperly set up or fail job execution. Such elements have to be taken into account whenever targeting a Grid environment for problem solving. In this paper we explore uSLA-based scheduling on a real Grid, Grid3, by means of a specific workload (the BLAST workload) and a specific scheduling framework, GRUBER (an architecture and toolkit for resource uSLA specification and enforcement). The paper provides extensive experimental results and comparisons with other scheduling strategies. We also address, in great detail, the performance of different uSLA-based site selection strategies and the overall performance in scheduling workloads over Grid3 with workload sizes ranging from 10 to 10000 jobs. Copyright c � 2006 John Wiley & Sons, Ltd.