engleski

Evolutionary Hyper-heuristic for Solving the Strip-Packing Problem

Strip-packing problem (marker making) is an optimization problem, where a set of cutting parts need 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 (AEF). 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% and 87.19% obtained for the datasets respectively.

strip-packing, marker making, genetic algorithm, grid algorithm, optimization

nije evidentirano