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.
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.
@cite_5
2011949460 2963083784 2767913537 1847958188
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. We revisit the classic online bin packing problem studied in the half-century. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called bins of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method where items of one class can be packed into more than two types of bins, where a bin type is defined according to the number of such items grouped together. Additionally, we allow the smallest class of items to be packed in multiple kinds of bins, and not only into their own bins. We combine this with the approach of packing of sufficiently big items according to their exact sizes. Finally, we simplify the analysis of such algorithms, allowing the analysis to be based on the most standard weight functions. This simplified analysis allows us to study the algorithm which we defined based on all these ideas. This leads us to the design and analysis of the first algorithm of asymptotic competitive ratio strictly below 1.58, specifically, we break this barrier by providing an algorithm AH (Advanced Harmonic) whose asymptotic competitive ratio does not exceed 1.57829. Our main contribution is the introduction of the simple analysis based on weight function to analyze the state of the art online algorithms for the classic online bin packing problem. The previously used analytic tool named weight system was too complicated for the community in this area to adjust it for other problems and other algorithmic tools that are needed in order to improve the current best algorithms. We show that the weight system based analysis is not needed for the analysis of the current algorithms for the classic online bin packing problem. The importance of a simple analysis is demonstrated by analyzing several new features together with all existing techniques, and by proving a better competitive ratio than the previously best one. We study the classic Bin Packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio between updates. Formally, each item @math has a @math , and we want to use @math bins and incur a movement cost @math , either in the worst case, or in an amortized sense, for @math as small as possible. We call @math the of the algorithm. This is motivated by cloud storage applications, where fully-dynamic Bin Packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure. In this paper we consider the following bin packing problem with conflicts. Given a set of items V = 1,...,n with sizes s 1 ,...,s n ∈ (0,1) and a conflict graph G = (V, E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j') ∈ E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem. We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ∈) of optimal provided that the optimum number is sufficiently large. The running time of the algorithm is polynomial both in n and in 1 2.