Computational Intelligence - February 2015 - 42
Improvement Over SRCI
50%
40%
30%
20%
10%
0%
0.01
Best Two Phase Heuristic+LS
(400) - 50.8%
GA+SA
(200) - 49.3%
(400) - 30.1%
(200) - 28.5%
(100) - 12.1%
(100) - 33.1%
(50) - 17.1%
(50) - 8.4%
0.10
1.00
10.00
Time (Seconds, Logarithmic Scale)
100.00
Figure 5 Improvements and time efficiency of the reordering
local search method, compared with GA+SA from [23].
that the best heuristics are in this case MinDMaxP (for the
small problems) and MinTMaxP (for the large problems), two
of the best ones in terms of profit in Table 3.
It stands out the good performance of MaxPMinT for
n = 50 VM requests, as it is the heuristic that found the solutions with the lowest number of on-demand instances needed,
but the profit of such solutions is very poor (it is the worst
value in Table 3). We suspect that the reason is that MaxPMinT
allocates a high number of VMs into RIs with higher capacity,
therefore causing an important loss in the profit (this is supported by the good makespan/flowtime values of its solutions).
MaxMaxProfit is globally the one providing best profit values (as shown in Table 2), but it surprisingly provides the worst
results in terms of the number of on-demand instances used.
The reason is that the difference between high capacity RI and
a low capacity RI is much higher than the cost of using an ondemand instance. Therefore, while other heuristics focus on
optimizing the use of the available resources, MaxMaxProfit
might decide to book an on-demand resource even when
there are available RIs, that could be later assigned to a VM that
better fits its features.
Summarizing, the experimental comparison of two phase
heuristics indicates that the MaxMaxProfit heuristic is the most
appropriate choice among the studied ones for the virtual broker: it clearly outperforms the compared heuristics in terms of
profit, and it is among the best ones according to the makespan
and flowtime metrics (that measure the resources utilization
and the QoS offered to users, respectively).
2) Comparison against the best previous results for the VMMP
from [22]: Table 6 on the VMMP website reports the comparison of the profit results computed using the proposed heuristic
against the best previous method for the VMMP (the onephase SRCI heuristic, presented in [22]). In it, most of the proposed heuristics generally outperform the compared SRCI
algorithm. Only MaxPMinT is performing worse than SRCI
in all cases. All the other proposed heuristics outperform SRCI
for all workload instances, with improvements of up to 5.45
cost units over it (meaning 7.4% better). However, the best
improvements are obtained by MaxMaxProfit heuristic for the
42
IEEE ComputatIonal IntEllIgEnCE magazInE | fEbruary 2015
biggest problems (400 workload dimension), reporting a solution 30% better than the best previously existing one.
In summary, all proposed two-phase heuristics but MaxPMinT outperform SRCI in terms of profit for the virtual broker, with overall improvements of up to 10.6%.
3) Reordering local search results: We now proceed to analyze
the performance of the proposed LS algorithm when applied
to improve the results of the two-phase heuristics. To simplify,
we chose the best five proposed heuristics for this study (the
results are provided in Table 7 on the VMMP website). From
the results, we see that the application of the LS after the
selected two-phase heuristics leads to an improvement of the
solution quality in all cases (up to 82.23%), with the only
exception of one scenario for the smallest workload dimension.
The best improvements are computed by MinGAPMaxP for
the smallest scenario of the 200 workload dimension. The solution that better benefits in more cases from the execution of
the LS is the one provided by MaxMaxProfit, reporting an
average improvement of 8.6% for all problem classes. This is,
precisely, the best of the studied algorithms in terms of profit.
We also compared the average improvements computed by
the best two-phase heuristics empowered with the local search
over the SRCI heuristic versus the improvements computed by
the GA+SA metaheuristic (all values are summarized in Table 8
on the VMMP website).
Results show that all of the local-search-empowered twophase heuristics are able to compute significantly more profitable schedules than the SRCI heuristic. In particular, the
MaxMaxProfit+LS heuristic performs the best with an average
profit improvement of 19.72%, and a maximum profit
improvement of up to 81.72%. As expected, results show that
the GA+SA metaheuristic is able to compute solutions with
greater profit improvements on most of the scenarios. Nevertheless, the MaxMaxProfit+LS heuristic computes more accurate solutions for the majority of the most loaded instance scenarios, that is, the instance scenarios with greater VM requests
and RI ratio.
The previously commented improvements on the profit of
the virtual broker achieved when using the reordering local
search after the two-phase heuristics do not come totally for
free. A moderate impact is observed in both QoS metrics studied: the makespan and flowtime results are 2.4% and 5.1%
worse in average, respectively, when using the reordering local
search. Although these values do not represent a major degradation in QoS, they suggest that the reordering local search
technique should be applied carefully, paying special attention
to those user-related metrics that could affect the virtual broker reputation.
In Fig. 5, we compare the performance in terms of time
and quality of solutions (improvement of profit with respect
to SRCI) of the best two-phase heuristics and the hybrid
genetic algorithm GA+SA, which holds the best known
results for this problem [23]. It can be seen that GA+SA outperforms the proposed methods by roughly 20%, however
this improvement comes with a loss on the makespan and
Table of Contents for the Digital Edition of Computational Intelligence - February 2015
Computational Intelligence - February 2015 - Cover1
Computational Intelligence - February 2015 - Cover2
Computational Intelligence - February 2015 - 1
Computational Intelligence - February 2015 - 2
Computational Intelligence - February 2015 - 3
Computational Intelligence - February 2015 - 4
Computational Intelligence - February 2015 - 5
Computational Intelligence - February 2015 - 6
Computational Intelligence - February 2015 - 7
Computational Intelligence - February 2015 - 8
Computational Intelligence - February 2015 - 9
Computational Intelligence - February 2015 - 10
Computational Intelligence - February 2015 - 11
Computational Intelligence - February 2015 - 12
Computational Intelligence - February 2015 - 13
Computational Intelligence - February 2015 - 14
Computational Intelligence - February 2015 - 15
Computational Intelligence - February 2015 - 16
Computational Intelligence - February 2015 - 17
Computational Intelligence - February 2015 - 18
Computational Intelligence - February 2015 - 19
Computational Intelligence - February 2015 - 20
Computational Intelligence - February 2015 - 21
Computational Intelligence - February 2015 - 22
Computational Intelligence - February 2015 - 23
Computational Intelligence - February 2015 - 24
Computational Intelligence - February 2015 - 25
Computational Intelligence - February 2015 - 26
Computational Intelligence - February 2015 - 27
Computational Intelligence - February 2015 - 28
Computational Intelligence - February 2015 - 29
Computational Intelligence - February 2015 - 30
Computational Intelligence - February 2015 - 31
Computational Intelligence - February 2015 - 32
Computational Intelligence - February 2015 - 33
Computational Intelligence - February 2015 - 34
Computational Intelligence - February 2015 - 35
Computational Intelligence - February 2015 - 36
Computational Intelligence - February 2015 - 37
Computational Intelligence - February 2015 - 38
Computational Intelligence - February 2015 - 39
Computational Intelligence - February 2015 - 40
Computational Intelligence - February 2015 - 41
Computational Intelligence - February 2015 - 42
Computational Intelligence - February 2015 - 43
Computational Intelligence - February 2015 - 44
Computational Intelligence - February 2015 - 45
Computational Intelligence - February 2015 - 46
Computational Intelligence - February 2015 - 47
Computational Intelligence - February 2015 - 48
Computational Intelligence - February 2015 - 49
Computational Intelligence - February 2015 - 50
Computational Intelligence - February 2015 - 51
Computational Intelligence - February 2015 - 52
Computational Intelligence - February 2015 - 53
Computational Intelligence - February 2015 - 54
Computational Intelligence - February 2015 - 55
Computational Intelligence - February 2015 - 56
Computational Intelligence - February 2015 - 57
Computational Intelligence - February 2015 - 58
Computational Intelligence - February 2015 - 59
Computational Intelligence - February 2015 - 60
Computational Intelligence - February 2015 - 61
Computational Intelligence - February 2015 - 62
Computational Intelligence - February 2015 - 63
Computational Intelligence - February 2015 - 64
Computational Intelligence - February 2015 - Cover3
Computational Intelligence - February 2015 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com