A study on two-dimensional layout : efficient clustering and nesting of arbitrarily-shaped patterns and stocks


Student thesis: Doctoral Thesis

View graph of relations


  • Shu Kin CHENG


Awarding Institution
Award date15 Jul 2003


The cutting stock problem is of interest to various industries because an important factor that increases competitive power in the manufacturing of any product is to utilize minimum amount of the raw materials involved. In past, the computer techniques and hardware resources were quite limited. Different researchers thus simplified the cutting stock problems by ignoring, for example, pattern entities, concavity feature, etc., with the intention of finding out only a reasonably feasible solution from the complicated and huge search space (NP-complete) within an acceptable and workable computation time. After generating an initial solution, an experienced marker often modified the computer output so as to obtain a near-optimal solution. With this approach, the solutions obtained may not be consistent and a high level of automation cannot be achieved. In the last decade, high-speed computers have become affordable and increasingly used in every kind of industry. The computation tasks needing overnight runs a few years ago are now completed within a few minutes only. Hence, it should be possible to solve stock problems rapidly and accurately by using intelligent software applications. The main aim of this research is to develop and use intelligent strategies for solving cutting stock problems. This research basically focussed on both computing precision and speed while satisfying various industrial needs in terms of essential manufacturing factors/constraints. The accomplished work is presented below: Efficient pattern approximation not only poses less demand on memory requirement but also provides a high level of automation and possibly accuracy. Depending on the required accuracy level, a mathematical formula is used to define the number of dividing points to approximate curves and arcs of two-dimensional flat patterns. An approximate pattern is automatically created by joining the dividing points without the need to execute numerous computation tasks, such as, entity drawing, trimming, breaking, etc. Clustering involving ' pairwise' and 'sliding' techniques has been widely used for nesting of irregular shapes, and they are adopted individually and independently. While the former provides an interactive computation speed at the expense of accuracy, the latter tends to find the best solution through an exhaustive search that makes it unsuitable for interactive purposes. A Hybrid technique is developed in this study that combines the strength of these two clustering techniques. Flat patterns are first brought together by the traditional pairwise algorithm, and the compactness is further increased by following limited sliding steps intelligently to improve the cluster quality. For this purpose, defining a 'breakpoint' between two clustering steps is a critical factor since an optimal solution usually lies between two traditional sliding steps. Also, the traditional methods are based on minimal-area enclosure of rectangle or convex polygon. It is found that they can provide only a local optimal solution. However, it is proved that breakpoint generation improves the effectiveness of conventional clustering process in both computing precision and speed. The breakpoint provides 'Stringy Effect', which is based on minimizing the distance between centroids of patterns during clustering. No matter how much the computer hardware becomes advanced, computer users always expect shorter computation times. Cutting stock problems involve a lot of computations, such as, finding entity intersection, overlap elimination between patterns, entity transformation, etc. The number of steps exponentially increase with clustering iterations due to NP-hard problem nature. Even with a fast computer, the processing time is unacceptably long and, thus, intelligent methods that can decrease the search space are highly desirable. By incorporating Freeman projection technique and branch-and-bound techniques, the sliding technique has been executed highly efficiently. The 'Freeman chain code' detects and eliminates the unnecessary entities during the identification of intersection through the recognition of hidden lines. The 'branch-and-bound technique' helps in defining the exact regions that will lead to intersections while sliding. With the combined use of these two techniques, search for intersection of various entities of the patterns can be reduced to less than 25% compared to traditional techniques. Two geometric parameters, termed as, Edge Attractive Index (EAI) and Vertex Attractive Index (VAI), are defined to speed up the process of clustering. These parameters can be obtained for different pairs of patterns, which form the basis for deciding the sequence of clustering when a large number of patterns are involved. The process is repeatedly applied after each clustering operation until all patterns are clustered. This technique can provide optimal or near optimal solutions without exhaustive search and consideration of all possible pattern combinations. Geometrical tiling of a single pattern or selected cluster step by step from the original position to an orientation of 180 degrees, i.e., orthogonal packing, is widely used. However, this is a blind search of best stock layout and, computationally, it becomes inefficient with increasing number of pattern entities. Also, it is not highly suitable for handling patterns with a range of orientation constraints. In this study, an algorithm is proposed which uses the Genetic Algorithm (GA) to optimize large-scale nesting with the consideration of multiple orientation constraints. A technique can be regarded as blind search if there is no clear definition of termination. Traditional methods for solving the cutting stock problem. through clustering and nesting process, seem to be not intelligent enough to solve the problem efficiently due to numerous pattern positions that become possible. A concept of 'Compact Neighborhood' that relates the number of neighbors and the sharing space between them is introduced in this study, and an algorithm is presented to provide quick and precise solutions. This concept leads to what is termed as 'Universal Compact Yield (UCY)' that provides a theoretical maximum yield for the geometry of patterns being considered in nesting. Hence, UCY can be used to set the criterion for termination on a scientific basis. Several manufacturing factors have been considered in this study so as to make the developed algorithms directly useful for various industrial applications. Typically, irregular shapes are allocated onto rectangular stock in sheet metal industries, and flat pattern(s) is/are duplicated and nested onto the stock with the consideration of bridge width, rolling direction, etc. Besides blanks allocation strategy, optimal offset generation and orientation constraints of patterns have been considered. For clothing industry, the developed algorithm can improve the effectiveness of nesting processes with a rigorous mathematical consideration of the range of orientation limits of the patterns being nested. In leather industry, cutting stock problem always involves a number of different patterns to be nested onto a given irregular stock. Therefore, an efficient allocation method is a key to achieve success. The traditional method is to represent both patterns and stock into pixels, with the resolution fixed by an experienced worker depending on the required precision and computation time. In this study, an algorithm is developed to automate such tasks while achieving higher stock yields. This algorithm also makes use of the several efficient techniques described above to provide efficient solutions to this type of cutting stock problems. The working principles and effectiveness of the various algorithms developed have been demonstrated with typical examples.

    Research areas

  • Mathematical optimization, Cutting stock problem