Research On Packing Rectangle Items In Two-dimensional Irregular Stone Block

In the field of stone processing,packing identical rectangle items in natural stone block is the most known problem.Natural stone is irregular shape.For the problem packing identical rectangle items in irregular stone plate,the common solution is to find its largest internal rectangle,and then to pack directly in the largest internal rectangle.But,the layout of packing rectangle items in the largest interal rectangle may not be the optimal result,and the solution of the largest rectangle inside the irregular shape is a very difficult problem.The main contents can be summarized as follows:(1)Guillotine cutting is the most known problem in the identical rectangle packing problem.Therefore,the classical PLP problem was first studied.The optimal layout of PLP problem with"guillotine cut" constraint was obtained by using the mathematical model which was established on the basis of dynamic algorithm.The automatic cutting of the bridge cutting machine was realized according to the cutting path of the bridge cutting machine which was determined by the order of the single strip.By using machine vision detection and non-contact scanning and image processing of the stone plate,the boundary of two-dimensional irregular shape was obtained.Based on the boundary coordinates,packing identical rectangle items with "guillotine cut"constraint in the irregular shape was solved.The experimental results showed that the problem of packing rectangles items in irregular stone plate could be solved by the proposed method quickly and efficiently.(2)Due to the irregularity of natural stone,the problem that packing identical rectangle items in arbitrary convex polygon was studied.The strategy for solving the problem that packing identical rectangles in convex polygon was based on the fact that the question "Is it possible to pack m rectangles in the polygon?" could be answered.Therefore,the strategy for packing the largest possible number of rectangles consisted of answering the above question for increasing values of m.The arbitrary convex polygon could be represented by closed contour composed of line segments induced from vertices of the polygon.Two constraints of packing identical rectangle items in arbitrary convex polygon were summarized as follows:one was that rectangle item must be totally over the convex polygon and the other was any pair of items could not overlap with each other,i.e.the containment constraint and the non-overlapping constraint.The objective function was modeled on the basis of the two constraints described above;the objective function was solved by GA where the decision variables were the positions where rectangle items must be placed.The numerical experiments illustrated the ecficiency and superiority of the proposed approach.(3)Due to the irregularity of natural stone,the problem that packing identical rectangle items in arbitrary concave polygon was studied.Due to the characteristics of the concave polygon,the relative position of the concave polygon and the rectangular member is difficult to be determined.In recent years,the most popular tool determining whether a rectangle item was inside an arbitrary concave polygon totally was Inner Fit Polygon(IFP)and a new approach calculating the IFP formed by a convex polygon and a concave polygon was given.A new condition that a new inserted item would not overlap with those already packed items was given according to the non-overlapping constraint of a pair of polygons.The polygons were discretized by creating a grid of the same precision on the NFP and the IFP.A heuristic approach analogous to search tree was proposed on the basis of the discretization.The numerical experiments showed that the proposed approach was efficient.Based on the above research,a basic theory research on the problem of packing identical rectangle items in two-dimensional arbitrary region was produced,and the corresponding algorithm and solution were proposed,which greatly enhanced production efficiency of enterprises.