Adaptive parallel job scheduling with resource admissible allocation on two-level hierarchical grids

2012 | journal article; research paper. A publication of Göttingen

Jump to: Cite & Linked | Documents & Media | Details | Version history

Cite this publication

​Adaptive parallel job scheduling with resource admissible allocation on two-level hierarchical grids​
Quezada-Pina, A.; Tchernykh, A.; González-García, J. L. ; Hirales-Carbajal, A.; Ramírez-Alcaraz, J. M.; Schwiegelshohn, U. & Yahyapour, R.  et al.​ (2012) 
Future Generation Computer Systems28(7) pp. 965​-976​.​ DOI: 

Documents & Media


GRO License GRO License


Quezada-Pina, Ariel; Tchernykh, Andrei; González-García, José Luis ; Hirales-Carbajal, Adán; Ramírez-Alcaraz, Juan Manuel; Schwiegelshohn, Uwe; Yahyapour, Ramin ; Miranda-López, Vanessa
We evaluate job scheduling algorithms that integrate both tasks of Grid scheduling: job allocation to Grid sites and local scheduling at the sites. We propose and analyze an adaptive job allocation scheme named admissible allocation. The main idea of this scheme is to set job allocation constraints, and dynamically adapt them to cope with different workloads and Grid properties. We present 3-approximation and 5-competitive algorithms named MLB a + PS and MCT a + PS for the case that all jobs fit to the smallest machine, while we derive an approximation factor of 9 and a competitive factor of 11 for the general case. To show practical applicability of our methods, we perform a comprehensive study of the practical performance of the proposed strategies and their derivatives using simulation. To this end, we use real workload traces and corresponding Grid configurations. We analyze nine scheduling strategies that require a different amount of information on three Grid scenarios. We demonstrate that our strategies perform well across ten metrics that reflect both user-and system-specific goals.
Issue Date
Future Generation Computer Systems 
Gesellschaft für wissenschaftliche Datenverarbeitung 



Social Media