Optimisation of a multi-objective two-dimensional strip packing problem based on evolutionary algorithms

Abstract

This paper considers a real-world two-dimensional strip packing problem involving specific machinery constraints and actual cutting production industry requirements. To adapt the problem to a wider range of machinery characteristics, the design objective considers the minimisation of material length and the total number of cuts for guillotinable-type patterns. The number of cuts required for the cutting process is crucial for the life of the industrial machines and is an important aspect in determining the cost and efficiency of the cutting operation. In this paper we propose the application of evolutionary algorithms to address the multi-objective problem, for which numerous approaches to its single-objective formulation exist, but for which multi-objective approaches are almost non-existent. The multi-objective evolutionary algorithms applied provide a set of solutions offering a range of trade-offs between the two objectives from which clients can choose according to their needs. By considering both the length and number of cuts, they derive solutions with wastage levels similar to most previous approximations which just seek to optimise the overall length.

Keywords:

• cutting stock problems
• packing problems
• evolutionary algorithms
• Pareto optimisation

Acknowledgements

This work was funded by the EC (FEDER) and the Spanish Ministry of Education and Science as part of the ‘Plan Nacional de I+D+i’ (TIN2005-08818-C04-04). The work of Gara Miranda was developed under grant FPU-AP2004-2290, while the work of Jesica de Armas was funded by grant FPU-AP2007-02414.