Information Technology Reference
In-Depth Information
means the objective function value to be added to actual
objective functions. The sum of
J
cc
(
ʸ
,
p
(
j
,
k
,
l
))
jJ
is called as fitness
value which represent how much nutrient that bacterium detected, the accumulated
fitness value denotes the health level of bacterial which will be used in reproduction
step to discarded the unhealthy bacterium. The whole formula denotes the combined
cell-to-cell attraction and repelling effects, where
J
cc
(
ʸ
,
p
(
j
,
k
,
l
)
and
(
,
k
,
l
)
ʸ =
[
ʸ
,
ʸ
,...,
ʸ
]
is a position in
1
2
p
i
θ
is the
t
m
component of the
th
optimization domain and
i
bacterium at position
θ
.
d
is the depth of attractant released by the cell and
w
tan
is a
attrac
tan
t
attrac
t
measure of the width of the attractant signal.
h
is the height of the repellant
repellant
effect and
w
is a measure of the width of the repellant.
h
is often chose as
repellant
repellant
attra
d
tan
.
Reproduction: After
N
chemotaxis steps, a reproduction step is taken. First the
bacteria are sorted by the accumulated fitness value in an ascending order. The half
bacteria which have the higher fitness value are discarded. The other half bacteria are
asexually split into two bacteria which are then placed in the same direction. The
whole process makes the swarm size constant.
Elimination and dispersal: Bacteria may die due to some sudden changes like
significant local rise of temperature.
e
P
is the elimination-dispersal probability. The
eliminated bacteria are often randomly placed in the optimization domain.
the same value of
t
3.2
The Proposed Algorithm
In this section, we present the bacteria foraging optimization algorithm to solve
workflow scheduling in Grid environment. Each bacterium is a solution to the
workflow scheduling problem. The objective of the BFO is to find the bacterium
which has the minimum makespan.
3.2.1 Bacterial Representation and Initial Position Generation
One key issue when designing the BFO algorithm lies in its solution representation
where the bacteria bear the necessary information related to the problem domain. For
workflow scheduling problem, an intermediate representation is obtained as
following. The bacterium is encoded with a scheduling vector and allocation matrix.
The scheduling vector indicated the scheduling sequence of all tasks. The allocation
matrix defined the mapping between tasks to grid resources. The scheduling vector is
a permutation of task number, beside it needs to follow the restriction of DAG. Given
tasks
T
=
{
T
,
T
,...,
T
}
, the scheduling vector can be denoted as follows.
1
2
SV
=
{
T
,
T
,...,
T
}
(5)
k
1
k
2
kn
Every task number is presented in the scheduling vector and appears only once.
The scheduling vector specified the scheduling order of the workflow application.
The initial scheduling vector can be generated using a breath-first search procedure
over the workflow DAG.
