Computational Intelligence - February 2015 - 37
the broker. These two articles deal with the problem of
resource provisioning using information from the historical
utilization and demands of the cloud infrastructure.
In our approach, we investigate how the virtual broker can
optimally manage a given infrastructure of RIs to satisfy the
customers' demand, maximizing the profit while providing
acceptable QoS. On-demand instances will be used to cope
with those requests that cannot be assigned to any RI, despite
the profit loss. In our previous works [22][23], we introduced
the model for VM planning and developed simple greedy heuristics and metaheuristics [24] to solve the problem. The experimental analysis demonstrated that the simple heuristics are
effective for solving scenarios with a reasonable number of VM
requests for a given infrastructure, but they are not able to deal
properly with highly loaded scenarios [22]. In this article we
introduce fast and efficient methods for VM planning, including two-phase heuristics and a reordering local search, that
allow computing more accurate solutions for the virtual broker
in reduced execution times.
IV. Two-Phase List Scheduling Heuristics and
Reordering Local Search for the VMMP
This section introduces the class of list scheduling heuristics
and describes both the new scheduling heuristics proposed for
the VMMP and the fast reordering local search used to improve
the solutions.
A. List Scheduling Heuristics
The class of list scheduling heuristics [25] includes many deterministic scheduling methods that work by assigning priorities
to tasks based on a particular criterion. After that, the list of
tasks is sorted in decreasing priority, and each task is assigned
to a processor, depending on the task priority and the processor availability.
Many list scheduling techniques have been proposed to provide easy methods for tasks-to-machines scheduling. This class
of methods has also often been employed in hybrid algorithms,
with the objective of improving the search of metaheuristic
approaches applied to solve scheduling problems in heterogeneous computing systems [26][27].
The simple approach in the basic list scheduling algorithm
can be extended to consider two phases for searching the most
appropriate task (VM request in our problem) to be scheduled
to a certain machine (RI in our problem) in each time step.
This strategy leads to a more complex and sounded search, following a holistic criteria to perform the mapping, often allowing to improve the objective (profit) values.
The two-phase approach applied to the VMMP is described
in Algorithm 1. It follows a schema that applies two phases (i.e.,
double loop) to perform the VM-to-RI assignment. A list of
unmapped requests is kept. In the first phase, N pairs (VM
request, RI) are selected considering a specific criterion. Then,
in the second phase, one of the previous N pairs is selected
regarding an overall comparison, possibly using a different criterion than the one used in the first phase. The proposed strat-
Algorithm 1: Two-phase list scheduling heuristic for the VMMP.
1 VM requests assigned = 4
2 while unassigned VM requests do
3 for each unassigned VM request, each RI do
4
determine a list of the most suitable pairs (VM request, RI)
according to the first phase criterion
5
for each pair (VM request, RI) do
6
evaluate second phase criterion (VM request, RI)
7
end for
8 end for
9 if selected RI allows meeting the VM request deadline
then
10
assign the selected VM request to the selected RI
11 else
12
assign the selected VM request to execute in a
on-demand VM in the cloud
13 end if
14 insert selected VM request to VM requests assigned
15 end while
egy can be extended by considering two objective functions, as
we applied for makespan and energy optimization in heterogeneous grid systems planning [28].
B. Two-Phase List Scheduling Heuristics for the VMMP
In this work, we conceive and implement seven two-phase list
heuristic algorithms, which provide different approaches to
solve the VMMP, by using diverse criteria for assigning priorities to VM requests. The new heuristics take into account the
VMMP objective of maximizing the profit, but also reducing
makespan metric (defined as the difference between the finish
and start time of a given batch of tasks), since obtaining balanced schedules implies a better utilization of the available
resources. It also implies better QoS metrics, such as minimizing
the queue waiting time, and fulfilling the deadline constraints.
The proposed two-phase heuristics for the VMMP include:
1) Maximum Maximum Profit (MaxMaxProfit). A greedy profit-oriented list scheduling heuristic that follows an
approach similar to the well-known MinMin scheduling
heuristic for makespan optimization [25]. However, MaxMaxProfit uses the contribution of each request to the
global profit objective function in the VMMP formulation, instead of minimizing the execution time. MaxMaxProfit first loops on VM requests, and then for each
request a loop over the RIs is performed, and the contribution of assigning the request to that RI to the global
profit is computed. In case the RI fulfills the hardware
requirements (memory, CPU, storage and number of
cores), the contribution of assigning the VM request v i to
the machine r j is defined as: i) if ST (v i) # D ^v i h (deadline is not violated), then the cost contribution is
T (v i) # ^ p ^ ri h - C ^r j hh, and ii) if ST (v i) 2 D (v i), then the
cost contribution is T (v i) # (p (ri) - COD (r j)), where ri is
the cheapest RI that satisfies the request v i . After that, the
request that contributes the most to the global profit is
assigned to execute in the correspondent instance. This
scheduling method is fully focused on improving the
february 2015 | Ieee ComputatIonal IntellIgenCe magazIne
37
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