Genetic Algorithms to the Nesting Problem in the Leather Manufacturing Industry

摘要

The nesting problem in the leather manufacturing is the problem of placing a set of irregularly shaped pieces (called stencils) on a set of irregularly shaped surfaces (called leathers sheets). This paper presents a novel and promising processing approach. After the profile of leather sheets and stencils is obtained with digitizer, the discretization makes the processing independent of the specific geometrical information. The constraints of profile are regarded thoroughly. A heuristic bottom-left placement strategy is employed to sequentially locate stencils on sheets. The optimal placement sequence and rotation are deterimined by genetic algorithms (GA). A natural concise encoding method is developed to satisfy all the possible requirements of the leather nesting problem. The experimental results show that the proposed algorithm can not only be applied to the normal two-dimensional nesting problem, but also especially suitable for the placement of multiple twodimensional irregular stencils on multiple two-dimensional irregular sheets.