Research On Optimization Approach For Rectangular Packing Problem Based On Industrial Background

Blank nesting plan optimization has been widely used in modern industrial production, while the rectangular packing problem optimization is one of the most common issues. And the most important part of this rectangular packing problem optimization is to find out the cutting method with minimum production cost by giving certain amount of rectangular plate and objective parts with certain size. The cost of production is mainly determined by the used amount of raw material and difficulty of cutting processing. According to different processing technology, Rectangular packing problem can be divided into two kinds: “guillotine cutting” constraint and “non-guillotine” constraint. This thesis studies the former one, whose typical application scenarios include production and processing of glass, stone, wood and other plate.This thesis firstly introduces the present research status of packing optimization problem at home and aboard and the background and significance of the research on packing optimization designing under multi-type and multi-size raw material in stone industry condition. Then explores how to establish mathematical model under constrained conditions of current processing technology of rectangular packing problem. In the process, quantify “cut difficulty” and put it into the objective function, thus makes up for the deficiency of evaluation method in cutting solution merely based on the outturn rate. And then the current classical algorithms of cutting rectangular plates are presented, with an emphasis on surplus rectangle algorithm. Furthermore, by researching the application of genetic algorithm in packing optimization, a new scheme that put raw material into chromosome coding was proposed, which solves this input problem of material with various specification in rectangular packing problem. At the same time, the synthesis of non-liner fitness evaluation function based on objective function in mathematical model and the designing of crossover operator accord with rectangular packing problem were also studied. Besides, by analyzing the disadvantages of the previous designing genetic algorithm under much same-size raw material and parts condition, a similar reuse strategy, which was in an attempt to be integrated into genetic algorithm but finally realized through greedy algorithm by a staging combined use of greedy and genetic algorithms, was proposed. This strategy resolves problems between genetic algorithm packing result and production practice. On this basis, by means of whole putting, which was applied to greedy algorithm, the packing algorithm was improved. As for the underutilized raw material problem, which can be well solved through binary search method. Finally an automatic layout system for stone industry, which was divided into UI module and algorithm module for easy maintainability and added with common used functions in stone industry, was realized by utilizing previously designed packing algorithm.Eventually, the blank layout program of all the 220 objective parts was defined by testing the automatic layout system based on a practical test case with multi-type and multi-size raw material and parts. And the whole outturn rate is 94 percent. At the same time, layout result has the features of similar reuse and whole putting. From the result, the conclusion indicates that the packing algorithm has reached the aim of the design.