Evolutionary Hyper-heuristic for Solving the Strip-Packing Problem

AbstractStrip-packing problem (marker making) is an optimization problem, where a set of cutting parts needs to be placed on a marker so that the items do not overlap, and do not exceed the boundaries of a marker. In this research a novel Grid algorithm is introduced, and improvement methods: Grid-BLP and Grid-Shaking. These algorithms were combined with genetic algorithm, and a novel placement order All equal first. An individual representation of a genetic algorithm has been developed that is consisted of placement sequence, rotation of a cutting part, the choice of a placement algorithm, and dynamic grid parameter. Experiments were conducted to determine the best placement algorithm for a dataset, and hyper-heuristic efficiency. The implementation has been developed and experiments were conducted in MATLAB using GEATbx toolbox on five datasets from textile industry: ALBANO, DAGLI, MAO, MARQUES and MAN SHIRT. The marker efficiency in percentage was recorded with best results: 85.17, 81.76, 78.67, 84.67 ...