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.
Illustration of one-dimensional cutting-stock problem
A paper machine can produce an unlimited number of master rolls, each 5600 mm wide. The following 13 items must be cut, in the table below.The important thing about this kind of problem is that many different product units can be made from the same master roll, and the number of possible combinations is itself very large, in general, and not trivial to enumerate.
The problem therefore is to find an optimum set of patterns of making product rolls from the master roll, such that the demand is satisfied and waste is minimized.
Bounds and checks
A simple lower bound is obtained by dividing the total amount of product by the size of each master roll. The total product required is 1380 x 22 + 1520 x 25 +... + 2200 x 20 = 407160 mm. Each master roll is 5600 mm, requiring a minimum of 72.7 rolls, which means 73 rolls or more are required.Solution
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:Classification
Cutting-stock problems can be classified in several ways. One way is the dimensionality of the cutting: the above example illustrates a one-dimensional problem; other industrial applications of 1D occur when cutting pipes, cables, and steel bars. Two-dimensional problems are encountered in furniture, clothing and glass production. When either the master item or the required parts are irregular-shaped this is referred to as the nesting problem.Not many three-dimensional applications involving cutting are known; however the closely related 3D packing problem has many industrial applications, such as packing objects into shipping containers.
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. 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:- Two-stage, where the rolls produced in the first stage are then processed a second time. For instance, all office stationery is produced in such a process. The complication arises because the machinery in the second stage is narrower than the primary. Efficient utilisation of both stages of production is important and what is efficient for the primary stage may be inefficient for the secondary, leading to trade-offs. Metallised film, and plastic extrusion on paper are further examples of such a process.
- Winder constraints where the slitting process has physical or logical constraints: a very common constraint is that only a certain number of slitting knives are available, so that feasible patterns should not contain more than a maximum number of rolls. Because winder machinery is not standardised, very many other constraints are encountered.
- An example of a customer requirement is when a particular order cannot be satisfied from either of the two edge positions: this is because the edges of the sheet tend to have greater variations in thickness and some applications can be very sensitive to these.
- An example of a quality issue is when the master roll contains defects that have to be cut around. Expensive materials with demanding quality characteristics such as photographic paper or Tyvek have to be carefully optimised so that the wasted area is minimised.
- Multi-machine problems arise when orders can be produced on more than one machine and these machines have different widths. Generally availability of more than one master roll width improves the waste considerably; in practice however additional order splitting constraints may have to be taken into account.
- There is also a semi-continuous problem, where the produced rolls do not have to be of the same diameter, but can vary within a range. This typically occurs with sheet orders. This is sometimes known as a 1½ dimensional problem. This variant also occurs in the production of corrugated fiberboard, where it is called, somewhat confusingly, the corrugator scheduling problem.
- Because some paper machines are relatively narrow compared to the demanded items, some companies have invested in a skiving secondary process, whereby two reels are joined side-by-side to make up a wider roll. Producing narrower reels in the primary process leads to lower overall waste.
- In the metals industry one key difference is that typically the master rolls are produced earlier and are generally different from each other. Therefore, there are similarities with the multi-machine problem mentioned above. The presence of length variations creates a 2-D problem, because waste can occur both width-wise and length-wise.
Cutting-stock problem in the glass industry
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.History
The cutting stock problem was first formulated by Kantorovich in 1939. In 1951 before computers became widely available, L. V. Kantorovich and V. A. Zalgaller suggested 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.Mathematical formulation and solution approaches
The standard formulation for the cutting-stock problem starts with a list of m orders, each requiring pieces, where. We then construct a list of all possible combinations of cuts. Let be the number of those patterns. We associate with each pattern a positive integer variable, representing how many times pattern is to be used, where. The linear integer program is then:where is the number of times order appears in pattern and is the cost of pattern. The precise nature of the quantity constraints can lead to subtly different mathematical characteristics. The above formulation's quantity constraints are minimum constraints. When 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 :
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. Gilmore and Gomory showed that this approach is guaranteed to converge to the 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. This limitation is overcome in modern algorithms, which can solve to optimality very large instances of the problem.
The cutting-stock problem is often highly degenerate, in that multiple solutions with the same amount of waste are possible. This degeneracy arises because it is possible to move items around, creating new patterns, without affecting the amount of waste. This gives rise to a whole collection of related problems which are concerned with some other criterion, such as the following:
- The minimum pattern count problem: to find a minimum-pattern-count solution amongst the minimum-waste solutions. This is a very hard problem, even when the waste is known. There is a conjecture that any equality-constrained one-dimensional instance with n orders has at least one minimum waste solution with no more than n + 1 patterns. This conjecture was first refuted in April 2020 with an example with 9 sizes that requires 11 patterns.
- The minimum stack problem: this is concerned with the sequencing of the patterns so as not to have too many partially completed orders at any time. This was an open problem until 2007, when an efficient algorithm based on dynamic programming was published.
- The minimum number of knife changes problem : this is concerned with sequencing and permuting the patterns so as to minimise the number of times the slitting knives have to be moved. This is a special case of the generalised travelling salesman problem.