Cutting stock problem

In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem in mathematics that arises from applications in industry. In terms of computational complexity, the problem is an NP-hard problem reducible to the knapsack problem. The problem can be formulated as an integer linear programming problem.

Formulation and solution approaches

The standard formulation for the cutting-stock problem (but not the only one) starts with a list of m orders, each requiring q_j, j = 1,\ldots,m pieces. We then construct a list of all possible combinations of cuts (often called "patterns"), associating with each pattern a positive integer variable x_i representing how long each pattern is to be used. The linear integer program is then:

\min\sum_{i=1}^n c_i x_i
\text{s.t.}\sum_{i=1}^n a_{ij} x_i \ge q_j, \quad \quad \forall j=1,\dots,m
x_i \ge 0, integer

where a_{ij} is the number of times order j appears in pattern i and c_i is the cost (often the waste) of pattern i. The precise nature of the quantity constraints can lead to subtly different mathematical characteristics. The above formulation's quantity constraints are minimum constraints (at least the given amount of each order must be produced, but possibly more). When c_i=1 the objective minimises the number of utilised master items and, if the constraint for the quantity to be produced is replaced by equality, it is called the bin packing problem. The most general formulation has two-sided constraints (and in this case a minimum-waste solution may consume more than the minimum number of master items):

q_j \le \sum_{i=1}^n a_{ij} x_i \le Q_j, \quad \quad \forall j=1,\dots,m

This formulation applies not just to one-dimensional problems. Many variations are possible, including one where the objective is not to minimise the waste, but to maximise the total value of the produced items, allowing each order to have a different value.

In general, the number of possible patterns grows exponentially as a function of m, the number of orders. As the number of orders increases, it may therefore become impractical to enumerate the possible cutting patterns.

An alternative approach uses delayed column-generation. This method solves the cutting-stock problem by starting with just a few patterns. It generates additional patterns when they are needed. For the one-dimensional case, the new patterns are introduced by solving an auxiliary optimization problem called the knapsack problem, using dual variable information from the linear program. The knapsack problem has well-known methods to solve it, such as branch and bound and dynamic programming. The Delayed Column Generation method can be much more efficient than the original approach, particularly as the size of the problem grows. The column generation approach as applied to the cutting stock problem was pioneered by Gilmore and Gomory in a series of papers published in the 1960s.[1][2] Gilmore and Gomory showed that this approach is guaranteed to converge to the (fractional) optimal solution, without needing to enumerate all the possible patterns in advance.

A limitation of the original Gilmore and Gomory method is that it does not handle integrality, so the solution may contain fractions, e.g. a particular pattern should be produced 3.67 times. Rounding to the nearest integer often does not work, in the sense that it may lead to a sub-optimal solution and/or under- or over-production of some of the orders (and possible infeasibility in the presence of two-sided demand constraints). This limitation is overcome in modern algorithms, which can solve to optimality (in the sense of finding solutions with minimum waste) very large instances of the problem (generally larger than encountered in practice[3][4]).

The cutting-stock problem is often highly degenerate, in that multiple solutions with the same waste are possible. This degeneracy arises because it is possible to move items around, creating new patterns, without affecting the waste. This gives rise to a whole collection of related problems which are concerned with some other criterion, such as the following:

Illustration of one-dimensional cutting-stock problem

A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600 mm wide. The following 13 items must be cut:

Width Rolls
1380 22
1520 25
1560 12
1710 14
1820 18
1880 18
1930 20
2000 10
2050 12
2100 14
2140 16
2150 18
2200 20

Solution

A minimum-waste solution, sequenced to minimise knife changes, shown as small white circles

There are 308 possible patterns for this small instance. The optimal answer requires 73 master rolls and has 0.401% waste; it can be shown computationally that in this case the minimum number of patterns with this level of waste is 10. It can also be computed that 19 different such solutions exist, each with 10 patterns and a waste of 0.401%, of which one such solution is shown below and in the picture:

{| class="wikitable" border="0" cellpadding="4"

!Repetition !align=center | Contents |- | align=center | 2 || 1820 + 1820 + 1820 |- | align=center | 3 || 1380 + 2150 + 1930 |- | align=center | 12 || 1380 + 2150 + 2050 |- | align=center | 7 || 1380 + 2100 + 2100 |- | align=center | 12 || 2200 + 1820 + 1560 |- | align=center | 8 || 2200 + 1520 + 1880 |- | align=center | 1 || 1520 + 1930 + 2150 |- | align=center | 16 || 1520 + 1930 + 2140 |- | align=center | 10 || 1710 + 2000 + 1880 |- | style="border-bottom:3px solid grey" align=center | 2 || 1710 + 1710 + 2150 |- | align=center | 73 |} MATLAB CODE:

clear;
close all;
clc

%% Defining Decision Variable by YALMIP Command

X = intvar(10,1);

c = [5460 5460 5580 5580 5580 5600 5600 5590 5590 5570];

a=[ 0 0 0 0 3 0 0 0 0 0 0 0 0
    1 0 0 0 0 0 1 0 0 0 0 1 0
    1 0 0 0 0 0 0 0 1 0 0 1 0
    1 0 0 0 0 0 0 0 0 2 0 0 0
    0 0 1 0 1 0 0 0 0 0 0 0 1
    0 1 0 0 0 1 0 0 0 0 0 0 1
    0 1 0 0 0 0 1 0 0 0 0 1 0
    0 1 0 0 0 0 1 0 0 0 1 0 0
    0 0 0 1 0 1 0 1 0 0 0 0 0
    0 0 0 2 0 0 0 0 0 0 0 1 0
    ];

order = [22 25 12 14 18 18 20 10 12 14 16 18 20]';

F = c*X;

%% Constraints

Constraints = [a'*X >= order ,X>=0];

Objective = (F) ;

Options = sdpsettings('solver','');

solvesdp(Constraints,Objective,Options )

Repetition = value(X)

Classification

Cutting-stock problems can be classified in several ways.[9] One way is the dimensionality of the cutting: the above example illustrates a one-dimensional (1D) problem; other industrial applications of 1D occur when cutting pipes, cables, and steel bars. Two-dimensional (2D) problems are encountered in furniture, clothing and glass production. Not many three-dimensional (3D) applications involving cutting are known; however the closely related 3D packing problem has many industrial applications, such as packing objects into shipping containers (see e.g. containerization: the related sphere packing problem has been studied since the 17th century (Kepler conjecture)).

Cutting-stock problem in paper, film and metal industries

Industrial applications of cutting-stock problems for high production volumes arise especially when basic material is produced in large rolls that are further cut into smaller units (see roll slitting). This is done e.g. in paper and plastic film industries but also in production of flat metals like steel or brass. There are many variants and additional constraints arising from special production constraints due to machinery and process limits, customer requirements and quality issues; some examples are:

Cutting-stock problem in the glass industry

The guillotine problem is a problem of cutting sheets of glass into rectangles of specified sizes, using only cuts that continue all the way across each sheet.

Example of a guillotine cut
Example of a non-guillotine cut

The assortment problem

The related problem of determining, for the one-dimensional case, the best master size that will meet given demand is known as the assortment problem.[11]

History

The cutting stock problem was first formulated by Kantorovich in 1939.[12] In 1951 before computers became widely available, L. V. Kantorovich and V. A. Zalgaller suggested[13] solving the problem of the economical use of material at the cutting stage with the help of linear programming. The proposed technique was later called the column generation method.

References

  1. Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-stock problem. Operations Research 9: 849-859
  2. Gilmore P. C., R. E. Gomory (1963). A linear programming approach to the cutting-stock problem - Part II. Operations Research 11: 863-888
  3. Goulimis C (1990). Optimal solutions for the cutting stock problem. European Journal of Operational Research 44: 197-208
  4. de Carvalho V (1998). Exact solution of cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research 5: 35–44
  5. S. Umetani, M. Yagiura, and T. Ibaraki (2003). One dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research 146, 388–402
  6. A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo (1996). Setup minimizing conditions in the trim loss problem. European Journal of Operational Research 95:631-640
  7. C. McDiarmid (1999). Pattern Minimisation in Cutting Stock Problems. Discrete Applied Mathematics, 121-130
  8. Maria Garcia de la Banda, P. J. Stuckey. Dynamic Programming to Minimize the Maximum Number of Open Stacks. INFORMS Journal on Computing, Vol. 19, No. 4, Fall 2007, 607-617.
  9. Wäscher, G.; Haußner, H.; Schumann, H. An Improved Typology of Cutting and Packing Problems. European Journal of Operational Research Volume 183, Issue 3, 1109-1130
  10. M.P. Johnson, C. Rennick & E. Zak (1997), Skiving addition to the cutting stock problem in the paper industry, SIAM Review, 472-483
  11. Raffensperger, J. F. (2010). "The generalized assortment and best cutting stock length problems". International Transactions in Operational Research 17: 35. doi:10.1111/j.1475-3995.2009.00724.x.
  12. L. V. Kantorovich Mathematical methods of organizing and planning production. Leningrad State University. 1939
  13. Kantorovich L. V. and Zalgaller V. A. . (1951). Calculation of Rational Cutting of Stock. Lenizdat, Leningrad.

Further reading

This article is issued from Wikipedia - version of the Wednesday, May 04, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.