The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon

The nofit polygon is a powerful and effective tool for handling the geometry required for a range of solution approaches to two-dimensional irregular cutting-stock problems. However, unless all the pieces are convex, it is widely perceived as being difficult to implement, and its use has therefore been somewhat limited, The primary purpose of this paper is to correct this misconception by introducing a new method of calculating the nofit polygon. Although it is based on previous approaches which use the mathematical concept of Minkowski sums, this new method can be stated as a set of simple rules that can be implemented without an indepth understanding of the underlying mathematics. The result is an approach that is both very general and easy to use. Scope and purpose Cutting and packing problems involving irregular shapes are common in industries ranging from clothing and footware to engineering and shipbuilding. An important feature of any automated solution technique for such problems is the way in which the geometric calculations are handled. One of the most efficient approaches is to pre-process many of the calculations using a concept known as the nofit polygon (NFP). However, use of the NFP has been limited due to the difficulty in its calculation for arbitrary irregular pieces, This paper outlines the concept of the NFP in the context of the irregular cutting-stock problem and introduces a new simplified approach to its calculation. The aim is to make this powerful concept more easily accessible to those involved in the cutting and packing of irregular shapes, (C) 2000 Elsevier Science Ltd. All rights reserved.