Exact solution of the Two-Dimensional Finite Bin Packing Problem

Exact solution of the Two-Dimensional Finite Bin Packing Problem

0.00 Avg rating0 Votes
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: ,
Keywords: cutting stock
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.