Two-Dimensional Bin Packing Algorithm Development
Budget: $10 – $30 USD
Bin packing
In the two-dimensional bin packing problem, we are given an unlimited number of finite identical rectangular bins, each having width W and height H, and a set of n rectangular items with width wj <= W and height hj, for 1 <= j <= n. The problem is to pack, without overlap, all the items into the minimum number of bins. The items cannot be rotated. Most of the off-line algorithm in the literature are of greedy type, and can be classified into two families:
one phase algorithms directly pack the items into the finite bins;
two phase algorithms start by packing the items into a single strip, i.e., a bin having width W and infinite height. In the second phase, the strip solution is used to construct a packing into finite bins.
2.1 Two-phase algorithms
The following two phase algorithms make use of some level-oriented algorithms to obtain a strip packing. Suppose H1, H2, ··· are the heights of the resulting levels of the strip packing. A finite bin packing solution is then obtained by solving a one-dimensional bin packing problem (with item size Hi and bin capacity H).
Hybrid First-Fit (HFF) [4]
In the first phase, a strip packing is obtained by the FFDH algorithm. The second phase adopts the First-Fit Decreasing (FFD) algorithm, which packs an item to the first bin that it fits or start a new bin otherwise.
Time complexity: O(n·log n).
The approximation ratio of HFF is 17/8 [4]. The bound is not proved to be tight: the best lower bound of HFF known is 91/45.
Hybrid Next-Fit (HNF) [5]
NFDH is adopted in the first phase. In the second phase, the one-dimensional bin packing problem is solved by the Next-Fit Decreasing (NFD) algorithm, which packs an item to the current bin if it fits, or start a new bin otherwise.
Time complexity: O(n·log n).
The approximation ratio of HNF is 3.382 [5].
Hybrid Best-Fit (HBF) [2]
In the first phase, BFDH strategy is adopted. The second phase adopts the Best-Fit Decreasing (BFD) algorithm, which packs an item to the best bin (one with the smallest space left) that it fits or start a new bin otherwise.
Floor-Ceiling (FC) algorithm [7][9]
Consider a particular level, the horizontal line defined by the top (resp. bottom) edge of the tallest item is called the ceiling (resp. floor) of the level. In the first phase, FC packs an item into a level either from left to right with their bottom edge on the level floor or from right to left, with their top edge on the level ceiling. The first item packed on a ceiling must be one which cannot be packed on the floor in the same level. The order of preference when FC packs an item in the first phase: (i) on a ceiling (provided that the requirement above is satisfied), using best-fit (BF) algorithm; (ii) on a floor, using BF algorithm; (iii) on the floor of a new level.
In the second phase, the levels are packed into finite bins, either by BFD or by an exact algorithm for the one-dimensional bin packing problem, halted after a prefixed number of iterations.
Time complexity: The implementation of the first phase given in [8] requires O(n3 ) time, while the complexity of the second one depends on the selected algorithm.
In the two-dimensional bin packing problem, we are given an unlimited number of finite identical rectangular bins, each having width W and height H, and a set of n rectangular items with width wj <= W and height hj, for 1 <= j <= n. The problem is to pack, without overlap, all the items into the minimum number of bins. The items cannot be rotated. Most of the off-line algorithm in the literature are of greedy type, and can be classified into two families:
one phase algorithms directly pack the items into the finite bins;
two phase algorithms start by packing the items into a single strip, i.e., a bin having width W and infinite height. In the second phase, the strip solution is used to construct a packing into finite bins.
2.1 Two-phase algorithms
The following two phase algorithms make use of some level-oriented algorithms to obtain a strip packing. Suppose H1, H2, ··· are the heights of the resulting levels of the strip packing. A finite bin packing solution is then obtained by solving a one-dimensional bin packing problem (with item size Hi and bin capacity H).
Hybrid First-Fit (HFF) [4]
In the first phase, a strip packing is obtained by the FFDH algorithm. The second phase adopts the First-Fit Decreasing (FFD) algorithm, which packs an item to the first bin that it fits or start a new bin otherwise.
Time complexity: O(n·log n).
The approximation ratio of HFF is 17/8 [4]. The bound is not proved to be tight: the best lower bound of HFF known is 91/45.
Hybrid Next-Fit (HNF) [5]
NFDH is adopted in the first phase. In the second phase, the one-dimensional bin packing problem is solved by the Next-Fit Decreasing (NFD) algorithm, which packs an item to the current bin if it fits, or start a new bin otherwise.
Time complexity: O(n·log n).
The approximation ratio of HNF is 3.382 [5].
Hybrid Best-Fit (HBF) [2]
In the first phase, BFDH strategy is adopted. The second phase adopts the Best-Fit Decreasing (BFD) algorithm, which packs an item to the best bin (one with the smallest space left) that it fits or start a new bin otherwise.
Floor-Ceiling (FC) algorithm [7][9]
Consider a particular level, the horizontal line defined by the top (resp. bottom) edge of the tallest item is called the ceiling (resp. floor) of the level. In the first phase, FC packs an item into a level either from left to right with their bottom edge on the level floor or from right to left, with their top edge on the level ceiling. The first item packed on a ceiling must be one which cannot be packed on the floor in the same level. The order of preference when FC packs an item in the first phase: (i) on a ceiling (provided that the requirement above is satisfied), using best-fit (BF) algorithm; (ii) on a floor, using BF algorithm; (iii) on the floor of a new level.
In the second phase, the levels are packed into finite bins, either by BFD or by an exact algorithm for the one-dimensional bin packing problem, halted after a prefixed number of iterations.
Time complexity: The implementation of the first phase given in [8] requires O(n3 ) time, while the complexity of the second one depends on the selected algorithm.