The Cloud Computing paradigm consists in providing customers with virtual services of the quality which meets customers' requirements. A cloud service operator is interested in using his infrastructure in the most efficient way while serving customers. The efficiency of infrastructure exploitation may be expressed, amongst others, by the electrical energy consumption of computing centers. We propose to model the energy consumption of private Clouds, which provides virtual computation services, by a variant of the Bin Packing problem. This novel generalization is obtained by introducing such constraints as: variable bin size, cost of packing and the possibility of splitting items. We analyze the packing problem generalization from a theoretical point of view. We advance on-line and off-line approximation algorithms to solve our problem to balance the load either on-the-fly or on the planning stage. In addition to the computation of the approximation factors of these two algorithms, we evaluate experimentally their performance. The quality of the results is encouraging. This conclusion makes a packing approach a serious candidate to model energy-aware load balancing in Cloud Computing.
@cite_5: In this paper, we consider the variable sized bin packing problem where the objective is to minimize the total cost of used bins when the cost of unit size of each bin does not increase as the bin size increases. Two greedy algorithms are described, and analyzed in three special cases: (a) the sizes of items and bins are divisible, respectively, (b) only the sizes of bins are divisible, and (c) the sizes of bins are not divisible. Here, we say that a list of numbers a1,a2,…,am are divisible when aj exactly divides aj−1, for each 1<j⩽m. In the case of (a), the algorithms give optimal solutions, and in the case of (b), each algorithm gives a solution whose value is less than 119C(B*)+4119, where C(B*) is the optimal value. In the case of (c), each algorithm gives a solution whose value is less than 32C(B*)+1.
If any bin is as good as the others, putting items inside a solution to this problem is trivial, as one will always be interested in using the largest bin. We thus suppose that bin utilization induces a certain cost associated to this bin. This assumption leads to the Variable Sized Bin Packing with Cost Problem (VSBPCP). The reader might already observe that in the BPP the cost of packing is always the same regardless of the bins chosen. This fact explains that the new problem is NP-hard @cite_5 . Intuitively, one can consider that the cost of packing varies in function of a bin capacity. From this point of view we are no longer interested in minimizing the number of bins used but in minimizing the global packing cost as a voluminous bin which remains 'almost empty' may be more expensive in use than several little bins 'almost totally' full. Solving the VSBPCP we have at our disposal @math classes of bins and the infinite number of bins of any class available.