View source for Cutting problem

{{TEX|done}}
''rational cutting problem''

The choice of an allocation of parts in pieces of material that gives, as a rule, all the parts of a given complete set with minimal material expenses. Due to differences in technology and organization, distinctions are made among mathematical rational cutting models for mass and individual production: for straight (segments, rectangles, parallelepipeda) or curved parts, for constant or varying sizes and forms of the pieces of material, and models accounting for the location of defects on the material (see [[#References|[1]]]). Constraints on the admissible pattern can be taken into account to reflect the specific features of the industry and the equipment used. Cutting problems are equivalent to packing problems, i.e. certain problems of allocation of objects in drying kilns, and the positioning of cargo on freight cars and ship decks.

In the case of mass production with identical pieces of material and when it is possible to list explicitly all admissible patterns $i=1,\dots,N$ of cutting the piece into parts of some of the required $j=1,\dots,m$ types, the cutting problem reduces to the following [[Linear programming|linear programming]] problem: Find the level $x_i\geq0$ at which each pattern is used, for which $\sum_ix_i=\min$ subject to the conditions $\sum_ia_{ij}x_i\geq b_j$, where $a_{ij}$ is the number of parts of the $j$-th type in the $i$-th cutting, and $b_j$ is the number of such parts required for the production per a unit of volume. In practice it usually is impossible to list all the patterns. Then the above linear programming problem is solved, starting with some fixed set of admissible patterns, by the simplex method. In the course of the simplex procedure the list of patterns under consideration usually changes. At every step, one of those patterns is selected (generated by a computer) that according to the estimates of the dual linear programming problem could improve the current basic solution. In case of a  "one-dimensional"  material (that has to be cut in length only) this generation can be performed in acceptable time using [[Dynamic programming|dynamic programming]] (see [[#References|[1]]], [[#References|[2]]]). In the case of cutting rectangles this approach can also be implemented in principle, but in real problems the computations may be too laborious. If so, heuristic algorithms are used to generate better patterns: as a rule, it is enough to consider cuttings with not more than three different types of parts (cf. [[#References|[2]]], [[#References|[3]]]).

Similar cutting problems are formulated and solved in cases when it is possible to choose one or several standard sizes of material or if it is necessary to use available material of different sizes (see [[#References|[1]]]). Programs for solving cutting problems in the one-dimensional and rectangular cases take account of constraints imposed by characteristics of the equipment used (see [[#References|[2]]], [[#References|[3]]]). These programs include some service functions such as calculation of material norms for parts and the output of cutting maps.

A one-dimensional material of varying length is often used in mass production. In this case the cutting problem is to choose a pattern for the next piece of a certain specific length. In machine manufacturing it is advantageous to use specially calculated rulers prescribing a cutting plan for the remainder left after several parts have been cut out [[#References|[1]]]. In the clothing industry specialized mini-computers solving only the cutting problem are used to design the cutting of fabric rolls of different lengths (see [[#References|[4]]]). In metallurgy the length of a steel plate is measured at the rolling mill while in operation and the cutting device is controlled automatically on the basis of the solution of the cutting problem obtained from a computer (see [[#References|[5]]]). In the glass industry outside the USSR, defects of glass are detected automatically and computers solve a cutting problem subject to the requirement that defects should be avoided. In the timber industry logs also have a scatter of sizes and forms. But the coefficients $a_{ijk}$ (characterizing the output of boards of type $j$ from logs of type $k$ with the saws positioned according to variant $i$) are statistically stable. In this branch of industry the cutting problem was mathematically formulated long ago (see [[#References|[1]]]) and was solved effectively in reality (see [[#References|[6]]]).

For the case of mass production and curved parts useful programs were developed which allow one to choose optimal patterns for one- and two-row stamping in the case of an infinite strip (see [[#References|[7]]], [[#References|[8]]]), or for stamping strips cut out from a given plate. Judging by eye also remains effective for preliminary planning sets of patterns involving various curved parts with subsequent solution of the linear programming problem on the chosen set of patterns.

In the case of individual production the cutting problem requires the solution not of a linear programming problem but of a more complicated [[Integer programming|integer programming]] problem, again with an implicit coefficient matrix since the feasible allocations have not been listed. For linear and rectangular parts applicable heuristic approximation algorithms have been programmed (see [[#References|[2]]]).

There have been some developments for the case of curved parts in individual production but up to now (1983) satisfactory computer algorithms have not been developed yet. The shipbuilding industry is among the most interested in algorithms of this kind. Fairly effective are interactive systems combining the advantages of the human eye assessments with the computer's ability to process corrections, calculations and output of the designed variants.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.V. Kantorovich,   V.A. Zalgaller,   "Rational cutting of industrial materials" , Novosibirsk  (1971)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.A. Mukhacheva,   ''Kuzn.-Shtampovochn. Proizvodstvo'' , '''6'''  (1979)  pp. 14–17</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> , ''Software for linear and rectangular cutting. Proc. All-Union Sci. Sem.'' , Ufa  (1980)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  I.I. Galynker,   I.V. Safronova,   "Mechanical technology in the clothing industry" , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  V. Epstein,   A. Lagutin,   ''Material.-Tekhn. Snabzhenie'' , '''11'''  (1976)  pp. 77–81</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  I.V. Sobolev,   "Production control in the timber industry" , Petrozavodsk  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  L.B. Belyakova,   N.O. Ryabinina,   ''Kuzn.-Shtampovochn. Proizvodstvo'' , '''11'''  (1977)  pp. 25–28</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  Yu.G. Stoyan,   A.A. Panasenko,   "Periodical allocation of geometrical objects" , Kiev  (1978)  (In Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.E. Beasley,   "An algorithm for the two-dimensional assortment problem"  ''European J. Operations Research'' , '''19'''  (1985)  pp. 253–261</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.C. Gilhore,   R.E. Gohory,   "A linear programming approach to the cutting Stock problem"  ''Operatons Research'' , '''11'''  (1963)  pp. 863–888</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L.S. Ladson,   "Optimization theory for large systems" , Macmillan  (1970)  pp. Chapt. 4</TD></TR></table>