Research On 2D Irregular Packing Problems

The major subject of this thesis is the so-called 2D Irregular Packing Problem. It is a problem that arises in a variety of industrial application. Typical applications include garment manufacturing, sheet metal cutting, furniture making, and shoe manufacturing. The main objectives are to maximize space utilization and minimize the wastage. On the whole, 2D Irregular Packing Problem is particularly important in practical application.The major contribution of this thesis is a new geometry tool called discrete no-fit polygon. The new Bottom-Left algorithm that proposed by Burke et. al might generate invalid results for some special cases. To fix this problem, a new concept named discrete no-fit polygon (DNFP) was introduced and a decomposition theorem of DNFP was given and strictly proved. Moreover, we proposed a construction algorithm of DNFP, computational results showed that the algorithm is very fast and effective.The utilization of DNFP actually changes the original problem into a much simpler one that merely consists of points and intervals. Not only can it greatly decrease the geometry complexity of the original problem, but also it makes the original problem be easily solved by a variety of heuristic strategies. The basic hill climbing algorithm and genetic algorithm were implemented based on this new geometric tool. We applied our algorithms to 15 benchmark problems. The solutions were generated within a short period of time and the density is relatively high. These results revealed that the algorithm based on discrete no-fit polygon is fairly efficient.