Linear cutting in Excel. Programs for optimizing material cutting

07.03.2022

Economical linear cutting of materials (cutting of moldings) is relevant for many industries and in construction. This is sawing logs and boards in woodworking, cutting bars, reinforcing bars, angles, channels, pipes, I-beams into blanks ...

In the production of metal structures and mechanical engineering, transverse cutting of rolls with paper and fabric in the pulp and light industry.

Despite the apparent simplicity, the solution of linear cutting problems is not very easy, but worthwhile. The introduction of a scientific approach to cutting molded materials allows you to reduce the cost of them, sometimes by more than 10%! Read the article to the end and make sure these words are right.

The topic under consideration relates to linear programming problems. To solve such problems, scientists in the last 70 years have come up with several different methods.

Method of indices L.V. Kantorovich and V.A. Zalgallera, with a certain skill, allows you to effectively perform linear cutting "manually" without the use of computer technology. I recommend to curious readers to familiarize themselves with this method by reading the book of the above-named authors “Rational Cutting of Industrial Materials”.

The simplex method based on the ideas of L.V. Kantorovich, was described and developed in detail by a number of scientists from the USA in the middle of the 20th century. Add-in MS Excel "Search for a solution" (Solver) uses this algorithm. It is with this method thatexcelwe will solve the problem of linear cutting in this article.

Later, genetic, greedy and ant colony algorithms appeared and were developed. However, we will confine ourselves to listing them and get down to business, without climbing into the jungle of theories (although there, “in the wilds”, it is very interesting).

Let's turn on Excel and, using a simple example of cutting metal rods into parts, we will get acquainted with one of the ways to solve practical problems of linear cutting. Mathematicians often refer to this problem as the "cutting problem".

I did not invent the initial data for the example, but took it from the article by Pokrovsky M.A. "Minimizing the inevitable losses of materials in industrial production when cutting them into piece blanks" published in No. 5 (May 2015) of the electronic scientific and technical journal "Engineering Bulletin" published by FGBOU VPO "MSTU im. N.E. Bauman (link:engbul. bmstu. en/ doc/775784. html).

The goal that I pursued was to compare the results of solving the problem.

An example of solving the problem of linear cutting in MS Excel.

Let's agree that:

1. Billets are raw material in the form of bars, strips, rods, etc. the same length.

2. Details are elements that need to be obtained by cutting the original blanks into pieces.

3. The width of the saw, cut, rub is taken equal to zero.

The task:

To complete one of the orders, the procurement section must chop three standard sizes of parts on combined shears from identical bars-blanks 1500 mm long:

151 pieces 330 mm long

206 pieces 270 mm long

163 pieces 190 mm long

It is required to find the optimal cutting plan that uses the minimum amount of material and, accordingly, gives the minimum amount of waste.

Initial data:

1. The length of the original blanks Lh in millimeters we write in the combined cell

D3E3F3: 1500

2. We assign numbers i all standard sizes of parts, starting from the longest and ending with the shortest in the cells

D4; E4; F4: 1; 2; 3

3. Part lengths Ldi in millimeters we write in

D5; E5; F5: 330; 270; 190

4. Number of details Ndi in pieces put into

D6; E6; F6: 151; 206; 163

5. We proceed to a very important stage - filling in the cutting options.

Must remember and understand 2 principles for doing this job.

1. Waste lengths must be less than the smallest part ( 0< lo j < Ldmin ).

2. We start “laying” parts into the workpiece with the largest parts and with the largest number of them, consistently moving in the direction of decreasing.

If there is no part size in the cutting option, then we leave the cell empty, we will not write zero to facilitate the visual perception of the table.

Cutting option No. 1:

An attempt to cut out 5 parts No. 1 from one blank is impossible, so we write in the cell

It is also impossible to add part No. 2 or part No. 3 to the nest, so we leave the cells empty

Cutting option No. 2:

We decrease the number of parts No. 1 by 1 from the previous version and write it in

We are trying to add 2 parts No. 2 - it doesn’t work, so we add to

It remains possible to supplement the cutting with detail No. 3. We enter into

Adhering to the principles voiced, we fill in by analogy all the 18 cutting options possible in this case.

Having made a couple of tables of cutting options yourself, you will understand the logic of actions and will spend a few minutes on this work.

If the first principle is not fulfilled during cutting, then the cell with the length of the departure is automatically painted in red. The conditional formatting applied to cells G7…G24 will clearly help you in this work.

In cells H7 ... H24 do not write anything! They are used to display the result of the solution!

Preparing for the solution:

* In cells G7 ... G24, the lengths of waste (cuts) remaining as a result of cutting are calculated according to the formula

lo j = L h -Σ (Ldi * Ndij )

6. The number of parts of each standard size, made according to all applied nesting options, will be calculated in cells D26, E26 and F26 according to the formula

Ndicalc = Σ (Ndij * Nhj )

The number of parts in the cutting plan found at the end of the solution must fully correspond to the specified number of parts!

7. The required number of workpieces to complete the optimal cutting plan will be determined in the combined cell D27E27F27 using the formula

N calc =ΣN hj

8. The total length of all blanks required to perform a linear nest of all parts will be calculated in the combined cell D28E28F28 using the formula

Lh Σ = L h*Nfrom calculation

9. The total length of all waste resulting from the execution of the found cutting plan will be calculated in the combined cell D29E29F29 using the formula

Labout Σ = Σ (Laboutj * Nhj )

10. The proportion of waste generated by the optimal linear cutting plan from the total amount of material used will be calculated in the merged cell D30E30F30 using the formula

Ωo = Lo Σ /Lз Σ

Solution:

The preparation is completed, 18 options for the most optimal cutting of one workpiece into parts are determined and all the necessary formulas are entered. Now we have to solve the main problem: to determine optimal cutting plan - how many blanks, and according to what cutting options to cut to finally get all the necessary parts in the right quantity with a minimum of waste.

1. Select in the main menu "Service" - "Search for a solution ...".

2. In the window of the same name "Search for a solution" that appears, we make the settings.

2.1. We assign the total length of the waste to the objective function Lo Σ and enter the link in the target cell window.

2.2. Set the "Equal:" switch to the "minimum value" position.

2.3. Specify cells with variables Nz j in the Changing Cells window.

2.4. We enter restrictions in the window of the same name. As conditions, we indicate the need for equality of the given Nd i and settlement Nd icalc the number of parts, as well as variables Nz j- the estimated number of blanks by cutting options - we impose a restriction: these must be integers.

3. We press the "Parameters" button and in the "Solution search parameters" window that pops up, we make the settings as shown in the following screenshot. Close the window with the OK button.

4. In the "Search for a solution" window, click the "Run" button and wait for Excel to find a solution. This may take several minutes.

5. After saving the found solution with the OK button, the results will be displayed in cells H7 ... H24 on the Excel sheet.

The following picture shows the found optimal linear cutting plan.

What is the result?

Linear cutting in Excel blanks for tasks like the one discussed in this article is performed by the method described above in 10-15 minutes! “Manually”, without knowing the method of Kantorovich indices, you will not find a solution in such a time.

By running the "Search for a solution" several times with different search parameters, we managed to find 5 different plans for felling blanks. All 5 plans require the same number of blanks - 93 and give only 2.21% waste!!! These plans are almost 6% better than the plan calculated by Pokrovsky and more than 10% more economical than the "Traditional" plan (see the link to the original source in the first part of the article). A very worthy result was achieved quickly and without the use of expensive programs.

It should be noted that the Excel Solver add-in ("Search for a solution"), which uses the simplex method when solving linear programming problems, can work with no more than 200 variables. As applied to the linear cutting problem we have considered, this means that the number of cuttings cannot exceed 200 variants. For simple tasks, this is enough. For more complex tasks, you should try to apply a “mixture” of the “greedy” algorithm and the simplex Solver method, selecting no more than 200 most economical ones from the complete list of cuttings. Then we stock up on patience and achieve results. You can try to break a complex problem into several simple ones, but the “optimality level” of the solution found will most likely be lower.

Perhaps the considered option for solving linear cutting issues is not “aerobatics”, but it is definitely a step forward compared to the “traditional” approach in many industries.

The use of the MS Excel "Search for a Solution" (Solver) add-in was already discussed on the blog once in an article. I think that this wonderful tool is worthy of close attention and will help more than once gracefully and quickly solve a number of new non-trivial problems.

P.S. Links to the best free linear cutting software I found on the web:

http://stroymaterial-buy.ru/raschet/70-raskroy-lineynih-izdeliy.html

http://forum-okna.ru/index.php?app=core&module=attach§ion=attach &attach_id=7508

http://forum.dwg.ru/attachment.php?attachmentid=114501&d=13823277 74

http://www.planetcalc.ru/917/

The programs on the last two links implement greedy heuristics and perform linear nesting in the task from the article, using as many as 103 blanks. The use of greedy algorithms is justified in cases where it is necessary to reduce the total time of the cutting operation with too many cutting options in more optimal plans.

Below the article in the "Reviews" block, you can write your comments, dear readers.

See Linear Programming Models for Nesting Problems.

Example #1. The products of the paper company are produced in the form of paper rolls of standard width - 2 meters each. On special orders of consumers, the company supplies rolls of other sizes, for which standard rolls are cut. Typical orders for rolls of non-standard sizes are given in table.

It is required to find such combinations of different options for cutting standard rolls in order to fully satisfy the received orders with minimal losses (waste).
Let's consider all possible options for cutting a standard roll, we will give the corresponding data in Table.

Roll Width(m)	Roll cutting options						Minimum number of rolls
Roll Width(m)	1	2	3	4	5	6	Minimum number of rolls
0,5	0	2	2	4	1	0	150
0,7	1	1	0	0	2	0	200
0,9	1	0	1	0	0	2	300
Waste in m	0,4	0,3	0,1	0	0,1	0,2	-

Let's define variables:
X j - the number of standard rolls cut according to the option j, j=1, 2, 3,4,5, 6.
Limitations are directly related to the requirement to ensure the production of the required number of non-standard rolls. Using the data in the table, we get:
2X 2 + 2 X 3 + 4 X 4 + X 5 \u003d 150 - the number of rolls 0.5 m wide,
X 1 + X 2 + 2 X 5 \u003d 200 - the number of rolls 0.7 m wide,
X 1 + X 3 + 2 X 6 \u003d 300 - the number of rolls 0.9 m wide.

The expression for the total amount of paper loss (waste) (in m) is
0.4X 1 + 0.3 X 2 + 0.1 X 3 + 0.1 X 5 + 0.2 X 6.

Thus, the general mathematical model has the form
min f (x) \u003d 0.4 X 1 + 0.3X 2 + 0.1X 3 + 0.1X 5 + 0.2X 6.
with restrictions:
2X 2 + 2 X 3 + 4 X 4 + X 5 = 150
X 2 + X 2 + 2 X 5 = 200
X 2 + X 3 + 2 X 6 = 300

The problem of cutting materials

This task is to develop such a plan that provides the necessary set of products with minimal waste (in length, area, weight, cost, etc.) when cutting materials or provides the maximum number of product sets. Example #2. It is required to develop an optimal plan for cutting standard steel sheets, ensuring the output of the planned number of blanks of different types with minimal total waste, if it is known that four types of different blanks must be cut from a batch of sheet steel in the amount of bi (i = 1, 2, ..., 4) pieces . A steel sheet of standard sizes can be cut in four ways. Each possible cutting method corresponds to a cutting chart. From the cutting charts, the output of workpieces in pieces of different types a ij (i = 1, 2,…4; j = 1,2,…,4), as well as the waste area cj (j = 1, 2,…,n) at cutting of one sheet of steel according to the j-th method of cutting. How many sheets of steel must be cut in one way or another so that waste is minimal?

Table 3

Kinds blanks	Task plan for the number of blanks (b 1)	Output of blanks (pcs) of different types from nesting charts (a ij)
Kinds blanks	Task plan for the number of blanks (b 1)	1	2	3	4
1	240	1	4	0	1
2	200	1	0	4	0
3	120	1	0	0	3
4	140	1	1	0	3
Waste area, m 2 (cj)		1,4	0,1	2,1	0,1

Let's make an economic-mathematical model of the problem. Let us denote by x j - the amount of source material (steel sheets) that must be cut according to one of the methods j. Constraints in the task must correspond to the planned output of blanks of various types. The objective function is to find the minimum waste when cutting

F=1.4 x 1 +0.1 x 2 +2.1 x 3 +0.1 x 4 →(min)..
Restrictions on the output of blanks of the i-th type for all j cutting methods:

Example #3. For cutting (sawing, processing) the material of one sample is supplied in the amount of a units. It is required to make from it l different components in quantities proportional to the numbers b 1 , b 2 ,…,b l (completeness condition). Each unit of material can be cut in n different ways, and using the i-th method (i = 1, 2,…,n) gives a ik units of the k-th product (k = 1, 2,…,l). It is necessary to find a cutting plan that provides the maximum number of sets.
Let's make an economic-mathematical model of the problem.
Let x i denote the number of units of material cut by the i-th method, and x the number of manufactured sets of products. Then the objective function is reduced to finding

F=x→(max),
with restrictions: by the total amount of material equal to the sum of its units, cut in various ways; according to the requirement of completeness and non-negativity of variables.

Example #4. The company has logs of length L m, which must be cut into pieces of length l 1 , l 2 , l 3 m in the amount of p 1 , p 2 , p 3 respectively.
It is necessary to draw up an optimal plan for cutting the material, which ensures minimal waste, subject to the plan for the output of blanks. The initial data are given in the table.

A task	Length	Blanks dimensions, m			Number of blanks, pcs.
A task	Length	l 1	l 2	l 3	p1	p2	p 3
68	6,5	2,1	2,3	1,4	600	720	900

Solution: First, let's make a mathematical model of our problem. Possible cutting options and waste for each of them will be written in the form of a table.

Workpiece length	Cutting options							Number of blanks
Workpiece length	1	2	3	4	5	6	7	Number of blanks
2,1	3	2	2	1	1	0	0	600
2,3	0	1	0	1	0	2	1	720
1,4	0	0	1	1	3	1	3	900
Remaining, m	0,2	0	0,9	0,7	0,2	0,5	0

Denote by x i the number of logs cut according to the i-th option (i=1..7). Then the total residual waste will be written as a linear function:
Z = 0.2x1 + 0x2 + 0.9x3 + 0.7x4 + 0.2x5 + 0.5x6 + 0x7
At the same time, the conditions for fulfilling the plan in terms of the number of blanks must be met, i.e.
3x1 + 2x2 + 2x3 + x4 + x5 = 600
x2 + x4 + 2x6 + x7 = 720
x 3 + x 4 + 3x 5 + x 6 + 3x 7 = 900

Thus, to solve the stated problem, it is necessary to find minZ under restrictions. Since minZ = -max(-Z(x)), then instead of the function minimization problem, we will solve the function maximization problem:
Z = -(0.2x 1 + 0x 2 + 0.9x 3 + 0.7x 4 + 0.2x 5 + 0.5x 6 + 0x 7)

Example number 5. For sewing one product, you need to cut out 6 parts from the fabric. At the garment factory, two options for cutting the fabric were developed. The table (located below) shows the characteristics of cutting options for 10 m 2 of fabric, completeness, i.e. the number of parts of a certain type that are needed to sew one product. The monthly supply of fabric for sewing products of this type is 405 m 2 . In the coming evening, it is planned to sew 90 items.
Build a mathematical model of the problem that allows you to complete the tailoring plan with a minimum amount of waste in the next month.

Table - Characteristics of options for cutting fabric pieces of 10m 2

Cutting option	Number of parts, piece/cut						Waste, m 2 / cut
Cutting option	1	2	3	4	5	6	Waste, m 2 / cut
1	60	0	90	40	70	90	0,5
2	80	35	20	78	15	0	0,35
Completeness, piece/product	1	2	2	2	2	2

Mathematical statement of the problem

Task Variables
In this problem, the required values are not explicitly indicated, but it is said that a monthly plan for sewing 90 products must be completed. For tailoring 90 products per month, it is required to cut a strictly defined number of parts. The cut is made from pieces of fabric of 10 m 2 in two different ways, which allow you to get a different number of details. Since it is not known in advance how much fabric will be cut by the first method and how much by the second, then as the desired values, you can set the number of fabric segments of 10 m 2 cut by each of the methods:
x 1 - the number of pieces of fabric of 10m 2, cut by the first method during the month, [cut / month];
x 2 - the number of pieces of fabric, 10m 2 each, cut by the first method during the month, [cut / month];

objective function
The goal of solving the problem is to fulfill the plan with a minimum amount of waste. Since the number of products is strictly planned (90 pcs/month), this parameter does not describe the CF, but refers to a constraint, the failure of which means that the problem has not been solved. And the criterion for the effectiveness of the implementation of the plan is the parameter "amount of waste", which must be minimized. Since when cutting one piece (10 m 2) of fabric according to the 1st option, 0.5 m 2 of waste is obtained, and according to the 2nd option - 0.35 m 2 (see table 1), the total amount of waste when cutting (CF) has view
L(x) = 0.5x1 + 0.35x2 = min,

Restrictions
The number of fabric cuts in various ways is limited by the following conditions:

A plan for tailoring products must be completed, in other words, the total number of cut parts must be such that 90 products per month can be sewn from it, namely: there must be at least 90 of the 1st type and parts of other types - at least 180 (see completeness in the table).
Fabric consumption should not exceed a monthly stock in the warehouse;
The number of pieces of cut fabric cannot be negative.

The restriction on the plan for sewing coats has the following meaningful form of entry.
(Total number of parts No. 1 cut for all options) ≥ (90 pieces);
(Total number of parts No. 2 cut for all options) ≥ (180 pieces);
(Total number of parts No. 6 cut for all options) ≥ (180 pieces);

Mathematically, these restrictions are written as :
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;

The tissue consumption limit has the following forms of recording:
meaningful
(total fabric cut per month)≤ (405m2)
mathematical
x 1 + x 2 ≤405/10

The non-negativity of the number of cut segments is given in the form
x 1 ≥ 0, x 2 ≥ 0

Thus, the mathematical model of the problem has the form
L(x) \u003d 0.5x 1 + 0.35x 2 \u003d min [m 2 waste / month],
60x1 + 80x2 ≥90;
35x2 ≥180;
90x1 + 20x2 ≥180;
40x1 + 78x2 ≥180;
70x1 + 15x2 ≥180;
90x1 ≥180;
x 1 + x 2 ≤40.5
x 1 ≥ 0, x 2 ≥ 0

Example number 6. There are 69 pipes for the heating network, 1070 cm each. They must be cut into pipes of 130, 150 and 310 cm. Find such an option for cutting the incoming pipes, in which the waste would be minimal.

Stage 1. We determine the options for the optimal cutting of pipes.

Cutting options	1	2	3	4	5	6	7	8	9	10	11	12	13
310	3	2	2	2	2	1	1	1	1	0	0	0	0
150	0	3	2	1	0	3	2	1	0	3	2	1	0
130	1	0	1	2	3	2	3	4	5	4	5	7	8
Remains	10	0	20	40	60	50	70	90	110	100	120	10	30

Stage 2.
Let's make an economic-mathematical model of the problem. Let's denote by x j - the number of pipes that need to be cut according to one of the ways j. The objective function is to find the minimum waste when cutting:
10x 1 + 20x 3 + 40x 4 + 60x 5 + 50x 6 + 70x 7 + 90x 8 + 110x 9 + 100x 10 + 120x 11 + 10x 12 + 30x 13 → min

x 1 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 + x 10 + x 11 + x 12 + x 13 = 69

Answer: only the second cut option should be used (zero waste)

The program is designed to optimize the cutting of profiles and other long materials (bar, log, pipe, window sill).
The "dense stacking" algorithm is used, that is, the taken product is placed on the shortest rest of the workpiece on which it is placed. If it does not fit anywhere, a new blank is taken. The task of optimization is to find a sequence of products in which fewer blanks will be used and the length of business trimmings will be longer. On the first measure, items are placed on the whips in random order. There is an "initial population". In the process of solving, the population mutates and multiplies, unsuccessful specimens die, and the best ones continue to evolve. Everything, as in the animal and plant world + artificial selection.

Live demo on the site

Start

Advantages

Windowsoft:cutting provides high quality cut maps. Numerous implementations confirm the actual cutting factor of no more than 1% when optimizing batches from 30 contours (~120 cuts)
To read the initial data and record the results of cutting, the program uses simple text file formats, which simplifies integration with accounting systems implemented by the customer
If necessary, nesting can be performed under Linux or OS X in a browser or Node.js passing parameters via url, web socket or javascript objects

Linear optimizer algorithms

Windowsoft:Cutting uses a genetic algorithm. Its essence is this:
Let's call each distribution of products by whips a solution. Let us define an objective function that allows us to compare the quality of solutions. Let us form several arbitrary solutions, call them a generation. Let's define the rules for obtaining the next generation. Instances with the best objective function transfer most of their "gene pool", this is our "artificial selection". Now it remains to leave the system to itself, let it mutate and optimize the cutting results
During the development process, the "Monte Carlo" method was tested, when our "instances" are random and do not depend on each other, and "Ant algorithms" (ACO- ant colony optimization). All methods proved to be quite efficient, but the genetic algorithm turned out to be slightly more efficient.

Delivery options

There are two delivery options for the Windowsoft:cutting cutting module - as part of an integrated solution for Custom Production Management and as a separate executable file. Interaction with the cutting program in the first scenario is completely hidden from the user. The operator works with standard 1C documents:

Based on customer orders, a production plan is formed
Based on the plan - shift tasks with a list of products and necessary materials
Nesting is optimized inside the production order
In the process of optimization, the program takes off the business trim from the work in progress and places the newly formed business trim in the cellular warehouse
A shift job is able to print cutting forms for manual production or generate files for CNC machines
Also, labels for cut products and layout schemes for carts and pyramids are printed from a shift job.
On the basis of production tasks, requirements are formed - invoices for the transfer of materials to the workshop, taking into account the needs and standard packaging

Software Interface (Linear Nesting API)

The input data file, setup.ini, is placed in the folder with the executable file.
Output data files - result.txt, resultproduct.txt and resultstick.txt - are generated in the same folder.
You can download files with Oknosoft:cutting demo data from the link at the end of the page. The files use the following tags:

Outputvariant - the structure of the file's output file. Possible values: tab, oknosoft, default oknosoft
- In the "oknosoft" option, the resultproduct.txt and resultstick.txt files are generated with information about the placement of products on blanks and the resulting trim
- The "tab" variant displays five values separated by "tab" characters: product length, whip number, whip length, cut number and workpiece remainder
Algorithm - the algorithm used. Possible values: random, conservative, genetic, default genetic
- Random - random selection of options
- Conservative - instances of the next iteration come from the same "parent"
- Genetic - from two parents
Variation - variability, parameter of "conservative" and "genetic" algorithms. The higher, the less the offspring "similar" to the parents. The default is 1.
Generations - number of algorithm iterations, default 40000
Persons - the number of "instances" in the "population", the number of solutions used in one iteration. The "random" algorithm simply does generations*persons of iterations with one instance (solution)
KnifeWidth - saw width
StickLength - the length of the new stick
Products - product length
Scraps - the length of the scrap used in the nest
Wrongsnipmin - the minimum length of a "bad" swatch
Wrongsnipmax - the maximum length of a "bad" cut
Optimization results won't have clippings with lengths between Wrongsnipmin and Wrongsnipmax

Pair cutting

Used when preparing data for machines that support pair sawing. In this case, two profile whips are placed in the machine at once, and in one cutting cycle, two identical semi-finished products are formed.

The task of pair cutting is solved by grouping data before transferring it to the optimization program and then duplicating the results of cutting into pairs of products and workpieces. When nesting inside UPZP, the system takes into account the properties of the nomenclature and uses single or pair cutting, depending on the capabilities of cutting machines

Cutting a large number of products

On the one hand, in order to achieve a high quality of optimization, a significant number of products of different lengths must be received at the input of the program so that the optimizer has "what to sort". On the other hand, with very large batches, the probability of finding the maximum at a fixed number of iterations of the enumeration decreases. Experiments have shown that a batch of 60-120 blanks is optimal (which corresponds to a production cycle of 30-60 products with paired cutting). If you need to optimize more than 120 workpieces, the best results can be achieved by dividing the problem into N parts and performing successive optimizations for each part. Processing the formation of batches of production tasks is able to group products by type of profile and select products with maximum dispersion into shift tasks, saving the operator from the routine work of compiling production documents

Download cutting examples and documentation

Demo single and double cut cards: 60.01 Cutting sheets
Documentation and sample files:

Cutting Line - Program for linear cutting

Version: 2.49

Bit depth: 32bit

Tabletka: Cured

When developing the algorithmic part of the programs, the principle of waste minimization was chosen as the main criterion, and when developing the interface part, the author sought to make the programs simple and convenient in everyday use.

The program of optimal cutting of linear blanks into parts

The program has the following functions and features:

Our price list includes three products related to the common theme of sorting and optimization:

Linear cutting program for profiles and long materials
Program for two-dimensional cutting of glass, sandwiches, chipboard and other sheet materials
Route optimization program for solving logistics problems

Nesting modules can be supplied both as part of the integrated solution Windowsoft: Custom Production Management, and as separate programs. When calling cutting programs from 1C, no import is required - data export to intermediate files. The user works in a standard interface, and all the subtleties of 1C interaction with external optimizers perform processing of filling in tabular parts. For the purposes of accounting for inventory balances, business trimmings and materials in production, standard documents and registers of typical 1C configurations are used.

Linear cutting (profile, pipe, log)

Provides inventory-confirmed crop percentage

Live demo on the site

The example below is not a static image, but a working web application.
You can start profile cutting with the button Start, set your dimensions of products and workpieces, change the optimization settings and evaluate the solution.
Of course, the optimizer in the browser is slower than the native program, but it allows you to get workable results for free without having to download and install anything on your computer.

20000 r.

Cutting glass and sheet materials

Generates cutting charts of the highest quality. Provides a percentage of material savings close to the theoretical limit. Outperforms popular Opty-Way, MaxCut, PerfectCut, Cutting, etc. programs by 10-12% in such indicators as the area of non-working residues, the total area of the material being cut and the number of whole sheets used

All 2D nesting algorithms were developed by OOO Programs of Cutting, Novosibirsk, developer: Shilyaev Vladimir Genrikhovich. Oknosoft is the official dealer of the developer and, under a sublicense agreement, has the right to both sell the program as a separate product and use it as part of our developments

40000 r.

Why optimize nesting in the program?

Many customers say: "I have a good sawer. He perfectly cuts the glass and the profile in the head. Only triangles get into the garbage."
Most often, this is true. At the same time, one of the tasks of the leader is to organize a predictable process, the stability of which does not depend on the genius of the performers. Software cut optimization based on the production plan is one of the measures that brings this goal closer.

If we assume that a person can go through more combinations in his head than a computer in the same period of time, the ~1% cutoff coefficient obtained by automatic cutting will look more attractive than the uncontrolled and unmanaged 1% that Genius can provide. Transferring optimization tasks to the program can free up additional time (1-2 hours a day), which he will spend for the benefit of the business.

In fact, the situation with trimming in most enterprises is worse. Coefficients of the order of 4-7% are laid in the specification, and if the workshop works with 3-5% trimming, this is considered a good result. A 3-5% reduction in the actual crop factor is 30-50 thousand rubles saved for every million spent on materials. And yet, this will make it possible not to include extra rubles in the planned cost and offer the buyer more favorable prices.

The problem of optimal consumption of materials consists of several parts.

Warehouse accounting of measured materials

Depending on the characteristics of the business, customers use several accounting schemes for materials:

Based on the production plan, requirements are formed - invoices indicating the products. The issuance of additional materials (not enough) is reflected in separate documents. The indication of products in these documents is desirable, but not a necessary condition. In this case, only those materials that are in the specifications of the products manufactured today and only in the required quantity are issued to the workshop. The disadvantage of this approach is the need to draw up more documents and the lack of a stock of materials at the sites (maybe this is an advantage?)
Requirements - invoices are generated asynchronously, without reference to the production plan, based on the requests of the masters. This approach allows you to get a "live warehouse" with minimal operator costs for the storekeeper, but does not protect against overspending of materials. The entire responsibility for the compliance of the consumption with the specifications lies in this case with the masters and workers. Plan-fact cost analysis will show deviations, but it may be too late

Accounting for business trim

It is possible in a scenario where requirements - invoices are generated based on the production plan. The rest of the business trimming at the beginning of cutting is taken from a special register and can be adjusted by the operator in accordance with the actual balance. When conducting a production assignment, data on the amount of materials that need to be received from the warehouse are placed in the requirements - invoices, and the data on the resulting business trim are added back to the register.

Interaction of performers

When deciding whether to use the nesting optimizer, consider:

With automatic cutting, it is impossible to organize welding (assembly) of products "from under the saw", since the segments related to one product will be "scattered" throughout the optimization map
The production cycle is lengthening, it is required to organize a pool for storing blanks. A compromise is cutting in batches of 30 - 50 pieces. At the same time, high cutting rates are achieved and a uniform loading of welding areas and fittings is obtained.
The efficiency with which the shop can respond to changes in the plan is reduced. If a manager needs to wedge a new product into today's plan, this will worsen the optimization results.

Linear cutting software

Version: 2.49
Developer: Shibaev Yury Anatolyevich Ukraine, Cherkasy
Developer site: http://www.cuttinghome.com/
Bit depth: 32bit
Compatible with Windows 7: yes
Interface language: English + Russian
Tabletka: Cured
System Requirements: Minimum
Description: The CUTTING program is designed for optimal cutting of material into linear parts. The program can be used in woodworking, furniture production, metal cutting, glass cutting, etc. The programs are based on a unique, high-speed algorithm that allows you to quickly cut with minimal waste.

When developing the algorithmic part of the programs, the principle of waste minimization was chosen as the main criterion, and when developing the interface part, the author sought to make the programs simple and convenient in everyday use.
The program has the following functions and features:
. setting an arbitrary number of workpieces and segments to be cut
. setting blanks and segments according to certain characteristics, for example, name and color
. calculation taking into account the type of material (material name, color)
. setting the width of the cutting tool
. calculation of the total lengths of segments and residues
. setting different cutting modes
. restoring previous nests of the current session
. saving specified workpieces and cuts as specifications
. adding a saved BOM to a new analysis option
. saving the nest to a file with the possibility of later recovery
. viewing and printing of cutting results, both in graphical and tabular form
. complete system of reference information.

Our price list includes three products related to the common theme of sorting and optimization:

Linear cutting program for profiles and long materials
Program for two-dimensional cutting of glass, sandwiches, chipboard and other sheet materials
Route optimization program for solving logistics problems

Linear cutting (profile, pipe, log)

Provides inventory-confirmed crop percentage<1%. Ряд клиентов приобрели наши алгоритмы для замены программ оптимизации, поставлявшихся производителями отрезных станков. В программе использован алгоритм плотной укладки и генетический алгоритм поиска решения. На вход поступают данные о количестве и размерах изделий и деловых отходов. На выходе формируются карты раскроя с указанием тележек и ячеек. При необходимости, формируются файлы для обрабатывающих центров, станков с ЧПУ и этикетки с подробной информацией об отрезаемой заготовке и примыкающих элементах.

Live demo on the site

20000 r.

Cutting glass and sheet materials

40000 r.

Why optimize nesting in the program?

The problem of optimal consumption of materials consists of several parts.

Warehouse accounting of measured materials

Depending on the characteristics of the business, customers use several accounting schemes for materials:

Based on the production plan, requirements are formed - invoices indicating the products. The issuance of additional materials (not enough) is reflected in separate documents. The indication of products in these documents is desirable, but not a necessary condition. In this case, only those materials that are in the specifications of the products manufactured today and only in the required quantity are issued to the workshop. The disadvantage of this approach is the need to draw up more documents and the lack of a stock of materials at the sites (maybe this is an advantage?)
Requirements - invoices are generated asynchronously, without reference to the production plan, based on the requests of the masters. This approach allows you to get a "live warehouse" with minimal operator costs for the storekeeper, but does not protect against overspending of materials. The entire responsibility for the compliance of the consumption with the specifications lies in this case with the masters and workers. Plan-fact cost analysis will show deviations, but it may be too late

Accounting for business trim

Interaction of performers

When deciding whether to use the nesting optimizer, consider:

With automatic cutting, it is impossible to organize welding (assembly) of products "from under the saw", since the segments related to one product will be "scattered" throughout the optimization map
The production cycle is lengthening, it is required to organize a pool for storing blanks. A compromise is cutting in batches of 30 - 50 pieces. At the same time, high cutting rates are achieved and a uniform loading of welding areas and fittings is obtained.
The efficiency with which the shop can respond to changes in the plan is reduced. If a manager needs to wedge a new product into today's plan, this will worsen the optimization results.

Programs for optimizing material cutting

This catalog includes links to several domestic computer programs for optimizing material cutting.and several publications on this topic.

The material cutting optimization method is based on the work "Calculation of the rational cutting of industrial materials", 1951, written by Soviet scientists L. V. Kantorovich and V. A. Zalgaller, in which linear programming algorithms are systematically presented, and also dynamic programming for the problem is described. about cutting and combining it with linear programming algorithms.

A large number of cutting optimization programs have been developed in the world, both of a general nature and purely special ones. Below are links to programs available for download from the developers' websites. There are also descriptions of them.

cutting
the program is designed for automatic compilation of optimal cutting maps for sheet and roll materials,

for example, chipboard, MLF (in the manufacture of furniture), glass or any other sheet or roll materials. Allows you to efficiently and quickly obtain nesting cards with a large yield percentage. Paid, demo available
developer site http://picaro.ru
Astra Cutting
the program is designed to optimize the cutting of sheet materials ( particle board, metal, glass and plastics ) . Astra Nesting provides fast input of information about orders and materials; automatic and manual generation of cutting charts; full accounting of dimensional residues and their cutting in subsequent orders; printing of cutting charts and specifications. Paid
developer site http://www.astrapro.ru Basis-cutting
a program for the automated creation of maps for cutting sheet material, which combines the optimal location of the contours of rectangular parts in the given dimensions of the source material with a high calculation speed. It is an integral part of the Basis - Constructor - Furniture Maker complex. Paid, demo available
developer site http://www.bazissoft.ru Cutting
programs of the CUTTING family are designed for optimal cutting of material into rectangular or linear parts. The programs can be used in woodworking, furniture production, metal cutting, glass cutting, etc. The programs are based on a unique, high-speed algorithm that allows you to quickly cut with minimal waste. Paid, demo available
developer site http://www.cuttinghome.com
cutting line
the program is designed for optimal cutting of linear blanks into linear segments of various lengths and can be used in the woodworking and pulp and paper industries, metalworking, clothing production, etc. Paid, demo available
developer site http://www.cuttinghome.com

PaneCut is a program for optimizing the cutting of sheet and linear materials, which allows you to significantly reduce the percentage of waste materials used.Paid, demo available
developer site http://www.vsgroup.ua
NCL- P Program of automatic cutting of sheet material for details of any configuration. Developer Polevov A.V.Free
program website http://freesoft.ru/ncl_v13
Optimum
program for optimal cutting of materials into rectangular parts.Shareware
developer site http://wincad.ru

Bazis Furniture Maker
a complex of interrelated programs that allow you to effectively organize individual or serial production of cabinet furniture at any enterprise: from furniture giants to individual entrepreneurs. The composition of the system: Basis-Furniture Maker (basic), Basis-Cutting, Basis-Estimate, Basis-Interior.

Paid, demo available
developer site http://www.bazissoft.ru
bCAD-furniture maker
a specialized software package designed for the design and preparation of the production of cabinet furniture. The package includes the basic bCAD module, supplemented with specific tools. The Nesting application allows you to automatically create a nesting map for the details of the received models. When you select a material, the application automatically offers a list of parts from the selected material that are present in the project. The parameters of the sheets used, the direction of the first saw, the number of sets are set. The application allows you to take into account the cutting residues, save their parameters and use them in the future.
developer site http://bcad-ug.ru

It is not difficult to find other similar programs on the net, incl. free

Theory and practice of automated cutting of materials in the production of cabinet furniture. Bunakov P.Yu., Kaskevich N.V., Kolomna: GOSGI, 2010. 170 p.

Optimization of material cutting in mechanical engineering: textbook / S.I. Vdovin, O.E. Jur. - Eagle: OSU named after I. S. Turgenev, 2016. - 45 p.

V.A. Skaternoy "Optimization of cutting materials in the light industry" ed. Clothing industry. Legprombytizdat, 1989,- 144 s

Compiled by Abushenko Alexander Viktorovich, Oct. 2005, references checked Jan. 2017

OPTIMIZATION OF SHEET MATERIAL CUTTING INTO RECTANGLES OF VARIOUS SIZES

Giniatullina Regina Airatovna

1st year master's student, Department of Applied Mathematics and Informatics, KNRTU. A.N. Tupolev, Russian Federation, Kazan

Email:Regina[email protected] yandex. en

Galiev Shamil Ibragimovich

scientific adviser, Dr. tech. Sci., Professor of ITKiI KNRTU im. A.N. Tupolev, Russian Federation, Kazan

Guillotine cutting of steel and other sheets is widely used in mechanical engineering and other industries. This nesting is actually the task of packing squares of various sizes into a given sheet using the guillotine procedure. It is important to reduce sheet waste. Interest in packaging problems is explained by their great practical significance. As a rule, such tasks relate to material-intensive industries, where one of the main factors in reducing the cost of products is the rational use of resources. This task has a wide range of practical applications in those industries where packaging (cutting) tasks traditionally arise in mechanical engineering, woodworking, light and construction industries. .

1. Review by task

In industry, in the manufacture of various types of end products, the problem arises of optimally cutting sheets of given sizes into rectangular blanks. This task is as follows: the dimensions of the squares, the size of the sheet are known. It is required to place the given squares in the sheet without overlapping with each other so that it is possible to cut the sheet with a guillotine. Guillotine cutting is understood as cutting, implemented by a sequence of through cuts parallel to the edges of the material. In addition, these squares must be orthogonally packed without rotations, that is, for each selected element of type , the side with height must be parallel to the side of the sheet with height H. We will consider the problem of packing squares of different sizes into a rectangle. Let's solve this problem using one exact algorithm. It is based on a recursive procedure running the branch-and-bound algorithm (which we will also look at) iteratively with different inputs to determine the optimal value of the solution.

2. Purpose of the project

The purpose of this work is to study and implement an algorithm capable of finding solutions for packing squares into a rectangle. The problem under consideration is widely used in various industries: mechanical engineering, woodworking, light and construction industries.

It is necessary to implement the possibility of displaying the result obtained in the form of squares of various sizes inscribed in a rectangle and the corresponding additional information required by the user. For example, such as: algorithm running time, various error information, etc.

3. General requirements

1) Manually setting the dimensions of the sheet-rectangle (width and height) into which the squares will be packed;

2) Manual input of square sizes (they can be either the same or different);

3) Visual review of the results of the algorithm execution (with the output of relevant information: algorithm execution time, the number of squares of a certain size inscribed in a rectangle);

4) Saving information about already entered squares to a file.

4. Relevance of the problem

The main goal of the designed system is compliance with the basic square packing algorithm and ease of use by the end user, fault tolerance.

The tasks and functions of the designed system must comply with the requirements.

The algorithm proposed in this paper can be used to efficiently solve the problem of packing squares into a rectangular area of given dimensions. This problem has a wide range of practical applications in those industries where cutting-packing tasks traditionally arise. The considered algorithm can be used in practical calculations and included in automated design and control systems. It can also be said that the problem is relevant at the moment, since there is a need to pack squares into a rectangle and this need will never end, which means that the problem will always be relevant.

Cutting-packing problems occupy an important place in modern combinatorial optimization and attract the attention of many scientists, both in Russia and abroad.

Interest in cutting-packing problems is explained, in particular, by their great practical significance. As a rule, cutting-packing applications are related to material-intensive industries, where one of the main factors for reducing the cost of manufactured products is the rational use of resources.

5. Existing cutting systems.

There are many software products for cutting sheet material, such as ORION, ASTRA CUTTING, TEHTRAN. Let's consider one of them on the example of TEHTRAN.

For enterprises using thermal cutting machines, the introduction of modern information technologies is one of the most urgent tasks. It is clear that the reduction of the time for preparing cutting programs, the optimal placement of parts on the sheet, and the lower consumption of material will decisively affect the cost and quality of products.

New software product Techtran / Cutting complements the line of programs of the family Techtran and is intended for designing programs for cutting sheet material. The capabilities of the CAM system are combined here with the functions of organizing the production process. The approach to the solution used in the program summarizes the experience of a number of enterprises operating thermal cutting machines. The task is to quickly arrange the parts on sheets in an optimal way and obtain control programs for cutting these parts according to the cutting task, which consists of the nomenclature of selected parts and their quantity for each item. Business waste sheets remaining after work should be recorded in the system database for further use.

6. Formalization of the problem and development of a mathematical model

We present a mathematical model of the problem, following the work.

The branch-and-bound algorithm is based on the integer linear programming (ILP) model. For the sake of simplicity in this formulation, we assume that each element is distinct, that is, for each type j rectangles, we define identical elements having width , height and gain . Let (1) be the total number of elements. For each element k we introduce a binary variable that takes the value 1 if and only if the element k included in the optimal solution. The ILP model for the general two-dimensional knapsack problem is as follows:

where: - the dimensions of the inscribed square,

The dimensions of the rectangle itself,

U- any upper bound on the value of the optimal solution, and C denotes the set of all subsets of elements that cannot be guillotine-packed into a sheet. For the threshold value U we use , that is, the value of the optimal solution for the two-dimensional knapsack problem, corresponding to the simplification according to which the guillotine constraints are omitted. Note that restrictions (3) and (4) are redundant, but added to the formulation to strengthen it. Our algorithm solves a simplified problem in which constraints (5) are eliminated and whether the current solution is valid or not is checked by solving the following separation problem: will all elements from fit into the sheet with a guillotine approach? If the answer is positive, then the optimal solution of the general two-dimensional knapsack problem is found. Otherwise, a new violated constraint is found, and the process is repeated.

This approach is similar to the method proposed by Caprara and Monasi for the exact solution of the 2D knapsack problem and according to Piesinger and Sigard for solving the general 2D knapsack problem itself. More precisely, model (2)-(6) is solved by a specialized branch and bound method in which the elements are ordered. The upper bounds are obtained from the LP relaxation of problem (2)-(3) using the Martello and Toth upper bound. The reverse pass occurs whenever the upper bound does not exceed the current solution, or when some constraints (3)-(5) are violated.

In problem 2-6, it is not taken into account that the cutting is guillotine. Considering all the conditions, we consider a recursive solution method.

7. Method of solution

In this subsection, we consider a recursive procedure for enumerating two-dimensional guillotine packings. In a procedure called recursive, we denote each valid arrangement of a subset of elements on a leaf as a valid packing. Each valid packing can be represented as a non-negative integer vector, where each coordinate represents the number of elements of the type in the package. Denote as packing profit . We say that the allowable packing is maximum if no further elements can be packed into a sheet, i.e., packing turns out to be unfeasible for all element types, so that . For two valid packages and we define new packaging as follows: , .

The recursive procedure implicitly enumerates all valid packings by recursively dividing the sheet into two parts by means of a (horizontal or vertical) guillotine cut. The procedure takes as input the parameter , which is the lower bound on the profit of any admissible (guillotine) packing.

As noted by Christodes and Whitlog, for any two-dimensional packing problem there is an optimal solution corresponding to a normal pattern, that is, a solution in which, for any packed element, its left side is adjacent to either the right side of another element or the right side of the sheet. This means that we can only consider vertical cuts, by coordinates , which can be obtained as a combination of element widths, i.e., which belong to the set:

In a similar way, we consider only horizontal sections, along the coordinates belonging to the following set:

We assume that the elements of both sets and are sorted in ascending order and set and .

Given and and a decision threshold , let be the set of all feasible (permissible) packings of given elements into a sheet of size , which can produce (together with the residual elements and the sheet) a profit greater than or equal to . For two given satisfiable packings And we formally denote by the pairwise sum of packings in sets and :

Intuitively, is the set of packings that can be obtained by combining any packing with any packing , regardless of the sizes of the sets and . It is clear that once the set is defined we can find sets with the condition that all (respectively ) elements belong to an ordered set (respectively ). In a similar way, knowing a set allows us to define sets. Indeed, it suffices to note that each package , which can produce a profit at least equal to , in the rectangle , can be obtained as the sum of the two allowable packings defined for the smaller rectangle. Formally: , anywhere And for some , or And for some . Thus, knowing and for each and , we can easily obtain (generate) in a recursive way .

The basic algorithm can be improved as follows. For each package on a sheet of width and height , an upper bound, say , for maximum profit, can be obtained when the residual area is calculated. To this end, consider examples of backpacks with a capacity of , the types of elements possible in copies, each with a profit and weight . The optimal solution from this case, or any upper bound on this value, gives an upper bound on the maximum profit that can be obtained by packing the remaining elements into the remainder of the sheet. It is clear that all elements such that can be removed from the set since they cannot lead to a feasible solution that has a profit greater than . In our implementation, we calculate the value of the upper bound on the optimal solution of the (one-dimensional) case of the knapsack problem (see ). The values of the upper bounds and obtained by Haifi and the same values proposed by Yang-Gun and Kang for the two-dimensional (orthogonal) knapsack problem without constraints, we use the minimum of these values as the upper bound.

In addition, note that the width and height of the sheet can be reduced to and , respectively, resulting in a lower knapsack power when solving the knapsack relaxation problem, hence more accurate upper bounds. Finally, note that only the maximum allowable packing must be stored for each set, and that any non-maximum element may be ignored. This reduces the number of elements in , hence the memory and computation time requirements of the algorithm.

8. Input and output data of the system

Input data:

1. The width of the rectangle-sheet;

2. The height of the rectangle-sheet;

3. Sizes of squares;

Output:

5. Rectangles located on the monitor screen;

6. Text file with information about inscribed rectangles;

7. Additional information about fitting rectangles in the form of various messages on the screen.

8.5. User interface development

It is advisable to make the user interface in graphical form, as it is most convenient for use.

Data input and output form

Figure 1. User Interface

We first enter the width of the rectangle, press enter, the height - enter, and enter the sizes of the squares, for example 23 - enter, 45 - enter, etc., press 0 to stop entering the squares and the result file appears in the place where the project is saved .png where you can see the packing of squares.

The same window displays information about the number of squares of certain sizes. Press 0 and see information about the time of filling the rectangular area with squares.

After all the actions done, we get:

Figure 2. The result of the program

and the package itself:

Figure 3. Packing squares into a rectangle

Table 1.

Numerical results of the program

Rectangle Size	Estimated number of squares	Total number of squares

Conclusion: the more squares entered, the longer the algorithm execution time.

9. Conclusion

In accordance with the purpose of the study, the following tasks were set and performed:

1. Formulation of the cutting-packing problems under consideration in terms of mathematical programming and a qualitative assessment of the methods for their solution;

2. An algorithm for solving the problem of packing squares of various sizes into a rectangle has been developed and researched;

3. The effectiveness of the developed method was analyzed based on the results of numerical experiments.

Bibliography:

1.Tekhtran / Cutting sheet material [Electronic resource] - Access mode. - URL: http://9132222.ru/catalog/soft/techtran/textran.html (accessed 06/12/2014).

2.Caprara A, Monaci M. On the two-dimensional knapsack problem. Operations Research Letters 2004;32:5–14.

3. Christofides N, Whitlock C. An algorithm for two-dimensional cutting problems. Operations Research 1977;25:30–44.

4. Hifi M. An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock. Computers and Operations Research 1997;24:727–36.

5. Martello S, Toth P. Knapsack problems: algorithms and computer implementations. Chichester: John Wiley & Sons; 1990.

6.Pisinger D, Sigurd M. Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS Journal on Computing 2007;19:36–51

7.Young-Gun G, Kang MK. A new upper bound for unconstrained two-dimen-sional cutting and packing. Journal of the Operational Research Society 2002;53:587–91.