Solving two-dimensional layout optimization problems with irregular shapes by using meta-heuristic

The focus of this thesis is developing methodologies for 2-dimensional problems that involve irregular shapes, where the objective is to find an arrangement of the irregular pieces in order to minimise waste material. There are two main approaches popular with researchers; in this research project we will group them into iterative constructive heuristics (ICH) and those heuristics which search over the physical layout (SOL). ICH seeks to generate good layouts by placing pieces on the stock sheet piece by piece according to a placement rule. The orders the pieces are placed is controlled by a search algorithm. SOL works with the physical layout and tries to improve the solution by moving the placement position of pieces. Overlap is often permitted and penalised in the cost function in order to generate new solutions. Both approaches are competitive and each new publication brings better results with respect to the benchmark data sets. Although this can be credited to better algorithm design, it could also be argued that researchers are getting better at incorporating sophisticated specific features in their algorithms to handle the 17 benchmark data sets. In this research we intend to investigate the two representations of the problem and establish some principles of the strengths and weaknesses of each method with respect to data type. In order to conduct this research the algorithms will be developed using only the basic principles of both approaches and discarding any special features found in the literature. The aim is to deduct from the experimental results an understanding of what solution representation should be applied given the data type, performance requirements and number of pieces.