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.