| Article ID: | iaor2005960 |
| Country: | Germany |
| Volume: | 1 |
| Issue: | 1 |
| Start Page Number: | 27 |
| End Page Number: | 42 |
| Publication Date: | Jan 2003 |
| Journal: | 4OR |
| Authors: | Mingozzi A., Boschetti M.A. |
| Keywords: | heuristics |
The Two-Dimensional Finite Bin Packing Problem (2BP) consists of determining the minimum number of large identical rectangles, bins, that are required for allocating without overlapping a given set of rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. In this paper we describe new lower bounds for the 2BP where the items have a fixed orientation and we show that the new lower bounds domintate two lower bounds proposed in the literature. These lower bounds are extended in Part II for a more general version of the 2BP where some items can be rotated by 90°. Moreover, in Part II a new heuristic algorithm for solving both versions of the 2BP is presented and computational results on test problems from the literature are given in order to evaluate the effectiveness of the proposed lower bounds.