Exact solutions for the 2d-strip packing problem using the positions-and-covering methodology.
PLoS One
; 16(1): e0245267, 2021.
Article
em En
| MEDLINE
| ID: mdl-33444394
We use the Positions and Covering methodology to obtain exact solutions for the two-dimensional, non-guillotine restricted, strip packing problem. In this classical NP-hard problem, a given set of rectangular items has to be packed into a strip of fixed weight and infinite height. The objective consists in determining the minimum height of the strip. The Positions and Covering methodology is based on a two-stage procedure. First, it is generated, in a pseudo-polynomial way, a set of valid positions in which an item can be packed into the strip. Then, by using a set-covering formulation, the best configuration of items into the strip is selected. Based on the literature benchmark, experimental results validate the quality of the solutions and method's effectiveness for small and medium-size instances. To the best of our knowledge, this is the first approach that generates optimal solutions for some literature instances for which the optimal solution was unknown before this study.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Algoritmos
Idioma:
En
Revista:
PLoS One
Assunto da revista:
CIENCIA
/
MEDICINA
Ano de publicação:
2021
Tipo de documento:
Article
País de afiliação:
México
País de publicação:
Estados Unidos