<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Problem generators are practical solutions for generating a set of inputs to specific problems. These inputs are widely used for testing, comparing and optimizing placement algorithms. The problem generator presented in this paper fills the gap in the area of 2D Cutting &amp; Packing as the sum of the area of the small objects is equal to the area of the Large Object and has at least one perfect solution. In this paper, the already proposed Upper Deck algorithm is revisited and used to test the proposed generator outputs. This algorithm bypasses the dead area problem that occurs in most of all well-known strategies of the 2D Single Knapsack Problem where we have a single large rectangle to cover with small, heterogeneous rectangle shapes, whom total area exceeds the large object’s area. The idea of placing the small shapes in a free corner simplifies and speeds the placement algorithm as only the available angles are checked for possible placements, and collision detection only requires the checking of corners and edges of the placed shape. Since the proposed generator output has at least one exact solution, a series of optimization performed on the algorithm is also presented.</p></abstract>

Problem generators are practical solutions for generating a set of inputs to specific problems. These inputs are widely used for testing, comparing and optimizing placement algorithms. The problem generator presented in this paper fills the gap in the area of 2D Cutting & Packing as the sum of the area of the small objects is equal to the area of the Large Object and has at least one perfect solution. In this paper, the already proposed Upper Deck algorithm is revisited and used to test the proposed generator outputs. This algorithm bypasses the dead area problem that occurs in most of all well-known strategies of the 2D Single Knapsack Problem where we have a single large rectangle to cover with small, heterogeneous rectangle shapes, whom total area exceeds the large object’s area. The idea of placing the small shapes in a free corner simplifies and speeds the placement algorithm as only the available angles are checked for possible placements, and collision detection only requires the checking of corners and edges of the placed shape. Since the proposed generator output has at least one exact solution, a series of optimization performed on the algorithm is also presented.

Exact fit problem generator for cutting and packing, revisiting of the upper deck placement algorithm

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Problem generators are practical solutions for generating a set of inputs to specific problems. These inputs are widely used for testing, comparing and...

Exact fit problem generator for cutting and packing, revisiting of the upper deck placement algorithm

Publié en ligne: 29 août 2018

Pages: 73 - 85

Reçu: 15 mars 2018

DOI: https://doi.org/10.2478/ausi-2018-0005

Mots clés
Cutting stock problem, problem generator, genetic algorithm

© 2018 Levente Filep et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Exact fit problem generator for cutting and packing, revisiting of the upper deck placement algorithm

Publié en ligne: 29 août 2018

Pages: 73 - 85

Reçu: 15 mars 2018

DOI: https://doi.org/10.2478/ausi-2018-0005

Mots clésCutting stock problem, problem generator, genetic algorithm

© 2018 Levente Filep et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
Cutting stock problem, problem generator, genetic algorithm