Optimal cutting of materials

The most important factor in increasing the efficiency of industrial production is the saving of material resources. The saving of materials is a rather complex complex task, in the solution of which it is necessary to take into account constructive, technological and organizational factors. Careful analysis of each of them allows you to develop various methods and tools that allow you to save resources. One of the effective means, providing a significant (up to 20%) economy of material resources, is their optimal or rational cutting.

In practice, material resources are most often represented in the form of rolls (Fig. 1), strips, rectangular sheets, rods, etc.

In general, cutting, for example, of sheet and long products is the selection of economically feasible options for placing blanks on the material or blank strips on sheets in accordance with the selected order form, taking into account the available equipment. An example of industrial equipment for cutting rolls is presented in Fig.2.

By optimal cutting, we mean a cutting that, with this type of production, makes it possible to produce the final product with minimal labor, time and materials with the use of existing equipment. Consequently, the definition of optimal cutting is a complex multifactorial task. Even if we simplify the solution of this problem to the level of the problem of two-dimensional (2D) rectangular cutting, and in this case (this problem) will belong to the class of NP-difficult combinatorial optimization problems, that is, there is no polynomial complexity algorithm for its exact solution. In addition, such a problem contains an NP-difficult problem also as a subtask. Therefore, in solving even this problem, exhaustive (exact) algorithms reduce to a complete search of all possible variants. But the use of precise algorithms for solving the cutting problems led to significant expenditures of computer time, which was not always economically expedient. Currently, there are methods of solution based on different approaches, which make it possible to reduce the amount of calculations. In particular, in the whole world, great importance has always been given to the development and investigation of heuristic optimization methods, including the so-called meta-heuristic methods, which are invariant with respect to the type of problem.

However, taking into account the modern development of high-performance computing equipment (such as CUDA - Compute Unified Device Architecture), there are more opportunities for using precise algorithms, which leads to an increase in the accuracy of calculations. CUDA is a software and hardware architecture that allows you to significantly (by several orders of magnitude) increase computer processing power due to the use of graphics processors of the video module (video card). The architecture of the video card allows you to "parallelize" the processing of data. In addition, the exchange rate between the memory and the video processor is much higher than in the classical scheme: RAM is a cache-central processing unit. This is due to the parallelization of data - at a time when one data in the video card starts to be processed by a single stream processor, other data is simultaneously loaded into another. In the financial market, for example, the companies Numerix and CompatibL when using CUDA in the software product designed for the analysis of counterparty risk, achieved an acceleration of work by 18 times. Numerix is ​​used by nearly 400 financial institutions in the world, including BNP Paribas in the banking sector.

CUDA® from NVIDIA is a parallel computing platform and programming model that has a set of extensions for programming languages C and C ++, which allow expressing the parallelism of data and tasks at the level of small and large structural units. This greatly simplifies the use of this technology for nesting and packaging problems, and it is possible to implement both exact and heuristic algorithms with a significant (more than 10 times) reduction in computer time spent on calculations.

The simplest variant for determining the optimal cutting is a one-dimensional (1D) linear cutting (Fig. The material for cutting into blanks of given sizes comes in the form of identical rolls (rods, strips). In this case, a map of all possible cutting variants is made in one dimension (for example, along the length or width of the material), the remainder in each variant being less than the length (or width) of the blank having the shortest (or width) length. When drawing a nesting chart, it is also necessary to take into account such technological parameters of the equipment for cutting (stamping, etc.), as the thickness of the cut, the width of the side edges, and the like.

In this case, usually, a mathematical model of the problem is compiled in a standard form with a linear function (objective function) (1), which reaches a minimum and a system of constraints (2) under conditions of non-negativity (3).

Then the system of linear algebraic equations is solved by the Jordan-Gauss method. A feasible solution for which the objective function will reach a maximum (or minimum) will be the optimal solution. This algorithm is implemented in the software product "C-MES: Production Management "(hereinafter referred to as C-MES). In C-MES with 1D cutting of rolls, optimization of knife change is also provided, i.e. Further processing of the found solution is carried out to achieve a minimum number of shifts of knives

The economic effect of using C-MES for linear cutting (rolls, rods, rails, etc.) is as follows:

• increase in output of finished products (from 2% and above);
• reduction of expenses for equipment adjustment;
• Reduction of the terms of fulfillment of production orders (up to 10%);
• increase the speed of planning.
• Total savings in this case will be calculated by the formula:

                                    Э = ЭН + ЭСД,

where EN is the savings from a decrease in the rate of consumption of material resources,

ESD - saving on wages of employees of the enterprise and fees charged on their salary.

Using the example of the calculation of the economic efficiency of the optimal cutting method for metalworking enterprises, it follows that as a result of the application of the optimal material cutting method, the cost of production is reduced by an average of 9.32%.

Of considerable interest is the problem of two-dimensional (2D) rectangular nesting. This is due to the vast scope of practical application of these tasks, as well as the high complexity of the problem being solved. In view of the complexity of this task, heuristic decision algorithms are widely used in practice. The emergence and development of probabilistic methods of local search for the optimum led to the development of algorithms that serve as decoders in multipass algorithms.

In essence, the placement of the rectangles is reduced to their packing, when they do not have intersections. Most of the exact methods for solving this problem are reduced to a search of the whole set of admissible solutions and the finding of an optimum among them. The efficiency of the search can be improved by applying various kinds of improvements (improvements). A large group of methods of accelerated search is known as the "branch and boundary method", which is a sort of complete search. In the calculation process, sets (subsets) of admissible, but not optimal solutions are removed.

Depending on the current input data, one or another method of improving the search is selected and preliminary preparation of the input data for the selected sorting method is also carried out. These operations reduce the computation time to an acceptable (economical) level. The conditions for placing the rectangles are described by a system of linear inequalities and by the same number of integer variables. The resulting system of inequalities is solved using linear programming methods. In this case, the algorithm makes it possible to solve the problem of rectangular cutting accurately (or optimally). The result of this algorithm implemented in the software product "C-MES: Production Management" is shown in Fig.4.

Additional optimization is also possible to increase the area of one of the residues (Fig. 5).

The economic effect of using C-MES for rectangular cutting is composed of the same components as for linear cutting. But the increase in output of finished goods can be up to 10%, and the efficiency of drawing up plans can increase by 50%. This is explained by the fact that this type of cutting is more labor-intensive operation, and in most cases the result of planning such a task without using effective tools will not be optimal. Consequently, the economic effect of the introduction of C-MES for 2D nesting will be more significant with the optimal loading of equipment that allows to produce rectangular cutting (Fig 6).

When solving problems of 3D nesting (packaging) (3D), in most cases, heuristic (approximate) algorithms are used. Any approximate solution assumes the existence of an algorithm that would allow us to determine exactly how to produce a 3D cut or place boxes in a container. Basically, they are built on decomposition - the note of these problems to problems of smaller dimension. Various variants of this procedure are applied - for example, splitting into layers and filling each layer according to an individual algorithm or "wall construction". There are algorithms when after filling each layer or "building a wall" additional optimization is performed.

The number of precise algorithms for solving the three-dimensional nesting-packing problem is limited in comparison with the number of available heuristic optimization methods. One of the reasons for this is the complexity of presenting probable packaging and imposing constraints on real problems. Nevertheless, various methods have been developed to solve this problem. For example, a model based on the Cartesian coordinate system provides vertical, horizontal stability and in most cases allows finding the optimal solution. The method of planes for solving 3D nesting problems is theoretically justified. A variant of the direction of loading of a three-dimensional orthogonal container, using the example of implementing algorithms for solving orthogonal packaging problems of objects, is shown in Fig.7.

In the C-MES concept, the definition of optimal 3D nesting is also used as a solution to the problem of packing cargo during transportation between production sites of the enterprise.

Thus, the program (algorithm) of any (1D, 2D, 3D) nesting includes two basic steps: the stage of plotting the map of all possible variants of nesting and the step of calculating optimal nesting options.

In connection with the trend towards the widespread use of artificial neural networks (INS) in recent years, it seems possible and even promising to use them for solving 3D nesting problems, despite the fact that training INS is a complex and time-consuming process.

It should be noted that in the world there are many software products for the formation of different types of cuttings, but in general they are supplied as separate solutions. C-MES is a comprehensive software product designed to perform the following functions:

• state control and resource allocation;
• dispatching production;
• collection and storage of data;
• management of production personnel;
• quality control;
• management of production processes;
• tracing and genealogy of products;
• efficiency analysis.

The nesting function is integrated into C-MES and therefore allows to calculate optimal cuts based on the current situation in a particular production based on real-time data and therefore more economically efficient. These data are formed during monitoring and dispatching of the following production procedures (functions):

• management of needs and methods of reproduction;
• calculation of packages for work centers with batch mode of operation;
• formation of the production schedule, including, taking into account the supply chains;
• collection of the fact of fulfillment;
• re-planning taking into account deviations.

Given the modularity of the C-MES, the nesting module can be used in conjunction with other modules and independently, thereby providing flexibility in the application of the nesting function in the current production environment. However, for effective interaction between production processes within the enterprise, it is more expedient to use the calculation of cutting in combination with the above functions.

C-MES is a complex business application designed to perform such large computing tasks as nesting tasks. Economically feasible time costs for solving 2D and 3D cuts can only be obtained by using parallel computations that can be implemented in several ways: either locally (for example, though not in all cases using CUDA technology) or using data centers (DPC). C-MES can be supplied in both versions, while the second option (use of data centers in the SaaS model) for small and medium-sized enterprises is less expensive, and such companies can use large computing power to enable all stakeholders and departments to make effective decisions.