22-02-2013, 04:22 PM
Chemical Reaction Optimization for Task Scheduling in Grid Computing
Chemical Reaction.pdf (Size: 630.57 KB / Downloads: 52)
Abstract
Grid computing solves high performance and high-throughput computing problems through sharing resources ranging from
personal computers to supercomputers distributed around the world. One of the major problems is task scheduling, i.e., allocating
tasks to resources. In addition to Makespan and Flowtime, we also take reliability of resources into account, and task scheduling is
formulated as an optimization problem with three objectives. This is an NP-hard problem, and thus, metaheuristic approaches are
employed to find the optimal solutions. In this paper, several versions of the Chemical Reaction Optimization (CRO) algorithm are
proposed for the grid scheduling problem. CRO is a population-based metaheuristic inspired by the interactions between molecules in
a chemical reaction. We compare these CRO methods with four other acknowledged metaheuristics on a wide range of instances.
Simulation results show that the CRO methods generally perform better than existing methods and performance improvement is
especially significant in large-scale applications.
INTRODUCTION
WITH the advancement of high-speed networks, grid
computing (also known as computational grid) is
proposed and considered as the foundation of the nextgeneration
Internet [1]. The goal of a grid system is to solve
large-scale and high-performance computing problems
through sharing many geographically distributed computing
resources belonging to different administrative domains.
Grid technology has a wide range of applications in
many fields of science and engineering, e.g., astronomy,
meteorology, bioinformatics, transportation, financial modeling,
drug discovery, high energy physics, data mining,
and image manipulation [2], [3], [4].
Metaheuristics
Since we shall compare CRO with GA, SA, PSO, and TA, we
describe them below.
GA, a particular class of evolutionary algorithms, was
created by Holland [11]. It follows the natural selection law,
which means only the fittest can survive. GA is a
population-based metaheuristic and produces the next
generation with the techniques inspired by evolutionary
biology, such as inheritance, mutation, crossover, and
selection. Consider a solution as an organism. The better
the quality of a solution, the higher the probability it will
survive. Through crossover (also called recombination) and
mutation, GA can escape from the local optimal to search
for the global optimal.
SA, originated from annealing in metallurgy, imitates its
process of decreasing the defects of a substance according to
a cooling procedure. For each iteration, SA generates a new
solution randomly in the neighborhood of the present
solution, and it will be accepted if it is better, or accepted
with a probability controlled by a temperature parameter.
As the temperature gradually drops, the ability to jump out
of local optima decreases and finally moves to the global
optimum.
Grid Scheduling
Recently grid scheduling has attracted much attention.
Many grid computing infrastructure have emerged, such as
the e-Minerals Grid [17] in the United Kingdom, and the
EGEE project [18] funded by the European Commission. At
the same time, a number of scheduling systems have been
developed, such as Condor-G [19], AppLes [20], and
CHIMERA [21]. In [22], scheduling in grids can be classified
into different types. From the system’s perspective, scheduling
can be centralized, hierarchical or decentralized.
Also, the system can process the tasks in batches or handle a
task immediately once submitted. Other policies like
Deferred Assignment Scheduling (DAS) [23], [24] are
adopted by some researchers as well. Moreover, tasks can
also be independent or have precedence relationship. In
most cases, applications with intensive use of CPUs may be
split into independent parts, which can be considered as
independent tasks. For those applications involving extensive
data sharing among resources, we need to account
for the precedence relationship between tasks, also known
as the Grid Workflow. In this paper, we consider problems
in batch-processed mode with independent tasks.
SIMULATION RESULTS
In this section, we first show simulation results with
permutation-based and vector-based representations, respectively.
Second, the outcomes of employing these two
different representations are compared. Details on the
simulation environment, parameter analysis for CRO and
weights selection for the fitness functions are given in [31].
Permutation-Based Results
In this section, we use the permutation type as the solution
representations. Operator mechanisms adapted to this type
are also employed. As described in Section 2, PSO evolves
according to the velocity and position of the particles. In
essence, PSO is updated (generating new solutions) automatically,
and does not utilize any operator mechanism to
get new solution. The only thing that influences the
performance of this algorithm is the parameter settings.
Hence, it will perform the same in both permutation- and
vector-based representations.
CONCLUSION
Grid Computing has emerged as one of the hot research
areas in the field of computer networking. Scheduling,
which decides how to distribute tasks to resources, is one of
the most important issues. CRO, inspired by the chemical
reaction process, is a metaheuristic approach and can be
applied to solve NP-hard problems, like grid scheduling.
Compared with the previous version [32]