Back to Search
Start Over
Exact solutions for the 2d-strip packing problem using the positions-and-covering methodology.
- Source :
-
PloS one [PLoS One] 2021 Jan 14; Vol. 16 (1), pp. e0245267. Date of Electronic Publication: 2021 Jan 14 (Print Publication: 2021). - Publication Year :
- 2021
-
Abstract
- 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.<br />Competing Interests: The authors have declared that no competing interests exist.
- Subjects :
- Computer Simulation
Algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 1932-6203
- Volume :
- 16
- Issue :
- 1
- Database :
- MEDLINE
- Journal :
- PloS one
- Publication Type :
- Academic Journal
- Accession number :
- 33444394
- Full Text :
- https://doi.org/10.1371/journal.pone.0245267