Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The two-dimensional Bin Packing Problem (2DBPP) consists of planning a set of rectangular items into a fixed width and height 2D bins orthogonally, without overlapping, while minimizing the number of bins [1–5]. The 2DBPP is an intractable optimization problem and widely faced during the industrial manufacturing processes. Proposed algorithms find a pareto-optimal solution for both the minimal number of bins with the most efficiently load-balanced placing of the rectangular items. rotating objects (Orientation: whether the objects can be rotated or not is a key aspect of the 2DBPP) in packing creates better results but objects may not be rotatable in every problem definition. The textile industry can change the orientation of single color shirts by rotating the shirts while the process is in cutting phase, because there is no difference between rotation or not. However, the orientation of fragile items is important in shipping. If an item can be rotated then it is called as non-oriented or orientation-free. If an object of problem cannot be rotated it is called as oriented or orientation-fix. Online and offline are two categories of 2DBPP according to the availability of information about all items. Online bin packing (OnBP) means that objects arrive one by one and there is no way to know the complete input sequence, so it must be inserted into a bin immediately without waiting other items. Load balancing of 2DBPP, is the stabilization of total moments of rectangle items on the left of Centre of Gravity (CG) of bins with total moments of rectangles on the right of CG of bins. Euclidean Center of bin is considered as CG of a bin.

In the proposed algorithms, we use solution methods inspired from Evolutionary Algorithms (EA). Reproduction, mutation, recombination and selection are key mechanisms of EA that are used for solving NP-Hard optimization problems. BPP, Travelling Salesman and Quadratic Assignment Problem [2, 6] are well-known challenging NP-Hard problems modelled and solved successfully with EAs. Genetic Algorithm (GA) and Memetic Algorithm (MA) are the most efficient approaches of EAs. GA mimics the natural evolution process and has the ability to find (near-) optimal solutions in a large search space. Survival of the fittest individual is a rule allowing the best solution in each iteration to converge to a (near-) optimal solution in practical times. In GA, parents mate and produce offsprings and the best individuals are selected to survive to the next generation. MA is another growing area of EA. The fittest of individuals is selected as the solution of optimization problem. It mimics natural evolution process but it may differ from GA by performing individual learning which is also known as meme(s).

We propose two different Multiheuristic Multiobjective GA (MH-MOGA) that optimize both the minimal number and the load-balancing of the bins. The first proposed multiobjective algorithm, MHO-MOGA, uses heuristics: FNF, FFF, BFDH, UTS and LGFof to solve oriented multi objective 2D offline BPPs. The second proposed multiobjective algorithm, MHNO-MOGA, uses heuristics: FNF, FFF, BFDH, UTS, LGFof and LGFi and tries to find a pareto-optimal solution (minimal number of bins and most effective load-balancing of items) for non-oriented multiobjective 2D offline BPPs.

2 Formulation of the Load-Balancing Problem

Multiobjective 2DBPP with load balancing [7–9] tries to minimize Eq. 1

$$\begin{aligned} (C/2 + LB/2) \end{aligned}$$
(1)

where

$$\begin{aligned} C = \sum \limits _{j=1}^{n}c_{j} \end{aligned}$$
(2)
$$\begin{aligned} LB = \sum \limits _{j=1}^{C} \left| \sum \limits _{i=1}^{B}p_{ij}d_{i}m_{ij}\sqrt{(x_{ij} + (w_{ij}/2) - x_{CG})^2 + (y_{ij} + (h_{ij}/2) - y_{CG})^2}\right| \end{aligned}$$
(3)

which is subject to

$$\begin{aligned} x_{i} + (w_{i}w_{i}^{x}) + (h_{i}h_{i}^{x}) \le x_{k} + (1 - le_{ik}), \quad \forall i,k, i < k \end{aligned}$$
(4)
$$\begin{aligned} x_{k} + (w_{k}w_{k}^{x}) + (h_{k}h_{k}^{x}) \le x_{i} + (1 - ri_{ik}), \quad \forall i,k, i < k \end{aligned}$$
(5)
$$\begin{aligned} y_{i} + (w_{i}w_{i}^{x}) + (h_{i}h_{i}^{x}) \le y_{k} + (1 - un_{ik}), \quad \forall i,k, i < k \end{aligned}$$
(6)
$$\begin{aligned} y_{k} + (w_{k}w_{k}^{x}) + (h_{k}h_{k}^{x}) \le y_{i} + (1 - ab_{ik}), \quad \forall i,k, i < k \end{aligned}$$
(7)
$$\begin{aligned} le_{ik} + ri_{ik} + un_{ik} + ab_{ik} \le p_{ij} + p_{kj} - 1, \quad \forall i,k, i < k \end{aligned}$$
(8)
$$\begin{aligned} \sum \limits _{j=1}^{C}p_{ij} = 1,\quad \forall i \end{aligned}$$
(9)
$$\begin{aligned} \sum \limits _{i=1}^{B}p_{ij} \le Mc_{j},\quad \forall j \end{aligned}$$
(10)
$$\begin{aligned} x_{i} + (w_{i}w_{i}^{x}) + (h_{i}h_{i}^{x}) \le W_{j} + (1 - p_{ij})M,\quad \forall i,j \end{aligned}$$
(11)
$$\begin{aligned} y_{i} + (w_{i}w_{i}^{y}) + (h_{i}h_{i}^{y}) \le H_{j} + (1 - p_{ij})M,\quad \forall i,j \end{aligned}$$
(12)
$$\begin{aligned} w_{i}^{x}, w_{i}^{y}, h_{i}^{x}, h_{i}^{y}, le_{ik}, ri_{ik}, ab_{ik}, un_{ik}, p_{ij}, c_{j} \in {0, 1}, \quad \forall i,k, i < k \end{aligned}$$
(13)
$$\begin{aligned} x_{i}, y_{i} \ge 0, \quad \forall i \end{aligned}$$
(14)
$$\begin{aligned} m_{ij} \in {-1, 1}, \quad \forall i \end{aligned}$$
(15)
$$\begin{aligned} x_{CG} \ge (W/2) \end{aligned}$$
(16)
$$\begin{aligned} y_{CG} \ge (H/2) \end{aligned}$$
(17)
B :

total number of rectangles

C :

total number of bins

LB :

the total sum of load balancing

\(w_{i}, h_{i}\) :

width and height of rectangle i

\(d_{i}\) :

weight of rectangle i

\(W_{j}, H_{j}\) :

width and height of bin j

\(x_{i}, y_{i}\) :

left-bottom corner of rectangle i as coordinate

\(x_{CG}\) :

x coordinate of center of gravity of bin which is equal to (W/2)

\(x_{CG}\) :

y coordinate of center of gravity of bin which is equal to (H/2)

\(w_{i}^{x}, w_{i}^{y}\) :

width of rectangle i is parallel to X and Y axis

\(h_{i}^{x}, h_{i}^{y}\) :

height of rectangle i is parallel to X and Y axis

\(le_{ik}\) :

rectangle i is placed on the left side of rectangle k

\(ri_{ik}\) :

rectangle i is placed on the right side of rectangle k

\(ab_{ik}\) :

rectangle i is placed above rectangle k

\(un_{ik}\) :

rectangle i is placed under rectangle k

\(p_{ij}\) :

\(p_{ij} = 1\) if rectangle i is placed in bin j otherwise \(p_{ij} = 0\)

\(m_{ij}\) :

\(m_{ij} = 1\) if \((x_{ij} + (w_{ij}/2) - x_{CG}) \ge 0\) otherwise \(m_{ij} = -1\)

\(c_{j}\) :

\(c_{j} = 1\) if bin j is used otherwise \(c_{j} = 0\)

M :

an arbitrarily large number used in Bin-M constraints

3 Proposed Algorithms

The chromosome is an array of values representing a possible solution to a 2DBPP. There are two parts in the chromosome. Rectangle items and a heuristics part that keeps the heuristics. Permutation encoding which is a form of keeping width-height of rectangular items and processing sequence between rectangles is used to keep the identification of rectangles. Gene (rectangle item) packing is done in two different ways. If Heu1 is equal to Heu2, then all genes are packed as a whole by using Heu1 and the result of Heu1 shows the number of required bins for solution. If Heu1 is different than Heu2, then Heu1 packs the first half of the genes and Heu2 packs the second half of the genes. The sum of required bins of Heu1 and Heu2 shows the number of required bins for solution. Elitist selection that gives higher chance to better chromosomes in the population is used in the proposed algorithms.

Single point crossover is used in our algorithms. Three different mutation operators are used in the algorithms in accordance with the orientation possibility of the items. The proposed mutation operators work on the rectangular items part of a chromosome. Swap mutation, rotation mutation (for non-oriented items), and swap-rotation mutation are the mutation operators.

The proposed MA mimics the natural evolution process. Our algorithms consider load balancing with center of gravity to each bin. In order to calculate center of gravity, each bin’s center point is selected as Center of Gravity (CG). When a rectangle box is inserted, the Euclidean distance of its center to bins CG is calculated and multiplied by the weight of rectangle. This calculated value is CG of a rectangle. If sign of x coordinate of rectangle is minus then CG of rectangle is subtracted from total CG of Bin. If sign of x coordinate of rectangle is plus then CG of rectangle is added to total CG of Bin. When all rectangles are inserted to bins, absolute values of total CG of bins are added. This calculated value is called as CG of a chromosome. The load balance of a bin is explained in Eq. 18 and load balance of a chromosome is explained in Eq. 19.

$$\begin{aligned} LB_{Bin} = \sum \limits _{j=1}^{\#Rect}d_{ij}m_{ij}\sqrt{(x_{ij} + (w_{ij}/2)- x_{CG})^2 + (y_{ij} + (h_{ij}/2) - y_{CG})^2} \end{aligned}$$
(18)
$$\begin{aligned} LB_{Chromosome} = \sum \limits _{i=1}^{\#Bin} \left| \sum \limits _{j=1}^{\#Rect}d_{j}m_{ij}\sqrt{(x_{ij} + (w_{ij}/2) - x_{CG})^2 + (y_{ij} + (y_{ij}/2)- y_{CG})^2}\right| \end{aligned}$$
(19)

Multiheuristic Oriented Multiobjective GA (MHO-MOGA) is proposed to solve oriented multiobjective offline 2DBPP. FNF, FFF, BFDH, LGFof and UTS are applied as heuristics on the base of a GA. Swap mutation operation is used to keep orientation of items. Multiheuristic Non-Oriented Multiobjective GA (MHNO-MOGA) is developed for optimization of non-oriented items. Each individual uses one or two of the heuristics: FNF, FFF, BFDH, UTS, LGFof and LFGi to pack rectangles into bins. At the beginning of GA, each individual picks one of the heuristics. At the next phase, an individual can have two different heuristics. Each heuristic is applied to the corresponding part of rectangle list. Rotation mutation and swap-rotation mutation are used to change orientation of rectangles. Best result of GA becomes the solution of the problem.

4 Experimental Setup and Results

Two well known offline 2DBPP instance sets are used for the experiments (Berkey-Wang and Martello-Vigo) [10, 11]. Experimental setup consists of UTS, LFGi and GA whose heuristics are FNF, FFF, BFDH and LGFof. First, we apply GA to the problem and later the best result’s rectangle list is given as input to UTS and LGFi. The parameter setting for the population size and the number of generations are decided to be 60 and 40 respectively. These parameter settings are used in all of the proposed algorithms throughout the experiments. The general results of MHNO-MOGA experiments are listed in Tables 1 and 2. We compared our results with LGFi algorithm.

Table 1 Result of MHNO-MOGA Ro for Berkey-Wang instances
Full size table
Table 2 Result of MHNO-MOGA Ro for Martello-Vigo instances
Full size table

In order to analyze runtime and efficiency of the algorithms, we randomly picked five different item size (20, 40, 60, 80, 100) 2DBPP. Each test is run for five times. Best values of FNF, FFF, BFDH, LGFof and LGFi are used as results. For the proposed algorithms and UTS, we used the average values of the experiments. Comparisons of algorithms according to 500 instance test setup are also explained in detail. The runtime analysis of FNF, FFF, BFDH, UTS, LGFof and MHO-MOGA for oriented multiobjective random picked tests are shown in Table 3. MHO-MOGA is reported to be the most time consuming algorithm.

Table 3 Runtime of algorithms for oriented multiobjective problems in msec
Full size table

The general results of second experiment are listed in Tables 4 and 5. We compared our results with LGFi algorithm.

Table 4 Result of MHNO-MOGA SwRo for Berkey-Wang instances
Full size table
Table 5 Result of MHNO-MOGA SwRo for Martello-Vigo instances
Full size table

Result (bin/cg) analysis of FNF, FFF, BFDH, UTS, LGFof and MHO-MOGA for oriented multiobjective random picked tests are shown in Table 6.

Table 6 Results (bin/cg) of algorithms for oriented multiobjective problems
Full size table
Table 7 Results (bin/cg) of heuristics and MHO-MOGA for oriented multiobjective 500 problem set
Full size table
Table 8 MHO-MOGA versus heuristics for oriented multiobjective 500 problem set
Full size table
Table 9 Runtime of algorithms for non-oriented multiobjective problems in msec
Full size table

Results (bin/cg) of FNF, FFF, BFDH, UTS, LGFof and MHO-MOGA for oriented single objective 500 problem set are shown in Table 7.

Superiority of MHO-MOGA to FNF, FFF, BFDH, UTS and LGFof for oriented multiobjective 500 problem set are shown in Table 8.

Runtime analysis of FNF, FFF, BFDH, UTS, LGFof, LGFi and MHNO-MOGA for non-oriented multiobjective random picked tests are shown in Table 9. MHNO-MOGA is reported to be the most time consuming algorithm.

Result (bin/cg) analysis of FNF, FFF, BFDH, UTS, LGFof, LGFi and MHNO-MOGA for non-oriented multiobjective random picked tests are shown in Table 10.

Table 10 Results (bin/cg) of algorithms for non-oriented multiobjective problems
Full size table

Results (bin/cg) of FNF, FFF, BFDH, UTS, LGFof, LGFi and MHNO-MOGA (r) for non-oriented multiobjective 500 problem set (according to continuous lower bound) are shown in Table 11.

Table 11 Results (bin/cg) of heuristics and MHNO-MOGA (r) for non-oriented multiobjective 500 problem set
Full size table

Superiority of MHO-MOGA (r) versus FNF, FFF, BFDH, UTS, LGFof and LGFi for non-oriented multiobjective 500 problem set are shown in Table 12.

Table 12 MHO-MOGA(r) versus heuristics for non-oriented multiobjective 500 problem set
Full size table

Results (bin/cg) of FNF, FFF, BFDH, UTS, LGFof, LGFi and MHNO-MOGA (sr) for non-oriented multiobjective 500 problem set (according to continuous lower bound) are shown in Tables 11 and 13.

Table 13 Results (bin/cg) of heuristics and MHNO-MOGA(sr) for non-oriented multiobjective 500 problem set
Full size table

Superiority of MHNO-MOGA (sr) versus FNF, FFF, BFDH, UTS, LGFof and LGFi for non-oriented multiobjective 500 problem set are shown in Table 14.

Table 14 MHO-MOGA (sr) versus heuristics for non-oriented multiobjective 500 problem set
Full size table

5 Conclusions and Future Work

In this study, two novel robust algorithms for the multiobjective optimization of offline 2DBPP are proposed. Our experimental results show that while the well known heuristics sometimes produce better results for minimizing the number of bins in 2DBPP they are not efficient for solving the multiobjective load balancing problem of 2D bins while also minimizing bins. MHO-MOGA and MHNO-MOGA give better results not only for minimum number of bins but also for the load balancing of 2D bins. MHNO-MOGA makes use of rotation and swap-rotation mutation operators. MHNO-MOGA with rotation mutation outperforms LGFi heuristic for 95.0 % of the problems. MHNO-MOGA with swap-rotation mutation outperforms LGFi heuristic for 96.0 % of the problems and 97.2 % of the benchmark problems for the LGFof heuristic.