Genetic algorithms applied to leather lay plan material utilization

Abstract

This paper presents a genetic algorithm method for the leather-nesting problem that involves cutting shoe upper components from hides so as to maximize material utilization. A significant proportion of the manufacturing cost of a pair of shoes is invested in the natural raw material, and so the efficient utilization of this resource is of prime importance. Consequently, the part nesting and cutting process is one of the most important stages in the manufacture of leather shoes. The genetic algorithm method presented for leather lay-planning is capable of handling some of the more intractable aspects of the problem, namely multiple non-convex shapes, irregularly shaped hides, directionality constraints and surface grading quality issues. The underlying encoding method is based on the use of the no-fit polygon (NFP), lay angles and directionality angle constraints. The NFP allows the genetic algorithm to evolve non-overlapping configurations. Lay-plan results are presented using standard shoe component shapes and scanned hide input data conforming to a grading scale commonly used in shoemaking.

Keywords

genetic algorithms leather nesting image processing

References

Bounsaythip

Maouche

Neus

Evolutionary search techniques: Application to automated lay-planning optimisation problem. In IEEE International Conference on Systems, Manufacturing and Cybernetics (SMC), Vancouver, Canada, 1995, Vol. 5, pp. 4497–4503.

Anand

McCord

Sharma

Balachander

An integrated machine vision based system for solving the non-convex cutting stock problem using genetic algorithms. J. Mfg Systems, 1999, 18(6), 396–415.

Heistermann

Lengauer

The nesting problem in the leather manufacturing industry. Ann. Ops Res., 1995, 57, 147–173.

Clay

Crispin

A. J.

Automated lay-planning in leather manufacturing. In 17th National Conference on Manufacturing Research, Cardiff, Wales, 2001, pp. 257–262.

Crispin

A. J.

Clay

Taylor

Bayes

Hackney

Reedman

Genetic algorithms applied to material utilization in leather shoe manufacturing. In 18th National Conference on Manufacturing Research, Leeds, 2002, pp. 267–272.

Goldberg

D. E.

Genetic Algorithms in Search, Optimisation and Machine Learning, 1989 (Addison-Wesley, Longman Incorporated, Reading, Massachusetts).

Mitchell

An Introduction to Genetic Algorithms, 1998 (Massachusetts Institute of Technology Press, Cambridge, Massachusetts).