Job scheduling in grid computing using simulated annealing

Abstract

Grid computing has emerged as a platform to aggregate heterogeneous resources into a virtual computing resource that can provide non trivial quality of service to end users. A Key problem in grid computing platforms is the mapping of tasks to resources in order to achieve higher performance and economic use of resources. Grid scheduling is a complex problem and has been proved to be an NP Hard problem. Research has been conducted to study intensely the challenges of scheduling in Grid computing environments. In this research we present a model that continuously improves the Makespan, the time spent from the start of the first task in a job to the end of the last task of the job. We use the Alchemi Grid computing platform to implement and evaluate the model. The underlying scheduling algorithm in the model is the simulated annealing algorithm. We have developed a prototype of the model and embedded it in the Alchemi Grid platform as an alternative scheduling module to the default scheduling module that utilizes the First-In-First-Out scheduling algorithm. We have evaluated the model against the default scheduling model in Alchemi and found it to produce better scheduling performance (lower makespans).