With the rapid advancement of computer technology, efficient and fast processors have entered daily production and life. In industrial production, some computationally intensive tasks have become simple and easy. The conditional full-combination layout algorithm proposed in this article It is based on the development of computers and put forward for the layout of a limited number of parts in production and life. The conditional full-combination nesting algorithm can accurately obtain one or more nesting methods that can meet the requirements, and provide stable and accurate results for the nesting of a limited number of parts.
4.1 Conditional combined algorithm that imitates the cup filling process
To put the three objects of different volume in the same cup, stone, sand and flour, in order to put the stones, sand and flour into the cup, we usually choose to put the stones in the cup first Then put the sand into the cup. At this time, the smaller individual sand will fill the void created by the stones. Finally, put the flour into the cup. Because the flour particles are very small, the flour particles will be filled by The voids created by rocks and sand.
However, we do not choose to fill the cups in this order. We want to choose to fill the cup with flour and then sand into the cup, and finally put the stones in the cup. We will find that all the stones in the original cup cannot be put back into the cup. In the same way, when we want to intercept two-dimensional rectangular parts of different sizes on the same plate as shown in Figure 4.1, we can first sort all parts by area or sort by area, and arrange the larger parts first. Then, arrange the smaller rectangular parts into the plate one by one. According to this arrangement sequence, it is the same as putting the stones into the cup and then sand and flour.
In the layout process, we will change the position of the larger part according to the principle explained in the previous part, and select the part with a larger area to change the position of the part, and then use the smaller part to change the gap. Fill, and finally use the best material utilization rate as the selection condition for our nesting results.
Figure 4.1 Schematic diagram of rectangular parts discharged into the plate
According to the process of imitating the cup filling, we can split the layout process into the following steps:
(1) First select the larger group of parts, the middle group of parts, and the smaller group of parts.
(2) Arrange the larger parts into the plate first, then into the middle parts, and finally into the smaller parts.
(3) Appropriate agitation or vibration must be carried out each time the parts are discharged.
According to the above layout steps, we get the following problems that need to be solved:
(1) How to group rectangular parts by size and make them suitable for layout optimization.
(2) How to realize the stirring function or vibration function in the layout optimization process is mainly the realization of the layout process and the control of various parameters.
(3) How to realize the positioning of the rectangular piece on the plate.
According to the above problems to be solved, the solution process proposed in this article is: first sort the rectangular parts by area, and selectively rotate the sorted rectangular parts, that is, only allow part of the rectangular parts to rotate by themselves, here On this basis, all the rectangular parts after the rotation are selectively combined and arranged, that is, only part of the rectangular parts are allowed to be combined and arranged. The rotation of the rectangular parts realizes the change of their position, and the combined arrangement of the rectangular parts realizes the rectangular parts. The change of mutual position. Therefore, after each rotation of each rectangular part, there are several combinations and arrangement results. Then the rectangular part is positioned according to each result obtained above, and the function of inserting the smaller rectangular part is realized during the positioning process. It's like small grains of sand are filled into the gaps of rocks. Evaluate and record each positioning result, select the best result and place the rectangular parts on the plate.
In the previous part, the layout rules used in this article have been outlined. If you want to arrange the larger parts first and then the smaller parts, you must sort the rectangular parts by area and record the aspect ratio. The rotation and combination arrangement of the rectangular parts realize various positions of the parts in the plate. In the rotation process, we group the rectangular parts according to their own conditions, that is, the rectangular parts that have little effect on the layout result after the rotation are distinguished from the rectangular parts that have a greater impact on the layout result after the rotation. Rectangular parts whose own conditions have a greater influence on the layout result are allowed to participate in rotation, while rectangular parts that have little influence on the result according to their own conditions do not need to participate in their own rotation.
Two rotation modules are designed to realize the rotation function of rectangular parts. Each rotation module has two control parameters to control the range of the rectangular parts participating in the rotation. The first rotation module is to realize the rotation function of the rectangular parts with greater influence at the front of the order, the second rotation module is to realize the rotation function of the rectangular parts with greater influence at the rear of the order, and for the two rotation modules Rectangular parts that are not involved do not have their own rotation function.
Similarly, in the process of permutation and combination, the rectangular parts are grouped according to their own conditions, that is, whether to participate in the permutation and combination of rectangular parts that has little effect on the layout result and whether to participate in the combination arrangement has a greater impact on the layout result Rectangular parts are treated differently. If the rectangular part's own condition makes the rectangular part have a greater impact on the layout after participating in the assembly arrangement, the rectangular part needs to participate in the assembly arrangement. If the rectangular part's own condition has a small influence on the layout result, this rectangle is not required Parts participate in permutation and combination.
In this paper, two permutation and combination parameters are designed to control the range of rectangular parts participating in the permutation and combination function. For example, if the area of the larger rectangular part is very different from the area of the smaller rectangular part after sorting, and the area of the smaller part is smaller than the set threshold, you can set the parameter to control the combination arrangement to make it smaller The parts do not participate in the combination arrangement. For those rectangular parts with a small area, in order to make them fill the gaps best, we make these parts also have a rotation function. If the large parts in the front have special advantages, for example, when the three rectangular parts in the front are the same and just fill the bottom width of the plate, the control parameters can be set so that the first three parts do not participate in the combination arrangement.
The main principle of the conditional full-combination permutation algorithm:
(1) The grouping of large and small parts is realized by sorting, rotating and dividing the rectangular parts, and setting the parameters of arrangement and combination. Sorting rectangular pieces by area from largest to smallest is the beginning of grouping the parts, and then by setting the rotation module parameters, arrangement and combination parameters, the sorted rectangular pieces are actually divided into groups.
(2) The change of the position of the rectangular part includes the change of its own position and the change of the position between the rectangular parts. By rotating, combining and arranging rectangular parts, and inserting rectangular parts, the position of rectangular parts can be changed, that is, the function of stirring in the layout process can be realized. The process of this stirring function is not completed at once, but slowly carried out several times. The parts after sorting are first rotated and then arranged and combined. Therefore, after each rotation, there will be a combination of other parts. Correspondingly, for every change of position, the combined result needs to be evaluated and recorded.
(3) Arrange the rectangular parts on the plate according to the positioning rules of the rectangular parts, and evaluate the layout results according to the optimized conditions. Commonly used evaluation methods include the minimum utilization rate of plates, the minimum nesting height method, and the lowest comprehensive price method. According to a set of nesting results obtained after evaluation, we select the best result for use.
4.2 Analysis of rotating effect of large and small parts
In life, we all know that when a larger object is moved, a smaller distance will produce a larger space change. When a smaller object is moved the same distance, the space change after the movement is smaller. Similarly, in the layout of rectangular parts, when we change the position of a larger rectangular part, a larger gap will be generated, while the same position change of a smaller part will produce a smaller gap, as shown in Figure 4. As shown in 4, it is known that the length of the rectangular part A is L and the width is H, and the gap area generated when it is rotated clockwise by the angle e is S1. Knowing that the length of the rectangular part B is W and the width is P, and W
It can be seen from (1)(2) that S1>S2. When it is known that the area of the rectangular part A and B is relatively large, and the area of the rectangular part B is relatively small, if the value of W/P is not significantly greater than 1 or significantly less than 1, the rectangular part B is in the layout process It will no longer perform its own rotation, which will have less impact on the result of nesting. When the aspect ratio of the rectangular part is obviously greater than 1 or obviously less than 1, or the area of the rectangular part is relatively large, a slight change in its position during the nesting process will have a greater impact on the nesting result. Therefore, in the layout process, we have to set the corresponding threshold to determine which parts to change their positions, and which parts to not change their positions. Canceling some changes in the position of the parts during the layout process will effectively reduce the complexity of the layout and improve the efficiency of the layout.
Figure 4.2 Rotation effect analysis of rectangular parts
4.3 Analysis of the effect of inserting small parts
4.3.1 Analysis of the effect of inserting small parts with obvious length and width
Small parts with obvious length and width refer to parts whose aspect ratio is obviously greater than 1 or obviously smaller than 1. Figure 4.4 shows that for parts with obvious length and width, although their area is not large. Belongs to small parts in sorting. However, because of the two adjacent sides, one of the sides is longer and the other is shorter, the entire rectangle is long and strip-shaped. From the analysis of the previous rotation effect, it can be seen that the gap generated after the long side is rotated by a predetermined angle is relatively large. Therefore, the change of its own position will have a greater impact on the insertion of parts.
In the layout process, for the parts with obvious length and width, we should put their numbers in the record table and allow them to participate in the rotation function. If its area is large or the aspect ratio is very obvious (or when it reaches a set threshold), the rectangular pieces should also be allowed to change their positions with respect to each other. As shown in Figure 4.5, rectangle A is a long rectangular piece with obvious length and width. Rectangular piece A is the third to be discharged into the board during the discharge process. When it is discharged vertically, it is obvious that the board is used The rate is not high. The nesting effect is better when it is discharged horizontally after rotating itself.
Figure 4.3 The length and width are relatively obvious nesting effect
4.3.2 Analysis of the effect of inserting small parts with insignificant aspect ratio but larger size
A rectangular piece with an insignificant aspect ratio but a larger size means that the ratio of the two adjacent sides of the rectangular piece is close to 1, and the area of the rectangular piece is larger than that of other small parts. Because the aspect ratio of this rectangular piece is not obvious, and the side lengths of two adjacent sides are similar, the layout effect produced by changing its position is not obvious. And because its area is larger in smaller parts, it is often not possible to insert other smaller small rectangular parts after using it to insert, so such rectangular parts can be allowed to participate in the mutual position between other rectangular parts Variety.
In the nesting process, we let the large rectangular parts participate in both their own position changes and mutual position changes, and then only the mutual position changes of this part are beneficial to the nesting effect and the nesting speed. As shown in Figure 4.4(a), there is a gap on the left side of the layout. The rectangular piece A on the right has the smallest area in sorting, but its area is relatively large. When it is discharged into the gap, the remaining space cannot be placed. Fill in other rectangular pieces.
In the layout process, the rectangular part A should be allowed to be combined and arranged to change the mutual position with other rectangular parts. The aspect ratio of rectangular part A is not obvious, so it does not need to change its position during the nesting process to meet the nesting effect as shown in Figure 4.6(b). As shown in Figure 4.5(a) Rectangular part B is the part with the smallest area in the sorting of parts, but its area is relatively large as a whole, its inserting function is not flexible, and its aspect ratio is not obvious. The gap produced after layout is not obvious. If it is smaller, it has little effect on the layout effect. Therefore, only the rectangular part B is changed in position with other rectangular parts as shown in Figure 4.5(b).
Figure 4.4 Analysis of the rotation effect of a rectangular piece with an unobviously large aspect ratio
Figure 4.5 Analysis of the effect of the combination arrangement of larger pieces with an unobvious aspect ratio
4.3.3 Analysis of the effect of inserting small parts with inconspicuous aspect ratio and small size
Rectangular parts with an inconspicuous aspect ratio and small area refer to those parts that are mainly used for inserting empty parts with a smaller overall size. The characteristic is that the ratio of adjacent side lengths is close to 1, and the area of this rectangular part is relatively large in the sort Small, its area differs greatly from the area of a larger rectangular piece. These small rectangular pieces can be used to insert some smaller gaps in order to achieve the purpose of saving materials. In the process of inserting, if you want to make use of those smaller gaps, you need to change the position of these smaller rectangular pieces, and then make multiple attempts to insert them. As shown in Figure 4.6(a), the two small rectangular pieces on the right side cannot be placed in the narrow and long gap on the right side of the board horizontally. If they are rotated by 90°. The gap can be used as shown in Figure 4.6(b). Therefore, in the layout process, such rectangular parts need to be rotated.
Figure 4.6 The analysis of inserting a rectangular piece with a less obvious aspect ratio
4.4 Initial treatment of rectangular parts
Rectangular parts need to undergo initial processing before nesting. The main purpose is to grasp the basic situation of each rectangular part before nesting, and to set various thresholds in the nesting process according to the mastered situation. In the early stage, the master wife included: the number of rectangles, finding the area, calculating and recording the aspect ratio, sorting the rectangles by area size, and recording the ratio of the area of each rectangle to the largest rectangle.
There are many sorting methods. This article uses the selective sorting method, that is, the numbers numbered from 1 to 11 are sorted from largest to smallest. First, find the maximum value of all numbers, and then exchange the maximum value with the number numbered 1. Then find the maximum value of the numbers from 2 to n, and then exchange the maximum value with the number 2. After n-1 exchanges, the sorting of the numerical value of all numbers is completed.
4.5 Mixing process and parameter control
4.5.1 Rotation function
This article realizes the change of the position of the rectangular part by adding the rotation function. Rotating the rectangular part is to turn itself 90. Spin. This article uses two rotation modules. The first module is mainly for the change of the position of the larger part in the front after sorting, and the back rotation is mainly for the realization of multiple position states of the smaller parts after sorting, so as to facilitate the adjustment of smaller parts. Insert empty function. The two rotating modules use the same principle.
The principle of the rotation function is to convert decimal to binary. The number of binary digits is the number of rectangular parts. The positions of the rectangular parts after sorting also correspond to the binary digits of the binary digits. There are only two numbers of 0 and 1 in the binary number. The position of the binary digit of 0 means that the corresponding rectangular part does not rotate, and the position of the binary digit of 1 means that the corresponding rectangular part is rotated. Determine the number of rectangular parts that need to be rotated by n, and control the number of rectangles to be rotated from
Turn, binary arrangement (when n=3): (000)(100)(010)(110)(001)(101)(011)(111) that is 2 to the 3rd power of combinations.
4.5.2 Combination arrangement function
The combination arrangement function is to realize the change of the position of the rectangular parts by combining and arranging the rectangular parts. There are many ways to realize the combination arrangement. This article adopts the principle of recursion to realize the full arrangement. In this module, we design two parameters Respectively control the start position and end position of the arrangement, that is, the rectangles within the range of the two parameters participate in the combination arrangement, so as to achieve a certain grouping function. Take the arrangement of (1, 2, 3, 4, 5) as an example, the principle is as follows:
(1) The arrangement of the number 5 is itself, the arrangement of the numbers 4 and 5 is 4, 5 and 5, 4, that is, the full arrangement of 5 starting with 4 and the full arrangement of 4 starting with 5.
(2) The arrangement of the numbers 3, 4, 5 is <3,4,5)(3,5,4)(4,3,5)(4,5,3)<5,3.4)(5, 4, 3) Six sets of numbers. That is, the combination of all permutations of 4 and 5 starting with 3, the combination of all permutations of 3 and 5 starting with 4, and the combination of all permutations of 3 and 4 starting with 5.
(3) In the same way, the arrangement of (1,2,3,4,5) is the full arrangement of (2,3,4,5) at the beginning of 1, and the full arrangement of (2,3,4,5) at the beginning of 2<1,3,4,5). , 3 (1,2,4,5) full permutation, 4 {1 72,3,5) full permutation and 5 (1,2,3,4) full permutation. Exchange all the numbers in the group number with the first number, so that it is always n. A full array of 1 number.
4.5.3 Parameter control analysis
The control parameters included in this article are: the first rotation module start value n1 and end value n2, the second rotation module start value n3 and end value n4, permutation and combination start value a1 and end value a2, aspect ratio threshold y, comparison Small parts threshold B1, middle part threshold B:. According to the initial processing of rectangular parts, set the aspect ratio threshold y, the smaller part threshold B1, and the middle part threshold B2. The ratio of the area of each rectangular piece to the largest rectangular piece is smaller than B1. The smaller rectangular piece is defined as the smaller rectangular piece, the larger rectangular piece larger than B2, and the middle rectangular piece between B1 and B2.
When the ratio of the area of each rectangular piece to the largest rectangular piece is greater than B1, these rectangular pieces need to participate in the combination arrangement, that is, the mutual position changes with other rectangular pieces. Therefore, in the sorting by area, the last rectangular piece greater than the value of B1 has a sequence number a2, and the first one smaller than the steep one has a sequence number a1. In the initial processing, all rectangular pieces larger than the aspect ratio threshold need to change their positions. The main purpose of the second rotation module is to realize the function of inserting smaller parts, so its parameter n4 is the serial number of the rectangular part with the smallest area after sorting, that is, the number of rectangular parts, and the parameter n3 is the serial number of the last rectangular part greater than the value of B1. . The optimization effect produced by the change of the position of the larger rectangular piece is more obvious, so n1 is set to 0. For the last rectangular piece with a larger area than the y value among the rectangular pieces with a relatively medium area, the order number according to the area is set as n2.
4.6 Positioning and blanking of rectangular parts
4.6.1 Positioning method of rectangular parts
The BL (Bottom-Left) algorithm was proposed by Baker. Its central idea is to place the parts from the upper right corner of the sheet to the lower left corner. Therefore, the starting position of the part discharge is in the lower left corner. The part moves downward and vertically as much as possible, and when it cannot move, it moves horizontally to the left, and then repeats downward and vertical movement when it cannot move in the horizontal direction, and repeats downward and leftward until it cannot move. The specific steps of the BL algorithm are as follows:
(1) As shown in Figure 1, place part A above the upper right corner of the sheet.
(2) Move part A down vertically to the lowest possible position until it can no longer move down.
(3) Move part A horizontally to the left to the left as far as possible, until it can no longer move to the left.
(4) Repeat (2) and (3) until it cannot move.
(5) Press (1) to (4) to discharge the next part.
Figure 4.7 BL algorithm
The time complexity of the BL algorithm is O (iv), which is equal to the number of rectangular parts. Its advantage lies in fast calculation speed and less memory, but the blank area generated during the discharge process cannot be filled.
4.6.2 Realization of inserting rectangular parts
It has already been introduced that the BL algorithm generates blank areas and cannot be filled by itself. For this, Chazelle proposed the BLF (BL-Fill) algorithm, whose idea is based on the BL algorithm. When discharging each rectangular part, take the bottom left corner as the starting position, and then continuously compare whether the discharging position interferes with the rectangular parts that have been disposed before, until the discharging of the rectangular parts is completed. In this way, the BLF algorithm has played a role in filling the discharge gap, and the time complexity is mostly O(N3).
Figure 4. 8BLF algorithm
4.7 Summary
By studying the nesting features of known sheet metal parts, a combined nesting algorithm is proposed for the mixed layout of large parts and small parts for sheet metal parts. This algorithm is inspired by the principle of putting stones, sand and flour into cups commonly used in daily life. By imitating the process of filling cups, the parts are discharged onto the plate, thereby improving the utilization rate of the plate, and The results show that this kind of algorithm is effective, and the layout result of this kind of algorithm is controllable, especially for the situation where there are a limited number of rectangular parts and the sizes of rectangular parts are mixed.
