The industrial application of new irregular cutting and packing algorithms - Hellier, Robert (2013)
This thesis investigates the field of irregular two-dimensional stock cutting from the perspective of an industrial practitioner. The new approaches and developments in the thesis have been motivated by industrial considerations and have been used directly in industrial software applications. Irregular two-dimensional stock cutting problems occur in a wide range of industries and in almost all cases, for reasons of effective use of staff time, solution speed and efficiency, the application of the automated nesting algorithms are advantageous over manual methods. Reduction in the use of raw materials is a direct cost saving for any business and therefore has a significant impact on operating profitability. The approaches developed in this thesis have, at the time of publication, produced the best known solutions for all of the 26 known irregular problem instances from the scientific literature. In order to explore some of the unique features of the approaches, motivated by industrial concerns, the thesis also introduces additional benchmark problems. In order to achieve these high quality solutions and attain the level of reliability required in industrial applications this work introduces a complete and robust technique for the production of no-fit polygons for irregular shapes including arcs, interlocking concavities and holes. The robustness of the technique and its ability to handle arcs and holes make this the first algorithm in the literature not to suffer from degenerate cases and makes it highly valuable to industrial practitioners, as well as a valuable tool for research scientists. The placement algorithms presented in this work take advantage of the geometry of the shapes being placed in order to produce solutions very rapidly and to a high degree of accuracy. These placement techniques, in combination with numerous local search techniques, achieve high quality solutions for a wide range of problems. Indeed these techniques are being used in industrial settings worldwide today on a vast range of problems and in numerous industrial sectors.