Exact solutions for the 2d-strip packing problem using the positions-and-covering methodology

Nestor M Cid-Garcia and Yasmin A Rios-Solis

PLOS ONE, 2021, vol. 16, issue 1, 1-20

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.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0245267 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 45267&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0245267

DOI: 10.1371/journal.pone.0245267

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().