Оптималды кесу мәселесі: Операциялық зерттеулердегі қолданысы

Mathematical problem in operations research

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.

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.

Cutting stock problems can be classified in several ways. 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. When either the master item or the required parts are irregular shaped (a situation often encountered in the leather, textile, metals industries) this is referred to as the nesting problem. 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)).

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:
Two stage, where the rolls produced in the first stage are then processed a second time. For instance, all office stationery (e. g. A4 size in Europe, Letter size in US) 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 (from an energy or material use perspective) and what is efficient for the primary stage may be inefficient for the secondary, leading to trade offs. Metallised film (used in packaging of snacks), and plastic extrusion on paper (used in liquid packaging, e. g. juice cartons) 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 (also known as a web welding) secondary process, whereby two reels (produced by slitting the initial jumbo reels) are joined side by side (with a little overlap) 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 (both in terms of width and length). 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. The guillotine problem is another 2 D problem of cutting sheets into rectangles of specified sizes, however only cuts that continue all the way across each sheet are allowed. Industrial applications of this problem can be found in the glass industry. The cutting stock problem of determining, for the one dimensional case, the best master size that will meet given demand is known as the assortment problem.

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.