Information Technology Reference

In-Depth Information

scheduling vector. We adopt the crossover operation in the Genetic Algorithm [9] to

construct a new scheduling vector. It has been approved that if the two scheduling

vectors are both feasible scheduling vector, then the newly constructed scheduling

vector is valid scheduling vector through crossover operation [9].

The crossover operation randomly chooses other bacterium's scheduling vector to

form a pair of scheduling vector. For each pair, it randomly generates a cut-off point,

which divides the scheduling vector of the pair into the first part and the second part.

Then the subtasks in each second part are reordered. The new ordering of the subtasks

in one's second part is the relative position of these subtasks in the other original

scheduling vector in the pair. Fig. 3 demonstrates such a scheduling vector crossover

process given the workflow graph in Fig. 1.

SV

1 3 4 5 6 2 8 7 9 10

1

SV

1 4 3 2 5 9 6 8 7 10

Cut-off index is 4 (start from 0)

2

new

SV
1

1

3

4

5

2

9

6

8

7

10

new

SV
2

1

4

3

2

5

6

8

7

9

10

Fig. 3.
A scheduling vector crosses over example

Because scheduling vector is discrete value, the swarm effects doesn't consider the

scheduling vector.

3.2.4 The Bacterial Foraging Algorithm

After defined the solution representation, we provide the BFO based scheduling

heuristic. BFO algorithm provide mapping of the entire task to a set of given resource

based on the model described in section 2.The pseudo code of our bacterial foraging

algorithm is given in Algorithm 1.

Algorithm 1: BFO based scheduling heuristic

Input: workflow application model
WF
, grid resource
GR

Output: schedule all tasks to resources and minimize

the makespan of workflow application

Parameter:

S
the number of bacteria in the population

(
iC
the size of the step taken in the random direction

specified by the tumble

)

: