The 2-dimensional cutting stock problem is an important problem in the garment manufacturing industry. The problem is to arrange a given set of 2-dimensional patterns onto a rectangular bolt of cloth such that the efficiency is maximised. This arrangement is called a marker. Efficiency is measured by pattern area I marker area. Efficiency varies depending on the shape and number of patterns being cut, but an improvement in efficiency can result in significant savings. Markers are usually created by humans with the aid of CAD software. Many researchers have attempted to create automatic marker making software but have failed to produce marker efficiencies as high as human generated ones. This thesis presents a mathematical model which optimally solves the 2-dimensional cutting stock problem. However, the model can only be solved in a practical amount of time for small markers. Subsequently, two compaction algorithms based on mathematical modelling have been developed to improve the efficiency of human generated markers. The models developed in this thesis make use of a geometrical calculation known as the no-fit polygon. The no-fit polygon is a tool for determining whether polygons A and B overlap. It also gives all feasible positions for polygons B with respect to polygon A, such that the two polygons do not overlap. For the case when both polygons A and B are non-convex, current calculation methods are either time consuming or unreliable. This thesis presents a method which is both computationally efficient and robust for calculating the no-fit polygon when polygons A and B are non-convex. When tested on a set of industrial markers, the compaction algorithms improved the marker efficiencies by over 1.5% on average.
展开▼
