Information Technology Reference
In-Depth Information
For every algorithm, we have done eight sets of experiments and every experiment
was repeated 10 times with random seed. The task number of workflow DAG graph
ranged from 20 to 160. The resource number is fixed as 10. The computation cost of
each task was randomly selected from a normal distribution, so as the communication
data size between tasks. We assume the resources are fully connected and their
computation capacities are randomly selected from a normal distribution. The
makespan value of the best solutions through the optimization run was recorded and
the average makespan was calculated from the 10 different trials. The average time of
each algorithm to generate the optimal solution was also recorded. The percentage of
improvement in makespan for BFO algorithm is calculated as formula [11]:
∑
avg
Makespan
BFO
δ
=
(
-
)
×
100
(11)
∑
avg
Makespan
other
Table 2 shows the performance comparisons of the three algorithms.
bes
M
denotes the best makespan value of the ten trials.
av
M
denotes the average
makespan of the ten trials.
av
T
denotes the average execution time to get a optimal
solution for each algorithm. The three variables are all measured in seconds.
Table 2.
Comparison of results for different tasks (s)
Tasks
ACO
PSO
BFO
av
M
av
M
av
M
bes
M
T
bes
M
T
bes
M
T
avg
avg
avg
20 98.1 106.6 0.1 102.7 104.2 2.1 91.6 91.8 3.0
40 172.8 194.8 0.6 172.8 174.9 4.4 161.7 162.4 5.0
60 233.5 247.2 1.4 216.0 217.7 6.5 207.1 213.2 6.4
80 314.4 326.0 3.3 292.4 298.9 9.3 277.0 278.4 7.8
100 420.3 432.7 8.5 387.1 387.4 11.0 376.8 382.4 9.4
120 475.6 504.4 12.0 421.5 425.6 14.0 419.4 421.9 11.1
140 574.5 602.5 20.4 500.5 513.2 16.2 498.4 508.8 12.4
160 695.6 719.7 33.5 594.3 597.3 17.3 593.6 596.3 13.9
It is observed that the BFO-based algorithm show better performance than ACO
and PSO with the improvement of 11.8% and 3.1% in average makespan. According
to the Table 2, we compare the execution time in Figure 4.
It is observed that the execution time of PSO and BFO algorithm is linearly
increased as the task increased, while the execution time of ACO algorithm increased
drastically. When the task number is below 60, ACO and PSO algorithm takes less
time to generate an optimal solution. When the number exceeds 60, the BFO
algorithm takes less time to generate an optimal solution than PSO method.
