Solving fully dynamic bin packing problem for virtual machine allocation in the cloud environment by the futuristic greedy algorithm

Abstract

Many scientists apply fully dynamic bin packing problem solving for resource allocation of virtual machines in cloud environments. The goal of problem-solving is to reduce the number of allocated hosts (bins) and virtual machines (items) migration rates for reducing energy consumption. This study demonstrates a greedy futuristic algorithm (proposed algorithm) for fully dynamic bin packaging with an average asymptotic approximation ratio of 1.231, better than other existing algorithms. The proposed algorithm identifies inappropriate local selections using special futuristic conditions to prevent them as much as possible. Eventually, suitable choices determine and discard the improper ones. The proposed algorithm illustrates an asymptotic approximation ratio of (t/ (t-1)) OPT, where the value of t depends on the distribution of the arrived and departed items. Also, OPT is the number of bins by an optimal solution. Finally, in experiments of datasets using a maximum utilization of 80% of each bin, the average migration rate is 0.338. Using the proposed method for allocating resources in the cloud environment can allocate hosts to a virtual machine using almost optimal use. This allocation can reduce the cost of maintaining and purchasing hosts. Also, this method can reduce the migration rate of virtual machines. As a result, decreasing migration improves the energy consumption cost in the cloud environment.

Keywords

Fully dynamic bin packing special futuristic conditions futuristic greedy migration reducing

1 Introduction

Modern computer science is trying to find approximate solutions to NP-Hard problems. This research, considers the approach of online approximation algorithms. Online approximation algorithms usually calculate a good upper or lower limit and compare their solutions with these limits. The upper and lower limit analysis is appropriate in the worst case but often leads to pessimistic analysis. The issue of bin packing is one of the essential issues in allocating resources in the cloud environment. There are many practical applications for bin packaging. For example, placing computer files of different sizes in fixed-size memory blocks, or allocating resources in the cloud environment, scheduling parallel processors. In this paper, the proposed method considers the problem of bin packing as a problem-solving solution in allocating hosting resources to virtual machines [1].

The increasing growth of cloud services and applications is accompanied by the consumption of large amounts of energy. Therefore, efficient management methods to reduce energy consumption in cloud data centers have become one of the most important priorities. An appropriate management method to reduce energy consumption is the proper allocation of physical servers of cloud computing resources. Proper allocation of hosts to the virtual machine and integrating the virtual machine increase energy efficiency in cloud infrastructure migrating virtual machines can use the minimum number of hosts to allocate virtual machines reduces the activated physical machine. Since the virtual machine transfer operation consumes extra energy, the virtual machine’s migration frequency must also be limited and controlled. Bin packing problem solving is used to find the appropriate resource allocation. Bin packing problem, consider hosts as bins and virtual machines as items [2].

The problem of bin packing can be described as packing n items into m bins such that the sum of the items’ weight in each bin would not exceed its capacity, while the number of utilized bins is minimized [3, 4].

There are many variations to this problem. The online and dynamic bin packing problems are examples of the problems in which no information is provided about the future items. The packing is accomplished based on the available information [5].

These problems can be classified into four categories as follows based on online depart and arrival and also repacking capability [6]:

Online bin packing: In this type of packing, items arrive, but they do not depart. Items are packed online once and cannot be repacked.

Relaxed online bin packing: In this type of packing, items arrive, but they do not depart. They are packed online and repacked in the future.

Dynamic bin packing: In this type of packing, items can arrive and depart while repacking is not allowed.

Fully dynamic bin packing: In this type of packing, items can arrive and depart, and repacking is allowed. Some bins are defined as the open bin. An open bin is a bin that can be repacked. Fully dynamic bin packing is classified into two categories: limited open bins or unlimited open bins. Limited open bins are bins that can be repacked with a Limited number of packing.

One of the new applications of fully dynamic bin packing is allocating resources in the cloud computing environment. The reason is that it is possible to reallocate hosts with virtual machines through migration. The purpose of resource allocation in cloud computing is that host machines (e.g., their processors) are allocated to virtual machines with the minimum number of hosts. Minimizing the number of physical host machines in data centers, server maintenance costs, and energy costs are reduced [7, 8]. Further, the fully dynamic bin packing has multiple online scheduling applications, which shortens the time of makespan in parallel processing and online management of facilities [9].

The use of bin packing methods in allocating resources in the cloud environment significantly decreases energy consumption. Also, proper allocation of hosts will reduce migration rates of virtual machines as virtual machine migrations diminish due to a lack of resources in a host [10].

This research’s main goal is to provide a new greedy algorithm for solving the fully dynamic bin packing problem. It firstly solves the problem in polynomial time. Further, it provides a better asymptotic approximation ratio than the other existing algorithms while also minimizing the summation of bins’ free space.

This paper introduces the research problem and related literature in sections 1.1, section 1.2, and section 1.3. It further discusses commonly used algorithms in sections 1.4, section 1.5, and section 2 review related work. The proposed algorithm and its idea are described in section 3. After presenting the proposed method, we analyze the asymptotic approximation ratio formally in section 4. Experimental results in section 5 discuss several allocated bins and swapping rates, and challenges. Finally, section 6 concludes the paper.

1.1 Defining the research problem

In online algorithms (like fully dynamic bin packing), items arrive over time, and each item must be placed in a bin before the next item arrives. Online algorithms predict the current allocation of probabilistic future cases [11].

The research problem is known as a fully dynamic bin packing. In this problem, a series of bins exist with equal capacity C (hosts with equal processing power) and a series of items (virtual machines with variable processing power) with different weights within the range. We want to pack the items into bins, which must be done with the minimum number of bins. The goal is to reduce the total cost of energy consumption and the cost of purchasing hosts by almost a minimum of hosts and migration reduction. The problem assumptions include:

Online items frequently arrive and depart (virtual machines are created or deleted/turned on or shut down / migrate).

Items are packed online, and it is possible to repack the bins or release them (hosts are allocated or reallocated to virtual machines online).

No information is available about the usage of CPU requests from future items (virtual machines).

Bins are homogeneous with identical capacity (hosts are homogeneous).

Items are indivisible. The fraction of the item cannot be packed. Indeed, items cannot be broken (each virtual machine can only run on one host. We cannot run part of one virtual machine on another host).

The research problem is known as a fully dynamic bin packing. In this problem, a series of bins are defined with equal capacity C (hosts with equal processing power) and series of items (virtual machines with variable processing consumption) with different weights within the range. Optimal solution is to pack the items into bins, which it be performed with the minimum number of bins. The goal is to reduce the total cost of energy consumption and the cost of purchasing hosts by almost a minimum of hosts and migration reduction. The problem assumptions include:

Online items arrive and frequently depart (virtual machines are created or deleted/turned on or shut down / migrate).

Items are packed online, and it is possible to repack the bins or release them (hosts are allocated or reallocated to virtual machines online).

No information is available about the usage of CPU requests from future items (virtual machines).

Bins are homogeneous with identical capacity (hosts are homogeneous).

Items are indivisible. The fraction of the item cannot be packed. Indeed, items cannot be broken (each virtual machine can only run on one host. Hence, part of one virtual machine cannot run on another host).

1.2 Online algorithms [6]

Sometimes, resource allocation problems are online. These problems include of little information or no information of successive items. An online algorithm may have a look-ahead, that is, the ability to know some of the future requests; the algorithm may be allowed to postpone some selections or revise some of them after the arrival of more input; or the algorithm may be allowed to make assumptions about the request sequence, for example, resource allocation in the cloud environment can be online because required resources for virtual machines vary in the cloud environment. Also, there is little information or no information on future resource requests of virtual machines, so the allocation of host resources is online—likewise, a fully dynamic bin packing problem in the online VM allocation.

1.3 Asymptotic competitive ratio [6]

The asymptotic competitive ratio is called the limiting approximation ratio. Let OPT, S denote the optimal solution and approximation solution, for instance, I. The absolute approximation ratio (α) in approximation algorithms is formula (1): $S ⩽ α . OPT$ (1)

Computer science scholars can use approximation algorithms when computation occurs online or semi online, and they know no complete information about the next inputs. Thus, the asymptotic competitive ratio () is used for online approximation algorithms (instead (α)).

The asymptotic competitive ratio () in online or semi online approximation algorithms is formula (2): $S ⩽ β . OPT + K, K ⩽ Constant value$ (2)

1.4 Introducing commonly used greedy algorithms in resource allocation

Greedy algorithms try to find a proper solution by discovering locally optimal choices at each step. In many problems, a greedy strategy does not usually produce an optimal solution. Still, a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. The basic algorithms for solving resource allocation problems are as follows: Next Fit, first fit, and best fit, worst fit, harmonic, and refined harmonic.

These basic algorithms are compared in an asymptotic approximation ratio, as presented in Table 1.

Table 1
Comparison of basic algorithms in online bin packing [12]

Algorithm Asymptotic approximation ratio

Next fit 2

Best fit 1.7

Worst fit 1.7

First fit 1.7

Harmonic 1.691

Refined Harmonic 1.639

Algorithm	Asymptotic approximation ratio
Next fit	2
Best fit	1.7
Worst fit	1.7
First fit	1.7
Harmonic	1.691
Refined Harmonic	1.639

The worst fit acts in contrast to the best fit. The asymptotic approximation ratio is the same in the first fit, worst fit, and best-fit algorithms, but the best fit is empirically more appropriate.

The harmonic algorithm has a better performance with an approximation of 1.691. The refined harmonic algorithm outperforms the harmonic algorithm and reduces the asymptotic approximation ratio to 1.639.

1.5 Special refined harmonic (SRH)

The refined harmonic algorithm classifies items into several types based on their weights. Each item of type I is packed into using the next fit algorithm [13]. In this research, a particular case of a refined harmonic algorithm defined as the SRH algorithm. SRH algorithm is shown in Algorithm 1. In the SRH algorithm, the weight of all items is classified into two categories: $1 . Item weights \in (0 \frac{C}{3}] pack into bin of type I$ $2 . Item weights \in (\frac{C}{3} \frac{C}{2}] pack into bin of type II$

Items are packed based on their weight into one of two types of bins with equal capacity.

Algorithm 1. Special refined harmonic algorithm (SRH)
While (item arrive or depart) do % online arrive or depart
If (item depart) then
Release item of bin % remove item of bin
Reorganize bin % calculate and merge the free spaces
If (item arrive) then
$if Size \in (0 \frac{C}{3}]$ then insert item to one bin of type I
$if Size \| \in (\frac{C}{3} \frac{C}{2}]$ then insert item to one bin of type II

1.6 Challenges of the research problem

There are three major challenges to fully dynamic bin packing solving. The first challenge, fully dynamic bin packing, is a complete NP problem. In this problem, items may dynamically arrive and depart the bin. Items can be moved from bin to other bin by adjusting the packaging to accommodate incoming and outgoing items. Although competitive analysis is an excellent way to analyze online algorithms, it sometimes conflicts with intuition. The main problem in competitive analysis is comparing the performance of an online algorithm concerning these contradictions. The solution to this problem is to compare the problem solving with the offline algorithm’s optimal solution [14].

The second challenge, in some cases, reducing migration rates, is a critical issue. For example, in resource allocation issues in the cloud environment, reducing the migration rate reduces energy costs [15].

The third challenge, fully dynamic packing with advice, is an area of research where one attempts to measure how much knowledge of the future is necessary to achieve a given competitive ratio. The lower bound results show robust bounds on what is possible using semi-online algorithms. On the other hand, when the advice is of an obtainable form, algorithms using advice can lead to semi-online algorithms. There are strong relationships between advice complexity and randomization, and advice complexity has led to introducing the first complexity classes for the online problem [16].

According to the mentioned challenges, the proposed method is considered for three factors. The first factor, the proposed method presents an algorithm theoretically for reducing energy consumption based on reducing migration rate and the number of allocated hosts. The proposed method solves problems regardless of the environmental factors and overheads in real conditions. Thus, this method can perform efficiently platform-independent in all cloud environments.

The second factor, the proposed algorithm determines what virtual machine is selected intelligently for migration to which host. Hence, it can decrease the energy consumption of the CPU by the usage of minimum hosts and their migrations in the cloud environment.

The third factor is that the proposed method creates bins allocation to efficiency because it determines the appropriate dynamic space of existing bins performs better than static space. Static techniques cannot change dynamic packaging because they do not detect inappropriate packing according to new and future requests. This method creates more empty spaces in the bins by the dynamic changes in the packing. More empty spaces more likely to accommodate future items with more capacity.

2 Literature review

Previous works can be studied in four categories of bin packing based on online depart and arrival and repacking capability (Online bin packing, relaxed online bin packing, dynamic bin packing, and fully dynamic bin packing). These categories can be used in cloud environments with several energy consumptions. In addition to the number of hosts, are critical factors in resource allocation. Hence, we investigate algorithms by migration ratio and approximation ratio.

2.1 Online bin packing

Balogh et al. (2010) [17] designed a harmonic algorithm for online bin packing problem. They calculated the lower bound as 1.54037. Zheng et al. (2015) [12] presented an algorithm with an approximation ratio $\frac{1}{2 + α}$ for online bin packing, where α is the item weight in (α, 1/2]. Their work focused on improving the algorithm’s next fit with a lower bound $\frac{4}{3}$ and approximation ratio $\frac{13}{9}$ . Renault et al. (2015) [18] developed the next fit algorithm. They presented a new algorithm with an approximation ratio $(1 - \frac{2 m}{n}) logm$ in online bin packing of cloud computing, where n is the number of jobs and m represents the number of physical machines (bins). Finally, Balogh et al. (2018) [19] meliorated the asymptotic competitive ratio to 1.54278. They improved the lower bound on any online algorithm’s asymptotic competitive rate for bin packing to above 1.54278. They exhibited the advantage of branching and the applicability of full adaptively in lower bounds for the classic online bin packing problem. They applied a new method for weight-based analysis, which is usually used only in proofs of upper bounds.

The four mentioned methods are designed based on the classification of bins for placing different ranges of items. These categories created less space in the bins without consideration of item distribution. These categories create less space when the items permutations cannot pack items in bins with less space. For this reason, categorization alone cannot be an accurate method to improve the solution.

Decreasing space depends on the type of distribution and the capacity of the bins. Online bin packing methods can use this approach because there is no information from the future items, and there is no ability to repackage. Békési et al. investigated the bin packing problem by considering the number of items. They analyzed the best absolute competitive ratio and proved tight bounds of 2 for any k≥4 (k is the number of items). Additionally, they presented bounds for relatively small values of k concerning the asymptotic competitive ratio and the absolute competitive ratio. In particular, they provided tight bounds on the absolute competitive rate of First Fit for k = 2, 3, 4. They amended the known lower bounds on asymptotic competitive ratios for multiple values of k. [20]. Online bin packing can improved solutions by new limitations in problem definition. For example, Epstein et al. improved the lower bound on the asymptotic competitive ratio for online bin packing of rectangles. They showed exact proof for lower bound 1.91 [21]. Some scientists also improved the approximate solution by knowing detailed information about future items for packing in bins. Angelopoulos et al. investigated the complexity of the online bin packing problem. They considered some additional information concerning the input. They could improve upon both known upper and lower bounds of online algorithms. Their algorithm achieved a competitive ratio arbitrarily nearby 1.5, using constant-size advice. Also, they illustrated a more complex algorithm that still requires only constant-size advice and has a competitive rate arbitrarily close to 1.47012 [22].

2.2 Relaxed online bin packing

The relaxed online bin packing methods can improve the solution based on the bins repacking. Gambosi et al. (2000) [23] surveyed relaxed online bin packing. They considered bins that could be repacked again. They improved the solution, but their method created a high rate of migration. Therefore, this algorithm’s use in the cloud environment is not recommended because the migration rate of the virtual machine increases energy costs.

Epstein et al. (2009) [24] studied the migration factor 1+ɛ for relaxed online bin packing. They presented an algorithm with an asymptotic competitive ratio 1+ɛ of and swapping factor $2 O (\frac{1}{ɛ} log (\frac{1}{ɛ}))$ . Balogh et al. (2008) [25] proposed another improved algorithm with a lower bound on the asymptotic competitive ratio of 1.3877 and an efficient migration rate. In their algorithm, the repacking of bins depended on the constant number of items. Thus, with the increase in items, the migration rate increased almost uniformly. Jansen et al. (2013) [26] improved the lower bound by intelligent repacking. Also, Balogh et al. (2014) [27] presented an algorithm based on a harmonic fit algorithm with a competitive ratio of 3/2 by a novel migration method. Both accomplished their research using proper repackaging. But they failed to reduce immigration rates acceptably.

Jansen et al. introduced a sample of relaxed online bin packing with limited conditions. Hence, they could improve the asymptotic approximated ratio and migration ratio. They attended the relaxed online strip packing problem. Rectangular items come online and have to be placed without rotations into a fixed-width strip such that the packing height is minimized. In addition to that, the repacking of previously packed items is permitted. The amount of repacking is calculated by the migration factor, defined as the total size of repacked items divided by the arrival item’s size. They illustrated that no algorithm with a constant migration rate could generate solutions with an asymptotic ratio better than 4/3. Against this background, they permitted amortized migration, i.e., to preserve migration for a later time step [28].

2.3 Dynamic bin packing

Balogh et al. (2014) [29] proposed an FT algorithm with an approximation ratio of 5/3 in cloud resource allocation. In their algorithm, particular bins were kept open as they may have been packed more efficiently in the future. Their method is not suitable for cloud and realistic environments because, in real environments, the bins cannot open for a long time. This method offered appropriate solutions, but its practical application is rare.

Due to the lack of repackaging in dynamic bin packing, Li et al. (2016) [30] proposed the Hybrid First Fit (HFF) algorithm for dynamic bin packing with a competitive ratio of $\frac{5}{4} M + \frac{19}{4}$ , where M is defined as $\frac{m}{n}$ :m and n represent the maximum and minimum interval ratios of the items. This approach does not involve repacking and outperforms previous algorithms such as harmonic++. This method cannot present a proper solution.

Boyar et al. (2016) [16] can improve the solution by considering extra information about items. They proposed an algorithm for the dynamic bin packing problem. They designed an algorithm with a competitive ratio $\frac{3}{2}$ of using limited information about the items. They could provide conditions with a competitive ratio $\frac{9}{8}$ . Also, Heydrich et al. (2016) [31] used an innovative technique for proper allocation by combining larger sizes in pair bins. They could improve an algorithm with a lower bound of 1.5762 for dynamic bin packing.

Spencer et al. (2019) [32] used a meta-heuristic algorithm for solving multi-objective dynamic bin packing problems in storing cooling objects. The dynamic bin packing problem is shown based on cookie generation at a bakery, where cookies get in batches at a cooling rack with limited capacity and are placed into bins with three approaches. The first approach is to minimize the number of used bins. The second approach is to reduce the average initial heat of each bin, and the third approach is to reduce the maximum time until the bins can be moved. The new meta-heuristic method was used for various benchmark bin packing problems and different dynamic bin packing problems. It improved overall in the small dynamic problem, but its performance could not be better or worse in the large dynamic. They illustrated proper solutions in a real environment by experimental results. But, they couldn’t prove their results theoretically.

2.4 Fully dynamic bin packing

In fully dynamic bin packing, items can arrive or depart. Also, bins can be repacked. Sebastian Berndt et al. (2018) [6] presented an approach for a fully dynamic bin packing offering a tradeoff between the migration rate and the number of items. The complexity of the algorithm is polynomial, and it is based on the migration rate and the number of items. In this algorithm, the number of repacking depends on the number of items and data distribution. It needs maximum packing O(logn). The maximum number of bins was $O (\frac{1}{ɛ^{3}} \log (\frac{1}{ɛ}))$ , and the migration rate was $O (\frac{1}{ɛ^{4}} \log (\frac{1}{ɛ})$ ). They found that the approximation ratio could be improved based on elevating the migration rate. They didn’t present proper results in fully dynamic bin packing because of the migration ratio depending on the number of items. Therefore, the migration ratio may be high.

Balogh et al. (2017) [33] presented an advanced harmonic algorithm with an asymptotic competitive ratio of 1.57829 for decreasing migration ratio. For this purpose, a new category was applied where items could be packed in two or more bins. This algorithm was designed for fully dynamic bin packing to prevent some restrictions for better packing in the future. Indeed, the algorithm can avoid some inappropriate greedy selections. Another technique for decreasing migration ratio is designed by buffer using. Zhang et al. (2017) [34] investigated items with a finite weight between the constant a and1, along with a limited buffer. The bin packing was explored in the cloud environment. Also, vectorpot, sandpiper, heaviest first, enhanced FFD, and VISP algorithms were considered. Their work focused on the design of an algorithm based on load balancing and avoidance of overloads. They solved the problem with a finite and constant buffer, where the lower bound changed from 1.3333 to 1.4230, while the upper bound varied from 1.4444 to 1.4243. Hence, this method cannot be implemented in some systems due to a lack of buffer.

Another method for improving solutions in fully dynamic bin packing is using unlimited repacking. Feldkord et al. (2017) [35] presented a tight approximation for fully dynamic bin packing without bundling. They developed an algorithm with invariant repacking of bins. The approximation ratio of their algorithm was 1.3871. Of course, this method is not used in environments with limited repackaging.

Another example, Feldkord et al. investigated Fully Dynamic Bin Packing with items size in (0, 1] that must be placed in bins of the same size. Items arrive or depart from the packing. Their algorithm maintained a feasible packing while only repacking a bounded number of items in each time step. They presented an algorithm that repacks only a fixed number of items per time step. They do not depend on the bundling of small items, which allowed those solutions to move an unbounded number of small items as one. Their algorithm has an asymptotic approximation ratio of 1.3871 [38]. But this method used limited repacking with a frequent fixed number.

Gupta et al. (2017) [36] introduced fully dynamic bin packing with limited repacking. They discussed a tradeoff between the number of bins and the migration rate of items. They discussed the fully dynamic bin packing problem where new items can arrive, and old items may depart. They could present algorithms with a low asymptotic competitive ratio while repacking items. Cloud storage applications can use their method to reduce the number of used disks and file backup’s transformation between disks. They illustrated optimal tradeoffs between the number of used bins and the number of repacked items.

Some scientists have achieved better results with a limited weight range of items. For example, Albers et al. studied the random order ratio of Best Fit and tightened the long-standing gap by proving an improved lower bound of 1.10. In this research, all items were considered larger than 1/3. They showed that the random order ratio converges quickly to 1.25. Furthermore, this case is related to the classical maximum-cardinality matching problem in the fully dynamic bin packing. They proved upper and lower bounds of 21/16 and 1.2, respectively, for all items that are larger than 1/3. [37].

Limitations of the Lower bound and upper bound for fully dynamic bin packing is found by Epstein. Epstein et al. studied the minimum variant of the online open-end bin packing problem. Items have arrived one by one, and an item can be packed into a bin while there is empty capacity in the bins. They designed an improved online algorithm whose asymptotic competitive ratio does not exceed 1.180952381, and they illustrated a new lower bound of 1.1666666 on the asymptotic competitive rate of any online algorithm [39].

2.5 Cloud resource allocation by bin packing

The following are experiences of repackaging in real cloud environments by bin packing problems. These experiments are based on experimental experiments. Hence, we used these experiments to present a proposed algorithm based on theory. This experience is used in cloud resource allocation. Resource allocation strategies in virtualized data centers have received considerable attention recently as they can substantially impact the energy efficiency of a data center. It led to new decision and control strategies with significant managerial impact for IT service providers. The proposed method focuses on dynamic environments where virtual machines need to be allocated or not allocated to servers over time. Simple bin packing heuristics have been analyzed and used to place virtual machines upon arrival. However, these placement heuristics can lead to suboptimal server utilization because they cannot consider virtual machines, which arrive in the future. The proposed method ran extensive lab experiments and simulations with different controllers and different workloads to understand which control strategies achieve high energy efficiency levels in different workload environments. We found that combinations of placement controllers and periodic reallocations achieve the highest energy efficiency subject to predefined service levels. While the type of placement heuristic had little impact on the average server demand, the type of virtual machine resource demand estimator used for the placement decisions significantly impacted overall energy efficiency [40].

Guruganesh et al. discussed the asymptotic competitive ratio for a fully dynamic BIN PACKING problem by general movement costs, unit movement costs, and weight costs. They used the term online BIN PACKING to refer to the classical insertion only model without any repacking and fully dynamic BIN PACKING (with recourse) to refer to the model with both insertions and deletions. They showed that any fully-dynamic BIN PACKING algorithm with limited recourse under general movement costs has an asymptotic competitive ratio at least any online BIN PACKING algorithm. [1] Devanur et al. presented a single algorithm that knows the entire request sequence ahead of time for every possible underlying distribution. They introduced the adversarial stochastic input model for items in bin packing. They presented algorithms to approximately solve (within a factor of 1+ɛ) the mixed packing-covering problem. They discuss the implications of their results to several special cases, including online combinatorial auctions, network routing, and the Adwords problem [41].

Fatima et al. presented a method for VM-placement in a cloud environment by bin packing. Their objective of VM-placement is to increase the utilization rate of physical machines (PMs). VM-placement is applied to save energy and cost. They proposed an enhanced particle swarm optimization algorithm with variable-sized bin packing (PSOLBP) for solving the VM-placement problem. Furthermore, the best-fit approach is also applied to the variable-sized bin packing problem (VSBPP). Their algorithm efficiently reduced the number of running PMs. [42, 43].

Kumaraswamy et al. proposed an algorithm based on QoS. The Cloud data centers have considerable challenges to maintain QoS and keep the Cloud performance high. Bin packing based algorithms are the most applied to achieve virtual machine placement (VMP). They discussed comparisons of the bin packing based VMP methods for the Cloud computing environment. Then they illustrated bin packing based algorithms perform resource allocation effectively. [44].

Masdari et al. investigated numerous VM placement schemes in the cloud computing environment. They present various factors’ effects in improving VM placement in the data centers.

Furthermore, they classified the VM placement schemes based on the placement algorithm’s type and evaluated their capabilities and goals [45].

Song et al. presented a method that uses virtualization technology to allocate resources dynamically based on application demands and maintain green computing by minimizing the number of actively used servers. They discussed the relaxed online bin packing problem and improved a practical, efficient algorithm that effectively performs a real system. They regulate the resources available to each VM, both within physical hosts. Experiment results demonstrate that their method achieved good performance compared to the current work [46].

These experimental methods improved results with knowing items approximated information. They have been presented practical methods with the classification of items and the avoidance of bin overflows. Experimental methods didn’t present an exact solution for all states. Proper repacking of bins has been a significant challenge in previous algorithms for fully dynamic bin packing. Proper repacking can reduce the free spaces in bins. Hence, the number of allocated bins and future swapping (migration) is reduced. This paper has proposed an FGA algorithm that can pack more items in bins through swapping items. The futuristic approach chooses items intelligently for swapping by special conditions. The proposed method prevents nearly improper swapping and repacking. Thus energy consumption can be reduced by decreasing the number of bins (hosts) and swapping rate of items (virtual machines).

3 Futuristic greedy algorithm based on location recognition (FGA)

There are several features for each greedy algorithm in solving approximation methods [47]:

The greedy approach performs a step by step selection without looking forward. Greedy choices can be heuristic or meta-heuristic or hyper-heuristic. Greedy methods may lead to the following:

Depending on the problem, greedy solutions can provide an optimal solution or approximate solution.

With a greedy local selection, many selections may not be considered in future choices, and inappropriate solutions may be accidentally presented.

FGA is a problem-solving approach that identifies inappropriate local choices in the greedy method and modifies these choices to improve the solution. FG approach is investigated for decreasing the execution time of reducers in paper with reference [48] recently.

In fully dynamic bin packing problem, if it is possible to modify the appropriate greedy selections at each stage by the futuristic greedy algorithm and migration, then better solutions will be obtained. It is necessary to know the conditions where local greedy approaches lead to inappropriate selections (definition 2, definition3). Indeed, this is an advantage of the futuristic approach, which prevents inappropriate greedy choices. With a futuristic greedy approach, according to allocating bins to items, it is possible to create more empty spaces in bins by swapping items and repacking bins. In this way, future items can be more likely to be placed in existing bins and avoid using new bins for packaging as much as possible.

The futuristic greedy method can improve local selections by repacking bins based on location recognition. Location recognition is determined by the current allocation of bins. The example 1 explains one of the most essential factors in inappropriate local selections. These factors create futuristic greedy conditions (definition 2, definition3).

Example 1: In Fig. 1, the following items have arrived or departed off the fully dynamic bin packing problem, respectively. Using the SRH algorithm, these items are packed in the bins and allocated to three bins. The capacity of each bin is 100. Online items are 34, 28, 37, 29, 19, 28, 37, 20, 47, 35 (red items not arrive, but they have arrived previously, and they depart). Figure 1 displays the steps of the SRH algorithm.

Fig. 1

Steps of SRH in fully dynamic bin packing.

In this example, items are packed into three bins via the SRH algorithm. Repacking after the SRH algorithm can reduce the required bins from three bins to two bins. Figure 2 reveals the combination of repacking and the SRH algorithm. A futuristic greedy approach based on location recognition can pack items into two bins. The allocated bins create greater free space. This space is a futuristic product as more items can be packed into greater free space in the future. The futuristic greedy selections can be altered in the following way: swapping occurs between (bin2 and item 47) and (bin1 and item 19). The futuristic greedy approach based on location recognition is a repacking for creating greater free space.

Fig. 2

Improper allocation with properly greedy selection.

3.1 Definitions and notations

The futuristic greedy conditions based on location recognition indicate the conditions where the items are repacked and are migrated. Futuristic greedy conditions increase the continuous free space. Subsequently, the probability of packing for future items increases. The augmentation of free spaces is a futuristic approach in the allocation process.

Notations

Suppose, bin_i and bin_j are two bins. Using an algorithm, bin_i is filled with x_ki items, and bin_j is filled with x_mj items. The free spaces of the bin_i and bin_j are called e_i and e_j respectively. Table 2 presents the notations of this research.

Table 2
Notations

Notation Description

bin _i i-th bin

x _ki k-th item weight of the i-th bin x_ki is an arbitrary item packed into the i-th bin

x _mj m-th item weight of the j-th bin x_mj is an arbitrary item packed into the j-th bin

C Capacity of each bin

∑_kx_ki Total weight of the items in the i-th bin

∑_mx_mj Total weight of the items in the j-th bin

S Number of allocated bins in the approximate solution

OPT Number of allocated bins in the optimal solution

$\bar{e}$ Number of bins (except the independent bin) covered with free spaces $= \frac{\sum_{i = 1}^{s - 1} e_{i}}{C}$

$e_{i}^{OPT}$ Free spaces value of bin_i in the optimal algorithm

e _i Free spaces value of bin_i in the approximated algorithm

e _s Free space of the independent bin

t Real value which is at least 3 and $e_{i} < \frac{C}{t}$

Notation	Description
bin _i	i-th bin
x _ki	k-th item weight of the i-th bin x_ki is an arbitrary item packed into the i-th bin
x _mj	m-th item weight of the j-th bin x_mj is an arbitrary item packed into the j-th bin
C	Capacity of each bin
∑_kx_ki	Total weight of the items in the i-th bin
∑_mx_mj	Total weight of the items in the j-th bin
S	Number of allocated bins in the approximate solution
OPT	Number of allocated bins in the optimal solution
$\bar{e}$	Number of bins (except the independent bin) covered with free spaces $= \frac{\sum_{i = 1}^{s - 1} e_{i}}{C}$
$e_{i}^{OPT}$	Free spaces value of bin_i in the optimal algorithm
e _i	Free spaces value of bin_i in the approximated algorithm
e _s	Free space of the independent bin
t	Real value which is at least 3 and $e_{i} < \frac{C}{t}$

Definition 1: reference model

A reference model is a bin packing model for two bins and several items. A swap of the reference model items may create greater free space in the two bins, which may be allocated to more future items in the two bins. Enlargement of free spaces in the reference model occurs through greedy futuristic conditions based on location recognition. Figure 3 indicates the reference model.

Fig. 3

Reference model.

Definition 2: Futuristic greedy conditions based on location recognition

If futuristic greedy conditions are determined based on location recognition, it might be created greater free space. Futuristic greedy conditions define a proper swap between items for creating greater free space. We suppose that the weights of a set of x_ki and x_mj are defined by ∑_kx_kiand∑_mx_mj respectively. Also, Max{ e_i, e_j } is defined by the maximum value within e_i, e_j. Hence, the following inequalities (3) are known futuristic greedy conditions based on location recognition. $\begin{matrix} \exists i, j, k, mif \\ (\sum_{k} x_{ki} > \sum_{m} x_{mj} and \sum_{k} x_{ki} - \sum_{m} x_{mj} < e_{j}) \\ then \\ Max {e_{i}, e_{j}} < e_{i} + (\sum_{k} x_{ki} - \sum_{m} x_{mj}) \end{matrix}$ (3)

Definition 3: Special futuristic conditions (SFC)

A special case of futuristic greedy based on location recognition is called SFC. It uses x_kiandx_mj instead of ∑_kx_ki and ∑_mx_mj respectively. In the special futuristic approach, all items are checked individually instead of summation. Special futuristic conditions are formally applied in the reference model as Rule 1 in inequalities (4):

Rule 1. Special Futuristic Conditions $\begin{matrix} \exists i, j, k, mif ((x_{ki} > x_{mj}) and (x_{ki} - x_{mj}) < e_{j})) then \\ Max {e_{i}, e_{j}} < e_{i} + (x_{ki} - x_{mj}) \end{matrix}$ (4)

Definition 4: Swapping

In the reference model, if special futuristic conditions are satisfied, then the swapping between two items x_ki and x_mj can occur in bin_i and bin_j. This operation is called swapping. This operation is represented by swapping (x_ki, x_mj).

Lemma 1: The special futuristic condition of the reference model provides the swapping between items in order to create more free space in one bin.

Proof: If special futuristic conditions are satisfied for two bins of the reference model, then x_ki and x_mj swaps. Then, new free spaces e_i and e_j are updated in bin_i and bin_j respectively. (Equalities (5), (6)) $e_{i_{new}} = e_{i} + (x_{ki} - x_{mj})$ (5) $e_{j_{new}} = e_{j} + (x_{ki} - x_{mj})$ (6)

Hence, the following inequality is resulted: $Max {e_{i}, e_{j}} < e_{i_{n} ew}$

The value of e_i is greater than the previous values of e_i and e_j and creates more free space. Thus, more free space is created in bin_i, which can further provide more space for packing more items. Figure 4 demonstrates the allocation after the swapping of items.

Fig. 4

Allocation after the swapping of items in FGA.

Definition 5: Reallocation conditions (RC)

In several bin allocation cases, a packed item in one bin can be repacked in the free space of other bins. It happens when the reallocation conditions are satisfied. These conditions for Fig. 4 are defined in Rule 2 inequalities (7):

Rule 2. Reallocation conditions $\begin{matrix} \exists i, j, k, mif ((x_{ki} > x_{mj}) and (e_{j} > x_{ki})) \\ thenMax {e_{i}, e_{j}} < e_{i} + x_{ki} \end{matrix}$ (7)

If the conditions in Rule 2 are satisfied for the reference model, then item x_ki can migrate to bin_j. Figure 5 reveals the status of bins after the migration of x_ki. These operations are nominated as migration (x_ki).

Fig. 5

Status of bins after swapping with reallocation Conditions.

Definition 6: Independent bin

When the last item is repacked, one bin (generally the previously allocated bin) accommodates a large free space. For this bin, SFC and RC conditions are not checked. Thus, this bin is called the independent bin.

Definition 7: Open bin

A bin is nominated as an open bin until items can be repacked in it. If the bin’s free space value equals zero, then this bin is set closed as items cannot be repacked in it. Hence, an open bin is defined based on the free space of the bin.

3.2 Proposed algorithm

Main idea of the proposed method is based on preventing inappropriate local selections in item packing. Hence, the proposed method avoids bins overflowing, and it revises improper choices by repacking. It determines special futuristic greedy for items swapping. Also, it determines reallocation conditions for bins releasing. The main advantage of the proposed method is that due to effective choices, it can create conditions that reduce the overflow of existing bins. Intelligent Swapping of items reduces the migration rate between bins. Departed items of the system can create improper empty spaces between bins. Dynamic allocation can detect empty spaces in bins. Then with the Swapping of items, maybe release a few bins dynamically. Using minimal bins in dynamic allocation can be useful in allocating cloud resources. Because using this method in the cloud environment can migrate virtual machines with minimal hosts. Thereby decreasing the number of hosts reduce energy consumption.

The proposed algorithm consists of two phases represented by Algorithm 2 (proposed method). It is showed in Fig. 6.

Fig. 6

Structure of the proposed algorithm.

Algorithm 2. the Proposed algorithm
Phase 1
While (two bins are filled) do // O(c)
arrived Item or departed item
Pack or remove item to two bins by SRH algorithm (in
section 1.3) // O(n)
Sort-Release Bins in ascending order based on the size of
free space //O(logn)
Phase 2
While (Item arrive or depart online) do // O(1) online control
If (item departs)
Remove(item from bin) // O(n)
If status of bin that item remove = Close bin
status of bin = Open bin // O(c)
while Check_SFC() do // O ( n ²)
% State of Special Futuristic Conditions
Swap (x_ki, x_mj) to bin_jitiinbi>, bin_iitiinbi> respectively //O (c)
while Check_RC() do
% state of Reallocation Conditions O ( n ²)
Migration (x_ki) to bin_jitiinbi> // O(c)
If (item arrives)
If (item can pack in open bins)
Pack item to open bins using BEST FIT algorithm
else
!Check_SFC() and !Check_RC()
% No SFC & NO RC
Pack item to new bin //O(c)
else
while Check_SFC() do
% State of Special Futuristic ConditionsO (n²)
swap (x_ki, x_mj) to bin_jitiinbi>, bin_iitiirespectivel // O(c)
while Check_RC() do
% state of reallocation Conditions //O (n²)
Migration (x_ki) to bin_jitiinbi> // O(c)
If (item can pack in open bins)
pack item to open bins using BEST FIT algorithm
else
Pack item to new bin // O(c)
Sort-Release Bins order based on the free space //O(nlogn)

In the first phase, items arrive and frequently depart until two bins are allocated. If items arrive, then items are packed into two bins by SRH algorithm (SRH is proposed in section 1.3), then existing bins are sorted based on their space. If an item departs from the system, then existing bins sort based on their space. As long as only two bins exist, these steps continue until a third bin is required. At this moment, phase 1 is completed.

In the second phase, if an item departs the bin, SFC conditions and RC conditions are checked; it is possible that swapping or migration operations are initiating. Meanwhile, if the bin’s status containing the item is closed, then the status of the bin must set open. After that, existing bins sort based on their empty space.

If an item arrives and can be packed in open bins in the second phase 2, it is packed into open bins by the best-fit algorithm (Algorithm 6). Otherwise, SFC conditions and RC conditions are checked; it is possible that swapping or migration operations are initiating. The arrived item may be packed to open bins by the best-fit algorithm, so that item weight is less than the empty space of one bin. Otherwise, the item places in a new bin. Finally, existing bins sort based on their empty space.

Algorithm 3 and Algorithm 4 investigate reallocation (RC) and SFC conditions respectively. At the end of each part, sort-release function as observed in Algorithm 5. This function sorts bins based on their free space in an ascending order. Also, it may release a bin or it may close several open bins. This function can close bins based on the based on the maximum amount of free space ɛ of the bin. In optimal status, ɛ is considered to zero.

Algorithm 3. check for Reallocation Conditions //O (n²)
Check_RC()
Status = False
For i = 1 to n do
For j = i+1 to n do
∃ k, mif ((x_ki > x_mj) and (e_jitiinbi> > x_ki)) then
ifMax { e_iitiinbi>, e_jitiinbi> } < e_iitiinbi> + x_kithen
Status = True
Return status

Algorithm 4. check for Special Futuristic Conditions //O (n²)
Check_SFC()
Status = False
For i = 1 to n do
For j = i+1 to n do
∃ k, mif ((x_ki > x_mj) and (x_ki - x_mj < e_jitiinbi>)) then
if Max { e_iitiinbi>, e_jitiinbi> } < e_iitiinbi> + (x_ki - x_mj) then
Status = True
Return status

Algorithm 5. Sort-Release bins in ascending order based on the
free space //O(nlogn)
Sort-Release
For all bins
If free space of bin = = C % C is capacity of bin
Release Bin
If free space of bin = = 0 % C is capacity of bin
Set status of bin = Close bin
Sort Bins in ascending order based on the free space

Algorithm 6. pack item to open bin with BEST FIT //O (n²)
BEST FIT
% number_bin = number of bin with minmum of remaining free
space
For i = 1 to no % no is number of bins
If item < free space of bin_iitiinbi>
E(i) = free space - item
Else
E(i) = inf % inf is infinity
[number_bin] = Find (minmum (E(i),i))
Pack item to bin_{number_bin}

Bins and items are considered in the order of hosts and virtual machines in the cloud environment. In this model, physical factors are ignored in the real environment. Because the proposed algorithm is examined without the physical environment factors theoretically, and it is performed the same in allocating resources in all environments.

Decreasing the number of hosts can reduce energy consumption in the cloud environment. Because each host has a constant energy consumption when used, and its variable energy consumption depends on the processing of the virtual machine and the migration rate of the virtual machine and etc.

Decreasing the migration rate of virtual machines can reduce the cost of consumption in the cloud environment. Therefore, an assigned virtual machine is an item that departs or arrives into the system. Determining the futuristic special conditions in hosts can determine the migration of virtual machines. Also, repackaging offers a dynamic allocation of hosts to virtual machines. The proposed method can be investigated in several different cloud environments. Results of studying can be assessed in suitable cloud environments.

Red expressions in algorithms show the complexity of each step of the proposed algorithm. Hence, the complexity of the proposed algorithm (Algorithm 2) is O (n²) (n is the number of bins).

Example 2: Through the FGA algorithm, the following items are packed in bins. Red items (31, 37, 36) depart. The capacity of each bin is 100.

Items: 36, 37, 15, 31, 5, 31, 42, 28, 31, 6, 16, 37, 28, 14, 36, 23, C = 100. In step one, the items are packed by the SRH algorithm until two bins are filled. Then, item 42 must be packed in the third bin. Thus, the items in step 1 are {36, 37, 15, 31, 5, 31}, with the results displayed in Fig. 7.

Fig. 7

Item packing for two elementary bins by special refined harmonic.

In the second phase, the futuristic conditions are checked between the two bins. In Fig. 8, the second and first bins satisfy SFC. Between the first and second bins, there is a proper swap, which occurs between the item weighing 37 in the first bin and the item weighing 31 in the second bin. Next, another swap occurs between the item weighing 36 in the first bin and the item weighing 31 in the second bin.

Fig. 8

Item packing for two primitive bins by special refined harmonic.

Then, in Fig. 9, reallocation conditions are satisfied. The item with the weight 37 from bin2 migrates to bin1. On the other hand, in Fig. 10, the SFC condition and reallocation conditions are not satisfied. Hence, the next items, 42, 28, would arrive and be considered further.

Fig. 9

Reallocation condition.

Fig. 10

Reallocation conditions and SFC conditions not being satisfied.

In Fig. 11, the item with weight 31 departs. Then, SFC conditions and reallocation conditions are considered, as observed in Fig. 12. Figure 13 reveals the next steps of the proposed algorithm. Finally, in this example bin₃ is an independent bin.

Fig. 11

Item 31 departs.

Fig. 12

SFC and reallocation conditions.

Fig. 13

Next steps of proposed algorithm in example 2.

4 Analysis of the proposed algorithm

As a sketch of analysis and calculation of the proposed algorithm’s asymptotic approximation ratio, the inequalities (8) and (9) must be proved. Then, inequality (10) can be derived from (8) and (9). $S < OPT + \bar{e} + 1$ (8) $\forall t ⩾ 3 e_{i} < \frac{C}{t} t ɛ R$ (9) $\forall k s ⩽ (\frac{t}{t - 1}) OPT + 1, t ⩾ 3$ (10)

Where, $\bar{e}$ is the number of bins (except the independent bin) covered with free spaces, and t is the real value, which is at least 3 where $e_{i} < \frac{C}{t}$ (they are presented in Table 2).

Lemma 2: At the end of the FGA algorithm, inequality (8) establishes: $S < OPT + \bar{e} + 1$ (8)

Proof: Suppose the numbers of bins for approximation and optimal solution are S and OPT, respectively. The summation of the packed items in the approximation and the optimal algorithms is $C * S - \sum_{i = 1}^{s} e_{i}$ and $C * OPT - \sum_{i = 1}^{OPT} e_{i}^{OPT}$ respectively. It is clear that summation of packed items in these two methods is equal. Thus, the following equation results: $\begin{matrix} S * C - \sum_{i = 1}^{s} e_{i} = OPT * C - \sum_{i = 1}^{OPT} e_{i}^{OPT} \\ \Rightarrow S - \frac{\sum_{i = 1}^{s} e_{i}}{C} = OPT - \frac{\sum_{i = 1}^{OPT} e_{i}^{OPT}}{C} \\ \Rightarrow S + \frac{\sum_{i = 1}^{OPT} e_{i}^{OPT}}{C} = OPT + \frac{\sum_{i = 1}^{s} e_{i}}{C} \\ = > S ⩽ OPT + \frac{\sum_{i = 1}^{s} e_{i}}{C} \end{matrix}$

Suppose that the free space of the independent bin is e_s; therefore: $S ⩽ OPT + \frac{\sum_{i = 1}^{s - 1} e_{i}}{C} + \frac{e_{s}}{C}, \frac{e_{s}}{C} < 1 \Rightarrow S < OPT + \bar{e} + 1$

Lemma 3: At the end of the FGA algorithm, inequality (9) establishes (except the independent bin): $\forall t ⩾ 3 e_{i} < \frac{C}{t} t ɛ R$ (9)

Proof: The Lemma 3 is proved in two steps. In the first step, it is proved that: $\forall i, j e_{i} < x_{mj}$

Then, in the second step is proved that: $\forall t ⩾ 3 e_{i} < \frac{C}{t}$ (10)

First step of proof:

At the end of the FGA algorithm, free spaces of bins are filled with items that lie within the range $(0 \frac{C}{2})$ . Therefore, the size of free spaces of the bins except the independent bin should be less than $\frac{C}{2}$ ; it is because if the free space of the bin is greater than $\frac{C}{2}$ , then it is filled with at least one item in the range $(0 \frac{C}{2})$ . Also, after the completion of the FGA algorithm, each pair of bins has the following properties (except for the independent bin):

The free space of bin_i cannot fill with the items of other bins such as bin_j, as all free spaces are filled through swapping and migration after the completion of SFC and RC. At the end of the proposed algorithm, special futuristic conditions are not satisfied between bins except for the independent bin. Hence, each bin’s free space size is smaller than that of all of the items that are packed in other bins. Accordingly, the free space of each bin is less than the minimum of items in other bins (except independent bin). At the end of the proposed algorithm, SFC condition and reallocation condition are not satisfied, therefore: $\forall i, j, m e_{i} < x_{mj}$ (11)

We can prove it by contradiction. Suppose that e_i > x_mj, and then it is proved that SFC conditions and reallocation conditions are satisfied. $\exists i, j, k, mif ((x_{ki} > x_{mj}) and (x_{ki} - x_{mj} < e_{j}))$ the two states are created:

State 1. If e_i > e_jthenMax { e_i, e_j } = e_i < e_i + (x_ki - x_mj) therefore SFC conditions are satisfied, which contradicts the initial hypothesis.

State 2. If e_i < e_jthenMax { e_i, e_j } = e_j < e_j + x_mj. Hence, reallocation conditions are satisfied, which contradicts with the initial hypothesis.

Second step of proof:

The following inequality is established at the end of the proposed algorithm as SFC conditions are not satisfied. $\exists i, j, k, mif ((x_{ki} > x_{mj}) and (e_{j} > x_{ki}))$ $then Max {e_{i}, e_{j}} > e_{i} + x_{ki}$

It is impossible that max{ e_i, e_j } equals e_i because: $\begin{matrix} \max {e_{i}, e_{j}} > e_{i} + (x_{ki} - x_{mj}) \Rightarrow e_{i} > e_{i} \\ + (x_{ki} - x_{mj}) \Rightarrow it is impossible \end{matrix}$

Therefore, e_i is less than e_j since we call sort_release function where the bins are sorted in ascending order based on empty space. Hence inequality (12) is considered: $e_{i} < e_{j}$ (12)

Also, the following inequalities establish by (11).

$\begin{matrix} \forall i, {je}_{i} < x_{1 j}, e_{i} < x_{2 j}, e_{i} < x_{3 j}, \dots . \\ \overset{Summation of inequalities}{\Rightarrow} t * e_{i} < \sum_{m = 1}^{t} x_{mj} \end{matrix}$ (13)

Bin_j consists of t items x_mj and free space e_j. Hence inequality (14) is considered: $\sum_{m = 1}^{t} x_{mj} + e_{j} = C$ (14)

Combination (13) and (14)

$\begin{matrix} t * e_{i} < \sum_{m = 1}^{t} x_{mj} \Rightarrow t * e_{i} + e_{j} < \sum_{m = 1}^{t} x_{mj} \\ + e_{j} \Rightarrow t * e_{i} + e_{j} < C \end{matrix}$ (15)

Combination (15) and (12) $t * e_{i} + e_{j} < C, e_{i} < e_{j} \Rightarrow {te}_{i} + e_{i} < C \Rightarrow e_{i} < \frac{C}{t + 1}$

The items lie within range $(0, \frac{C}{2})$ , and at least two items should be in each bin (except independent bin). In the worst case, e_i must be maximized by t = 2. Thus, $Max (e_{i}) < \frac{C}{3}$

In other words, $\forall t ⩾ 3 e_{i} < \frac{C}{t}$

Theorem 1: Asymptotic approximation ratio of The FGA algorithm with special futuristic conditions is $\frac{t}{t - 1} OPT$ where t is at least 3. (S is the number of bins with approximated solution and OPT is the number bins with optimal solution) $\forall tS ⩽ (\frac{t}{t - 1}) OPT + 1, t ⩾ 3$

Proof: The worst case of packing is when the items do not pack in the existing bins. Then, they are packed into new bins. According to the lemma 2, each bin_i consists of free space e_i with the items in the range $(0, \frac{c}{2})$ . According to inequality (9): $\forall t ⩾ 3 e_{i} < \frac{C}{t} t ɛ R$

Hence: $\begin{matrix} e_{i} < \frac{C}{t} \Rightarrow \sum_{i = 1}^{s - 1} e_{i} < \sum_{i = 1}^{s - 1} \frac{C}{t} \Rightarrow \frac{\sum_{i = 1}^{s - 1} e_{i}}{C} < \frac{\sum_{i = 1}^{s - 1} \frac{C}{t}}{C} \\ \Rightarrow \bar{e} < \frac{C * (s - 1)}{t * C} \Rightarrow \bar{e} < \frac{(S - 1)}{t} \end{matrix}$ Thus:

$\bar{e} < \frac{S - 1}{t}, t ⩾ 3$ Inequality (16)

According to the lemma 1, inequality (8) is replaced with inequality (16). $\begin{matrix} S < OPT + \bar{e} + 1 < OPT + \frac{(S - 1)}{t} + 1 \\ \Rightarrow S - \frac{S - 1}{t} < OPT + 1 \Rightarrow s \\ ⩽ (\frac{t}{t - 1}) OPT + 1, t ⩾ 3 \end{matrix}$

Corollary 1. Value “1” of inequality (3) represents the independent bin. Asymptotic approximation ratio $\frac{t}{t - 1}$ is suitable when the value of t increases, where t lies within range (3, n). For example, for t = 3, 3.2, 4, 4.5, 5, 6, 10, asymptotic approximation ratios are 1.5, 1.45, 1.33, 1.28, 1.25, 1.2, 1.11 respectively. Tight examples for the worst case are presented in Fig. 14.

Fig. 14

Tight examples for the worst case of FGA algorithm.

Lemma 4. The average case asymptotic approximation ratio of FGA algorithm is 1.231 for random data with uniform distribution.

Proof: The value of asymptotic approximation ratio depends on t in range (3, n) where t is real. The random data include uniform distribution with density function $\frac{1}{n}$ . Expected value of the asymptotic approximation ratio (Apr_i) with the uniform distribution is: $\begin{matrix} E ({Apr}_{i}) = \int_{3}^{n} tf (t) dt = \int_{3}^{n} (\frac{t}{t - 1}) * \frac{1}{n} dt \\ = \frac{n - 3 + ln (\frac{n - 1}{2})}{n} = \frac{n - 3 + \ln (n - 1) - ln (2)}{n} \\ ⩽ \frac{n + \ln (n - 1)}{n} ⩽ 1 + \frac{\ln (n - 1)}{n} \end{matrix}$

$\begin{matrix} Max (E ({Apr}_{i})) = Max (1 + \frac{\ln (n - 1)}{n}) = 1 \\ + \frac{\ln (3 - 1)}{3} ⩽ 1.231, n ⩾ 3 \end{matrix}$ (17)

Table 3 shows the comparisons between the asymptotic competitive ratios of the previous algorithms. The proposed method shows a better asymptotic competitive rate than the previous algorithms by a uniform distribution of items. The algorithms listed in Table 3 are used to solve the fully dynamic bin packing problem.

Table 3

Comparison of asymptotic competitive rates recent algorithms

Fully dynamic bin packing	Asymptotic competitive ratio
Balogh et al. (2017) [33]	1.57829
Feldkord et al. (2017) [35]	1.3871
Gambosi (2000) [23]	4/3
Proposed method	1.231

5 Experimental results

The allocation of resources in the cloud environment can reduce energy consumption for two reasons [6 –8]. The first reason, reducing the number of hosts (bins) can be decreased energy consumption. The second reason is that the reduction of the migration rate of virtual machines (items) can decrease energy consumption because each migration consumes some energy. The proposed method can decrease the migration rate (exchange of items) of virtual machines between hosts by intelligent choices based on a futuristic greedy approach. Matlab software and standard datasets (http://or.dei.unibo.it/library/bpplib) have been used for implementation. These datasets are presented in Table 4.

Table 4
Simulation Dataset

Dataset No of instances on

Fallkenauer 8 E.Falkenauer (1994)

hard28 28 The 28 VERY hard BPP

instances of J. Schoenfield

SCH_WAE2 100 Difficult instances

Waescher 17 Normal instances

AI 250 Difficult_Instances

Randomly_generated —- Difficult_Instances

ANI 40 Difficult_Instances

Dataset	No of instances	on
Fallkenauer	8	E.Falkenauer (1994)
hard28	28	The 28 VERY hard BPP
		instances of J. Schoenfield
SCH_WAE2	100	Difficult instances
Waescher	17	Normal instances
AI	250	Difficult_Instances
Randomly_generated	—-	Difficult_Instances
ANI	40	Difficult_Instances

Different instances in Table 5 are tested from each dataset. The proposed algorithm runs on a variable size of datasets. Finally, the experimental approximation ratio is compared with the asymptotic approximation ratio.

Table 5

Dataset instances

Dataset-instance	Size	Capacity of bin
Fallkenauer-binpack1	250	150
Fallkenauer-binpack2	250	150
Fallkenauer-binpack3	500	150
Fallkenauer-binpack4	1000	150
hard28-bpp14	136	1000
hard28-bpp832	139	1000
hard28-bpp40	144	1000
hard28-bpp419	179	1000
hard28-bpp531	175	1000
SCH_WAE2-bpp96	47	1000
SCH_WAE2-bpp97	47	1000
SCH_WAE2-bpp98	47	1000
SCH_WAE2-bpp99	49	1000
SCH_WAE2-bpp100	46	1000
Waescher_TEST0097	119	10000
Waescher_TEST0095	153	10000
Waescher_TEST0084	92	10000
Waescher_TEST0055B	239	10000
Waescher_TEST0055A	142	10000
AI- 1002_80000_DI_45	1002	80000
AI- 1002_80000_DI_46	1002	80000
AI- 1002_80000_DI_47	1002	80000
AI- 1002_80000_DI_48	1002	80000
AI- 1002_80000_DI_49	1002	80000
Randomly_generated-BPP_1000_	1000	1000
1000_0.2_0.8_5
Randomly_generated-BPP_1000_	1000	1000
1000_0.2_0.8_6
Randomly_generated-BPP_1000_	1000	1000
1000_0.2_0.8_7
Randomly_generated-BPP_1000_	1000	1000
1000_0.2_0.8_8
Randomly_generated-BPP_1000_	1000	1000
1000_0.2_0.8_9
ANI-1002_80000_NR_45	1002	80000
ANI-1002_80000_NR_46	1002	80000
ANI-1002_80000_NR_47	1002	80000
ANI-1002_80000_NR_48	1002	80000
ANI-1002_80000_NR_49	1002	80000

The experiments are based on the calculation of the free space average and the experimental approximation ratio Figs. 15 and 16. The free space average (Gap) and the experimental approximation ratio (experimental approximation ratio) are shown in Equations 18 and 19. $Gap = \frac{\sum_{i = 1}^{s} e_{i}}{S}$ (18) $Approximation ratio = \frac{S}{OPT}$ (19)

The proposed method in Figs. 17 and 18 are compared with recent algorithms in terms of migration rate and approximation rate. The proposed method reduced the migration rate due to finding special futuristic conditions by items swapping. Because investigation of SFC conditions is accomplished intellectual swapping, also, it prevents extra swapping. Also, due to the repackaging of the bins, fewer bins have been allocated in various experiments.

Fig. 15

Gaps percentage of datasets for standard algorithms.

Fig. 16

Approximation ratio of standard and common algorithms.

Fig. 17

Migration ratio percentage of datasets for the proposed algorithm.

Fig. 18

Approximation ratio of recent algorithms.

If the maximum free space of one bin is zero, this bin is defined as a closed bin. If the closed bin is defined based on the percentage of maximum free space of bin (ɛ), then the migration ratio is reduced, but the experimental approximation ratio may increase.

Figure 19 reports the relation (ɛ) with experimental approximation ratio and migration ratio. In the “SCH_WAE2” dataset, the range of items weight is (150 200) with C = 1000 (capacity of each bin). Hence, $ɛ = \frac{C}{5} = 200$ , the proposed algorithm presents a worse gap and greater experimental approximation ratio. However, $ɛ = \frac{C}{10} = 100 or ɛ = \frac{C}{20} = 50$ the proposed algorithm presents no difference. “Randomly_generated” datasets consist of C = 1000 with items ranging within (200 1000). The value of ɛ. in the datasets is 50, 100, and 200. Thus, the proposed algorithm presents similar results. When ɛ increases, it may reduce the migration rate. Also, the reduction of migration can shorten the execution time. This point must be considered for future research on a real simulation model in cloud computing.

Fig. 19

Migration ratio percentage for several values of ɛ.

When an item is departed in the proposed method, then its space in a bin is released. Repacking the bins can be reduced the empty spaces. This technique places empty spaces together, a larger space creates, and small, scattered empty spaces prevent. These operations perform by swapping items in the bins. It allows future items to be more likely to be packed in existing bins. Hence, the migration rate may reduce because the proposed algorithm tries to allocate all the items with the minimum bin to minimize the used bins’ space. Proper application of bins for packing items will reduce the number of used bins. Therefore, in different datasets, the proposed method shows a better approximation rate.

The proposed method performs intelligently so that swapped items together to create larger empty spaces in the bins. Also, dynamic allocation in the fact that items are departed may cause items containing one bin to be placed in other bins and one bin released during operation. Previous methods tried to minimize the bins’ empty spaces by classification the items and packing them in bins. Many methods attempted to pack the items in such a way as to minimize overflow in the bins. These methods had different functions due to the different distribution of items. And sometimes, they significantly increased the migration rate and the number of used bins. According to the calculations of futuristic, the proposed method packs items so that the migration rate is reduced. In addition to the number of bins are reduced. Of course, special futuristic conditions do not perform appropriately in some items.

The proposed algorithm may not improve the proper solutions in a few data sets. If combinations of items are investigated for swapping, it may find better solutions, but the algorithm’s complexity may increase. It seems that acquiring a pattern based on the dynamic programming model can prevent repetitive computations from checking all combinations. Designing this pattern can improve the FGA algorithm. In the proposed algorithm, swapping is accomplished intelligently based on SFC conditions. Hence, the migration rate depends on the number and the distribution of item weights and bins’ capacity.

The following example illustrates the situation where SFC conditions do not perform properly. In this example, there are no SFC and RC conditions. Nevertheless, the solution can be improved by items swapping (35, 37) in the first bin with items (weighing 18, 18, 16, 16) in the second bin. Hence, the solution of the fully dynamic bin packing problem is reduced from three bins to two bins, as observed in Fig. 20.

Fig. 20

Special futuristic greedy conditions no being satisfied.

6 Conclusion and future work

In this paper, the FGA algorithm was presented for solving fully dynamic bin packing. In this method, if an item arrives or departs online, SFC conditions and reallocation conditions are investigated. If these conditions are satisfied, then swapping is accomplished. Next, the items are packed in an open bin or a new bin. In this research, the swapping of one item depended on the distribution of items. It is also shown that the average case asymptotic approximation ratio of the FGA algorithm is 1.231 for the uniform distribution of items. The proposed method prevents extra swapping between items by SFC and RC conditions. Hence, proper swapping creates greater free space. Ultimately, items were packed in fewer bins through the free space created. The proposed algorithm can be analyzed by energy consumption in the real environment in future research. If this problem is considered in the cloud computing environment, the excessive swapping of items can be challenged. In the cloud computing environment, bins are regarded as physical host machines, while items are considered to be virtual machines. There is a tradeoff between the migration rate and the maximum free space of bins. This tradeoff can be studied in future research for energy consumption in the cloud computing environments.

Finally, the proposed algorithm guarantees an appropriate asymptotic approximation ratio com-pared with other greedy algorithms for fully dynamic bin packing. SFC and RC conditions are not established in some cases, but different swapping combinations may improve the solution. It can reduce the asymptotic approximation ratio, but the execution time of the proposed algorithm increases. The relationship between the execution time and asymptotic approximation ratio by combinations of swapping can be a new area for future research.

References

Guruganesh

, Topics in Approximation and Online Algorithms, Carnegie Mellon University Pittsburgh, PA, 2018.

Gambosi

, Postiglione

and Talamo

, Newalgorithms for on-line bin packing, in: Algorithms Complexity, Proc First Ital Conf 1990 44–59.

Cormen

T.H.

, Leiserson

C.E.

, Rivest

R.L.

and Stein

, Introduction to algorithms second edition, Knuth-Morris-Pratt Algorithm, Year. (2001).

Christensen

H.I.

, Khan

, Pokutta

and Tetali

, Approximation and online algorithms for multidimensional bin packing: A survey, Comput Sci Rev 24 (2017), 63–79.

Chekuri

, Cheriyan

, O’Donnell

, Salavatipour

M.R.

and Williamson

, Approximation algorithms and the hardness of approximation, (2011).

Berndt

, Jansen

and Klein

K.-M.

, Fully dynamic bin packing revisited, Math. Program (2018), 1–47.

Yang

C.-T.

, Liu

J.-C.

, Huang

K.-L.

and Jiang

F.-C.

, A method for managing green power of a virtual machine cluster in cloud, Futur Gener Comput Syst 37 (2014), 26–36.

, Tang

and Cai

, On dynamic bin packing for resource allocation in the cloud, in: Proc. 26th ACM Symp. Parallelism Algorithms Archit 2014, 2–11.

Dong

, Wang

and Cheng

, Energy-performance tradeoffs in IaaS cloud with virtual machine scheduling, China Commun 12 (2015), 155–166.

10.

Baker

, Aldawsari

, Asim

, Tawfik

, Maamar

and Buyya

, Cloud-SEnergy: A bin-packing based multi-cloud service broker for energy efficient composition and execution of data-intensive applications, Sustain Comput Informatics Syst 19 (2018), 242–252.

11.

Al-Dulaimy

, Itani

, Zantout

and Zekri

, Type-aware virtual machine management for energy efficient cloud data centers, Sustain Comput Informatics Syst 19 (2018), 185–203.

12.

Zheng

, Luo

and Zhang

, NF-based algorithms for online bin packing with buffer and bounded item size, J Comb Optim 30 (2015), 360–369.

13.

Seiden

S.S.

, On the online bin packing problem, J ACM 49 (2002), 640–671.

14.

Lazarev

D.O.

and Kuzyurin

N.N.

, On Online Algorithms for Bin, Strip, and Box Packing, and Their Worst-Case and Average-Case Analysis, Program Comput Softw 45 (2019), 448–457.

15.

Boyar

, Epstein

, Favrholdt

L.M.

, Larsen

K.S.

and Levin

, Online bounded analysis, Int. Comput. Sci. Symp. Russ 2016, 131–145in.

16.

Boyar

, Kamali

, Larsen

K.S.

and López-Ortiz

, Online bin packing with advice, Algorithmica 74 (2016), 507–527.

17.

Balogh

, Békési

and Galambos

, New lower bounds for certain classes of bin packing algorithms, Theor Comput Sci 440 (2012), 1–13.

18.

Renault

M.P.

, Rosén

and van Stee

, Online algorithms with advice for bin packing and scheduling problems, Theor Comput Sci 600 (2015), 155–170.

19.

Balogh

, Békési

, Dósa

, Epstein

and Levin

, A new lower bound for classic online bin packing, Int. Work. Approx. Online Algorithms, 2019, 18–28in.

20.

Békési

, Dósa

and Epstein

, Bounds for online bin packing with cardinality constraints, Inf Comput 249 (2016), 190–204.

21.

Epstein

, A lower bound for online rectangle packing, J Comb Optim 38 (2019), 846–866.

22.

Angelopoulos

, Dürr

, Kamali

, Renault

M.P.

and Rosén

, Online bin packing with advice of small size, Theory Comput Syst 62 (2018), 2006–2034.

23.

Gambosi

, Postiglione

and Talamo

, Algorithms for the relaxed online bin-packing model, SIAM J Comput 30 (2000), 1532–1551.

24.

Epstein

and Levin

, A robust APTAS for the classical bin packing problem, Math Program 119 (2009), 33–49.

25.

Balogh

, Békési

, Galambos

and Reinelt

, Lower bound for the online bin packing problem with restricted repacking, SIAM J Comput 38 (2008), 398–410.

26.

Jansen

and Klein

K.-M.

, A robust AFPTAS for online bin packing with polynomial migration, in: Int Colloq Autom Lang Program 2013, 589–600.

27.

Balogh

, Békési

, Dósa

, Sgall

and van Stee

, The optimal absolute ratio for online bin packing, in: Proc. Twenty-Sixth Annu. ACM-SIAM Symp. Discret. Algorithms 2014, 1425–1438.

28.

Jansen

, Klein

K.-M.

, Kosche

and Ladewig

, Online strip packing with polynomial migration, ArXiv Prepr. ArXiv1706.04939. (2017).

29.

Balogh

, Békési

, Galambos

and Reinelt

, On-line bin packing with restricted repacking, J. Comb. Optim 27 (2014), 115–131.

30.

Ren

, Tang

, Li

and Cai

, Competitiveness of dynamic bin packing for online cloud server allocation, IEEE/ACM Trans Netw 25 (2016), 1324–1331.

31.

Heydrich

, van Stee

, Beating the harmonic lower bound for online bin packing, ArXiv Prepr. ArXiv1511.00876. (2015).

32.

Spencer

K.Y.

, Tsvetkov

P.V.

and Jarrell

J.J.

, A greedy memetic algorithm for a multiobjective dynamic bin packing problem for storing cooling objects, J Heuristics 25 (2019), 1–45.

33.

Balogh

, Békési

, Dósa

, Epstein

and Levin

, A new and improved algorithm for online bin packing, ArXiv Prepr. ArXiv1707.01728. (2017).

34.

Zhang

, Han

, Lan

and Ting

H.-F.

, Online bin packing problem with buffer and bounded size revisited, J Comb Optim 33 (2017), 530–542.

35.

Feldkord

, Feldotto

and Riechers

, A tight approximation for fully dynamic bin packing without bundling, ArXiv Prepr. ArXiv1711.01231. (2017).

36.

Gupta

, Guruganesh

, Kumar

and Wajc

, Fully-dynamic bin packing with limited repacking, ArXiv Prepr. ArXiv1711.02078. (2017).

37.

Albers

, Khan

and Ladewig

, Best fit bin packing with random order revisited, in: 45th Int. Symp. Math. Found. Comput. Sci. (MFCS 2020), 2020.

38.

Feldkord

, Feldotto

, Gupta

, Guruganesh

, Kumar

, Riechers

and Wajc

, Fully-dynamic bin packing with little repacking, in: 45th Int. Colloq. Autom. Lang. Program. (ICALP 2018), (2018).

39.

Epstein

and Levin

, A note on a variant of the online open end bin packing problem, Oper Res Lett (2020).

40.

Wolke

, Tsend-Ayush

, Pfeiffer

and Bichler

, More than bin packing: Dynamic resource allocation strategies in cloud data centers, Inf Syst 52 (2015), 83–95.

41.

Devanur

N.R.

, Jain

, Sivan

and Wilkens

C.A.

, Near optimal online algorithms and fast approximation algorithms for resource allocation problems, J ACM 66 (2019), 1–41.

42.

Fatima

, Javaid

, Sultana

, Hussain

, Bilal

, Shabbir

, Asim

, Akbar

and Ilahi

, Virtual machine placement via bin packing in cloud data centers, Electronics 7 (2018), 389.

43.

Fatima

, Javaid

, Sultana

, Aalsalem

M.Y.

and Shabbir

, others, An efficient virtual machine placement via bin packing in cloud data centers, in: Int Conf Adv Inf Netw Appl 2019, 977–987.

44.

Kumaraswamy

and Nair

M.K.

, Bin packing algorithms for virtual machine placement in cloud computing: a review, Int J Electr Comput Eng 9 (2019), 512.

45.

Masdari

, Nabavi

S.S.

and Ahmadi

, An overview of virtual machine placement schemes in cloud computing, J Netw Comput Appl 66 (2016), 106–127.

46.

Song

, Xiao

, Chen

and Luo

, Adaptive resource provisioning for the cloud using online bin packing, IEEE Trans Comput 63 (2013), 2647–2660.

47.

Bai

, Burke

E.K.

and Kendall

, Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation, J Oper Res Soc 59 (2008), 1387–1397.

48.

Bakhthemmat

and Izadi

, Decreasing the execution time of reducers by revising clustering based on the futuristic greedy approach, J Big Data 7 (2020), 1–21.

Solving fully dynamic bin packing problem for virtual machine allocation in the cloud environment by the futuristic greedy algorithm

Abstract

Keywords

1 Introduction

1.1 Defining the research problem

1.2 Online algorithms [6]

1.3 Asymptotic competitive ratio [6]

Table 1 Comparison of basic algorithms in online bin packing [12] Algorithm Asymptotic approximation ratio Next fit 2 Best fit 1.7 Worst fit 1.7 First fit 1.7 Harmonic 1.691 Refined Harmonic 1.639

1.6 Challenges of the research problem

2 Literature review

2.1 Online bin packing

2.2 Relaxed online bin packing

2.3 Dynamic bin packing

2.4 Fully dynamic bin packing

2.5 Cloud resource allocation by bin packing

3 Futuristic greedy algorithm based on location recognition (FGA)

References

Table 1
Comparison of basic algorithms in online bin packing [12]

Algorithm Asymptotic approximation ratio

Next fit 2

Best fit 1.7

Worst fit 1.7

First fit 1.7

Harmonic 1.691

Refined Harmonic 1.639