| The problem of finding a dense packing of a set of two-dimensional polygonal shapes within another larger two-dimensional polygon is called nesting. This problem is widely encountered in companies fabricating metal parts, leather cutting industry and in the textile industry---in short, where the material is costly and scrap needs to be minimized. This thesis describes a new approach to nesting problems. It is a hybrid approach, which uses a parallel genetic algorithms and shape information in the form of feature matching. Here, the shape information has been used to do the local search and a parallel genetic algorithm has been employed for the global search. Various experiments were performed to determine a good set of parameters for use in feature matching and the parallel genetic algorithm. To reduce the chances of premature convergence of the parallel genetic algorithm, different topologies for communication among subpopulations and different migration schemes were tried. A good choice of communication patterns seems to maintain balance between the frequency of migration and the degree of interconnectivity among the subpopulations. The test problems show this approach to work well for the nesting problem, where the search domain is often very large. |
