Article ID: | iaor19991422 |
Country: | United States |
Volume: | 44 |
Issue: | 3 |
Start Page Number: | 388 |
End Page Number: | 399 |
Publication Date: | Mar 1998 |
Journal: | Management Science |
Authors: | Martello Silvano, Vigo Daniele |
Keywords: | cutting stock |
Given a set of rectangular pieces to be cut from an unlimited number of standardized stock pieces (bins), the Two-Dimensional Finite Bin Packing Problem is to determine the minimum number of stock pieces that provide all the pieces. The problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. We analyze a well-known lower bound and determine its worst-case performance. We propose new lower bounds which are used within a branch-and-bound algorithm for the exact solution of the problem. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach.