Research And Realization Of Irregular-part Nesting Based On Combination Envelope

Two-dimensional nesting problem is a kind of N-P complete problem,which widely exists in newspaper nesting,textile cutting,mechanical cutting and other fields.It can be divided into regular part nesting and irregular part nesting.Its essence is to optimize the nesting of specific shape,size and number of parts to be nesting on the plate of specified shape and size.In actual production,irregular part nesting can better meet the diversity of requirements,so it is more common.Although irregular part nesting is more complex than regular part nesting,its nesting algorithm is applicable to all two-dimensional nesting problems.In addition,the advantages and disadvantages of nesting algorithm directly affect the material utilization,nesting efficiency and even production efficiency of enterprises,so it is necessary to study irregular parts nesting.The topic of this paper originates from a laser equipment enterprise.Based on the research of two-dimensional nesting algorithm,aiming at irregular samples and considering the need of irregular parts nesting with small variety and large quantities in enterprises,an irregular parts nesting algorithm based on combination envelope is proposed.The algorithm transforms irregular parts into regular rectangular nesting by combining envelope strategy,i.e.using the method of graph adjacent combination and rectangular envelope,which can reduce the complexity of nesting.In this paper,genetic algorithm and minimum horizontal line algorithm are used to realize nesting,and the algorithm is applied to plate cutting in a laser equipment enterprise.The experimental results are compared with the system developed by the enterprise and purchased by the enterprise.The validity of the algorithm applied to the nesting of irregular parts with few varieties and large quantities is verified.The main research work of this paper is as follows:(1)Based on sorting out the general algorithm flow and key links of the twodimensional nesting problem,the applicability of each link is analyzed,which provides a theoretical basis for the subsequent irregular part nesting algorithm and the selection of each link algorithm.(2)Based on the requirement analysis of irregular part nesting in a laser equipment enterprise,an irregular part nesting algorithm based on combination envelope is proposed.The complex irregular part nesting is transformed into simple rectangular part nesting by combination of graphics and rectangular envelope,and the key strategies to realize the algorithm,such as coordinate transformation,graphic docking,collision detection and rectangular envelope,are carried out separately.Elaboration.(3)The genetic algorithm is used to solve the irregular part nesting based on the combination envelope,and the collision detection and the minimum horizontal line algorithm are combined to select the optimal nesting scheme with the fitness function value.(4)Using QT Creator and C++,and based on Visual Studio 2010,a demonstration model of irregular part nesting system was designed and developed.The experiment was carried out with irregular parts library provided by the European Special Interest Group on Cutting and Packaging.By comparing with the effect of self-developed and purchasing international advanced nesting system by enterprises,it was verified that the algorithm in this paper is of small variety and large quantity.Effectiveness and superiority of irregular parts nesting.