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

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