NIST

cutting stock problem

(classic problem)

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.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 27 April 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "cutting stock problem", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 27 April 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/cuttingStock.html