Design and evaluation of job scheduling strategies for grid computing

Abstract

Grid computing is intended to offer an easy and seamless access to remote resources. The scheduling task of allocating these resources automatically to user jobs is an essential part of a grid environment. This work discusses the evaluation and design of different scheduling strategies. A concept for the design process of such a scheduling system is presented. The evaluation of scheduling algorithms for single parallel machines is done by theoretical analysis and by simulation experiments. The theoretical approach by competitive analysis lead to bounds for the worst-case scenarios. As there is great interest in the scheduling performance of a real system installation, simulations have been applied for further evaluation. In addition to the theoretical analysis, the presented preemptive scheduling algorithm is also effcient in terms of makespan and average response time in a real system scenario if compared to other scheduling algorithms. In some of the examined scenarios the algorithm could outperform other common algorithms such as backfilling. Based on these results, scheduling algorithms for the grid environment have been developed. On one hand, these methods base on modifications of the examined conventional scheduling strategies for single parallel machines. On the other hand, a scheduling strategy with a market economic approach is presented. As a proof of concept a possible architecture of a scheduling environment is presented, which has been used for the evaluation of the presented algorithms. The work ends with a brief conclusion on the discussed scheduling strategies and gives an outlook on future work.