Definition: Find the best arrangement of shapes on rectangles to minimize waste or the number of rectangles. This is a two-dimensional variant of the bin packing problem. It is NP-complete.
Specialization (... is a kind of me.)
strip packing is a one-dimensional variant.
See also knapsack problem, optimization problem.
Note: This problem arises often in manufacturing. For instance, deciding how to cut pieces for pants from cloth or shapes from sheet metal.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 27 April 2009.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "cutting stock problem", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 27 April 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/cuttingStock.html