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
)
:
