Title: Comparison of two metaheuristics to solve a 2-D cutting stock problem with set-up cost in the paper industry

Authors: Stéphane Bonnevay; Gérald Gavin; Philippe Aubertin

Addresses: ERIC, Université de Lyon, 5 av. Mendès France, Bron 69676, France ' ERIC, Université de Lyon, 5 av. Mendès France, Bron 69676, France ' AXOPEN, 149 bd Stalingrad, 69100 Villeurbanne, France

Abstract: This paper deals with the two-dimensional cutting stock problem with set-up cost (2CSP-S). This problem is composed of three optimisation sub-problems: a 2-D bin packing (2BP) problem (to place images on patterns), a linear programming (LP) problem (to find for each pattern the number of stock sheets to be printed) and a combinatorial problem (to find the number of each image on each pattern). We have already developed two different metaheuristics to solve the 2CSP-S focusing on this third sub-problem: a simulated annealing and a genetic algorithm. In this article, we propose to compare these two approaches. It is important to notice that our approaches are not new packing techniques. This work was conducted for a paper industry company and experiments were realised on real and artificial data sets.

Keywords: combinatorial optimisation; genetic algorithms; metaheuristics; paper industry; setup costs; simulated annealing; 2D CSP; cutting stock problem; bin packing; linear programming.

DOI: 10.1504/IJMHEUR.2016.079107

International Journal of Metaheuristics, 2016 Vol.5 No.1, pp.31 - 50

Received: 07 Nov 2015
Accepted: 03 Jun 2016

Published online: 12 Sep 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article