The Algorithm And System For Two-Dimensional Irregular Nesting Problem

Two-dimensional (2D) nesting problem, a layout optimization problem, concerns how toplace pieces on two-dimensional sheets of materials in most efficient layout problem.2Dproblem has a wide range of applications in many manufacturing field, such as ship buildingindustry, textile industry, newspapers and periodicals layout, cutting, etc. In some enterpriseswhich have low production level, the nesting problem is solved by manual and so the resultsgreatly rely on workers’ experience. With the rapid economic development, a slightimprovement in material sheet utilization can make huge economic profits. Therefore, it hasattracted many scholars around the world to make researches on different type of2D nestingproblem for decades of years. However,2D irregular nesting problem in which the pieces areirregular has high complexity, and there still have no good method to solve the problem.Although some studies have showed that no-fit polygon (NFP) based algorithm and geneticalgorithm may have higher material sheet utilization, the calculation of NFP is very complexin implementation and is hard to use in reality. For the above problems, this dissertationfocuses on the research of heuristic algorithms to nest2D irregular pieces rapidly andefficiently. The main works are listed as follows:(1) A simple method to calculate the smallest surrounding rectangle is first proposed.Then, a heuristic based on laying out the smallest surrounding rectangle of irregular pieces ondifferent levels to nest the irregular pieces indirectly. This algorithm can nest the irregularpieces rapidly and avoid producing large holes.(2) Another approach which nests2D irregular pieces directly is proposed. It comparesthe matching degrees of the geometrical characteristic between the material sheet and theirregular pieces and takes the matching degrees as reference criterions of nesting. There is noneed to calculate the NFP in this approach and the pieces are laid out rapidly. Combining thepieces dynamically in the nesting process also helps to yield higher material sheet utilization.(3) Combining the above two algorithms, an algorithm which lay the irregular piecesdirectly based on positioning the part of nested region is proposed. The irregular pieces arelaid out on the position with minimum area waste by the analysis of the reference position onthe nested region. Then, the pieces move close to the nested region by using the “shake” type.By such means, the complexity of nesting the irregular pieces is simplified, and the speed ofnesting is improved.(4) At last, a software with the three proposed nesting algorithms is designed anddeveloped. It can interact data with the AutoCAD and could be applied the nesting algorithms to solve the problems in real production.