Metaheuristic algorithms for one-dimensional bin-packing problems: A survey of recent advances and applications

2.1 Approximate algorithms

Approximate algorithms were the first approach to solve the classical 1D BPP. There are two types of approximation algorithms: online and offline. In online algorithms, the items are considered one by one, with no knowledge of succeeding items. Hence, the placement of the current item is based solely on the size of the current item and the already packed items [15]. A compelling concept that is introduced in the context of online algorithms is that of bounded-space algorithms. Bins can either be open or closed, and items must only be packed into open bins. When a new bin is added, it is given the status of “open.” In some algorithms, the bin may be closed due to the inability to add items to the contents (as it may result in exceeding the maximum capacity). Therefore, a bin-packing algorithm is considered a k -bounded-space algorithm. This means that if there are k bins open and a single item is packed into a new bin, then one of the open bins must be closed [15].

The Next Fit (NF) heuristic packs the maximum number of items that the current bin can contain, and when there is no available space for the next item, the current bin is closed, a new bin is opened, and this bin becomes the current bin [16]. The First Fit (FF) heuristic differs from NF in that the bins are not closed. Each item is packed into the first bin that has sufficient space. If an item cannot fit into any of the available bins, a new bin is opened [16]. The Best Fit (BF) heuristic packs an item into the best, or most suitable, bin – that is, the bin with the smallest available space after including the current item into it. As in FF, if no bin can fit the current item, a new bin is opened [16].

On the other hand, offline algorithms have also been used to solve this problem. Famous examples are the NF-Decreasing, BF-Decreasing, and FF-Decreasing algorithms. This type of heuristic processes the data before packing the items into the bin. Generally, this means that the items are rearranged and sorted in increasing or decreasing order [4]; thereafter, these algorithms fill the bins just as the original NF, BF, and FF algorithms do. These offline algorithms are not guaranteed to return optimal solutions every time.

An example of an algorithm that is both online and offline is the Better-Fit heuristic algorithm (BFH) [17], which removes an existing item from a bin and replaces it with the current item if the current item better fills the bin. Moreover, if the packing of the current item results in a smaller available space than the packing of the existing item, then the latter item is removed from the bin it is in. This “replaced item” is then packed using the BFH. This continues for all items until better-fit cannot pack a replaced item. In this case, the BF heuristic is used to pack the object. This algorithm outperforms the BF heuristic in every instance. The performance of the algorithm is based on the sequence of items. If the items are arranged in decreasing order, then the results are equivalent to that of BF-Decreasing, and if the items are arranged in increasing order, the algorithm will place small items into the initial bins. Larger items cannot replace these. Therefore, the best performance is the average case in which the item weights (or sizes) are random [17].

2.2 Metaheuristic approaches

3.1 Adapting metaheuristics for the 1D BPP

Figure 1 illustrates a general overview of metaheuristic algorithms that are used to solve the 1D BPP. The algorithm begins by defining parameters, such as population size and any other values that must be specified to ensure the algorithm functions as intended. Next, the initial population is generated. This step is important, and the method chosen to do this impacts the efficiency of the algorithm greatly. Next, the solutions go through the “fit and evaluate” phase. This refers to using approximate algorithms (discussed in Section 2) to pack the items into bins. This packing is then evaluated by the objective function so that the solution is assigned a fitness value that will determine it’s position in the population. This phase additionally helps to determine the best solution in the population. This best solution is then stored in memory. The algorithm will then perform the specific local and global walks so that the population is improved by adding solutions with more favourable fitness values and generally discarding of unfavourable or weak solutions. The “fit and evaluate” phase must be repeated at this stage so that the best solution can be checked against, and if a better solution than the current best is found, then this solution replaces the best solution in memory and becomes the current best. Some algorithms may require an update to parameters, but this is not always the case; therefore, this is optional. Thereafter, the termination criterion is checked. Usually, termination criterion refers to the number of iterations (generations of population) the algorithm has gone through. However, the criterion may also be to check if the current best solution is an optimal solution. It is possible that either one or both of these conditions are checked at this point in the algorithm. If the criterion has been met, then the algorithm may end and produce the final solution. However, if the criterion has not been met, the algorithm returns to update the population using exploration and exploitation mechanisms, so that a better solution may be found, and the cycle continues.

Figure 1

A generalized metaheuristic algorithms flowchart for the 1D BPP.

3.2 Adapted metaheuristics for the 1D BPP

All equations have been taken directly from the surveyed papers, and all figures and algorithms have been adapted from these papers.

3.3 Adaptive fitness-dependent optimizer (AFDO)

In 2020, Abdul-Minaam et al. [19] adapted the FDO algorithm to solve discrete optimization problems and tested it on the BPP, and this was named AFDO. This algorithm aims to improve the solution quality for the BPP. For the adaptation, the authors suggested using a random initial population and added an update to the algorithm procedure. In this algorithm [19], an artificial bee scout represents a candidate solution to the BPP. Each solution is a vector of n dimensions where one dimension represents the index of an item, and another represents the index of the bin that the corresponding item is assigned to. Abdul-Minaam et al. [19] found this representation to aid in minimizing the number of bins used while allowing multiple items to be packed in one bin without exceeding the maximum bin capacity constraint. This can be seen in Figure 2. Figure 2(a) represents the list of items with their indexes and corresponding weights.

Figure 2

An example of solutions in the population illustrated in figure (a)–(c).

Since the initial population influences the execution time and quality of the result [19], the authors modified the FF heuristic such that the algorithm takes in a shuffled list of items and randomly assigns the items to the first available bin. This allows for the generation of diverse, feasible solutions in the initial population. Figure 2(b) and (c) represents possible solutions using the modified FF heuristic.

An additional variable to be considered in this algorithm is the weight factor, w f , that is either set to 0 (neglect the factor) or 1 (lowers the possibility of coverage and increases the level of convergence). This weight controls the stability of the search and dramatically influences the movement of the bees towards the next position. Therefore, it is a parameter that requires testing. The fitness weight is directly impacted by the weight factor, as shown in equation (1), where f ( X i , t ∗ ) represents the global best solution’s fitness value and f ( X i , t ) represents the current solution’s fitness value.

The new position of a scout bee relies on the movement rate, pace, and direction. Only a positive direction is considered in the AFDO algorithm. The pace is computed by considering the current solution( X i , t ), a random number, r , generated with uniform distribution (rate), and the fitness weight (the last two are critical parameters that improve the exploration of the search space), as can be shown in equation (2):

The cases in this equation represent the influences on the movement direction. In the first case, a random sequence of raw vectors is generated from the current solution, based on the number of bins and items in the specific problem instance. As can be shown in Figure 3, the final solution of the first case is raw vectors, of the form ⟨ item , old bin , new bin ⟩ . The random number, r , is set to 0.2 and represents the probability that a task (assignment of an item to a bin) is selected for an update in the aforementioned vector. If a task is selected, a new bin is randomly chosen for the item to be assigned to. This modification to the FDO algorithm provides the possibility of obtaining multiple solutions through the use of randomization. The number of items, I , is 10.

Figure 3

An example of using X i , t ⊗ r .

Therefore, 0.2 × 10 = 2 , so two raw vectors are produced.

In the second case, the result of the ⊖ operator is computed by taking the difference between the current solution and the global best solution thus far. This is given in terms of raw vectors, as shown in Figure 4. The form of the vectors is the same as mentioned previously. If an item is assigned to the same bin in both solutions, then no change is made. If an item is in two different bins in the solutions, then the raw vector is added to the set. The ⊗ operator represents the chance of f w choosing each generated raw vector. Since f w = 0.3 , three of the raw vectors are randomly chosen in the final output.

Figure 4

An example of using ( X i , t ⊖ X i , t ∗ ) ⊗ f w .

After that, the solution’s pace is calculated as in equation (3), and the new solution is introduced, as shown in Figure 5.

Figure 5

An example of updating a solution with pace.

It is worth noting that the reassignment of an item to a bin will only occur if the suggested reassignment does not cause the bin to overflow (in other words, exceed capacity). This is the reason that the first and third raw vectors in the pace in Figure 5 do not affect the resulting solution.

The algorithm continues until a predefined number of iterations is reached or the most optimal solution is found.

The pseudocode for this algorithm can be seen in Algorithm 1.

3.4 Adaptive cuckoo search (ACS) algorithm

The CS algorithm follows three cardinal rules: First, each cuckoo must lay one egg at a time and randomly chose a nest to dump this egg in. Second, the nests that contain eggs of the highest quality will proceed to the next generation. Third, there is a fixed number of available hosts, and the host bird discovers the cuckoo egg with a probability, p a , between 0 and 1 [34]. Additionally, this probability governs the balance between the local and global explorative walks.

In 2016, Zendaoui and Layeb [25] adapted the cuckoo search algorithm to solve the 1D BPP problem (ACS). Since the original CS algorithm was designed to solve continuous optimization problems, it could not directly be applied to solve the discrete BPP. Therefore, the authors proposed utilizing a method that linked the continuous output of the algorithm to integer representations that correspond to the index of the items in a given list. The ROV method was employed for this reason – it guarantees the feasibility of new solutions and avoids creating any additional overhead. This can be shown in Figure 6.

Figure 6

An example of employing ROV on a continuous solution.

For the representation of solutions in ACS [25], the authors assume that only one egg is laid in one nest, and each nest contains a single egg. The egg in this nest is a candidate solution represented by an item permutation, determined by the ROV. The FF method was used to assign the items to the bins and evaluate the fitness of a solution. Two essential movements are used to generate new solutions in the ACS. Firstly, a local random move which can be seen in equation (4). This move is used for exploitation and produces a new solution by utilizing two randomly selected solutions ( x j t and x k t ), a Heaviside function, a random number, ε , drawn from uniform distribution, and s which represents the step size. An example is provided in Figure 7.

Figure 7

An example of employing the local walk on a current solution.

Second, a global random move via Lévy Flights is used for exploration. This is shown in equations (5) and (6). A scaling factor, α , related to the scale of the problem to be solved must be set. Once the result of the Lévy Flight is calculated, it is added to the continuous version of the item permutation, and the solution is ranked once again with ROV, and then evaluated by the objective function. An example is provided in Figure 8.

where

Figure 8

An example of employing the global walk on a current solution.

A fraction, equal to p a (the switching parameter that is predefined), of nests with unacceptable fitness values are abandoned. In other words, these solutions are replaced with new solutions generated using the local walk movement. The algorithm tracks the best solution and only replaces this position if a solution with a lower fitness value is found (since the aim is minimization).

This algorithm continues until the number of iterations has reached a predefined number or if an optimal solution is found.

The pseudocode for this algorithm can be seen in Algorithm 2.

3.5 ILWOA

Although the convergence rate and performance of the original WOA [26] were good and obtained a high-quality solution in a negligible time when applied to a continuous search space, Abdel-Basset et al. [28] observed that WOA also performed well on combinatorial problems. This observation motivated the attempt to adapt this algorithm to solve the BPP. Therefore, in 2018, the ILWOA was developed. Three enhancements were made in this algorithm. The deployment of Lévy flights for whale movements improved the exploration capabilities of WOA, the original algorithm was embedded with a mutation phase in order to enhance convergence speed, and a logistic chaotic map was utilized to swap between exploitation and exploration phases efficiently.

Since it was necessary to discretize the search space, the authors used the LOV technique. As shown in Figure 9, this technique first ranks the descending order of continuous values, X i = [ x i , 1 , x i , 2 , … , x i , n ] , where 1 to n represents the dimensions of the solution. This results in a sequence, φ i = [ φ i , 1 , φ i , 2 , … , φ i , n ] . To decode the solution, the formula used is j i , φ i , k = k , where k represents the corresponding dimension [36].

Figure 9

An example of LOV.

The BF heuristic was employed for packing bins with the assigned items. The representation used in this study was simply a list of items. The Lévy distribution has an infinite mean and infinite variance. This causes a longer movement from the solution’s current position to the new position, which is much more efficient for the exploration phase.

For improved diversification of the given search space, the WOA [26] combines a couple of exploration search mechanisms. This is carried through and slightly modified in the ILWOA. The probability of these search mechanisms being employed on a candidate solution depends on a switching parameter.

Chaotic maps can be described as: “evolutionary functions that produce a deterministic bounded sequence of random numbers depending on initial condition” [28]. The authors decided to use logistic chaotic maps to determine the switching parameter value due to the random-like parameter adaptation [28]; this value is known as p . The value of a coefficient vector from the original WOA, C → , is replaced by a random step that is drawn from Lévy distribution (equation (6)). A random variable, r , and p dictate how the solutions are updated. A → is calculated as in equation (7). This coefficient vector includes a → which represents the shrinking feature of the spiral and decreases from 2 to 0, and r → which represents a random number between 0 and 1.

The use of two exploration mechanisms introduces improved diversification of the search space. Therefore, the value of A → influences whether the best solution or a randomly selected solution will affect the positions of solutions in the search space. This is explained below.

If r < p and A → < 1 , then the update is calculated using equation (8) and the solution is generated using equation (9). In these equations, the current best solution and the current solution are represented by x ∗ → ( t ) and x → ( t ) , respectively.

However, if r < p and A → ≥ 1 , then the update is calculated by equation (10), where x r → ( t ) is a random solution chosen from the current population, and the updated solution is generated by equation (11).

If r ≥ p , then the update is calculated by equation (12) and the position is updated spirally by equation (13). These equations simulate the whales’ movements around the prey, specifically, the best solution found thus far. In equation (13), b is a pre-specified constant that defines the shape of the spiral and l is a randomly selected number in the range [ − 1 , 1 ] .

The additional mutation phase occurs before and after each iteration. In this phase, the current best number of bins is tested for optimality. If the test is successful, the search stops. However, if the test fails, the solution is randomly modified by three operators, namely, swap, displacement, and reversion. The swap operator randomly chooses and swaps two indexes in the solution. The displacement operator randomly chooses a subset of items and inserts it into another place in the solution. Finally, the reversion operator randomly selects a subset of the solution and reverses the order of the items within that subset. These mechanisms further improve the exploration capabilities of the algorithm. Figure 10 illustrates these operators. This occurs until the maximum number of iterations has been reached.

Figure 10

Illustration of mutation operators.

The pseudocode for this algorithm can be seen in Algorithm 3.

3.6 Modified squirrel search algorithm

In 2019, El-Ashmawi and Abd Elminaam [32] modified the SSA algorithm in order to apply it to the BPP. This version of the algorithm generates random but feasible initial solutions. Additionally, various operating strategies are employed to update the locations of the squirrels. This aids in generating new populations during the exploration phase of the algorithm. The feasible initialization step ensures that the initial population’s randomness explores the solution space in an efficient manner. This was accomplished by improving the BF heuristic – randomly assigning items from the given list of items to the BF bin (such that total waste is minimized).

The evaluation of the population depends on the values of the fitness function, as is with most metaheuristics. The population must be sorted according to the ascending order of fitness value. The best squirrel (the one with the lowest fitness value) is assigned to the hickory tree. Being on this tree indicates that this particular squirrel is at the optimal food source. In other words, it is a current best solution. The next three squirrels with relatively low fitness values are assigned to the acorn tree. This implies that those squirrels are at the normal food source. In other words, these solutions are near-current-best. Finally, the rest of the squirrels are assigned to the normal tree. This means that these squirrels have no food source – implying that these solutions are quite far from the current best [32].

Individual solutions are updated according to the tree that they are assigned to. If a solution is on an acorn tree, it moves towards the hickory tree, and if it is on a normal tree, it can be moved towards either the acorn or the hickory tree. The probabilities of these updates are controlled by a random number ( r 1 , r 2 , r 3 ) drawn from a uniform distribution, between 0 and 1, and a constant, P d p . This constant is known as the “probability of a predator” and it is set beforehand. If the random number is not greater than the specified constant, the squirrel’s position is randomly updated – this procedure achieves good exploration of the search space. These updates are shown in equations (14), (15), and (16). The α , β , and γ values are random numbers between 0 and 1. These values denote the gliding distance of each squirrel.

The ⊖ operator calculates the difference between the two solutions and results in a set of swap operators – difference means to look at each item–bin entry in the solutions and, if the two solutions have the same item in the same bin, no swap operator is created, but if the two solutions have the same item in different bins, a swap operator of the form ⟨ item number , bin number ⟩ is added to the set. An example of this can be seen in Figure 4.

The ⊗ operator computes the probability that the swap operators in the set are selected and applied in the update (the probability is given by α , β , and γ ). Based on the result (a number) of this operation, random solutions are selected from the set. This can also be seen in Figure 4; however, the example uses f w in place of the random values in this algorithm.

The ⊕ operator updates the solution. In other words, it changes the location of the squirrel. This is done by replacing the item–bin pairs in the chosen solution with the selected swap operators. An example of this is shown in Figure 5; however, instead of a “set of swap operators,” “pace” is used. These functions are essentially the same.

If the random number ( r 1 , r 2 , r 3 ) is less than P d p , this indicates that a squirrel was not able to reach a source of food, but survives regardless and moves to a location that is randomly generated. This is done by generating swap operators randomly and applying the ⊕ operator to the solution. This is shown in equation (17). O i represents the swap operators, and 1 ≤ i ≤ m where m is the number of swap operators generated. These random walks introduce improved exploration in the space.

The stopping criterion is based on the number of iterations reached compared to a pre-specified maximum number or until the optimal value has been found.

The pseudocode for this algorithm can be seen in Algorithm 4.

3.7 Grouping genetic algorithm with controlled gene transmission (GGA-CGT)

In 2015, Quiroz et al. [35] published the GGA-CGT to solve the 1D BPP. The authors propose transmitting the best genes in a chromosome while maintaining the balance between diversity and selective pressure in the current population.

The algorithm consists of the following features: a novel technique for generating a high-quality initial population, grouping operators that aid in exploiting the search space of the problem, a rearrangement operator that aids in exploring the search space, and the balance of the evolution is ensured by the use of a novel reproduction technique that is capable of preventing premature convergence and governing the exploration phase.

The initial population is generated with a modified FF heuristic. Until a predefined number of iterations is reached or the optimal solution is found, the individuals in the population are recombined and mutated in a couple of phases. First, some individuals are selected with “controlled selection,” and the gene-level crossover and FF decreasing heuristic are employed on the selected individuals. Afterwards, “controlled replacement” is utilized to introduce the offspring. The second phase considers a predefined “lifespan” of individuals – according to this lifespan, elite individuals with superior fitness values are cloned, and several individuals are chosen to apply genetic alterations to. These alterations are accomplished with the use of “adaptive mutation” and “RP” (Rearrangement of Pairs). As in the first phase, controlled replacement is applied to individuals in the second phase, before they are added to the new population. Algorithm 5 shows the pseudocode for this algorithm.

GGA-CGT uses a group-based encoding scheme – so, there could be various lengths of chromosomes based on the number of bins used in the specific solution. Therefore, every gene in a chromosome is a “group” of items. Each group is packed into a single bin.

The authors introduced a rather interesting method of generating an initial population from a set N of n items by first finding a subset, N ˜ , of n ˜ items that have weights greater than half of the fixed bin capacity. This subset represents items that cannot be packed into a bin with items of the same subset, as this would cause a bin to overflow. The items of N ˜ are packed first into different bins, and then the remaining items of N (that are not part of N ˜ ) are randomly packed into the bins using the FF heuristic.

The grouping crossover operator called the gene-level crossover can be described as follows: A novel crossover for group-based representation was introduced, whereby the two selected parent solutions are compared on a gene-level. Two children are produced, as both of the selected solutions are given the opportunity to be the “first father.” First, the operator looks at the bins in each solution according to the descending order of how full each bin is. This is done so that the offspring have a better chance of inheriting the best bins in the parent solutions. To create the offspring, for every pair of bins, the bin that is more filled is inherited first. The bins are compared in parallel – so, the first bin of the first father and the first bin of the second father are considered a pair. After that, the other bin in the pair is inherited. This continues until all the bins in both parent solutions have been added. In the event of a pair of bins being equally filled (have the same amount of available space), the first father’s bin is inherited first. It can be observed that this method would result in a duplication of items since every bin from both solutions is added to the child solution. Therefore, if a bin contains an item that already exists in the solution (i.e., the item can be found in a previous bin), then the bin containing the duplicate item is eliminated from the child solution. This elimination may cause the child solution to be invalid since it would not contain all the items from the problem instance. The method resolves this issue by determining the missing items and placing these items into the existing bins by using the FF decreasing heuristic. This can be seen in Figure 11.

Figure 11

An example of the gene-level crossover operator. (a) An example of the list of items in a BPP instance. (b) An example of a first father. (c) An example of a second father. (d) The result of the offspring from the first and second father in the examples. (e) Partial solution after removing duplicates. (f) The completed child solution. Source: [35].

The grouping mutator operator permits introducing random changes into the population, resulting in more diversity in the solutions, so there is more exploration of the search space. The proposed mutator operator promotes transmitting the “best genes” in a chromosome and is applied at the gene level to avoid the loss of high-quality genes (which are essentially well-filled bins). This operator eliminates the bins that have the most available space (are not well-filled) and reinserts the items from the eliminated bins into the solution with the help of a rearrangement technique that is discussed later. The operation is called adaptive because the number of bins that will be eliminated in a solution, n b , is determined by equation (18) considering: the solution size ( m ) and how many bins in the solution and not completely filled ( τ ) , the elimination proportion ( ε ) as calculated in equation (19), and the probability of elimination ( P ε ) as calculated in equation (20).

where k defines the rate of change of the elimination proportion, ε , and probability, P ε , concerning the number of incomplete bins, τ .

The rearrangement heuristic, called “rearrangement by pairs,” or RP, is a technique that must be implemented in two steps. First, every bin is reviewed to determine the possibility of improving its packing schema by swapping pairs of already-packed and free items (free items are also known as “missing items” which are items that need to be placed in a bin but are not present in the solution being repaired). Second, the remaining items are inserted into the solution through the FF heuristic. This technique has a significant impact on the exploration and exploitation of the search space. Algorithm 7 explains the rearrangement by pairs procedure. S ′ denotes the result of swapping the items s and p from the bin B j with an item i from F . Feasible ( S ′ ) is true if the swap that has occurred results in a bin with a capacity that does not exceed the fixed maximum capacity, otherwise it is false. Both the items from S and F are considered in pairs. There are two possibilities for the two pairs of items, as shown in the IF-statements in the algorithm. These statements say two things: (1) if it can be done, replace the pair of items p and s from the bin with one of the free items from the pair that have a weight greater than or equal to the sum of the weight of p and s , as long as the replacement does not cause the bin to overflow; (2) if replacing the pair of items from the bin ( p and s ) with the free items ( i and k ) results in the free items filling the bin equal to or better than the items from the bin, swap the items p and s with i and k . Then, apply the FF heuristic to reinsert the items in F to make the solution valid.

Figure 12 shows an example of the adaptive mutator with the rearrangement heuristic.

Figure 12

An example of the adaptive mutator with RP operator. (a) An example of the list of items in a BPP instance. (b) An example of an individual in the population with bin capacity of 10. (c) Partial solution after elimination of two bins. (d) The completed child solution. Source: [35].

The authors additionally propose a “controlled selection” mechanism that balances the population diversity and selective pressure. Population diversity permits exploring new areas of the search space, which positively impacts solution quality and helps avoid premature convergence. The selective pressure awards fitter individuals in the population with a better chance of being chosen for mutation, reproduction, and survival. If these attributes are missing from the algorithm, the search process will not be guided but instead be random, which will result in promising regions of the search space being overlooked. Therefore, balancing these features greatly improves the GGA-CGT’s performance. Every individual is given the opportunity to contribute to the succeeding generation of the population; however, the proposed selection scheme ensures that the best individuals survive.

The controlled selection for crossover is as follows: for n c parents to generate n c children, create two sets of individuals, G and R , that will serve as parents. B is known as the elite group, which consists of the best solutions. The first set, G , which stands for “good,” contains n c / 2 solutions randomly chosen from the best n c solutions in the current population. In contrast, the second set, R , which stands for “random,” also contains n c / 2 solutions randomly selected but from the set: population minus B. The random selections are made with uniform probability. Moreover, because this crossover occurs pairwise between the two sets (hence, G i is crossed with R i , where 0 ≤ i < n c / 2 ), the manner in which the sets are chosen avoids a solution being crossed with itself.

The controlled selection for mutation is as follows: a fixed number of solutions, n m , will be mutated. The operator is applied to n m of the best solutions in the population. In this case, lifespan plays a role in determining if cloning occurs. If a chosen solution exists within a specific lifespan, then it is cloned. After this, solutions are selected from the population to mutate, according to decreasing fitness values.

The replacement strategy dictates which solutions are eliminated and replaced by the new progeny. The authors aim to promote exploration by always permitting new solutions to be added. There are two types of controlled replacement: one for crossover and one for mutation. In the controlled replacement for crossover, the first n c / 2 children generated from the crossover operator replace their parent from the random set, R (their second father). The remaining children replace solutions from a subset of the population that does not include the set of best ( B ) and random ( R ) solutions. In this latter case, the children either replace solutions from the described subset of the population with duplicate fitness (if they exist) or worst solutions. In the controlled replacement for mutation, the cloned solutions either replace solutions with duplicate fitness (if they exist), or the worst solution in the current population.

6.1 Scheduling and resource allocation

The application of BPP to the area scheduling and resource allocation basically deals with the problem of allocating limited resources or tasks with/without time consideration. Researchers have proposed different approaches or variation of the BPP in this regard. For example, Ojeyinka [49] applied the online and offline variants of the bin packing heuristics, implemented using the fill function, on the passenger-bus scheduling and the multiprocessor job scheduling problems. The goal of reducing the timespan needed for a multiprocessor to process all tasks using the BPP is exploited by Coffman et al. [50]. The performance of some scheduling algorithm was evaluated in ref. [51] using the BPP where the operating room time corresponds to the bin to be minimized. Leinberger et al. [52] showed how multi-capacity bin packing can lead to a highly sophisticated multi-resource allocation and scheduling. Furthermore, the scheduling of surgical operations using the BPP was exploited by Van Houdenhoven et al. [53].

6.2 Production

The BPP has several practical applications in the supply chain sectors, which cut across different manufacturing and service orientations. For instance, in manufacturing, the product to be manufactured can be considered to be a task to be accomplished within a time frame in a production cycle; the plant used for production is the bin to be allocated to the task (product), and finally, the goal of minimizing production cost is achieved by minimizing the number of bins [54]. Smart packing algorithm was designed by Khairuddin et al. [55] using the GA to solve the 3D bin or container packing problem. The authors in ref. [55] then applied their proposed method to reduce packaging waste due to ineffective packaging in the manufacturing process. Two-dimensional packing algorithm was similarly used in ref. [56] to solve the problem of composite material production in autoclave moulding. The aspect of product delivery using mobile robotics was exploited in ref. [57].

6.3 Health care community

The BPP is applied in this area to promote better cooperation between different components within the health care sector to provide an improved health care system. Surgical cases and resource scheduling using BPP were exploited in refs. [53,58,59]. The common goal here is to make optimal use of the operating rooms by scheduling surgeries that can be combined to achieve high throughput in the system. Patient scheduling for access to a practitioner was exploited in ref. [60], they used BPP for effective and optimal scheduling of patients to available practitioners. In the real sense, this problem is essentially a BPP with the modification that each bin might have a different total size. Each doctor forms a bin whose capacity is equal to the number of free hours in the doctor’s schedule, and each patient is an object to be placed into a bin, whose size is equal to the number of hours for which she needs to be seen. The overall goal here is to find the most efficient way to schedule patients across doctors, while upholding certain measure of fairness in terms of workload across the doctors, and maximizing fairness while getting every patient seen by the prescribed doctors on duty. However, this task would become even more complex and difficult to solve when dealing with a scenario where the doctors are specialists in different subfields and each patient needs to be seen by a doctor with a certain set of skills under the different subfields depending on their medical practice. Another interesting application of the BPP is in nurse scheduling, here a consideration of the capacity of the nurses and the various needs of the patients using BPP are taken into account. A nurse to patient allocation relative to the BPP was considered in ref. [61].

6.4 Distribution and inventory

Although some aspect of the distribution and inventory system can be classified as being part of the production category, distribution and inventory are well researched using the BPP. The BPP fits in here because of consideration of sizes and shape, technological and orientation constraints during delivery and so on. Gupta and Radovanovic [62] considered a scenario of items in the form of a sequence (for delivery or inventory) that must be packed on arrival. A similar scenario was considered in ref. [63] except that in this case, additional constraints of no buffering and readjustment were added. For an inventory, online order fulfilment is an integral part of e-commerce. Zhang et al. [64] proposed a solution to the dynamic stocking problem using a mixed integer programming. Besides, without adequate inventory in a warehouse, storage processing is interrupted. Ravichandran and Sasi [65] proposed a robust solution approach using the BPP-based farm optimization algorithm.

6.5 Logistics

The logistic process, in this case, implies packaging and routing of goods and services for different interests. This industry usually deals with the respective company rules on handling their products; however, this is by no means an easy task. Sajini Anand and Guericke [66] proposed a variable size BPP to achieve this objective. A smart packaging scheme was proposed by Khairuddin et al. [55]. A scenario where a decision must be made from a list of permissible actions upon the arrival of a stochastic request was exploited by Banerjee and Freund [67]. The authors in ref. [68] used BPP to address the problem of minimization of the distance of client’s location from the requested item location. The electric cars used are in multi-depots.

6.6 Cloud computing

In cloud computing, the problem of energy efficiency and cost of operation can be effectively managed if the number of servers used for a given task is minimized. This approach greatly fits into BPP, hence, several studies have been published in this regard. The placements of the virtual machines were considered to be the bins in ref. [69]. A heuristic method was proposed to solve a smaller version of the problem, with the primary goal of minimizing the problem objective function. A BPP model that implements the reversed auction in cloud computing was proposed by Ye et al. [70]. In the same vein, Srirama et al. [71] proposed a dynamic BPP strategy with auto scaling. In order to solve the complications of scheduling and autoscaling caused by container layer, Wang et al. [72] proposed an elastic scheduling for microservices (ESMS), which minimizes the cost of the virtual machines without compromising autoscaling.