An integrated machine vision based system for solving the nonconvex cutting stock problem using genetic algorithms

The two-dimensional stack cutting problem is well known and often studied. A genetic algorithm approach to the problem is developed that is capable of handling some of the more intractable forms of the problem: nonconvex parts; nonconvex sheets; multiple irregularly shaped sheets; and so on. An integrated system is developed that incorporates a machine vision module for acquiring the images of irregular (nonconvex) parts and sheets, polygonalizing them, and storing them in a database of parts and sheets. Using the polygonal images as well as the manufacturing schedules and priorities as input, a genetic algorithm is used to generate part layouts that satisfy the manufacturing constraints. The significant features of this approach are (1) the integration of all aspects of the layout process and (2) the flexibility of the genetic algorithm approach, which allows it to be adapted to fit the special requirements of different problems. The proposed methods can be particularly useful in the leather and apparel industries, where nonconvex parts and sheets are commonly used.