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).
Publisher
University of Nairobi