Cutting stock problem

From Glossary

Jump to: navigation, search

Determine a way to cut standard sheets of material into various shapes (like clothes parts) to minimize waste. This is a (linear) integer programming model: patterns are specified, and LaTeX: A_{i, j, k} is the amount of LaTeX: i-th stock (e.g., sheet or roll of material) used to generate the LaTeX: j-th output by the LaTeX: k-th pattern. Then, let LaTeX: x_k be level of LaTeX: k-th pattern used and LaTeX: y = Ax. Thus, LaTeX: \textstyle s_i = \sum_j y_{i,j} is the amount of the LaTeX: i-th stock used, which is limited by its availability: LaTeX: s \le S; and LaTeX: \textstyle v_j = \sum_i y_{i, j} is the amount of LaTeX: j-th output generated, which is required to be in some range, say LaTeX: L \le v \le U (allowing some demand overruns or underruns). Some models seek to minimize the total waste: LaTeX: \textstyle \sum_i S_i - s_i. Other models consider cost too. The most common problems are 2-dimensional (odd shapes from sheets of material); the 1-dimensional case is called the trim problem. In the latter case, the stock index LaTeX: i is not needed. For example, consider a stock of rolls of paper with a given width, which must be slit into rolls of various widths. Then, LaTeX: A_{j, k} is how much of a stock roll is used by the LaTeX: k-th pattern to generate a roll of the LaTeX: j-th width. Moreover, LaTeX: \textstyle y_j = \sum_k A_{j, k} x_k is the amount of a stock roll used by pattern LaTeX: j to generate a roll of width LaTeX: j.

Personal tools