Research On Irregular Sample Packing Algorithm

Packing problem is a combinatorial optimization problem that places as many samples as possible on the master in which the samples can’t overlapped with each other and out the range of it. Since the packing problem is widely used in industrial application, such as the garment manufacturing industry, leather processing industry, furniture manufacturing and so on, the study of it has great practical value.Because of the irregularity of samples and master, the complexity of irregular packing problem is increased and the research of it is to improve utilization of and packing time on the basis of the technical requirements.To improve packing algorithm of irregular samples, a new idea is proposed in this thesis which put the principle of lowest gravity center and concentrated gravity center into different section and the packing result is optimized by algorithm of particle swarm search and detection.The main work is as follows:1. In this thesis,an idea is proposed under the requirements of technical processing. In order to reduce the intersection of computation the No Fit Polygon is used to determine the location between two samples and NFP based on gravity is used to locate samples.2. In order to meet packing requirements, the paper proposes a layout strategy which uses different packing strategies in different quality region. We use subsided strategy which based on NFP in first section and the gravity center concentrated strategy is used to pack the samples in secondary region. In this way, we can meet the expectation that the gravity of samples in the first section is much lower, and the samples in secondary region are much more concentrated.3. Because of Particle Swarm Optimization algorithm isn’t adapt to irregular packing problem, this thesis proposes multi-way optimization, including particle design and test optimizations, to optimize the irregular sample layout effects. This strategy has a great advantage in solution of space search to optimize the packing results. In the optimization process, we design two kinds of particles in PSO and combine with improved layout strategy to determine the optimal location of packing, then use the test optimization in layout result to reduce the distance, and improve the quality of result.4. This thesis design and implement irregular system to realize the improved algorithm andthe significant improved utilization of sheets in this way is verified.